${\mathsf{Commit}}^{\mathsf{ivk}}$

Message decomposition

$\mathsf{SinsemillaShortCommit}$ is used in the ${\mathsf{Commit}}^{\mathsf{ivk}}$ function. The input to $\mathsf{SinsemillaShortCommit}$ is:

$${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{ak})||{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{nk}),$$

where $\mathsf{ak}$, $\mathsf{nk}$ are Pallas base field elements, and ${\ell }_{\mathsf{base}}^{\mathsf{Orchard}}=255.$

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

$$\begin{array}{rl}{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{ak})& =a||b_0||b_1\\ & =(\text{bits 0..=249 of }\mathsf{ak})||(\text{bits 250..=253 of }\mathsf{ak})||(\text{bit 254 of }\mathsf{ak})\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{nk})& =b_2||c||d_0||d_1\\ & =(\text{bits 0..=4 of }\mathsf{nk})||(\text{bits 5..=244 of }\mathsf{nk})||(\text{bits 245..=253 of }\mathsf{nk})||(\text{bit 254 of }\mathsf{nk})\end{array}$$

Then we recompose the chunks into message pieces:

$$\begin{array}{cl}\text{Length (bits)}& \text{Piece}\\ 250& a\\ 10& b=b_0||b_1||b_2\\ 240& c\\ 10& d=d_0||d_1\end{array}$$

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

Some of these constraints can be implemented with reusable circuit gadgets. We define a custom gate controlled by the selector $q_{{\mathsf{Commit}}^{\mathsf{ivk}}}$ 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:

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ & \text{short\_lookup\_range\_check}(b_0,4)\\ & \text{short\_lookup\_range\_check}(b_2,5)\\ & \text{short\_lookup\_range\_check}(d_0,9)\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot \text{bool\_check}(b_1)=0\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot \text{bool\_check}(d_1)=0\end{array}$$

where $\text{bool\_check}(x)=x\cdot (1-x)$ and $\text{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;
• $b_0$ ($4$ bits) is witnessed and constrained outside the gate;
• $b_1$ ($1$ bits) is witnessed and boolean-constrained in the gate;
• $b_2$ ($5$ bits) is witnessed and constrained outside the gate;
• $c$ ($240$ bits) is witnessed and constrained outside the gate;
• $d_0$ ($9$ bits) is witnessed and constrained outside the gate;
• $d_1$ ($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:

$$\begin{array}{rl}b& =b_0+2^4\cdot b_1+2^5\cdot b_2\\ d& =d_0+2^9\cdot d_1\\ \mathsf{ak}& =a+2^{250}\cdot b_0+2^{254}\cdot b_1\\ \mathsf{nk}& =b_2+2^5\cdot c+2^{245}\cdot d_0+2^{254}\cdot d_1\end{array}$$

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (b-(b_0+b_1\cdot 2^4+b_2\cdot 2^5))=0\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (d-(d_0+d_1\cdot 2^9))=0\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (a+b_0\cdot 2^{250}+b_1\cdot 2^{254}-\mathsf{ak})=0\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (b_2+c\cdot 2^5+d_0\cdot 2^{245}+d_1\cdot 2^{254}-\mathsf{nk})=0\end{array}$$

Canonicity checks

At this point, we have constrained ${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{ak})$ and ${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{nk})$ to be 255-bit values, with top bits $b_1$ and $d_1$ respectively. We have also constrained:

$$\begin{array}{rl}{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{ak})& =\mathsf{ak}(\mathrm{mod}{q}_{\mathbb{P}})\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{nk})& =\mathsf{nk}(\mathrm{mod}{q}_{\mathbb{P}})\end{array}$$

where $q_{\mathbb{P}}$ is the Pallas base field modulus. The remaining constraints will enforce that these are indeed canonically-encoded field elements, i.e.

$$\begin{array}{rl}{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{ak})& <q_{\mathbb{P}}\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\mathsf{nk})& <q_{\mathbb{P}}\end{array}$$

The Pallas base field modulus has the form $q_{\mathbb{P}}=2^{254}+t_{\mathbb{P}}$, where $$t_{\mathbb{P}}=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 $b_1=1$ (for $\mathsf{ak}$) or $d_1=1$ (for $\mathsf{nk}$).

In the constraints below we use a base-$2^{10}$ variant of the method used in libsnark (originally from [SVPBABW2012, Appendix C.1]) for range constraints $0\le x<t$:

