Instantly share code, notes, and snippets.

# kcalvinalvin/utreexo-algorithms.md

Last active March 14, 2024 08:11
Show Gist options
• Save kcalvinalvin/a790d524832e1b7f96a70c642315fffc to your computer and use it in GitHub Desktop.
Utreexo algorithms

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.