# NoteCommit

## Message decomposition

SinsemillaCommit is used in the NoteCommit function. The input to SinsemillaCommit is:

g⋆d​∣∣pk⋆d​∣∣I2LEBSP64​(v)∣∣I2LEBSPℓbaseOrchardp​​(ρ)∣∣I2LEBSPℓbaseOrchardp​​(ψ),

where:

- g⋆d​,pk⋆d​ are representations of Pallas curve points, with 255 bits used for the x-coordinate and 1 bit used for the y-coordinate.
- ρ,ψ are Pallas base field elements.
- v is a 64-bit value.
- ℓbaseOrchardp​=255.

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

g⋆d​pk⋆d​I2LEBSP64​(v)I2LEBSPℓbaseOrchardp​​(ρ)I2LEBSPℓbaseOrchardp​​(ψ)​=a∣∣b0​∣∣b1​∣∣b2​=(bits 0..=249 of x(gd​))∣∣(bits 250..=253 of x(gd​))∣∣(bit 254 of x(gd​))∣∣(y​ bit of gd​)=b3​∣∣c∣∣d0​∣∣d1​=(bits 0..=3 of x(pkd​))∣∣(bits 4..=253 of x(pkd​))∣∣(bit 254 of x(pkd​))∣∣(y​ bit of pkd​)=d2​∣∣d3​∣∣e0​=(bits 0..=7 of v)∣∣(bits 8..=57 of v)∣∣(bits 58..=63 of v)=e1​∣∣f∣∣g0​=(bits 0..=3 of ρ)∣∣(bits 4..=253 of ρ)∣∣(bit 254 of ρ)=g1​∣∣g2​∣∣h0​∣∣h1​=(bits 0..=8 of ψ)∣∣(bits 9..=248 of ψ)∣∣(bits 249..=253 of ψ)∣∣(bit 254 of ψ)​

Then we recompose the chunks into message pieces:

Length (bits)25010250601025025010​Pieceab=b0​∣∣b1​∣∣b2​∣∣b3​cd=d0​∣∣d1​∣∣d2​∣∣d3​e=e0​∣∣e1​fg=g0​∣∣g1​∣∣g2​h=h0​∣∣h1​∣∣h2​​​

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

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

- gd​ and pkd​ are witnessed and checked to be valid elliptic curve points.
- v 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 SinsemillaCommit message).
- The chunks contain the canonical decompositions of gd​, pkd​, ρ, and ψ (or else the prover could witness multiple equivalent inputs to SinsemillaCommit).

Some of these constraints are implemented with a reusable circuit gadget, short_lookup_range_check(). 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:

- a (250 bits) is witnessed and constrained outside the gate;
- c (250 bits) is witnessed and constrained outside the gate;
- f (250 bits) is witnessed and constrained outside the gate;

The following helper gates are defined:

- bool_check(x)=x⋅(1−x).
- short_lookup_range_check() is a short lookup range check.

### b=b0​∣∣b1​∣∣b2​∣∣b3​

b has been constrained to be 10 bits by the Sinsemilla hash.

#### Region layout

A6​b​A7​b0​b2​​A8​b1​b3​​qNoteCommit,b​10​​

#### Constraints

Degree332​ConstraintqNoteCommit,b​⋅bool_check(b1​)=0qNoteCommit,b​⋅bool_check(b2​)=0qNoteCommit,b​⋅(b−(b0​+b1​⋅24+b2​⋅25+b3​⋅26))=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(b0​,4)
- short_lookup_range_check(b3​,4)

### d=d0​∣∣d1​∣∣d2​∣∣d3​

d has been constrained to be 60 bits by the SinsemillaHash.

#### Region layout

A6​d​A7​d0​d2​​A8​d1​d3​​qNoteCommit,d​10​​

#### Constraints

Degree332​ConstraintqNoteCommit,d​⋅bool_check(d0​)=0qNoteCommit,d​⋅bool_check(d1​)=0qNoteCommit,d​⋅(d−(d0​+d1​⋅2+d2​⋅22+d3​⋅210))=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(d2​,8)
- d3​ is equality-constrained to zd,1​, where the latter is the index-1 running sum output of SinsemillaHash(d), constrained by the hash to be 50 bits.

### e=e0​∣∣e1​

e has been constrained to be 10 bits by the SinsemillaHash.

#### Region layout

A6​e​A7​e0​​A8​e1​​qNoteCommit,e​1​​

#### Constraints

Degree2​ConstraintqNoteCommit,e​⋅(e−(e0​+e1​⋅26))=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(e0​,6)
- short_lookup_range_check(e1​,4)

### g=g0​∣∣g1​∣∣g2​

g has been constrained to be 250 bits by the SinsemillaHash.

#### Region layout

A6​gg1​​A7​g0​g2​​qNoteCommit,g​10​​

#### Constraints

