0

With Utreexo, full nodes can build and verify blocks without storing the UTXO set. This is done by using proofs that the UTXOs in a transaction are included in the Utreexo accumulator. These proofs are broadcast with the transaction. To update the Utreexo accumulator, the only thing required are the UTXOs to be added, and the inclusion proofs of the now-used outputs to be removed.

However, I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process. It only mentions that "maintaining and updating proofs of every element in the set incurs no additional computational cost above computing the roots". I would guess that in the process of adding or deleting leaves, every UTXO who's proof changes will be touched, and could therefore be easily extracted simultaneously. Does anyone know more in depth how that process would happen?

Also, bonus question: do other kinds of accumulators (eg RSA accumulators) have a way of keeping proofs up to date like this?

2

Quick answer:

I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process

For a single block, a single batch proof is sent. There are no unused inclusion proofs since only one is sent. This "batch proof" proves the inclusion of all the UTXOs in the given block.

A "proof" that only proves the inclusion of a single utxo is only sent when for a transaction that would be going into the mempool.

how unused inclusion proofs are updated in this process

Since the proofs for a single utxo vary block to block, there isn't an "update" per say but a new proof is generated for every new block.

Longer answer:

I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process

To answer your question, we need to take a look at how accumulator proofs would differ when receiving a block vs receiving a transaction.

We recall that Utreexo is essentially a Merkle Tree. A Utreexo node is only required to keep the root of this tree. For a tree like so:

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

A Utreexo node can only keep the root and still be a fully validating node. Such node's view of the tree may look like this:

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

A "proof" is all the utxos needed to hash up to the root. For the above tree tree, to prove the inclusion of 00, the proof would include the hashes of (01, 09, 13)

The verifying node would make a tree like this and hash up to the root. If the calculated 14 from the inclusion proof matches the 14 it stored, the 00 utxo is verified to exist.

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                 13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
         09                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01   

To prove utxo 01, the proof would include the hashes of (00, 09, 13).

Notice the overlap in the proofs for 01 and 00. 09 and 13 are required by both 00 and 01. Furthermore, 01 is needed to prove 00 and 00 is needed to prove 01.

If given the above proof of 00, we can also verify 01:

 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                 13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
         09                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01   

Because a single block has a lot of these overlaps, we can just send one proof to verify all utxos being spent. There are no unused proofs to speak of.

how unused inclusion proofs are updated in this process

I find it helpful to not think of Utreexo as a black box that generates proofs but as a tree structure.

This tree is updated every block. So for every new block, the required proofs will change.

For the above tree of:

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

If this 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

Notice how the proof for 00 changed to (01, 09) from the previous proof of (01, 09, 13).

In the implementation, there aren't any "proofs" that are being kept and updated, but rather a single tree for a block in which the proofs are derived from.

2
  • I see. So basically, you're saying when the merkle forest is updated, the tree that contains the output is simply found and a new proof is extracted, replacing the old proof. That makes sense. Do you know anything about how this works in an RSA accumulator? – B T Nov 19 '20 at 22:57
  • No unfortunately I don't know enough about the implementation details of the RSA accumulators. – kcalvinalvin Nov 20 '20 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.