Commitment Tree

The commitment tree is a data structure stored in and maintained by the Handler. It is a depth-16 quaternary merkle tree defined over the Poseidon hash function. Every Nocturne note is hashed and inserted into this merkle tree so JoinSplit proofs can use it to prove note authenticity.

We use a quaternary tree because it uses fewer constraints in our ZK circuit than the equivalent depth-32 binary tree does.

"ZK" Subtree Update Insertions

Naive insertions into to commitment tree are very expensive - in our initial prototypes, it cost us 1.3M gas to insert a single note into the tree.

We reduce this down to ~16K per insertion (~250K for 16 insertions) by batching insertions and through a technique we call "subtree updates". Between this and batch proof verification, operations in nocturne have a total overhead of just under 300K.

The main idea behind subtree updates is to update the tree using a ZKP. At a high level, it goes like this:

1. On-chain, each new insertion gets placed into a "queue".

2. Every time the queue has at least 16 elements, we remove the batch from the queue and hash it using sha256 (cheap on-chain). This hash is called the accumulatorHash.

3. An off-chain actor called the subtree updater generates and submits a ZKP of the following statement: given the current commitment tree root oldRoot and a claimed new root newRoot, there exists a batch of insertions such that:

   1. accumulatorHash is the sha256 hash of the batch

   2. newRoot is the root of the tree if the batch was inserted into the tree whose root is oldRoot

4. The contract verifies this proof, plugging in the current tree root and the accumulatorHash it computed in step 2. If the proof is valid, then the contract simply sets the commitment tree root to newRoot.

Next, we'll cover it again, but in greater detail.

Subtree Updates in Detail

Within the Nocturne protocol, there are three events that create new notes to be inserted:

1. A deposit, which creates a new note in the clear with asset, value, and owner specified by the depositor

2. A refund, which creates a new note in the clear when there are assets remaining in the handler at the end of an operation.

3. A JoinSplit, which creates new notes confidentially, only revealing their note commitments (recall, is a Posedion hash of the note, not a sha256 hash of the note)

Whenever an insertion needs to take place the way it gets hashed into accumulatorHash needs to change because we don't want to put the whole note into storage. To deal with this, for each insertion, we define the insertion digest as follows:

1. If we're inserting a note (cases 1 and 2 above), the insertion digest is sha256(note).

2. If we're inserting a noteCommitment (case 3 above), the insertion digest is noteCommitment.

Now we can lay out the mechanism in full. Let's start by defining the the following state variables:

1. root: the current root of the commitment tree

2. count: the number of leaves in the tree. This does not include leaves that are queued but have yet to be inserted.

3. bitmap: a bitmap indicating which insertion is a note and which is a note commitment

4. batch: a uint256 array of size B, where B is the batch size, chosen upon instantiation. We use a batch size of 16. This array is used to track a batch of insertion digests, which we will define below.

5. batchLen: a length counter used to indicate how many new insertion digests are queued up in batch.

6. accumulatorQueue: a queue of accumulator hashes, which we will define below.

For each new note or note commitment to be inserted into the tree, we will compute the insertion digest, "push" it into batch, and increment batchLen. We will also set the corresponding bit in bitmap to 1 if we just inserted a note, 0 otherwise.

When batch is full (i.e. batchLen = B), we compute the batch's accumulatorHash, which is defined as sha256(batch || bitmap) and enqueue it into accumulatorQueue.

If we set B to a power of the tree arity (in our case four), then every batch will fall on a subtree of the commitment tree, making the batch insertion logic simple. This is why we call it a "subtree update". Nocturne currently uses B = 16, which is a power of four.

We hash batch || bitmap, not just batch to prevent a malicious subtree updater from lying about which case (note or note commitment) an insertion was, which would allow them to destroy deposits.

This is all more or less a fancy way to "queue" up batches of insertions in a manner such that we can avoid needing to store all of the individual insertions on-chain.

Then, an permissionless off-chain actor called the subtree updater will do the following to update the tree:

1. Constantly observe new insertions as they are enqueued on-chain.

2. Whenever a batch is filled, pull that batch's accumulatorHash from the chain and apply the batch to a local copy of the tree.

3. generate a ZKP that proves the following statement: if one were to apply the batch whose hash is accumulatorHash to a local copy of the tree with root oldRoot, the new root would be newRoot. The circuit for this is described in greater detail in subtree update circuit.
4. submit that to the chain by calling a method subtreeUpdate(proof, newRoot)

5. subtreeUpdate will verify the proof against the current root and the head of the accumulatorQueue.

6. If the proof is valid, subtreeUpdate can conclude that newRoot is correct, so it will

   1. dequeue from accumulatorQueue

   2. set root to newRoot

7. If the proof is invalid, subtreeUpdate will revert.

In this scheme, we never have to do any Poseidon hashing on-chain. While sha256 in-circuit is too expensive for a client, the Subtree Updater role can be carried out by a powerful-ish server - as long as someone is updating the tree, then the system will continue processing transactions.

In practice, the subtree update prover isn't that expensive. It only takes ~6s with rapidsnark on an Ubuntu desktop with an 16-core AMD Ryzen 9 5950X and 64GB of RAM.

The gas cost per insertion is now the cost to verify the subtree update proof split B ways, plus the gas cost of a few more (warm) storage reads/writes for the batch array and accumulatorQueue.