Degree32​ConstraintqNoteCommit,g​⋅bool_check(g0​)=0qNoteCommit,g​⋅(g−(g0​+g1​⋅2+g2​⋅210))=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(g1​,9)
- g2​ is equality-constrained to zg,1​, where the latter is the index-1 running sum output of SinsemillaHash(g), constrained by the hash to be 240 bits.

### h=h0​∣∣h1​∣∣h2​

h has been constrained to be 10 bits by the SinsemillaHash.

#### Region layout

A6​h​A7​h0​​A8​h1​​qNoteCommit,h​1​​

#### Constraints

Degree32​ConstraintqNoteCommit,h​⋅bool_check(h1​)=0qNoteCommit,h​⋅(h−(h0​+h1​⋅25))=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(h0​,5)

## 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 I2LEBSPℓbaseOrchardp​​(x(gd​)), I2LEBSPℓbaseOrchardp​​(x(pkd​)), I2LEBSPℓbaseOrchardp​​(ρ), and I2LEBSPℓbaseOrchardp​​(ψ) to be 255-bit values, with top bits b1​, d0​, g0​, and h1​ respectively.
- constrain I2LEBSPℓbaseOrchardp​​(x(gd​))I2LEBSPℓbaseOrchardp​​(x(pkd​))I2LEBSPℓbaseOrchardp​​(ρ)I2LEBSPℓbaseOrchardp​​(ψ)​=x(gd​)(modqP​)=x(pkd​)(modqP​)=ρ(modqP​)=ψ(modqP​)​​ where qP​ is the Pallas base field modulus.
- check that these are indeed canonically-encoded field elements, i.e. I2LEBSPℓbaseOrchardp​​(x(gd​))I2LEBSPℓbaseOrchardp​​(x(pkd​))I2LEBSPℓbaseOrchardp​​(ρ)I2LEBSPℓbaseOrchardp​​(ψ)​<qP​<qP​<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 the corresponding top bit is set to 1.

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

### x(gd​) with b1​=1⟹x(gd​)≥2254

Recall that x(gd​)=a+2250⋅b0​+2254⋅b1​. When the top bit b1​ is set, we check that x(gd​)0..=253​<tP​:

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

   Since b1​=1⟹x(gd​)0..=253​<tP​<2126, we know that x(gd​)126..=253​=0, and in particular b0​:=x(gd​)250..=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.

#### Region layout

A6​x(gd​)​A7​b0​b1​​A8​aa′​A9​za,13​za′,13​​qNoteCommit,x(gd​)​10​​

#### Constraints

Degree23323​ConstraintqNoteCommit,x(gd​)​⋅(a+b0​⋅2250+b1​⋅2254−x(gd​))=0qNoteCommit,x(gd​)​⋅b1​⋅b0​=0qNoteCommit,x(gd​)​⋅b1​⋅za,13​=0qNoteCommit,x(gd​)​⋅(a+2130−tP​−a′)=0qNoteCommit,x(gd​)​⋅b1​⋅za′,13​=0​​

### x(pkd​) with d0​=1⟹x(pkd​)≥2254

Recall that x(pkd​)=b3​+24⋅c+2254⋅d0​. When the top bit d0​ is set, we check that x(pkd​)0..=253​<tP​:

1. d0​=1⟹0≤b3​+24⋅c<tP​.

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

   a) 0≤b3​+24⋅c<2140. b3​ is already constrained individually to be a 4-bit value. zc,13​ is the index-13 running sum output by SinsemillaHash(c). By constraining d0​⋅zc,13​=0, we constrain b3​+24⋅c<2134<2140.

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

#### Region layout

A6​x(pkd​)​A7​b3​d0​​A8​cb3​c′​A9​zc,13​zb3​c′,14​​qNoteCommit,x(pkd​)​10​​

#### Constraints

Degree2323​ConstraintqNoteCommit,x(pkd​)​⋅(b3​+c⋅24+d0​⋅2254−x(pkd​))=0qNoteCommit,x(pkd​)​⋅d0​⋅zc,13​=0qNoteCommit,x(pkd​)​⋅(b3​+c⋅24+2140−tP​−b3​c′)=0qNoteCommit,x(pkd​)​⋅d0​⋅zb3​c′,14​=0​​

### v=d2​+28⋅d3​+258⋅e0​

#### Region layout

A6​value​A7​d2​​A8​d3​​A9​e0​​qNoteCommit,value​1​​

#### Constraints

Degree2​ConstraintqNoteCommit,value​⋅(d2​+d3​⋅28+e0​⋅258−value)=0​​

### ρ with g0​=1⟹ρ≥2254

Recall that ρ=e1​+24⋅f+2254⋅g0​. When the top bit g0​ is set, we check that ρ0..=253​<tP​:

1. g0​=1⟹0≤e1​+24⋅f<tP​.

   To check that 0≤e1​+24⋅f<tP​, we use two constraints:

   a) 0≤e1​+24⋅f<2140. e1​ is already constrained individually to be a 4-bit value. zf,13​ is the index-13 running sum output by SinsemillaHash(f). By constraining g0​⋅zf,13​=0, we constrain e1​+24⋅f<2134<2140.

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

