Batch append circuit

The batch append proof moves staged values into an indexed tree, twelve at a time. The forester makes it, and the program accepts it from anyone, because the proof is the only authority a commit needs.

Why it existsCopy Anchor Link

Nullifiers, registered identity commitments and fee-note nullifiers are first staged in a staging buffer, which the code calls the turnstile, and later inserted into an indexed Merkle tree where non-membership can be proven. The program does not store these trees' leaves, only a ring of recent roots and the next free index, so it cannot insert a value itself. The insertion is done off chain and proven.

Three trees use this circuit: the nullifier tree, the registration tree and the fee-nullifier tree. One verifying key, compiled into the program, serves all three, because the insertion is the same whatever the values mean.

What it provesCopy Anchor Link

The circuit is IndexedBatchAppend(12, 11, 8, 1, 8): twelve keys into a tree of 11 levels of 8 children and one level of 8, which holds 2³⁶ leaves. An indexed tree keeps its values as a sorted linked list, each leaf pointing at the next-larger value. Inserting a key means finding the leaf just below it, pointing that leaf at the new key, and writing a new leaf that points where the old one used to. The chart below shows one insertion.

flowchart LR
subgraph Before
  A1["Leaf 17, next 42"]
end
subgraph After
  A2["Leaf 17, next 30"] --> B2["Leaf 30, next 42"]
end
Before --> After

For each of the twelve keys in order, starting from the old root, the circuit proves three things.

The key is new. A predecessor leaf with value v and successor value w is in the tree at the running root, with v less than the key and the key less than w, or w zero for the largest leaf. A value already in the tree has no such predecessor, so it cannot be inserted a second time and the tree cannot hold a duplicate.

The predecessor is relinked. The predecessor leaf is rewritten to point at the new leaf's index and at the key, and the running root is updated to match.

The new leaf is written. A leaf holding the key and the predecessor's old successor is written at the next free index, into a slot that was empty, and the running root is updated again. Requiring the slot to be empty stops an insertion from overwriting an existing leaf.

Alongside, the circuit chains the twelve keys into one hash: starting from zero, each step hashes the chain so far with the next key, so the order of the keys changes the result. The public input is the Poseidon hash of four values: the old root, the new root, the keys chain and the start index.

The circuit has 279,462 non-linear constraints and needs a setup of 2^19.

Entry	circuits/zk/indexed_batch_append.circom
Instantiation	IndexedBatchAppend(12, 11, 8, 1, 8)

What the program suppliesCopy Anchor Link

forester_commit, registration_forester_commit and fee_forester_commit take only the new root and the proof. No account signs. The program fills in the other three values itself.

The old root is the tree's current root. A proof made against any earlier root fails, so two foresters racing to commit the same sub-batch cannot both succeed.

The keys chain is the chain of the next sub-batch's twelve keys. The staging buffer stores keys in the order they were staged, and when a sub-batch commits the program folds its twelve stored keys into the chain itself, starting from zero as the circuit does. The forester cannot choose which keys to insert or in what order.

The start index is the tree's next free index. The forester cannot choose where the new leaves go.

So a forester can only prove the one insertion the staging buffer already fixed. If the proof verifies, the new root it names becomes the tree's current root and joins the root ring, and the next free index advances by twelve. The handlers are listed in the reference section at the bottom of this page.

When commits happenCopy Anchor Link

Each staging buffer has two buffers of 30,000 keys. While one fills, the other can be committed. A buffer is committed only once it is full, in 2,500 sub-batches of twelve. When every sub-batch of a buffer is in the tree, the buffer is retired once its grace window of further roots has been committed, 512 for the nullifier and fee staging buffers and 64 for the registration one, or sooner if staging needs it back. Retiring empties it and raises the watermark, so a root from before the last of the buffer's keys reached the tree is refused from then on; see preventing double spends. The life of one buffer is shown below.

stateDiagram-v2
[*] --> Fill
Fill --> Full: 30,000th key staged
Full --> Inserted: 2,500th sub-batch committed
Inserted --> Fill: retired after its grace window of roots
Inserted --> Fill: retired early when staging needs it

If both buffers are full and neither has been fully committed, staging stops. Every instruction that stages into that staging buffer fails with StagingBlocked until a forester has committed every sub-batch of one buffer.

• For the nullifier staging buffer, that is every value transaction and every escape on that pool index.
• For the registration staging buffer, every registration.
• For the fee staging buffer, every fee collection.

The escape hatch needs no attester, but it does need room in the nullifier staging buffer, so it stops too.

What it does not proveCopy Anchor Link

The proof says nothing about who staged the keys or whether they were valid spends; the transaction, registration, escape-hatch and fee-collection handlers decided that when they staged them. It proves only that the tree after the commit is the tree before it with exactly these twelve keys inserted in this order.

ReferenceCopy Anchor Link

RelatedCopy Anchor Link