# MerkleCRH

## Message decomposition

$SinsemillaHash$ is used in the $MerkleCRH_{Orchard}$ hash function. The input to $SinsemillaHash$ is:

$l⋆∣∣left⋆∣∣right⋆,$

where:

- $l⋆=I2LEBSP_{10}(l)=I2LEBSP_{10}(MerkleDepth_{Orchard}−1−layer)$,
- $left⋆=I2LEBSP_{ℓ_{Merkle}}(left)$,
- $right⋆=I2LEBSP_{ℓ_{Merkle}}(right)$,

with $ℓ_{Merkle}=255.$ $left⋆$ and $right⋆$ are allowed to be non-canonical $255$-bit encodings of $left$ and $right$.

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

$l⋆left⋆right⋆ =a_{0}=a_{1}∣∣b_{0}∣∣b_{1}=(bits0..=239ofleft)∣∣(bits240..=249ofleft)∣∣(bits250..=254ofleft)=b_{2}∣∣c=(bits0..=4ofright)∣∣(bits5..=254ofright) $

Then we recompose the chunks into `MessagePiece`

s:

$Length (bits)25020250 Piecea=a_{0}∣∣a_{1}b=b_{0}∣∣b_{1}∣∣b_{2}c $

Each message piece is constrained by $SinsemillaHash$ to its stated length. Additionally, $left$ and $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 $SinsemillaHash$ message).

Some of these constraints can be implemented with reusable circuit gadgets. We define a custom gate controlled by the selector $q_{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 $SinsemillaHash(a)$, is copied into the gate. $z_{1,a}$ has been constrained by $SinsemillaHash$ to be $240$ bits, and is precisely $a_{1}$. We recover chunk $a_{0}$ using $a,z_{1,a}:$ $z_{1,a}⟹a_{0} =2_{10}a−a_{0} =a_{1}=a−z_{1,a}⋅2_{10}. $

### $b_{0},b_{1},b_{2}$

$z_{1,b}$, the index-1 running sum output of $SinsemillaHash(b)$, is copied into the gate. $z_{1,b}$ has been constrained by $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}⋅b_{2}=z_{1,b}.$ We also recover the subpiece $b_{0}$ using $(b,z_{1,b})$: $z_{1,b}⟹b_{0} =2_{10}b−b_{0..=10} =b−(z_{1,b}⋅2_{10}). $

### Constraints

$Degree2 Constraintshort_lookup_range_check(b_{1},5)short_lookup_range_check(b_{2},5)q_{decompose}⋅(z_{1,b}−(b_{1}+b_{2}⋅2_{5}))=0 $

where $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}⋅z_{1,a}$;
- $a_{1}$ ($240$ bits), equal to $z_{1,a}$;
- $b_{0}$ ($10$ bits), derived as $b_{0}=b−2_{10}⋅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}⋅b_{2}$ is constrained to equal $z_{1,b}$.

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

$lleftright =a_{0}=a_{1}+2_{240}⋅b_{0}+2_{250}⋅b_{1}=b_{2}+2_{5}⋅c $

$Degree222 Constraintq_{decompose}⋅(a_{0}−l)=0q_{decompose}⋅(a_{1}+(b_{0}+b_{1}⋅2_{10})⋅2_{240}−left)=0q_{decompose}⋅(b_{2}+c⋅2_{5}−right)=0 $

## Region layout

$az_{1,a} bz_{1,b} cb_{1} leftb_{2} rightl q_{decompose}10 $

## Circuit components

The Orchard circuit spans $10$ advice columns while the $Sinsemilla$ chip only uses $5$ advice columns. We distribute the path hashing evenly across two $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.