# Subtree Update Circuit

### Input Encodings

Almost all inputs (listed below) are as defined in the [JoinSplit Circuit](https://nocturne-xyz.gitbook.io/nocturne/joinsplit-circuit#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](https://nocturne-xyz.gitbook.io/nocturne/encodings#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.