#### Region layout

A6​ρ​A7​e1​g0​​A8​fe1​f′​A9​zf,13​ze1​f′,14​​qNoteCommit,ρ​10​​

#### Constraints

Degree2323​ConstraintqNoteCommit,ρ​⋅(e1​+f⋅24+g0​⋅2254−ρ)=0qNoteCommit,ρ​⋅g0​⋅zf,13​=0qNoteCommit,ρ​⋅(e1​+f⋅24+2140−tP​−e1​f′)=0qNoteCommit,ρ​⋅g0​⋅ze1​f′,14​=0​​

### ψ with h1​=1⟹ψ≥2254

Recall that ψ=g1​+29⋅g2​+2249⋅h0​+2254⋅h1​. When the top bit h1​ is set, we check that ψ0..=253​<tP​:

1. h1​=1⟹h0​=0.

   Since h1​=1⟹ψ0..=253​<tP​<2126, we know that ψ126..=253​=0, and in particular h0​:=ψ249..=253​=0.

2. h1​=1⟹0≤g1​+29⋅g2​<tP​.

   To check that 0≤g1​+29⋅g2​<tP​, we use two constraints:

   a) 0≤g1​+29⋅g2​<2140. g1​ is already constrained individually to be a 9-bit value. zg,13​ is the index-13 running sum output by SinsemillaHash(g). By constraining h1​⋅zg,13​=0, we constrain g1​+29⋅g2​<2129<2130.

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

#### Region layout

A6​ψh0​​A7​g1​h1​​A8​g2​g1​g2′​​A9​zg,13​zg1​g2′​,13​​qNoteCommit,ψ​10​​

#### Constraints

Degree23323​ConstraintqNoteCommit,ψ​⋅(g1​+g2​⋅29+h0​⋅2249+h1​⋅2254−ψ)=0qNoteCommit,ψ​⋅h1​⋅h0​=0qNoteCommit,ψ​⋅h1​⋅zg,13​=0qNoteCommit,ψ​⋅(g1​+g2​⋅29+2130−tP​−g1​g2​′)=0qNoteCommit,ψ​⋅h1​⋅zg1​g2​′,13​=0​​

### y-coordinate checks

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

y​=LSB∣∣k0​∣∣k1​∣∣k2​∣∣k3​=LSB∣∣ (bits 1..=9 of y) ∣∣ (bits 10..=249 of y) ∣∣ (bits 250..=253 of y) ∣∣ (bit 254 of y) ,​​

where LSB is b2​ for y(gd​), and d1​ for y(pkd​). Let j=LSB+2⋅k0​+210⋅k1​. We decompose j to be 250 bits using a strict 25−word ten-bit lookup. The running sum outputs allow us to susbstitute k1​=zj,1​.

Recall that b2​=y​(gd​) and d1​=y​(pkd​) were pieces input to the Sinsemilla hash and have already been boolean-constrained. k0​ and k2​ are constrained outside this gate to 9 and 4 bits respectively. To constrain the remaining chunks, we use the following constraints:

Degree3​ConstraintqNoteCommit,y​⋅bool_check(k3​)=0​​

Then, to check that the decomposition was correct: Degree22​ConstraintqNoteCommit,y​⋅(j−(LSB+k0​⋅2+k1​⋅210))=0qNoteCommit,y​⋅(y−(j+k2​⋅2250+k3​⋅2254))=0​​

### y(gd​) with k3​=1⟹y(gd​)≥2254

In these cases, we check that y(gd​)0..=253​<tP​:

1. k3​=1⟹k2​=0.

   Since k3​=1⟹y(gd​)0..=253​<tP​<2126, we know that y(gd​)126..=253​=0, and in particular k2​:=y(gd​)250..=253​=0.

2. k3​=1⟹0≤j<tP​.

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

   a) 0≤j<2130. This is expressed in the custom gate as k3​⋅zj,13​=0, where zj,13​ is the index-13 running sum output by the 10-bit lookup decomposition of j.

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

#### Region layout

A5​yj​A6​y~​k1​​A7​k0​zj,13​​A8​k2​j′​A9​k3​zj′,13​​qNoteCommit,y​10​​

#### Constraints

Degree3323​ConstraintqNoteCommit,y​⋅k3​⋅k2​=0qNoteCommit,y​⋅k3​⋅zj,13​=0qNoteCommit,y​⋅(j+2130−tP​−j′)=0qNoteCommit,y​⋅k3​⋅zj′,13​=0​​

Outside this gate, we have constrained:

- short_lookup_range_check(k0​,9)
- short_lookup_range_check(k2​,4)

### y(pkd​)

This can be checked in exactly the same way as y(gd​), with b2​ replaced by d1​.