## Message decomposition

is used in the function. The input to is:

where , are Pallas base field elements, and

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

Then we recompose the chunks into message pieces:

Each message piece is constrained by to its stated length. Additionally, and are witnessed as field elements, so we know 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).
• The chunks contain the canonical decompositions of and (or else the prover could witness an input to that is equivalent to and but not identical).

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

Chunks and are directly constrained by Sinsemilla. For the remaining chunks, we use the following constraints:

where and is a short lookup range check.

## Decomposition constraints

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

• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and boolean-constrained in the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and boolean-constrained in the gate.

We can now use them to reconstruct both the (chunked) message pieces, and the original field element inputs:

## Canonicity checks

At this point, we have constrained and to be 255-bit values, with top bits and respectively. We have also constrained:

where is the Pallas base field modulus. The remaining constraints will enforce that these are indeed canonically-encoded field elements, i.e.

The Pallas base field modulus has the form , where is 126 bits. We therefore know that if the top bit is not set, then the remaining bits will always comprise a canonical encoding of a field element. Thus the canonicity checks below are enforced if and only if (for ) or (for ).

In the constraints below we use a base- variant of the method used in libsnark (originally from [SVPBABW2012, Appendix C.1]) for range constraints :

• Let be the smallest power of greater than .
• Enforce .
• Let .
• Enforce .

### with

In these cases, we check that :

1. Since we know that and in particular

2. To check that , we use two constraints:

a) . This is expressed in the custom gate as where is the index-13 running sum output by

b) . To check this, we decompose into thirteen 10-bit words (little-endian) using a running sum , looking up each word in a -bit lookup table. We then enforce in the custom gate that

### with

In these cases, we check that :

1. Since we know that and in particular

2. To check that , we use two constraints:

a) . is already constrained individually to be a -bit value. is the index-13 running sum output by By constraining we constrain

b) . To check this, we decompose into fourteen 10-bit words (little-endian) using a running sum , looking up each word in a -bit lookup table. We then enforce in the custom gate that

## Region layout

The constraints controlled by the selector are arranged across 9 advice columns, requiring two rows.