Crypto currency

How are nodes supposed to update their inclusion proofs with Utreexo?

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.

Most Related Links :
Business News Governmental News Finance News

Source link

Back to top button