# Subtree Update Circuit

Details of subtree update 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

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`i`

th 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
`i`

th`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.

Last modified 6mo ago