NoteCommit

Message decomposition

$\mathsf{SinsemillaCommit}$ is used in the $\mathsf{NoteCommit}$ function. The input to $\mathsf{SinsemillaCommit}$ is:

$$\mathsf{g}{\star }_{\mathsf{d}}||\mathsf{pk}{\star }_{\mathsf{d}}||{I2LEBSP}_{64}(\mathsf{v})||{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\rho )||{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\psi ),$$

where:

• $\mathsf{g}{\star }_{\mathsf{d}},\mathsf{pk}{\star }_{\mathsf{d}}$ are representations of Pallas curve points, with $255$ bits used for the $x$-coordinate and $1$ bit used for the $y$-coordinate.
• $\rho ,\psi$ are Pallas base field elements.
• $\mathsf{v}$ is a $64$-bit value.
• ${\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}\mathsf{g}{\star }_{\mathsf{d}}& =a||b_0||b_1||b_2\\ & =(\text{bits 0..=249 of }x({\mathsf{g}}_{\mathsf{d}}))||(\text{bits 250..=253 of }x({\mathsf{g}}_{\mathsf{d}}))||(\text{bit 254 of }x({\mathsf{g}}_{\mathsf{d}}))||(y\text{ bit of }{\mathsf{g}}_{\mathsf{d}})\\ \mathsf{pk}{\star }_{\mathsf{d}}& =b_3||c||d_0||d_1\\ & =(\text{bits 0..=3 of }x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))||(\text{bits 4..=253 of }x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))||(\text{bit 254 of }x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))||(y\text{ bit of }\mathsf{p}{\mathsf{k}}_{\mathsf{d}})\\ {I2LEBSP}_{64}(v)& =d_2||d_3||e_0\\ & =(\text{bits 0..=7 of }v)||(\text{bits 8..=57 of }v)||(\text{bits 58..=63 of }v)\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\rho )& =e_1||f||g_0\\ & =(\text{bits 0..=3 of }\rho )||(\text{bits 4..=253 of }\rho )||(\text{bit 254 of }\rho )\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\psi )& =g_1||g_2||h_0||h_1\\ & =(\text{bits 0..=8 of }\psi )||(\text{bits 9..=248 of }\psi )||(\text{bits 249..=253 of }\psi )||(\text{bit 254 of }\psi )\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||b_3\\ 250& c\\ 60& d=d_0||d_1||d_2||d_3\\ 10& e=e_0||e_1\\ 250& f\\ 250& g=g_0||g_1||g_2\\ 10& h=h_0||h_1||h_2\end{array}$$

where $h_2$ is 4 zero bits (corresponding to the padding applied by the Sinsemilla $\mathsf{pad}$ function).

Each message piece is constrained by $\mathsf{SinsemillaHash}$ to its stated length. Additionally:

• ${\mathsf{g}}_{\mathsf{d}}$ and $\mathsf{p}{\mathsf{k}}_{\mathsf{d}}$ are witnessed and checked to be valid elliptic curve points.
• $\mathsf{v}$ is witnessed as a field element, but its decomposition is sufficient to constrain it to be a 64-bit value.
• $\rho$ and $\psi$ 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{SinsemillaCommit}$ message).
• The chunks contain the canonical decompositions of ${\mathsf{g}}_{\mathsf{d}}$, $\mathsf{p}{\mathsf{k}}_{\mathsf{d}}$, $\rho$, and $\psi$ (or else the prover could witness multiple equivalent inputs to $\mathsf{SinsemillaCommit}$).

Some of these constraints are implemented with a reusable circuit gadget, $\text{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:

• $\text{bool\_check}(x)=x\cdot (1-x)$.
• $\text{short\_lookup\_range\_check}()$ is a short lookup range check.

$b=b_0||b_1||b_2||b_3$

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

Region layout

$$\begin{array}{cccc}{A}_6& A_7& A_8& q_{\mathsf{NoteCommit},b}\\ b& b_0& b_1& 1\\ & b_2& b_3& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},b}\cdot \text{bool\_check}(b_1)=0\\ 3& q_{\mathsf{NoteCommit},b}\cdot \text{bool\_check}(b_2)=0\\ 2& q_{\mathsf{NoteCommit},b}\cdot (b-(b_0+b_1\cdot 2^4+b_2\cdot 2^5+b_3\cdot 2^6))=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(b_0,4)$
• $\text{short\_lookup\_range\_check}(b_3,4)$

$d=d_0||d_1||d_2||d_3$

$d$ has been constrained to be $60$ bits by the $\mathsf{SinsemillaHash}$.

Region layout

