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
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.
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.
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.