Checkpointing the UTXO set using the Merklix tree

In a previous post, I introduced Merklix trees as a cryptographic method to describe unordered sets or graphs. This makes it possible to prove that an element is included or not in an o(ln(n)) data structure, and use these proofs to change the structure, even without knowing its full contents.

I will now explain how this can be used to help process UTXO sets in blockchain technologies like Bitcoin.

Merklix proves existence or not

Before we get into the UTXO part, let’s demonstrate how to use a Merklix tree to prove the presence or absence of an element in a set.

In this example, we are trying to prove that Item1 is in the set. We do this by providing Item1 or its hash, 6eec, which are highlighted in red in the diagram because we do not want to show Item1 or simply want to make the proof more concise.

We then provide a path in the tree that leads to the root. This path is highlighted in yellow in the diagram. To verify the proof, one hashes 6eec with 3738 to get bf1b, which itself hashes with d9fe to get 2812, the root of the tree. We have proven that the element is indeed in the tree.

Now let's assume we want to prove that Item5 is not in the tree. Its hash is cd5a, where c = 1100.

Again, the proof is in the yellow element. By hashing bf1b and d9fe together, we can verify that they are both part of the tree and that they are siblings. bf1b has all elements starting at 0 as its children, and d9fe has elements starting at 111. Therefore, Item5 cannot be in any of these subtrees. However, if it were in the tree, it would be between these two nodes. Since these two nodes are siblings, we know that there is nothing between them, so we can conclude that Item5 is not in the set.

Update the tree using the Merklix proof

Because the path through the tree is provided by the proof, it can also be used to modify the tree itself. Again, this work does not require prior knowledge of the path to the root node. Now we have proved that Item5 is not in the tree, but maybe we want to add it?

The new nodes in the tree are shown in red. The yellow part of the picture shows the blocks in the proof. As you can see, once Item5 is inserted, the root of the tree can be calculated using only the hashes in the proof.

We also have a proof that Item1 is in the collection, so let's remove it.

Once again, the unique hash needed to compute the deletion result must either be included in the proof or calculated when Item5 was inserted.

From this, we can conclude that: If k << n, we can maintain a set of k changes in a Merklix tree of n elements in o(k * ln(n)), and tends to o(k) as k gets larger. The set of changes is shown in red in the figure.

Use the Merklix tree to generate proofs about the UTXO set

The UTXO set can be represented in a Merklix tree by using the txid as the key and some serialization of the unspent output as the value. For simplicity, in the illustrations above, I have been using the hashed value as the key, but there is no such obligation. I will not go into more detail about how the unspent output is serialized, but knowing this is enough to understand the concept.

When sending a transaction over the network, it is also possible to send a proof of the inputs in the UTXO set. This will allow nodes receiving the transaction and the proof to avoid querying their UTXO sets, which can be a slow process, especially if the set is large and needs to be on disk.

Additionally, this allows nodes to prune portions of the UTXO set. They can use the proof of existence to update their UTXO set to include the pruned portion. In the event that a transaction does not have a proof, a proof can be requested from another node for the portion of the UTXO set that was not pruned. If the proof shows that the input is in the UTXO set, then it can be verified against other aspects, and if this is valid, the transaction can be forwarded to other nodes. If the proof shows that it does not exist, then the transaction is rejected as invalid.

It is generally accepted that nodes on the network should not trust each other. In the case where proof cannot be formed, this will not be a problem. Nodes cannot lie. Worse, nodes can refuse to answer, in which case the request can be forwarded to another node.

Therefore, only very few nodes actually need to query their UTXO set, and the workload can be distributed across many nodes. This will be the first example of horizontal scaling in the Bitcoin blockchain. With this measure, the UTXO set can grow to crazy large sizes by only having a subset of nodes handle each of its shards. The nodes in the subset are responsible for their own subset of the requested shards.

For example, with about 5000 nodes, one can split the UTXO 64 ways, with about 78 nodes per shard.

Even if we assume that half of these nodes are untrustworthy and will not answer requests, that leaves 39 nodes per shard.

It can effectively reduce the storage requirements of each node by 64, and its UTXO checking workload is reduced by 2500. In absolute numbers, a 1.5Gb UTXO set requires about 24Mb of memory per node, and a block only needs to check a small portion of the UTXO for the network to handle the current workload.

If nodes adopt intelligent strategies, such as keeping in memory high velocity money and committing to disk and pruning from memory asynchronously savings, the network as a whole can achieve extremely high throughput of UTXO requests, allowing the UTXO set to grow by orders of magnitude without creating a significant problem.

Checkpointing the UTXO set in a block

While nodes can reconstruct the UTXO set by traversing the entire history of the blockchain, this means that the time it takes for a new node to bootstrap itself is o(n*t), where n is the number of transactions and t is the time. This will only get worse over time. If a node can get the root hash of the UTXO set, then the node can quickly become effective.

This can be done as a soft fork by putting it in the coinbase transaction, but it is better to put it in the block header as a hard fork. This way, a node can start validating on the network as long as it is connected, and start validating against known valid blocks and forwarding as the network progresses.