• Let $t^{\prime }$ be the smallest power of $2^{10}$ greater than $t$.
• Enforce $0\le x<t^{\prime }$.
• Let $x^{\prime }=x+t^{\prime }-t$.
• Enforce $0\le x^{\prime }<t^{\prime }$.

$\mathsf{ak}$ with $b_1=1⟹\mathsf{ak}\ge 2^{254}$

In these cases, we check that ${\text{ak}}_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $b_1=1⟹b_0=0.$

   Since $b_1=1⟹{\mathsf{ak}}_{\mathrm{0..}=253}<t_{\mathbb{P}}<2^{126},$ we know that ${\mathsf{ak}}_{\mathrm{126..}=253}=0,$ and in particular $$b_0:={\mathsf{ak}}_{\mathrm{250..}=253}=0.$$

2. $b_1=1⟹0\le a<t_{\mathbb{P}}.$

   To check that $a<t_{\mathbb{P}}$, we use two constraints:

   a) $0\le a<2^{130}$. This is expressed in the custom gate as $$b_1\cdot z_{a,13}=0,$$ where $z_{a,13}$ is the index-13 running sum output by $\mathsf{SinsemillaHash}(a).$

   b) $0\le a+2^{130}-t_{\mathbb{P}}<2^{130}$. To check this, we decompose $a^{\prime }=a+2^{130}-t_{\mathbb{P}}$ into thirteen 10-bit words (little-endian) using a running sum $z_{a^{\prime }}$, looking up each word in a $10$-bit lookup table. We then enforce in the custom gate that $$b_1\cdot z_{a^{\prime },13}=0.$$

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot b_1\cdot b_0=0\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot b_1\cdot z_{a,13}=0\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (a+2^{130}-t_{\mathbb{P}}-a^{\prime })=0\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot b_1\cdot z_{a^{\prime },13}=0\end{array}$$

$\mathsf{nk}$ with $d_1=1⟹\mathsf{nk}\ge 2^{254}$

In these cases, we check that ${\text{nk}}_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $d_1=1⟹d_0=0.$

   Since $d_1=1⟹{\mathsf{nk}}_{\mathrm{0..}=253}<t_{\mathbb{P}}<2^{126},$ we know that ${\mathsf{nk}}_{\mathrm{126..}=253}=0,$ and in particular $$d_0:={\mathsf{nk}}_{\mathrm{245..}=253}=0.$$

2. $d_1=1⟹0\le b_2+2^5\cdot c<t_{\mathbb{P}}.$

   To check that $0\le b_2+2^5\cdot c<t_{\mathbb{P}}$, we use two constraints:

   a) $0\le b_2+2^5\cdot c<2^{140}$. $b_2$ is already constrained individually to be a $5$-bit value. $z_{c,13}$ is the index-13 running sum output by $\mathsf{SinsemillaHash}(c).$ By constraining $$d_1\cdot z_{c,13}=0,$$ we constrain $b_2+2^5\cdot c<2^{135}<2^{140}.$

   b) $0\le b_2+2^5\cdot c+2^{140}-t_{\mathbb{P}}<2^{140}$. To check this, we decompose $b_2{c}^{\prime }=b_2+2^5\cdot c+2^{140}-t_{\mathbb{P}}$ into fourteen 10-bit words (little-endian) using a running sum $z_{b_2{c}^{\prime }}$, looking up each word in a $10$-bit lookup table. We then enforce in the custom gate that $$d_1\cdot z_{b_2{c}^{\prime },14}=0.$$

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot d_1\cdot d_0=0\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot d_1\cdot z_{c,13}=0\\ 2& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot (b_2+c\cdot 2^5+2^{140}-t_{\mathbb{P}}-b_2{c}^{\prime })=0\\ 3& q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\cdot d_1\cdot z_{b_2{c}^{\prime },14}=0\end{array}$$

Region layout

The constraints controlled by the $q_{{\mathsf{Commit}}^{\mathsf{ivk}}}$ selector are arranged across 9 advice columns, requiring two rows.

$$\begin{array}{cccccccccc}& & & & & & & & & q_{{\mathsf{Commit}}^{\mathsf{ivk}}}\\ \mathsf{ak}& a& b& b_0& b_1& b_2& z_{a,13}& a^{\prime }& z_{a^{\prime },13}& 1\\ \mathsf{nk}& c& d& d_0& d_1& & z_{c,13}& b_2{c}^{\prime }& z_{b_2{c}^{\prime },14}& 0\end{array}$$