<h2>Quick answer:</h2>
<blockquote>
<p>I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process</p>
</blockquote>
<p>For a single block, a single batch proof is sent. There are no unused inclusion proofs since only one is sent. This &quot;batch proof&quot; proves the inclusion of all the UTXOs in the given block.</p>
<p>A &quot;proof&quot; that only proves the inclusion of a single utxo is only sent when for a transaction that would be going into the mempool.</p>
<blockquote>
<p>how unused inclusion proofs are updated in this process</p>
</blockquote>
<p>Since the proofs for a single utxo vary block to block, there isn't an &quot;update&quot; per say but a new proof is generated for every new block.</p>
<h2>Longer answer:</h2>
<blockquote>
<p>I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process</p>
</blockquote>
<p>To answer your question, we need to take a look at how accumulator proofs would differ when receiving a block vs receiving a transaction.</p>
<p>We recall that Utreexo is essentially a <a href="https://en.wikipedia.org/wiki/Merkle_tree" rel="nofollow noreferrer">Merkle Tree</a>. A Utreexo node is only required to keep the root of this tree. For a tree like so:</p>
<pre><code> 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
 12              13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
 08      09      10      11                                                                                                                                                                                      
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01  02  03  04  05  06  07
</code></pre>
<p>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:</p>
<pre><code> 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                                                                                                                                                                                                             
 |-------\       |-------\                                                                                                                                                                                       
                                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
  
</code></pre>
<p>A &quot;proof&quot; 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 (<code>01</code>, <code>09</code>, <code>13</code>)</p>
<p>The verifying node would make a tree like this and hash up to the root. If the calculated <code>14</code> from the inclusion proof matches the <code>14</code> it stored, the <code>00</code> utxo is verified to exist.</p>
<pre><code> 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                 13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
         09                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01   
</code></pre>
<p>To prove utxo <code>01</code>, the proof would include the hashes of (00, 09, 13).</p>
<p>Notice the overlap in the proofs for <code>01</code> and <code>00</code>. <code>09</code> and <code>13</code> are required by both <code>00</code> and <code>01</code>. Furthermore, <code>01</code> is needed to prove <code>00</code> and <code>00</code> is needed to prove <code>01</code>.</p>
<p>If given the above proof of <code>00</code>, we can also verify <code>01</code>:</p>
<pre><code> 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
                 13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
         09                                                                                                                                                                                         
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01   
</code></pre>
<p>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.</p>
<blockquote>
<p>how unused inclusion proofs are updated in this process</p>
</blockquote>
<p>I find it helpful to not think of Utreexo as a black box that generates proofs but as a tree structure.</p>
<p>This tree is updated every block. So for every new block, the required proofs will change.</p>
<p>For the above tree of:</p>
<pre><code> 14                                                                                                                                                                                                              
 |---------------\                                                                                                                                                                                               
 12              13                                                                                                                                                                                              
 |-------\       |-------\                                                                                                                                                                                       
 08      09      10      11                                                                                                                                                                                      
 |---\   |---\   |---\   |---\                                                                                                                                                                                   
 00  01  02  03  04  05  06  07
</code></pre>
<p>If this tree is modified with the removal of node <code>07</code>. The resulting tree will look like so:</p>
<pre><code>  12                                                                                                                                                                                                              
  |-------\                                                                                                                                                                                                       
  08      09      10                                                                                                                                                                                              
  |---\   |---\   |---\                                                                                                                                                                                           
  00  01  02  03  04  05  06
</code></pre>
<p>Notice how the proof for <code>00</code> changed to (<code>01</code>, <code>09</code>) from the previous proof of (<code>01</code>, <code>09</code>, <code>13</code>).</p>
<p>In the implementation, there aren't any &quot;proofs&quot; that are being kept and updated, but rather a single tree for a block in which the proofs are derived from.</p>

CC BY-SA 4.0
2020-11-19T22:57:01.803Z
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
CC BY-SA 4.0
2020-11-20T08:14:24.043Z
No unfortunately I don't know enough about the implementation details of the RSA accumulators.
kcalvinalvin
CC BY-SA 4.0
2020-11-18T07:37:06.407Z
2020-11-18T07:37:06.407Z
kcalvinalvin
<p>With <a href="https://eprint.iacr.org/2019/611.pdf" rel="nofollow noreferrer">Utreexo</a>, 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.</p>
<p>However, I don't see anywhere in the paper that describes how unused inclusion proofs are updated in this process. It only mentions that &quot;maintaining and updating proofs of every element in the set incurs no additional computational cost above computing the roots&quot;. 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?</p>
<p>Also, bonus question: do other kinds of accumulators (eg RSA accumulators) have a way of keeping proofs up to date like this?</p>

CC BY-SA 4.0
2024-01-23T19:59:21.823Z
+1, great question. While it is more or less clear that it is indeed possible to update proofs without having access to all of the leaves, a detailed implementation spec would be nice to have.
Cosmik Debris
<utreexo>
How are nodes supposed to update their inclusion proofs with Utreexo?
B T
# How are nodes supposed to update their inclusion proofs with Utreexo?

(Asked by: username_0 on 2020-10-29)

With [Utreexo](https://eprint.iacr.org/2019/611.pdf), 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?

**Tags:** utreexo

> **Comments:**
> **username_1**: +1, great question. While it is more or less clear that it is indeed possible to update proofs without having access to all of the leaves, a detailed implementation spec would be nice to have.  

---

## 1 answers

### Answer by username_2 on 2020-11-18. Score: 2 | Accepted answer

## 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](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: No unfortunately I don't know enough about the implementation details of the RSA accumulators.  

---

