# MerkleCRH

## Message decomposition

is used in the hash function. The input to is:

where:

• ,
• ,
• ,

with and are allowed to be non-canonical -bit encodings of and .

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

Then we recompose the chunks into MessagePieces:

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

Some of these constraints can be implemented with reusable circuit gadgets. We define a custom gate controlled by the selector to hold the remaining constraints.

## Bit length constraints

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

, the index-1 running sum output of , is copied into the gate. has been constrained by to be bits, and is precisely . We recover chunk using

, the index-1 running sum output of , is copied into the gate. has been constrained by to be bits. We witness the subpieces outside this gate, and constrain them each to be bits. Inside the gate, we check that We also recover the subpiece using :

### Constraints

where is a short lookup range check.

## Decomposition constraints

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

• ( bits), derived as ;
• ( bits), equal to ;
• ( bits), derived as ;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate.
• is constrained to equal .

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

## Circuit components

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