MerkleCRH

Message decomposition

$\mathsf{SinsemillaHash}$ is used in the $\mathsf{MerkleCR}{\mathsf{H}}^{\mathsf{Orchard}}$ hash function. The input to $\mathsf{SinsemillaHash}$ is:

$$l\star ||\text{left}\star ||\text{right}\star ,$$

where:

• $l\star ={\text{I2LEBSP}}_{10}(l)={\text{I2LEBSP}}_{10}({\text{MerkleDepth}}^{\text{Orchard}}-1-\text{layer})$,
• $\text{left}\star ={\text{I2LEBSP}}_{{\ell }_{\text{Merkle}}^{\text{Orchard}}}(\text{left})$,
• $\text{right}\star ={\text{I2LEBSP}}_{{\ell }_{\text{Merkle}}^{\text{Orchard}}}(\text{right})$,

with ${\ell }_{\text{Merkle}}^{\text{Orchard}}=255.$ $\text{left}\star$ and $\text{right}\star$ are allowed to be non-canonical $255$-bit encodings of $\text{left}$ and $\text{right}$.

Sinsemilla operates on multiples of 10 bits, so we start by decomposing the message into chunks:

$$\begin{array}{rl}l\star & =a_0\\ \text{left}\star & =a_1||b_0||b_1\\ & =(\text{bits }\mathrm{0..}=239\text{ of }\text{ left })||(\text{bits }\mathrm{240..}=249\text{ of }\text{left})||(\text{bits }\mathrm{250..}=254\text{ of }\text{left})\\ \text{right}\star & =b_2||c\\ & =(\text{bits }\mathrm{0..}=4\text{ of }\text{right})||(\text{bits }\mathrm{5..}=254\text{ of }\text{right})\end{array}$$

Then we recompose the chunks into MessagePieces:

$$\begin{array}{cl}\text{Length (bits)}& \text{Piece}\\ 250& a=a_0||a_1\\ 20& b=b_0||b_1||b_2\\ 250& c\end{array}$$

Each message piece is constrained by $\mathsf{SinsemillaHash}$ to its stated length. Additionally, $\text{left}$ and $\text{right}$ are witnessed as field elements, so we know that they are canonical. However, we need additional constraints to enforce that the chunks are the correct bit lengths (or else they could overlap in the decompositions and allow the prover to witness an arbitrary $\mathsf{SinsemillaHash}$ message).

Some of these constraints can be implemented with reusable circuit gadgets. We define a custom gate controlled by the selector $q_{\mathsf{decompose}}$ to hold the remaining constraints.

Bit length constraints

Chunk $c$ is directly constrained by Sinsemilla. We constrain the remaining chunks with the following constraints:

$a_0,a_1$

$z_{1,a}$, the index-1 running sum output of $\text{SinsemillaHash}(a)$, is copied into the gate. $z_{1,a}$ has been constrained by $\text{SinsemillaHash}$ to be $240$ bits, and is precisely $a_1$. We recover chunk $a_0$ using $a,z_{1,a}:$ $$\begin{array}{rl}{z}_{1,a}& =\frac{a-a_0}{2^{10}}\\ & =a_1\\ ⟹a_0& =a-z_{1,a}\cdot 2^{10}.\end{array}$$

$b_0,b_1,b_2$

$z_{1,b}$, the index-1 running sum output of $\text{SinsemillaHash}(b)$, is copied into the gate. $z_{1,b}$ has been constrained by $\text{SinsemillaHash}$ to be $10$ bits. We witness the subpieces $b_1,b_2$ outside this gate, and constrain them each to be $5$ bits. Inside the gate, we check that $$b_1+2^5\cdot b_2=z_{1,b}.$$ We also recover the subpiece $b_0$ using $(b,z_{1,b})$: $$\begin{array}{rl}{z}_{1,b}& =\frac{b-b_{\mathrm{0..}=10}}{2^{10}}\\ ⟹b_0& =b-(z_{1,b}\cdot 2^{10}).\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ & \text{short\_lookup\_range\_check}(b_1,5)\\ & \text{short\_lookup\_range\_check}(b_2,5)\\ 2& q_{\mathsf{decompose}}\cdot (z_{1,b}-(b_1+b_2\cdot 2^5))=0\end{array}$$

where $\text{short\_lookup\_range\_check}()$ is a short lookup range check.

Decomposition constraints

We have now derived or witnessed every subpiece, and range-constrained every subpiece:

• $a_0$ ($10$ bits), derived as $a_0=a-2^{10}\cdot z_{1,a}$;
• $a_1$ ($240$ bits), equal to $z_{1,a}$;
• $b_0$ ($10$ bits), derived as $b_0=b-2^{10}\cdot z_{1,b}$;
• $b_1$ ($5$ bits) is witnessed and constrained outside the gate;
• $b_2$ ($5$ bits) is witnessed and constrained outside the gate;
• $c$ ($250$ bits) is witnessed and constrained outside the gate.
• $b_1+2^5\cdot b_2$ is constrained to equal $z_{1,b}$.

We can now use them to reconstruct the original field element inputs:

$$\begin{array}{rl}l& =a_0\\ \mathsf{left}& =a_1+2^{240}\cdot b_0+2^{250}\cdot b_1\\ \mathsf{right}& =b_2+2^5\cdot c\end{array}$$

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{decompose}}\cdot (a_0-l)=0\\ 2& q_{\mathsf{decompose}}\cdot (a_1+(b_0+b_1\cdot 2^{10})\cdot 2^{240}-\mathsf{left})=0\\ 2& q_{\mathsf{decompose}}\cdot (b_2+c\cdot 2^5-\mathsf{right})=0\end{array}$$

Region layout

$$\begin{array}{cccccc}& & & & & q_{\mathsf{decompose}}\\ a& b& c& \mathsf{left}& \mathsf{right}& 1\\ z_{1,a}& z_{1,b}& b_1& b_2& l& 0\end{array}$$

Circuit components

The Orchard circuit spans $10$ advice columns while the $\text{Sinsemilla}$ chip only uses $5$ advice columns. We distribute the path hashing evenly across two $\text{Sinsemilla}$ chips to make better use of the available circuit area. Since the output from the previous layer hash is copied into the next layer hash, we maintain continuity even when moving from one chip to the other.