$$\begin{array}{cccc}{A}_6& A_7& A_8& q_{\mathsf{NoteCommit},d}\\ d& d_0& d_1& 1\\ & d_2& d_3& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},d}\cdot \text{bool\_check}(d_0)=0\\ 3& q_{\mathsf{NoteCommit},d}\cdot \text{bool\_check}(d_1)=0\\ 2& q_{\mathsf{NoteCommit},d}\cdot (d-(d_0+d_1\cdot 2+d_2\cdot 2^2+d_3\cdot 2^{10}))=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(d_2,8)$
• $d_3$ is equality-constrained to $z_{d,1}$, where the latter is the index-1 running sum output of $\mathsf{SinsemillaHash}(d),$ constrained by the hash to be $50$ bits.

$e=e_0||e_1$

$e$ has been constrained to be $10$ bits by the $\mathsf{SinsemillaHash}$.

Region layout

$$\begin{array}{cccc}{A}_6& A_7& A_8& q_{\mathsf{NoteCommit},e}\\ e& e_0& e_1& 1\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},e}\cdot (e-(e_0+e_1\cdot 2^6))=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(e_0,6)$
• $\text{short\_lookup\_range\_check}(e_1,4)$

$g=g_0||g_1||g_2$

$g$ has been constrained to be $250$ bits by the $\mathsf{SinsemillaHash}$.

Region layout

$$\begin{array}{ccc}{A}_6& A_7& q_{\mathsf{NoteCommit},g}\\ g& g_0& 1\\ g_1& g_2& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},g}\cdot \text{bool\_check}(g_0)=0\\ 2& q_{\mathsf{NoteCommit},g}\cdot (g-(g_0+g_1\cdot 2+g_2\cdot 2^{10}))=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(g_1,9)$
• $g_2$ is equality-constrained to $z_{g,1}$, where the latter is the index-1 running sum output of $\mathsf{SinsemillaHash}(g),$ constrained by the hash to be 240 bits.

$h=h_0||h_1||h_2$

$h$ has been constrained to be $10$ bits by the $\mathsf{SinsemillaHash}$.

Region layout

$$\begin{array}{cccc}{A}_6& A_7& A_8& q_{\mathsf{NoteCommit},h}\\ h& h_0& h_1& 1\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},h}\cdot \text{bool\_check}(h_1)=0\\ 2& q_{\mathsf{NoteCommit},h}\cdot (h-(h_0+h_1\cdot 2^5))=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(h_0,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}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x({\mathsf{g}}_{\mathsf{d}}))$, ${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))$, ${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\rho )$, and ${I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\psi )$ to be 255-bit values, with top bits $b_1$, $d_0$, $g_0$, and $h_1$ respectively.
• constrain $$\begin{array}{rl}{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x({\mathsf{g}}_{\mathsf{d}}))& =x({\mathsf{g}}_{\mathsf{d}})(\mathrm{mod}{q}_{\mathbb{P}})\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))& =x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})(\mathrm{mod}{q}_{\mathbb{P}})\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\rho )& =\rho (\mathrm{mod}{q}_{\mathbb{P}})\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\psi )& =\psi (\mathrm{mod}{q}_{\mathbb{P}})\end{array}$$ where $q_{\mathbb{P}}$ is the Pallas base field modulus.
• check that these are indeed canonically-encoded field elements, i.e. $$\begin{array}{rl}{I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x({\mathsf{g}}_{\mathsf{d}}))& <q_{\mathbb{P}}\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}))& <q_{\mathbb{P}}\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\rho )& <q_{\mathbb{P}}\\ {I2LEBSP}_{{\ell }_{\mathsf{base}}^{\mathsf{Orchard}}}(\psi )& <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 the corresponding top bit is set to 1.

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 }$.

$x({\mathsf{g}}_{\mathsf{d}})$ with $b_1=1⟹x({\mathsf{g}}_{\mathsf{d}})\ge 2^{254}$

Recall that $x({\mathsf{g}}_{\mathsf{d}})=a+2^{250}\cdot b_0+2^{254}\cdot b_1$. When the top bit $b_1$ is set, we check that $x({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

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

   Since $b_1=1⟹x({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{0..}=253}<t_{\mathbb{P}}<2^{126},$ we know that $x({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{126..}=253}=0,$ and in particular $$b_0:=x({\mathsf{g}}_{\mathsf{d}}{)}_{\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.$$

Region layout

$$\begin{array}{ccccc}{A}_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\\ x({\mathsf{g}}_{\mathsf{d}})& b_0& a& z_{a,13}& 1\\ & b_1& a^{\prime }& z_{a^{\prime },13}& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\cdot (a+b_0\cdot 2^{250}+b_1\cdot 2^{254}-x({\mathsf{g}}_{\mathsf{d}}))=0\\ 3& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\cdot b_1\cdot b_0=0\\ 3& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\cdot b_1\cdot z_{a,13}=0\\ 2& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\cdot (a+2^{130}-t_{\mathbb{P}}-a^{\prime })=0\\ 3& q_{\mathsf{NoteCommit},x({\mathsf{g}}_{\mathsf{d}})}\cdot b_1\cdot z_{a^{\prime },13}=0\end{array}$$

$x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$ with $d_0=1⟹x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})\ge 2^{254}$

Recall that $x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})=b_3+2^4\cdot c+2^{254}\cdot d_0$. When the top bit $d_0$ is set, we check that $x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}}{)}_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $d_0=1⟹0\le b_3+2^4\cdot c<t_{\mathbb{P}}.$

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

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

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

