The Road to Millions of TPS — UTXO Proof and Sharding technology of BCH
Chapter 0 introduction
Today we are going to talk about a very cutting-edge technology, the UTXO proof of BCH. The next step is to discuss the truly revolutionary technology, UTXO sharding, based on the UTXO proof.
Chapter 1 “Physical Entities” of UTXO
Utxos are called non-cost outputs, and all of our bitcoins are essentially a bunch of UTXOs. We’re going to have a technical discussion today, and we’re going to assume that everyone here knows what UTXO is, so I’m going to skip that.
What is the “physical entity” of UTXO?
All UTXOs are stored on nodes, and the physical entity of the UTXOs set is a database file. Currently, the database technology called LeveDB is used. This database stores all UTXOs of BCH, which is updated with the block height. That is, every 10 minutes on average, utXOs that have been spent are deleted and newly constructed UTXOs are updated.
A specific UTXO contains four fields
1 TxID generated for this UTXO transaction; 2 Generates the output sequence number index for this UTXO transaction. Because most transactions are one or more inputs, multiple outputs, with the first input having a serial number of 0 and the second one having a 1. 3 lockscript lockscript. 4 is the amount value
All network-wide UTXOs are stored on LeveDB, and the current organizational structure looks like this
txid index => amount lockscript height coinbase
We can visualize UTXO as an Excel table store, with txID in the first column, serial number in the second column, and amount in the third column. The fourth column is the lock script, the fifth column is the block height, and the fifth column indicates whether the UTXO is a Coinbase transaction output, 1 if it is, and 0 if it is not. Since coinbase transaction outputs require 100 confirmations to be spent, and this is the concept of a mature zone for mining, there is a field to distinguish non-Coinbase transactions.
Chapter 2: How is UTXO now generated?
If you run a full node, you must download blocks, but never heard of downloading UTXO.
The current UTXO is actually traceable from the block file. When a node downloads a block, the node traverses the block file to find any unspent output and constructs a UTXO database locally. The UTXO database is updated every time a new block is downloaded. The main data stored by a complete node is divided into two parts. All transaction data is stored in the blockchain, and the UTXO set is extracted and stored in the UTXO set database.
The current Bitcoin network is a P2P network, but all the data transferred in the network is block files and transactions themselves, not UTXO database.
Since UTXO sets are one of bitcoin’s most important pieces of data, some people wondered if I could get the Bitcoin network to carry UTXO sets as well.
This is the starting point for designing the UTXO proof.
In Chapter 3, we reconstruct a UTXO database
The current UTXO data uses Levedb, which is a very simple database, but does not contain blockchain thinking. Let’s design a UTXO database that contains blockchain thinking.
We use a binary tree to store all utXOs. The leaf of the binary tree is a UTXO containing the TXID, serial number, lock script, amount, and Coinbase id, then hashes once to form the leaf node. The two leaves are hashed again to form the second node, and then all the way down to form the root node.
The Road to Millions of TPS — UTXO Proof and Sharding technology of BCH
We call the hash of this root a UTXO proof.
The hash value of the root node is stored by the mining node in OP_Return, an output in the Coinbase transaction. However, this is not a neat design. A good design would be to add a field in the block header file to store UTXO proofs through a hard fork.
For example, at the current height of 500,000, the full node will be traced back to a UTXO set from all existing block files and stored as a binary tree as a database. There will be a unique SET of UTXO data for the entire network.
When a node joins the network, you can download UTXO sets from other nodes on the network and verify that the downloaded UTXO sets are not forged through UTXO proof.
This describes static GENERATION and download of UTXO sets, but blockchain is dynamic, with an average of 10 minutes for a block to be updated and the UTXO set to be updated.
Chapter 4 implements UTXO dynamic update
Because of the mining nodes, one block is mined every ten minutes on average, and the last UTXO set is deleted based on the new block and new UNspent UTXOs are added. Using this binary tree algorithm, it is easy to delete and add UTXO sets.
After the update, a new UTXO set database and a UTXO proof are generated.
However, the problem is that a UTXO database is now 2G in size, and it takes 10 minutes to update a UTXO database. The average number of newly added nodes is 10 minutes, which is not enough time to download 2G data in 10 minutes.
At the same time, if a node broadcasts 2G UTXO data to the whole network, all nodes that need to download UTXO sets will ask such a node for data, and such a node will also crash.
So how do you design it? The answer is to use the blockchain model to construct and update the UTXO database using blockchain as well. But the blockchain always circulates between zero and 100 blocks. That is, an average of 100 blocks update a UTXO set, and a cell block is used in the middle to supplement the UTXO set.
For example, 500,000 high-mining nodes generate a UTXO set and include a UTXO proof in the block header. Let’s call this UTXO block 0 high-UTXO block.
Then a new block is created at 500001 height, at which point the miner node will trace the 500001 height block back to a UTXO block, which is recorded as a UTXO block at 1 height. The hashes of the two UTXO heights are then hashed into the block header as UTXO proofs.
0 height UTXO block and 1 height UTXO block add up to trace back to the latest UTXO set of the entire network.
…
All the way up to the 500,000th 99th height, the UTXO blockchain forms a short chain from 0 to 99 blocks.
All other full nodes can download all UTXO blocks in this 0 to 99 height time and construct a complete SET of UTXOs locally.
When the new pool node mines the 500,000th block, it regenerates a 0 height UTXO block and a 100 height UTXO cell block, and deletes the previous 0 height UTXO block locally.
In the future, every time a new bitcoin block is created across the network, the UTXO block will delete the oldest UTXO block and add a new UTXO block.
And so on and so on.
In this way, other nodes that need to download UTXO sets have enough time to download all UTXO sets and reconstruct UTXO sets locally. In addition, there is not too much pressure on a single node that provides UTXO block download service, because a P2P network can be formed to transmit UTXO blocks.
Chapter 5 Concluding Remarks
UTXO proves that this is roughly the whole principle. In this way, the entire network can maintain a unified UTXO database, and the P2P network can transmit UTXO data and update UTXO data.