In a previous article, I introduced Merklix trees as a way to cryptographically describe an unordered set or map. It is possible to produce proof that an element is contained or absent of the datastructure in o(ln(n)), and use these proof to mutate the structure, even without knowing its full content.

I will now explain how this can be used to help handling the UTXO set in blockchain technologies like Bitcoin.

## Merklix proof of presence and absence

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

In that example, we are trying to prove that **Item1** is in the set. We do so by providing either **Item1** or its hash, **6eec**, in the case we don’t want to reveal **Item1** or simply wish to make the proof compact. These are represented in red in the illustration.

We then provide a path in the tree that lead up to the root. This path is represented in yellow in the illustration. To verify the proof, one hash **6eec** with **3738** to get **bf1b**, it self hash with **d9fe** to give **2812**, the root of the tree. We proved 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 .

Once again, the proof is made of the elements in yellow. By hashing **bf1b** and **d9fe** together, one can verify that they are both part of the tree and that they are sibling. **bf1b** as all element starting by 0 as its children, and **d9fe** the elements starting by 111. Therefore, **Item5** cannot be in either of these subtrees. However, if it was in the tree, it would be in between these 2 node. Because these 2 nodes are sibling, one knows that there is nothing in between, and therefore, can conclude that **Item5** is not in that set.

## Using a Merklix proof to update the tree

Because the path in the tree is provided in the proof, it can also be used to modify the tree itself. Once again, this work without prior knowledge of the tree past its root. Now that we proved that **Item5** is not in the tree, maybe we want to add it ?

The new nodes in the tree are represented in red. The ones in yellow are blocks from the proof. As you can see, the new root node of the tree once **Item5** is inserted can be computed using only the hashes from the proof.

We also had a proof that **Item1** was in the set, let’s remove it.

Once again, the only hash needed to compute the result of the removal are either contained in the proof, or have been computed while inserting **Item5**.

From this, we can conclude that we can hold a set of k changes in a Merklix tree of n elements in o(k*ln(n)) if k << n, and tends toward o(k) when k gets bigger. The set of changes is in red in the illustration.

## Using a Merklix tree to produce proof about the UTXO set

The UTXO set can be represented in a Merklix tree by using the txid as a key and some serialization of the unspent output of the corresponding transaction as value. For simplicity, in the illustrations above, I always used the hash of the value as key, but there is no such obligation. I won’t dig into how the unspent outputs can be serialized, knowing that it is possible is enough to understand the concept.

When sending a transaction over the network, it is possible to also send a proof that the input are in the UTXO set. This will allow node that receive the transaction and the proof avoid querying their UTXO set, which can be a slow process, especially if the set is large and need to be on disk.

Additionally, it is possible for nodes to prune part of the UTXO set. They can update their UTXO set using the proof of presence, including the pruned parts. In case a transaction comes without a proof, a proof can be requested to another node that hasn’t pruned this part of the UTXO set. If the proof show the input is in the UTXO set, then other aspects of the validation can take place and the transaction forwarded to other nodes if it is valid. If the proof show absence, then the transaction can be rejected as invalid.

It is recognized that nodes on the network should not trust each others. That isn’t a problem in that case as the proof cannot be made up. The node cannot lie. At worse, the node can refuse to answer, in which case the request can be forwarded to another node.

As a result, only very few node needs to actually query their UTXO set and the workload can be spread over many nodes. This would be the first example of horizontal scaling in the Bitcoin blockchain. With such a measure in place, the UTXO can grow to absurdly large size with only a subset of the nodes handling each shard of it, each node in the subset handling itself a subset of the requests for that shard.

For instance, with about 5000 nodes, one could shard the UTXO 64 ways, with about 78 nodes per shard. Even if we consider that half these node are not trustworthy and won’t answer requests, that leaves with 39 nodes per shard. It would effectively reduce the storage requirement of each node by 64 and its UTXO check workload by 2500. In absolute numbers, with a UTXO set of 1.5Gb, a node would need about 24Mb of memory and no more than a handful of UTXO checks per block for the network to absorb the current workload.

If nodes adopt a smart policy, 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, such as to allow growth of the UTXO set by several orders of magnitude without it being a significant problem.

## Checkpoint the UTXO set in blocks

While a node can rebuild the UTXO set by replaying the whole history of the blockchain, this means the bootstrap time for a new node is o(n*t) where n is the transaction volume and t time. This will only get worse over time. A node could become quickly effective if it could get the root hash of the UTXO set.

This can be achieved as a soft fork by putting it in the coinbase transaction, but preferably as a hard fork by putting it in the block header. This way, a node could start validating on the network as soon as it connects and start validating backward toward a known valid block as well as forward as the network progresses.

Pingback: Introducing Merklix tree as an unordered Merkle tree on steroid | Deadalnix's den

Very nice.

Looks similar to this?

https://wiki.ripple.com/Hash_Tree

Indeed, it seems like both are very similar.

Also the Patricia Tree used by Ethereum it’s similar to the described Merklix tree.

Another approach could be of creating a Merkle Mountain Range with all the TXO set containing the spent/unspent information.

I believe our dynamic AVL+ balanced trees are more efficient for the UTXO case https://eprint.iacr.org/2016/994 , about secure bootstrapping with committed UTXO set, please see https://arxiv.org/abs/1603.07926 .

I don’t think so. Rebalancing makes it unsuitable for sharding as I understand it. There is also no reason to think the tree will get very unbalanced as it would require to break sha256.

Pingback: Using merklix tree to shard block validation | Deadalnix's den

For your proof of absence, what information exactly needs to be provided?

The two hashes alone are insufficient as you are not proving they represent the prefixes you claim (0 and 111 in your example). Does that mean the prefix needs to be incorporated into what is being hashed?

Pingback: - Bitsapphire