Subtree Update Circuit

Details of subtree update circuit

Input Encodings

Almost all inputs (listed below) are as defined in the JoinSplit Circuit.

The only special encoding we need for this circuit is to deal with the fact that accumulatorHash is a 256-bit value, which is not guaranteed to fit in an $\mathbb{F}_p$ element.

Another public input for the circuit is the path to the root of the subtree spanning our batch update. The way this is encoded requires a bit more detail about the commitment tree's structure.

Our note commitment tree is quaternary - each branch node has four children, not two. That means the "path" is not a sequence of booleans (left vs right), but a sequence of numbers between 0 and 4. For binary trees, usually people use the fact that the big-endian binary representation of the index of a given leaf is the path - starting at the root, each bit when read left-to-right tells us which way to go. This would be a D - log2(B) bit unsigned integer, where D is the depth of the tree and B is the batch size. For our quaternary tree, this is almost identical - the only difference is that we read the big-endian bit representation of the index two bits at a time, giving us a sequence of two-bit numbers 0-4 which tell us which child to traverse instead of a sequence of bits. If our tree is depth D then this will be a 2*D - log2(B) bit number. In our case, D = 16 and B = 16, which means our path will take up 28 bits. This gives us plenty of room so we can pack the 3 most-significant bits of accumulatorHash into the path's field element. The resulting encoding is as follows:

1. accumulatorHash is the $\mathbb{F}_p$ element represented by the 253 least-significant bits of the "actual" 256-bit accumulatorHash

2. encodedPathAndHash is the $\mathbb{F}_p$ element represented by the following bits, from most-significant to least-significant:

   1. 254 - (2*D - log2(B)) - 3 0 bits

   2. the 3 most-significant bits of the actual accumulatorHash

   3. the 2*D - log2(B) bits of the path from the root of the commitment tree to the root of the subtree spanning the batch insertion

Statement to Prove

The Subtree Update circuit has the following public inputs:

1. accumulatorHash - the 253 least-significant bits of the hash at the tip of the accumulatorQueue on-chain

2. encodedPathAndHash - a bit-packed field element containing the path from the root of the commitment tree to the root of the subtree spanning the batch and the 3 most-significant bits of accumulatorHash.

   • For notation's sake, I will use encodedPathAndHash.hashBits to refer to the 3 hash bits, and encodedPathAndHash.path to refer to the 2*D - log2(B) path bits

3. oldRoot - the old root of the commitment tree

4. newRoot - the claimed new root of the commitment tree

We also define the constant EMPTY_SUBTREE_ROOT, which is the root of the depth-log2(B) subtree containing B zeros.

And requires the following private data:

1. SubtreeMembershipProof - a depth 2*D - log2(B)-bit Merkle membership proof against newRoot whose claimed leaf is the root of the subtree

2. EmptySubtreeMembershipProof - a depth 2*D - log2(B)-bit Merkle membership proof against oldRoot whose claimed leaf is EMPTY_SUBTREE_ROOT.

3. notes - a size B array EncodedNote for each leaf in the tree. For note commitment insertions, the corresponding entry is ignored. These are encoded as defined in the encodings section.

4. leaves - a size B array containing the leaves of the subtree - that is, the note commitments of every note to be inserted, no matter which insertion case it is.

5. bitmap - B bits indicating which insertions are note insertions and which insertions are note commitment insertions. If bitmap[i] == 1, then the ith insertion should be treated as a note insertion, not a note commitment insertion.

6. preimage - a size B*256 bit array containing every insertion digest concatenated together.

We prove that the following conditions hold true, converting to/from big-endian bit representation as needed:

1. for the ith bit of bitmap:

   1. bit is 0 or 1

   2. if bit == 1, then

      1. preimage[i*256..(i+1)*256] = sha256(notes[i])

      2. leaves[i] = noteCommit(note), where noteCommit computes the note commitment of a note.

   3. otherwise, preimage[i*256 + 2..(i+1)*256] = leaves[i]

2. encodedPathAndHash.hashBits || accumulatorHash = sha256(preimage)

   1. where || denotes concatenation

3. SubtreeMembershipProof.leaf is the root of the depth-log4(B) subtree whose leaves are leaves.

4. EmptySubtreeMembershipProof.leaf is the root of an empty depth-log4(B) subtree.

5. EmptySubtreeMembershipProof.path represents the same path as encodedPathAndHash.path

6. SubtreeMembershipProof.path represents the same path as encodedPathAndHash.path

7. EmptySubtreeMembershipProof is a valid Merkle membership proof against oldRoot. This asserts that the subtree was empty before the insertion.

8. SubtreeMembershipProof is a valid Merkle membership proof against newRoot. This asserts that newRoot is the correct root resulting from the subtree update.