# Subtree Update Circuit ### Input Encodings Almost all inputs (listed below) are as defined in the [JoinSplit Circuit](/nocturne/protocol-details/joinsplit-circuit.md#note-encoding). 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](/nocturne/protocol-details/encodings.md#note-encoding). 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. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://nocturne-xyz.gitbook.io/nocturne/protocol-details/commitment-tree/subtree-update-circuit.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.