Utreexo algorithms

utreexo-algorithms.md

Add

Utreexo accumulator is a collection of proper merkle trees. All the merkle trees have 2 children or none.

Below is an example of adding 7 leaves to the tree. You can run the code I used to generate this at https://go.dev/play/p/um5263SDk59

This is an accumulator with 1 leaf. It has 1 root, which is also a leaf.

00:6e34 

This is an accumulator with 2 leaves. Notice how the existing root of 6e34 became a leaf and was hashed with 4bf5.

02:0224         
|-------\       
00:6e34 01:4bf5 

This is an accumulator with 3 leaves. Since 0224 already has 2 leaves, we can't add more to the node so we create a new root.

|---------------\               
04:0224                         
|-------\       |-------\       
00:6e34 01:4bf5 02:dbc1         

This is an accumulator with 4 leaves. The previously added root/leaf of dbc1 is hashed with the newly added leaf of 084f. 0224 and 9576 was also hashed together to create a new root of df46. Previously there were no roots that 0224 could hash with but with the inclusion of 9576, we now generate the parent.

06:df46                         
|---------------\               
04:0224         05:9576         
|-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 

This is an accumulator with 5 leaves. There's no one that e52d can hash with so we add it as its own root.

|-------------------------------\                               
12:df46                                                         
|---------------\               |---------------\               
08:0224         09:9576                                         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d                         

This is an accumulator with 6 leaves. Notice how we hash e52d and the newly added e77b together.

|-------------------------------\                               
12:df46                                                         
|---------------\               |---------------\               
08:0224         09:9576         10:9eec                         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d 05:e77b                 

This is an accumulator with 7 leaves. No sibling for 6758 to hash with so we add it as its own root.

|-------------------------------\                               
12:df46                                                         
|---------------\               |---------------\               
08:0224         09:9576         10:9eec                         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d 05:e77b 06:6758

This is an accumulator with 8 leaves. ca35 was hashed with 6758. This created something that 9eec can hash with to create a parent of 2959, which in turn was something df46 could be hashed with. Now we have an accumulator with just one root.

14:b151                                                         
|-------------------------------\                               
12:df46                         13:2959                         
|---------------\               |---------------\               
08:0224         09:9576         10:9eec         11:3402         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d 05:e77b 06:6758 07:ca35

Delete

Utreexo accumulator supports deletions of nodes from accumulator.

The code used to generate these trees can be found here: https://go.dev/play/p/36wALsKVhM2

Let's start of with an accumulator like so:

14:b151                                                         
|-------------------------------\                               
12:df46                         13:2959                         
|---------------\               |---------------\               
08:0224         09:9576         10:9eec         11:3402         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d 05:e77b 06:6758 07:ca35 

Let's delete leaf 6e34, the leaf at position 0. When we want to delete a leaf, we move the sibling of the deleted leaf to the parent position and hash up to update the hashes of the parents.

The above tree with 6e34 deleted looks like so:

14:726f                                                         
|-------------------------------\                               
12:2b77                         13:2959                         
|---------------\               |---------------\               
08:4bf5         09:9576         10:9eec         11:3402         
|-------\       |-------\       |-------\       |-------\       
                02:dbc1 03:084f 04:e52d 05:e77b 06:6758 07:ca35

Notice that 4bf5, the sibling, moved up to the parent position at 8. Because of this, the hashes at positions 12 and 14 are updated.

Let's now try deleting e52d and e77b at positions 4 and 5. What happens when we delete both children?

14:ecd7                                                         
|-------------------------------\                               
12:2b77                         13:3402                         
|---------------\               |---------------\               
08:4bf5         09:9576         10:6758         11:ca35         
|-------\       |-------\       |-------\       |-------\       
                02:dbc1 03:084f

Notice how 3402 moved up to position 13 from position 11. When we want to delete both children, we end up deleting the parent. So when we say we can to delete 4 and 5, what we really mean is that we want to delete 10.

So we do the same operations as before. Move the sibling of the leaf being deleted up by one row. As a result, 3402 moves up to position 13 with its children. The hash of 14 is updated as a result of this deletion.

Prove

Utreexo supports proving the existance of an element in the accumulator.

The code used to generate the string can be found here: https://go.dev/play/p/aqkUhwidpyc

Let's start of with an accumulator like so:

