# Commitivk

## Message decomposition

SinsemillaShortCommit is used in the Commitivk function. The input to SinsemillaShortCommit is:

I2LEBSPℓbaseOrchardp​​(ak)∣∣I2LEBSPℓbaseOrchardp​​(nk),

where ak, nk are Pallas base field elements, and ℓbaseOrchardp​=255.

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

I2LEBSPℓbaseOrchardp​​(ak)I2LEBSPℓbaseOrchardp​​(nk)​=a∣∣b0​∣∣b1​=(bits 0..=249 of ak)∣∣(bits 250..=253 of ak)∣∣(bit 254 of ak)=b2​∣∣c∣∣d0​∣∣d1​=(bits 0..=4 of nk)∣∣(bits 5..=244 of nk)∣∣(bits 245..=253 of nk)∣∣(bit 254 of nk)​​

Then we recompose the chunks into message pieces:

Length (bits)2501024010​Pieceab=b0​∣∣b1​∣∣b2​cd=d0​∣∣d1​​​

Each message piece is constrained by SinsemillaHash to its stated length. Additionally, ak and nk 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 SinsemillaShortCommit message).
- The chunks contain the canonical decompositions of ak and nk (or else the prover could witness an input to SinsemillaShortCommit that is equivalent to ak and nk but not identical).

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

## Bit length constraints

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

Degree33​Constraintshort_lookup_range_check(b0​,4)short_lookup_range_check(b2​,5)short_lookup_range_check(d0​,9)qCommitivk​⋅bool_check(b1​)=0qCommitivk​⋅bool_check(d1​)=0​​

where bool_check(x)=x⋅(1−x) and 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 (250 bits) is witnessed and constrained outside the gate;
- b0​ (4 bits) is witnessed and constrained outside the gate;
- b1​ (1 bits) is witnessed and boolean-constrained in the gate;
- b2​ (5 bits) is witnessed and constrained outside the gate;
- c (240 bits) is witnessed and constrained outside the gate;
- d0​ (9 bits) is witnessed and constrained outside the gate;
- d1​ (1 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:

bdaknk​=b0​+24⋅b1​+25⋅b2​=d0​+29⋅d1​=a+2250⋅b0​+2254⋅b1​=b2​+25⋅c+2245⋅d0​+2254⋅d1​​​

Degree2222​ConstraintqCommitivk​⋅(b−(b0​+b1​⋅24+b2​⋅25))=0qCommitivk​⋅(d−(d0​+d1​⋅29))=0qCommitivk​⋅(a+b0​⋅2250+b1​⋅2254−ak)=0qCommitivk​⋅(b2​+c⋅25+d0​⋅2245+d1​⋅2254−nk)=0​​

## Canonicity checks

At this point, we have constrained I2LEBSPℓbaseOrchardp​​(ak) and I2LEBSPℓbaseOrchardp​​(nk) to be 255-bit values, with top bits b1​ and d1​ respectively. We have also constrained:

I2LEBSPℓbaseOrchardp​​(ak)I2LEBSPℓbaseOrchardp​​(nk)​=ak(modqP​)=nk(modqP​)​​

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

I2LEBSPℓbaseOrchardp​​(ak)I2LEBSPℓbaseOrchardp​​(nk)​<qP​<qP​​​

The Pallas base field modulus has the form qP​=2254+tP​, where tP​=0x224698fc094cf91b992d30ed00000001 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 b1​=1 (for ak) or d1​=1 (for nk).

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

> - Let t′ be the smallest power of 210 greater than t.
> - Enforce 0≤x<t′.
> - Let x′=x+t′−t.
> - Enforce 0≤x′<t′.

### ak with b1​=1⟹ak≥2254

In these cases, we check that ak0..=253​<tP​:

1. b1​=1⟹b0​=0.

   Since b1​=1⟹ak0..=253​<tP​<2126, we know that ak126..=253​=0, and in particular b0​:=ak250..=253​=0.

2. b1​=1⟹0≤a<tP​.

   To check that a<tP​, we use two constraints:

   a) 0≤a<2130. This is expressed in the custom gate as b1​⋅za,13​=0, where za,13​ is the index-13 running sum output by SinsemillaHash(a).

   b) 0≤a+2130−tP​<2130. To check this, we decompose a′=a+2130−tP​ into thirteen 10-bit words (little-endian) using a running sum za′​, looking up each word in a 10-bit lookup table. We then enforce in the custom gate that b1​⋅za′,13​=0.

Degree3323​ConstraintqCommitivk​⋅b1​⋅b0​=0qCommitivk​⋅b1​⋅za,13​=0qCommitivk​⋅(a+2130−tP​−a′)=0qCommitivk​⋅b1​⋅za′,13​=0​​

### nk with d1​=1⟹nk≥2254

In these cases, we check that nk0..=253​<tP​:

1. d1​=1⟹d0​=0.

   Since d1​=1⟹nk0..=253​<tP​<2126, we know that nk126..=253​=0, and in particular d0​:=nk245..=253​=0.

2. d1​=1⟹0≤b2​+25⋅c<tP​.

   To check that 0≤b2​+25⋅c<tP​, we use two constraints:

   a) 0≤b2​+25⋅c<2140. b2​ is already constrained individually to be a 5-bit value. zc,13​ is the index-13 running sum output by SinsemillaHash(c). By constraining d1​⋅zc,13​=0, we constrain b2​+25⋅c<2135<2140.

   b) 0≤b2​+25⋅c+2140−tP​<2140. To check this, we decompose b2​c′=b2​+25⋅c+2140−tP​ into fourteen 10-bit words (little-endian) using a running sum zb2​c′​, looking up each word in a 10-bit lookup table. We then enforce in the custom gate that d1​⋅zb2​c′,14​=0.

Degree3323​ConstraintqCommitivk​⋅d1​⋅d0​=0qCommitivk​⋅d1​⋅zc,13​=0qCommitivk​⋅(b2​+c⋅25+2140−tP​−b2​c′)=0qCommitivk​⋅d1​⋅zb2​c′,14​=0​​

## Region layout

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

aknk​ac​bd​b0​d0​​b1​d1​​b2​​za,13​zc,13​​a′b2​c′​za′,13​zb2​c′,14​​qCommitivk​10​​