Field note
Indexed Merkle Trees: Proving a Nullifier Is Not Already There
A Merkle tree is excellent at proving membership. Supply a leaf and one sibling hash per level, and the verifier reconstructs the public root. But a normal sparse commitment tree does not automatically prove that an arbitrary value is absent.
Nullifiers need that negative statement. Before accepting a private spend, the system must prove the new nullifier has not appeared before, without scanning or revealing the entire spent set.
Index the sorted neighbors
In an indexed Merkle tree, each used leaf stores its value and the next value in sorted order. Suppose the tree contains 3, 8, and 12. To prove that 10 is absent, open the leaf for 8 and show that it points to 12. The circuit checks 8 < 10 < 12, so 10 cannot already be stored. Only the leaf for 8 needs a Merkle path because it already contains the next value.
The largest stored value has nothing after it. Its next-value field uses zero to mean “no upper value.” The circuit must handle that marker as the end of the list, not as the number zero.
Insertion replaces that one interval with two: the low leaf is rewritten to point at x, and x is written into a fresh leaf pointing where the low leaf used to. The root changes, and the new tree authenticates the enlarged set.
The strict inequalities are essential. A weak comparison could admit equality and therefore a duplicate. Every index must also be range-checked inside the circuit rather than trusted as host metadata.
Why the target uses two Merkle structures
The vault's commitment side is append-only and uses a fixed depth-32 incremental Merkle tree with a cached frontier. Membership always costs exactly 32 hashes, giving the AIR a fixed shape.
The nullifier side uses an Aztec-style indexed Merkle tree, also fixed at depth 32. Each Action proves non-membership against the settled root; an epoch inserts the accepted batch. This avoids an offline memory argument whose prover work would grow linearly with the lifetime nullifier set.
The PayMoney consequence
Claim consumes the Open offer. Its nullifier is the one coordination point that prevents two takers from settling claims on the same resource. Solve later consumes the Claimed offer, so the same offer outcome cannot be replayed. Withdrawal uses its own claim-nullifier mapping at L1 for exactly-once release.
The tree does not decide whether a transition is semantically valid. It answers a narrower and load-bearing question: is this consume-once identity fresh relative to the authenticated history? The AIR, resource kind, and authority checks supply the rest.
Read the CALM interpretation → · Read about private resources →