# NoteCommit

## Message decomposition

is used in the function. The input to is:

where:

• are representations of Pallas curve points, with bits used for the -coordinate and bit used for the -coordinate.
• are Pallas base field elements.
• is a -bit value.

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

Then we recompose the chunks into message pieces:

where is 4 zero bits (corresponding to the padding applied by the Sinsemilla function).

Each message piece is constrained by to its stated length. Additionally:

• and are witnessed and checked to be valid elliptic curve points.
• is witnessed as a field element, but its decomposition is sufficient to constrain it to be a 64-bit value.
• 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 multiple equivalent inputs to ).

Some of these constraints are implemented with a reusable circuit gadget, . We define custom gates for the remainder. Since these gates use simple boolean selectors activated on different rows, their selectors are eligible for combining, reducing the overall proof size.

## Message piece decomposition

We check the decomposition of each message piece in its own region. There is no need to check the whole pieces:

• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;
• ( bits) is witnessed and constrained outside the gate;

The following helper gates are defined:

has been constrained to be bits by the Sinsemilla hash.

#### Constraints

Outside this gate, we have constrained:

has been constrained to be bits by the .

#### Constraints

Outside this gate, we have constrained:

• is equality-constrained to , where the latter is the index-1 running sum output of constrained by the hash to be bits.

has been constrained to be bits by the .

#### Constraints

Outside this gate, we have constrained:

has been constrained to be bits by the .

#### Constraints

Outside this gate, we have constrained:

• is equality-constrained to , where the latter is the index-1 running sum output of constrained by the hash to be 240 bits.

has been constrained to be bits by the .

#### Constraints

Outside this gate, we have constrained:

## Field element checks

All message pieces and subpieces have been range-constrained by the earlier decomposition gates. They are now used to:

• constrain each field element , , , and to be 255-bit values, with top bits , , , and respectively.
• constrain where is the Pallas base field modulus.
• check 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 the corresponding top bit is set to 1.

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

Recall that . When the top bit is set, 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

Recall that . When the top bit is set, we check that :

1. 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

### with

Recall that . When the top bit is set, we check that :

1. 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

### with

Recall that . When the top bit is set, 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 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

### -coordinate checks

Note that only the LSB of the -coordinates was input to the hash, while the other bits of the -coordinate were unused. However, we must still check that the witnessed bit matches the original point's -coordinate. The checks for will follow the same format. For each -coordinate, we witness:

where is for , and for . Let We decompose to be bits using a strict word ten-bit lookup. The running sum outputs allow us to susbstitute

Recall that and were pieces input to the Sinsemilla hash and have already been boolean-constrained. and are constrained outside this gate to and bits respectively. To constrain the remaining chunks, we use the following constraints:

Then, to check that the decomposition was correct:

### 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 the -bit lookup decomposition of .

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

#### Constraints

Outside this gate, we have constrained:

This can be checked in exactly the same way as , with replaced by .