Merkle Proof Tutorial

Today we start we continue chapter 6 from Bitcoin: A Work in Progress.

Utreexo

One way to address this issue is with Tadge Dryja’s proposal, the Utreexo. Dryja is a research scientist at the MIT Digital Currency Initiative. You can find his presentation here.

Currently with Bitcoin, you can prune the archival block storage to save disk space. After your node downloads a block, processes it, and updates the UTXO set, it no longer has any use for the block. Your node knows exactly which coins exist in the UTXO set, which is all the information it needs to validate future transactions.

When pruning is enabled, your node holds on to the block for a few more days and then deletes it. This way, you need less than a gigabyte of storage, even though the blockchain itself is hundreds of gigabytes. The downside is that you don’t have the blocks, so you can’t share them with other nodes. This is acceptable as long as enough other nodes still have the full archive.

With Utreexo, you’re pruning the UTXO set. Instead of throwing away transactions (along with the blocks they’re in), you throw away the list of coins that exist. The only thing you keep is a Merkle root, i.e. a hash that represents all the coins in existence. Every leaf of the Merkle tree represents a single UTXO, and the Merkle root commits to all of them. For each coin that you care about, e.g. because it’s in your wallet, your node keeps a Merkle proof. When spending a coin, you need to attach this proof to your transaction so that other nodes can verify that the coin exists.

To put it another way, normally, when somebody sends you a transaction, the transaction says, “I’m spending this input, and you, the person running a node, have the responsibility to check whether that input exists in your own database.” And here, you’re flipping this around and telling the other node, “I have no idea which coins exist, because I don’t have enough RAM to track all that. You prove to me that this coin actually existed.” So the burden of proof is reversed, which begs the question of how.

Merkle Proof Tutorial

To prove the existence of Coin 3, you need to provide a Merkle proof consisting of the three marked items.

The figure above illustrates how you can prove the existence of Coin 3 using a Merkle proof, given a verifier that only knows the Merkle root (top). First, you reveal the coin itself, which is just a transaction output with an amount and scriptPubKey. The verifier hashes this to obtain Hash 1-0 (directly above Coin 3 in the figure). You then provide Hash 1-1. Even though you probably don’t own Coin 4 and you may not even know its amount and scriptPubKey, you do know its hash, because your wallet kept track of this information. With that, the verifier can calculate Hash 1. You then provide Hash 0, and now the verifier can see that your proof results in the same Merkle root hash they knew about. You’ve now demonstrated ownership of Coin 3 without the need for the verifier to know the entire UTXO set.