Append Commitment

There are a few important rules to our commitment tree:

1. Once a value is added, it cannot be removed or updated;
2. Adding a value means replacing the left-most EMPTY hash.

In other words, our tree is append-only.

Merkle Proof

We receive a lot of commitments, millions of them. But we only need to track our note commitments. If cannot decrypt a note, we cannot spend it.

Among these millions of commitments, only a few are to be tracked.

On request, i.e. when the user wants to spend a note, we must produce the Merkle Proof.

The MP is the list of hashes obtained by traversing the tree from our commitment to the root and collecting the sibling hash along the path.

For example, in the following tree

the path for F is [F, C, A] and the proof is [G, B]. The root has no sibling, therefore the proof is always shorter (by 1) than the path.

You also need the commitment value F and its position¹,

Incremental Appends

The tree is not static. Whenever we receive new blocks, with new transactions and new outputs, the tree gets new commitments and the proofs of our notes will change.

Let's start with a simpler problem.

Footnotes