Proofs for UTXO set with Utreexo accumulator

Question

I am trying to understand the Utreexo technology and I've met a problem. In Utreexo we have a forest of trees where every tree has 2^k leaves. We have 3 operations:

add(acc, newNode) : Proof // simply adds new UTXO to our Utreexo, and returns the proof for added element.
verify(acc, proof) : Bool // gets the proof as argument and checks that the element is still in set.
remove(acc, proof) // removes element with given proof from accumulator.

The question is: I added a new UTXO and got the proof. After that, some changes happend (different delitions and additions) and the structer of the Utreexo has changed. Now, as I see, my proof (that I received when I added the new UTXO) will not be correct. How to deal with this problem? Or I misunderstand something?

Answer 1

You're understanding how Utreexo works correctly. The proofs generated for a single accumulator state is only valid for that state. A new proof must be generated if the accumulator was changed with additions and deletions.

For example, a proof for a single UTXO at block #500,000 will not be valid for block #500,001.

Further explanation:

In a general sense, Utreexo is a fancy Merkle Tree. A "proof" is all the nodes needed to hash up to the root. For this tree:

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
 12              13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
 08      09      10      11                                                                                                                                                                                      
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01  02  03  04  05  06  07

A node is only required to keep the root, so that node's view of the tree may look like this where only the root, 14, is kept.

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                                                                                                                                                                                                             
 |-------\       |-------\                                                                                                                                                                                       
                                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
  

If someone wanted to proof the existence of node 00, they will need to provide the following nodes: 00, 01, 09, 13. These are node needed to be able to hash up to 14, which then the verifier will check if the 14 they stored matches the one calculated with the proof of 00, 01, 09, 13.

So for this tree, the proof generated will be nodes 00, 01, 09, 13.

Let's say then the tree is modified with the removal of node 07. The resulting tree will look like so:

  12                                                                                                                                                                                                              
  |-------\                                                                                                                                                                                                       
  08      09      10                                                                                                                                                                                              
  |---\   |---\   |---\                                                                                                                                                                                           
  00  01  02  03  04  05  06

If we want to prove 00 again, the nodes required are 00, 01, 09 and we will match it against 12. This is different from the previous proof of 00, 01, 09, 13.

In Bitcoin terms, since a modification to the accumulator happens when a new block is generated, the proof will change from block to block.