Region layout

$$\begin{array}{ccccc}{A}_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})}\\ x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})& b_3& c& z_{c,13}& 1\\ & d_0& b_3{c}^{\prime }& z_{b_3{c}^{\prime },14}& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})}\cdot \left(b_3+c\cdot 2^4+d_0\cdot 2^{254}-x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})\right)=0\\ 3& q_{\mathsf{NoteCommit},x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})}\cdot d_0\cdot z_{c,13}=0\\ 2& q_{\mathsf{NoteCommit},x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})}\cdot (b_3+c\cdot 2^4+2^{140}-t_{\mathbb{P}}-b_3{c}^{\prime })=0\\ 3& q_{\mathsf{NoteCommit},x(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})}\cdot d_0\cdot z_{b_3{c}^{\prime },14}=0\end{array}$$

$\mathsf{v}=d_2+2^8\cdot d_3+2^{58}\cdot e_0$

Region layout

$$\begin{array}{ccccc}{A}_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},value}\\ value& d_2& d_3& e_0& 1\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},value}\cdot (d_2+d_3\cdot 2^8+e_0\cdot 2^{58}-\mathsf{value})=0\end{array}$$

$\rho$ with $g_0=1⟹\rho \ge 2^{254}$

Recall that $\rho =e_1+2^4\cdot f+2^{254}\cdot g_0$. When the top bit $g_0$ is set, we check that ${\rho }_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $g_0=1⟹0\le e_1+2^4\cdot f<t_{\mathbb{P}}.$

   To check that $0\le e_1+2^4\cdot f<t_{\mathbb{P}},$ we use two constraints:

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

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

Region layout

$$\begin{array}{ccccc}{A}_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},\rho }\\ \rho & e_1& f& z_{f,13}& 1\\ & g_0& e_1{f}^{\prime }& z_{e_1{f}^{\prime },14}& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},\rho }\cdot (e_1+f\cdot 2^4+g_0\cdot 2^{254}-\rho )=0\\ 3& q_{\mathsf{NoteCommit},\rho }\cdot g_0\cdot z_{f,13}=0\\ 2& q_{\mathsf{NoteCommit},\rho }\cdot (e_1+f\cdot 2^4+2^{140}-t_{\mathbb{P}}-e_1{f}^{\prime })=0\\ 3& q_{\mathsf{NoteCommit},\rho }\cdot g_0\cdot z_{e_1{f}^{\prime },14}=0\end{array}$$

$\psi$ with $h_1=1⟹\psi \ge 2^{254}$

Recall that $\psi =g_1+2^9\cdot g_2+2^{249}\cdot h_0+2^{254}\cdot h_1$. When the top bit $h_1$ is set, we check that ${\psi }_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $h_1=1⟹h_0=0.$

   Since $h_1=1⟹{\psi }_{\mathrm{0..}=253}<t_{\mathbb{P}}<2^{126},$ we know that ${\psi }_{\mathrm{126..}=253}=0,$ and in particular $h_0:={\psi }_{\mathrm{249..}=253}=0.$

2. $h_1=1⟹0\le g_1+2^9\cdot g_2<t_{\mathbb{P}}.$

   To check that $0\le g_1+2^9\cdot g_2<t_{\mathbb{P}},$ we use two constraints:

   a) $0\le g_1+2^9\cdot g_2<2^{140}.$ $g_1$ is already constrained individually to be a $9$-bit value. $z_{g,13}$ is the index-13 running sum output by $\mathsf{SinsemillaHash}(g).$ By constraining $$h_1\cdot z_{g,13}=0,$$ we constrain $g_1+2^9\cdot g_2<2^{129}<2^{130}.$

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

Region layout