14:b151                                                         
|-------------------------------\                               
12:df46                         13:2959                         
|---------------\               |---------------\               
08:0224         09:9576         10:9eec         11:3402         
|-------\       |-------\       |-------\       |-------\       
00:6e34 01:4bf5 02:dbc1 03:084f 04:e52d 05:e77b 06:6758 07:ca35 

The beauty of accumulators are that you can prove and verify the existance of a leaf without the entire set. The only requirement that we have for utreexo nodes is to keep the roots. With this tree, that would just be b151.

So a node's perspective of the tree could be something like this where only the root is kept:

14:b151                                                         
|-------------------------------\                               

|---------------\               |---------------\               

|-------\       |-------\       |-------\       |-------\       

To prove to the above node that 6e34 exists in the tree, we need to give them 3 pieces of information:

1: 6e34 itself. 2: The position of 6e34 (this would be 0). 3: The hashes needed to hash 6e34 to b151.

The Prove function takes in #1 and outputs #2 and #3. The proof returned by the Prove function looks like so:

1 target: 0 3 proofs: 4bf5122f344554c5 9576f4ade6e9bc3a 29590a14c1b09384

To prove target 0, we know we need its aunt: 9. We also need to grab 9's aunt: 13. 13 has no aunt so we're done.

Verify

Utreexo nodes can verify the existence of an element in the accumulator with only the roots of the accumulator.

14:b151                                                         
|-------------------------------\                               

|---------------\               |---------------\               

|-------\       |-------\       |-------\       |-------\       

For the above tree, let's say that someone claims that 6e34 exists in the accumulator. To prove this claim, we're given this proof:

1 target: 0 3 proofs: 4bf5122f344554c5 9576f4ade6e9bc3a 29590a14c1b09384

From the proof, we know that 6e34 is located at position 0. We can calulate which positions are need to verify that 6e34 indeed is located at position 0. We grab the aunt of 0: 9. Then we grab the aunt of 9: 13. 13 has no aunt so we're done.

With this information, we can hash up to the root at 14. 0 is located at the left so we do a hash of Hash(6e34 || 4bf5). We calculate 0224. 8 is on the left so we calculate this hash Hash(0224 || 9576) and get df46. We finally calculate Hash(df46 || 2959) and get b151. This matches with the root that we kept and we've verified the claim that 6e34 exists in the accumulator.

What is the advantage of Utreexo vs other Merkle trees that support addition and deletion and are history independent, like Merkle Treaps which can be updated top down instead of bottom up and only need to change the nodes on the path from the root to the item you need to add/delete?

What is the advantage of Utreexo vs other Merkle trees that support addition and deletion and are history independent, like Merkle Treaps which can be updated top down instead of bottom up and only need to change the nodes on the path from the root to the item you need to add/delete?

You can delete or add an element with just the roots. iirc there aren’t any other hash based accumulators that allow you to delete at this time.

This gist was made specifically for an intern so that he could understand the algorithms with the full forest. Please refer to https://github.com/utreexo/biptreexo/blob/main/utreexo-accumulator-bip.md for the in depth explanation.

Thanks for your quick reply.

I know understand why merkle treaps are not the best choice, since if addition always happen to the right, then you only need the right most roots to add another element.

But for deletion, and since it disrupts the tree, it makes it harder for clients to passively hold a proof for a UTXO, as some of the nodes in their proofs might be no longer a part of the latest Utreexo roots.

I wonder if an append only merkle tree, with separate bitfield of spent leafs was explored somewhere and rejected as inefficient or infeasible.

Here is why I think having no deletion (and instead using a Bitfield could be beneficial), consider this state:

r08                                                         
|-------------------------------\                               
i10                            i11
|---------------\               |---------------\               
i00            i01              i02            i03
|-------\       |-------\       |-------\       |-------\       
u01     u02    u03     u04    u05      u06    u07      u08

If the tree does not support deletion, and depends on a bitfield instead to mark spent outputs, nodes can retail the left most arm (roots when the tree has 2**n utxos) of the tree:

• u01 (r01)
• i00 (r02)
• i10 (r10)
• r08

This way any utxo in a tree with the length 2**n, can be stable and not require any more updates to its proof, for example u04 proof will always be u03 because i00, i10, r08 and any future roots of this tree, will be available to all nodes.

Anyways, thanks again for entertaining my quesiton.