$$\begin{array}{ccccc}{A}_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},\psi }\\ \psi & g_1& g_2& z_{g,13}& 1\\ h_0& h_1& g_1{g}_2^{\prime }& z_{g_1{g}_2^{\prime },13}& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},\psi }\cdot (g_1+g_2\cdot 2^9+h_0\cdot 2^{249}+h_1\cdot 2^{254}-\psi )=0\\ 3& q_{\mathsf{NoteCommit},\psi }\cdot h_1\cdot h_0=0\\ 3& q_{\mathsf{NoteCommit},\psi }\cdot h_1\cdot z_{g,13}=0\\ 2& q_{\mathsf{NoteCommit},\psi }\cdot (g_1+g_2\cdot 2^9+2^{130}-t_{\mathbb{P}}-g_1{g_2}^{\prime })=0\\ 3& q_{\mathsf{NoteCommit},\psi }\cdot h_1\cdot z_{g_1{g_2}^{\prime },13}=0\end{array}$$

$y$-coordinate checks

Note that only the $y$ LSB of the $y$-coordinates $y({\mathsf{g}}_{\mathsf{d}}),y(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$ 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({\mathsf{g}}_{\mathsf{d}}),y(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$ will follow the same format. For each $y$-coordinate, we witness:

$$\begin{array}{rl}y& =\text{LSB}||k_0||k_1||k_2||k_3\\ & =\text{LSB}||\text{ (bits 1..=9 of y) }||\text{ (bits 10..=249 of y) }||\text{ (bits 250..=253 of y) }||\text{ (bit 254 of y) },\end{array}$$

where $\text{LSB}$ is $b_2$ for $y({\mathsf{g}}_{\mathsf{d}})$, and $d_1$ for $y(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$. Let $$j=\text{LSB}+2\cdot k_0+2^{10}\cdot k_1.$$ We decompose $j$ to be $250$ bits using a strict $25-$word ten-bit lookup. The running sum outputs allow us to susbstitute $k_1=z_{j,1}.$

Recall that $b_2=y({\mathsf{g}}_{\mathsf{d}})$ and $d_1=y(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$ were pieces input to the Sinsemilla hash and have already been boolean-constrained. $k_0$ and $k_2$ are constrained outside this gate to $9$ and $4$ bits respectively. To constrain the remaining chunks, we use the following constraints:

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},y}\cdot \text{bool\_check}(k_3)=0\end{array}$$

Then, to check that the decomposition was correct: $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\mathsf{NoteCommit},y}\cdot \left(j-(\text{LSB}+k_0\cdot 2+k_1\cdot 2^{10})\right)=0\\ 2& q_{\mathsf{NoteCommit},y}\cdot \left(y-(j+k_2\cdot 2^{250}+k_3\cdot 2^{254})\right)=0\end{array}$$

$y({\mathsf{g}}_{\mathsf{d}})$ with $k_3=1⟹y({\mathsf{g}}_{\mathsf{d}})\ge 2^{254}$

In these cases, we check that $y({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{0..}=253}<t_{\mathbb{P}}$:

1. $k_3=1⟹k_2=0.$

   Since $k_3=1⟹y({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{0..}=253}<t_{\mathbb{P}}<2^{126},$ we know that $y({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{126..}=253}=0,$ and in particular $$k_2:=y({\mathsf{g}}_{\mathsf{d}}{)}_{\mathrm{250..}=253}=0.$$

2. $k_3=1⟹0\le j<t_{\mathbb{P}}.$

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

   a) $0\le j<2^{130}$. This is expressed in the custom gate as $$k_3\cdot z_{j,13}=0,$$ where $z_{j,13}$ is the index-13 running sum output by the $10$-bit lookup decomposition of $j$.

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

Region layout

$$\begin{array}{cccccc}{A}_5& A_6& A_7& A_8& A_9& q_{\mathsf{NoteCommit},y}\\ y& \tilde{y}& k_0& k_2& k_3& 1\\ j& k_1& z_{j,13}& j^{\prime }& z_{j^{\prime },13}& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\mathsf{NoteCommit},y}\cdot k_3\cdot k_2=0\\ 3& q_{\mathsf{NoteCommit},y}\cdot k_3\cdot z_{j,13}=0\\ 2& q_{\mathsf{NoteCommit},y}\cdot (j+2^{130}-t_{\mathbb{P}}-j^{\prime })=0\\ 3& q_{\mathsf{NoteCommit},y}\cdot k_3\cdot z_{j^{\prime },13}=0\end{array}$$

Outside this gate, we have constrained:

• $\text{short\_lookup\_range\_check}(k_0,9)$
• $\text{short\_lookup\_range\_check}(k_2,4)$

$y(\mathsf{p}{\mathsf{k}}_{\mathsf{d}})$

This can be checked in exactly the same way as $y({\mathsf{g}}_{\mathsf{d}})$, with $b_2$ replaced by $d_1$.