Variable-base scalar multiplication

In the Orchard circuit we need to check $\mathsf{p}{\mathsf{k}}_{\mathsf{d}}=[\mathsf{ivk}]{\mathsf{g}}_{\mathsf{d}}$ where $\mathsf{ivk}\in [0,p)$ and the scalar field is ${\mathbb{F}}_q$ with $p<q$.

We have $p=2^{254}+t_p$ and $q=2^{254}+t_q$, for $t_p,t_q<2^{128}$.

Witness scalar

We're trying to compute $[\alpha ]T$ for $\alpha \in [0,q)$. Set $k=\alpha +t_q$ and $n=254$. Then we can compute

$\begin{array}{cl}[2^{254}+(\alpha +t_q)]T& =[2^{254}+(\alpha +t_q)-(2^{254}+t_q)]T\\ & =[\alpha ]T\end{array}$

provided that $\alpha +t_q\in [0,2^{n+1})$, i.e. $\alpha <2^{n+1}-t_q$ which covers the whole range we need because in fact $2^{255}-t_q>q$.

Thus, given a scalar $\alpha$, we witness the boolean decomposition of $k=\alpha +t_q.$ (We use big-endian bit order for convenient input into the variable-base scalar multiplication algorithm.)

$$k=k_{254}\cdot 2^{254}+k_{253}\cdot 2^{253}+\cdots +k_0.$$

Variable-base scalar multiplication

We use an optimized double-and-add algorithm, copied from "Faster variable-base scalar multiplication in zk-SNARK circuits" with some variable name changes:

Acc := [2] T
for i from n-1 down to 0 {
    P := k_{i+1} ? T : −T
    Acc := (Acc + P) + Acc
}
return (k_0 = 0) ? (Acc - T) : Acc

It remains to check that the x-coordinates of each pair of points to be added are distinct.

When adding points in a prime-order group, we can rely on Theorem 3 from Appendix C of the Halo paper, which says that if we have two such points with nonzero indices wrt a given odd-prime order base, where the indices taken in the range $-(q-1)/2..(q-1)/2$ are distinct disregarding sign, then they have different x-coordinates. This is helpful, because it is easier to reason about the indices of points occurring in the scalar multiplication algorithm than it is to reason about their x-coordinates directly.

So, the required check is equivalent to saying that the following "indexed version" of the above algorithm never asserts:

acc := 2
for i from n-1 down to 0 {
    p = k_{i+1} ? 1 : −1
    assert acc ≠ ± p
    assert (acc + p) ≠ acc    // X
    acc := (acc + p) + acc
    assert 0 < acc ≤ (q-1)/2
}
if k_0 = 0 {
    assert acc ≠ 1
    acc := acc - 1
}

The maximum value of acc is:

    <--- n 1s --->
  1011111...111111
= 1100000...000000 - 1

= $2^{n+1}+2^n-1$

The assertion labelled X obviously cannot fail because $p\ne 0$. It is possible to see that acc is monotonically increasing except in the last conditional. It reaches its largest value when $k$ is maximal, i.e. $2^{n+1}+2^n-1$.

So to entirely avoid exceptional cases, we would need $2^{n+1}+2^n-1<(q-1)/2$. But we can use $n$ larger by $c$ if the last $c$ iterations use complete addition.

The first $i$ for which the algorithm using only incomplete addition fails is going to be $252$, since $2^{252+1}+2^{252}-1>(q-1)/2$. We need $n=254$ to make the wraparound technique above work.

sage: q = 0x40000000000000000000000000000000224698fc0994a8dd8c46eb2100000001
sage: 2^253 + 2^252 - 1 < (q-1)//2
False
sage: 2^252 + 2^251 - 1 < (q-1)//2
True

So the last three iterations of the loop ($i=\mathrm{2..0}$) need to use complete addition, as does the conditional subtraction at the end. Writing this out using ⸭ for incomplete addition (as we do in the spec), we have:

Acc := [2] T
for i from 253 down to 3 {
    P := k_{i+1} ? T : −T
    Acc := (Acc ⸭ P) ⸭ Acc
}
for i from 2 down to 0 {
    P := k_{i+1} ? T : −T
    Acc := (Acc + P) + Acc  // complete addition
}
return (k_0 = 0) ? (Acc + (-T)) : Acc  // complete addition

Constraint program for optimized double-and-add

Define a running sum ${\mathbf{z}}_{\mathbf{j}}={\sum }_{i=j}^n({\mathbf{k}}_i\cdot 2^{i-j})$, where $n=254$ and:

$$\begin{array}{rl}& {\mathbf{z}}_{n+1}=0,\\ & {\mathbf{z}}_n={\mathbf{k}}_n,\text{(most significant bit)}\\ & {\mathbf{z}}_0=k.\end{array}$$

$\begin{array}{l}\text{Initialize }{A}_{254}=[2]T.\\ \\ \text{for }i\text{ from }254\text{ down to }4:\\ \text{bool\_check}({\mathbf{k}}_i)=0\\ {\mathbf{z}}_i=2{\mathbf{z}}_{i+1}+{\mathbf{k}}_i\\ x_{P,i}=x_T\\ y_{P,i}=(2{\mathbf{k}}_i-1)\cdot y_T\text{(conditionally negate)}\\ {\lambda }_{1,i}\cdot (x_{A,i}-x_{P,i})=y_{A,i}-y_{P,i}\\ x_{R,i}={\lambda }_{1,i}^2-x_{A,i}-x_{P,i}\\ ({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-x_{R,i})=2y_{\mathsf{A},i}\\ {\lambda }_{2,i}^2=x_{A,i-1}+x_{R,i}+x_{A,i}\\ {\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i-1})=y_{A,i}+y_{A,i-1}.\end{array}$

The helper $\text{bool\_check}(x)=x\cdot (1-x)$. After substitution of $x_{P,i},y_{P,i},x_{R,i},y_{A,i}$, and $y_{A,i-1}$, this becomes:

$\begin{array}{l}\text{Initialize }{A}_{254}=[2]T.\\ \\ \text{for }i\text{ from }254\text{ down to }4:\\ \text{// let }{\mathbf{k}}_i={\mathbf{z}}_i-2{\mathbf{z}}_{i+1}\\ \text{// let }{y}_{A,i}=\frac{({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-({\lambda }_{1,i}^2-x_{A,i}-x_T))}{2}\\ \text{bool\_check}({\mathbf{k}}_i)=0\\ {\lambda }_{1,i}\cdot (x_{A,i}-x_T)=y_{A,i}-(2{\mathbf{k}}_i-1)\cdot y_T\\ {\lambda }_{2,i}^2=x_{A,i-1}+{\lambda }_{1,i}^2-x_T\\ \{\begin{array}{ll}{\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i-1})=y_{A,i}+y_{A,i-1},& \text{if }i>4\\ {\lambda }_{2,4}\cdot (x_{A,4}-x_{A,3})=y_{A,4}+y_{A,3}^{\text{witnessed}},& \text{if }i=4.\end{array}\end{array}$

Here, $y_{A,3}^{\text{witnessed}}$ is assigned to a cell. This is unlike previous $y_{A,i}$'s, which were implicitly derived from ${\lambda }_{1,i},{\lambda }_{2,i},x_{A,i},x_T$, but never actually assigned.

The bits ${\mathbf{k}}_{3\dots 1}$ are used in three further steps, using complete addition:

$\begin{array}{l}\text{for }i\text{ from }3\text{ down to }1:\\ \text{// let }{\mathbf{k}}_i={\mathbf{z}}_i-2{\mathbf{z}}_{i+1}\\ \text{bool\_check}({\mathbf{k}}_i)=0\\ (x_{A,i-1},y_{A,i-1})=\left((x_{A,i},y_{A,i})+(x_T,y_T)\right)+(x_{A,i},y_{A,i})\end{array}$

If the least significant bit ${\mathbf{k}}_0=1,$ we set $B=\mathcal{O},$ otherwise we set $B=-T$. Then we return $A+B$ using complete addition.

Let $B=\{\begin{array}{ll}(0,0),& \text{ if }{\mathbf{k}}_0=1,\\ (x_T,-y_T),& \text{ otherwise.}\end{array}$

Output $(x_{A,0},y_{A,0})+B$.

(Note that $(0,0)$ represents $\mathcal{O}$.)

Incomplete addition

We need six advice columns to witness $(x_T,y_T,{\lambda }_1,{\lambda }_2,x_{A,i},{\mathbf{z}}_i)$. However, since $(x_T,y_T)$ are the same, we can perform two incomplete additions in a single row, reusing the same $(x_T,y_T)$. We split the scalar bits used in incomplete addition into $hi$ and $lo$ halves and process them in parallel. This means that we effectively have two for loops:

• the first, covering the $hi$ half for $i$ from $254$ down to $130$, with a special case at $i=130$; and
• the second, covering the $lo$ half for the remaining $i$ from $129$ down to $4$, with a special case at $i=4$.

$$\begin{array}{cccccccccccccccc}{x}_T& y_T& z^{hi}& x_A^{hi}& {\lambda }_1^{hi}& {\lambda }_2^{hi}& q_1^{hi}& q_2^{hi}& q_3^{hi}& z^{lo}& x_A^{lo}& {\lambda }_1^{lo}& {\lambda }_2^{lo}& q_1^{lo}& q_2^{lo}& q_3^{lo}\\ & & {\mathbf{z}}_{255}=0& & y_{A,254}=2[T{]}_y& & 1& 0& 0& {\mathbf{z}}_{130}& & y_{A,129}& & 1& 0& 0\\ x_T& y_T& {\mathbf{z}}_{254}& x_{A,254}=2[T{]}_x& {\lambda }_{1,254}& {\lambda }_{2,254}& 0& 1& 0& {\mathbf{z}}_{129}& x_{A,129}& {\lambda }_{1,129}& {\lambda }_{2,129}& 0& 1& 0\\ x_T& y_T& {\mathbf{z}}_{253}& x_{A,253}& {\lambda }_{1,253}& {\lambda }_{2,253}& 0& 1& 0& {\mathbf{z}}_{128}& x_{A,128}& {\lambda }_{1,128}& {\lambda }_{2,128}& 0& 1& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\\ x_T& y_T& {\mathbf{z}}_{130}& x_{A,130}& {\lambda }_{1,130}& {\lambda }_{2,130}& 0& 0& 1& {\mathbf{z}}_5& x_{A,5}& {\lambda }_{1,5}& {\lambda }_{2,5}& 0& 1& 0\\ x_T& y_T& & x_{A,129}& y_{A,129}& & & & & {\mathbf{z}}_4& x_{A,4}& {\lambda }_{1,4}& {\lambda }_{2,4}& 0& 0& 1\\ & & & & & & & & & & x_{A,3}& y_{A,3}& & & & \end{array}$$

For each $hi$ and $lo$ half, we have three sets of gates. Note that $i$ is going from $\mathrm{255..}=3$; $i$ is NOT indexing the rows.

$q_1=1$

This gate is only used on the first row (before the for loop). We check that ${\lambda }_1,{\lambda }_2$ are initialized to values consistent with the initial $y_A.$ $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 4& q_1\cdot \left(y_{A,n}^{\text{witnessed}}-y_{A,n}\right)=0\end{array}$$ where $$\begin{array}{rl}{y}_{A,n}& =\frac{({\lambda }_{1,n}+{\lambda }_{2,n})\cdot (x_{A,n}-({\lambda }_{1,n}^2-x_{A,n}-x_T))}{2},\\ y_{A,n}^{\text{witnessed}}& \text{ is witnessed.}\end{array}$$

$q_2=1$

This gate is used on all rows corresponding to the for loop except the last.

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_2\cdot \left(x_{T,cur}-x_{T,next}\right)=0\\ 2& q_2\cdot \left(y_{T,cur}-y_{T,next}\right)=0\\ 3& q_2\cdot \text{bool\_check}({\mathbf{k}}_i)=0,\text{ where }{\mathbf{k}}_i={\mathbf{z}}_i-2{\mathbf{z}}_{i+1}\\ 4& q_2\cdot \left({\lambda }_{1,i}\cdot (x_{A,i}-x_{T,i})-y_{A,i}+(2{\mathbf{k}}_i-1)\cdot y_{T,i}\right)=0\\ 3& q_2\cdot \left({\lambda }_{2,i}^2-x_{A,i-1}-x_{R,i}-x_{A,i}\right)=0\\ 3& q_2\cdot \left({\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i-1})-y_{A,i}-y_{A,i-1}\right)=0\end{array}$$ where $$\begin{array}{rl}{x}_{R,i}& ={\lambda }_{1,i}^2-x_{A,i}-x_T,\\ y_{A,i}& =\frac{({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-({\lambda }_{1,i}^2-x_{A,i}-x_T))}{2},\\ y_{A,i-1}& =\frac{({\lambda }_{1,i-1}+{\lambda }_{2,i-1})\cdot (x_{A,i-1}-({\lambda }_{1,i-1}^2-x_{A,i-1}-x_T))}{2},\end{array}$$

$q_3=1$

This gate is used on the final iteration of the for loop, handling the special case where we check that the output $y_A$ has been witnessed correctly. $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_3\cdot \text{bool\_check}({\mathbf{k}}_i)=0,\text{ where }{\mathbf{k}}_i={\mathbf{z}}_i-2{\mathbf{z}}_{i+1}\\ 4& q_3\cdot \left({\lambda }_{1,i}\cdot (x_{A,i}-x_{T,i})-y_{A,i}+(2{\mathbf{k}}_i-1)\cdot y_{T,i}\right)=0\\ 3& q_3\cdot \left({\lambda }_{2,i}^2-x_{A,i-1}-x_{R,i}-x_{A,i}\right)=0\\ 3& q_3\cdot \left({\lambda }_{2,i}\cdot (x_{A,i}-x_{A,i-1})-y_{A,i}-y_{A,i-1}^{\text{witnessed}}\right)=0\end{array}$$ where $$\begin{array}{rl}{x}_{R,i}& ={\lambda }_{1,i}^2-x_{A,i}-x_T,\\ y_{A,i}& =\frac{({\lambda }_{1,i}+{\lambda }_{2,i})\cdot (x_{A,i}-({\lambda }_{1,i}^2-x_{A,i}-x_T))}{2},\\ y_{A,i-1}^{\text{witnessed}}& \text{ is witnessed.}\end{array}$$

Complete addition

We reuse the complete addition constraints to implement the final $c$ rounds of double-and-add. This requires two rows per round because we need 9 advice columns for each complete addition. In the 10th advice column we stash the other cells that we need to correctly implement the double-and-add:

• The base $y$ coordinate, so we can conditionally negate it as input to one of the complete additions.
• The running sum, which we constrain over two rows instead of sequentially.

Layout

$$\begin{array}{ccccccccccc}{a}_0& a_1& a_2& a_3& a_4& a_5& a_6& a_7& a_8& a_9& q_{\text{mul\_decompose\_var}}\\ x_T& y_p& x_A& y_A& {\lambda }_1& {\alpha }_1& {\beta }_1& {\gamma }_1& {\delta }_1& z_{i+1}& 0\\ x_A& y_A& x_q& y_q& {\lambda }_2& {\alpha }_2& {\beta }_2& {\gamma }_2& {\delta }_2& y_T& 1\\ & & x_r& y_r& & & & & & z_i& 0\end{array}$$

Constraints

In addition to the complete addition constraints, we define the following gate:

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ & q_{\text{mul\_decompose\_var}}\cdot \text{bool\_check}({\mathbf{k}}_i)=0\\ & q_{\text{mul\_decompose\_var}}\cdot \text{ternary}({\mathbf{k}}_i,y_T-y_p,y_T+y_p)=0\end{array}$$ where ${\mathbf{k}}_i={\mathbf{z}}_i-2{\mathbf{z}}_{i+1}$.

LSB

Layout

$$\begin{array}{ccccccccccc}{a}_0& a_1& a_2& a_3& a_4& a_5& a_6& a_7& a_8& a_9& q_{\text{mul\_lsb}}\\ x_p& y_p& x_A& y_A& \lambda & \alpha & \beta & \gamma & \delta & z_1& 1\\ x_T& y_T& x_r& y_r& & & & & & z_0& 0\end{array}$$

Constraints

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ & q_{\text{mul\_lsb}}\cdot \text{bool\_check}({\mathbf{k}}_0)=0\\ & q_{\text{mul\_lsb}}\cdot \text{ternary}({\mathbf{k}}_0,x_p,x_p-x_T)=0\\ & q_{\text{mul\_lsb}}\cdot \text{ternary}({\mathbf{k}}_0,y_p,y_p+y_T)=0\end{array}$$ where ${\mathbf{k}}_0={\mathbf{z}}_0-2{\mathbf{z}}_1$.

Overflow check

${\mathbf{z}}_i$ cannot overflow for any $i\ge 1$, because it is a weighted sum of bits only up to $2^{n-1}=2^{253}$, which is smaller than $p$ (and also $q$).

However, ${\mathbf{z}}_0=\alpha +t_q$ can overflow $[0,p)$.

Note: for full-width scalar mul, it may not be possible to represent ${\mathbf{z}}_0$ in the base field (e.g. when the base field is Pasta's ${\mathbb{F}}_p$ and $p<q$). In that case, we need to special-case the row that would mention ${\mathbf{z}}_0$ so that it is correct for whatever representation we use for a full-width scalar. Our representation for $k$ will be the pair $({\mathbb{k}}_{254},k^{\prime }=k-2^{254}\cdot {\mathbb{k}}_{254})$. We'll use $k^{\prime }$ in place of $\alpha +t_q$ for ${\mathbf{z}}_0$, constraining $k^{\prime }$ to 254 bits so that it fits in an ${\mathbb{F}}_p$ element. Then we just have to generalize the argument below to work for $k^{\prime }\in [0,2\cdot t_q)$ (because the maximum value of $\alpha +t_q$ is $q-1+t_q=2^{254}+t_q-1+t_q$).

Since overflow can only occur in the final step that constrains ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1+{\mathbf{k}}_0$, we have ${\mathbf{z}}_0=k(\mathrm{mod}p)$. It is then sufficient to also check that ${\mathbf{z}}_0=\alpha +t_q(\mathrm{mod}p)$ (so that $k=\alpha +t_q(\mathrm{mod}p)$) and that $k\in [t_q,p+t_q)$. These conditions together imply that $k=\alpha +t_q$ as an integer, and so $2^{254}+k=\alpha (\mathrm{mod}q)$ as required.

Note: the bits ${\mathbf{k}}_{\mathrm{254..0}}$ do not represent a value reduced modulo $q$, but rather a representation of the unreduced $\alpha +t_q$.

Optimized check for $k\in [t_q,p+t_q)$

Since $t_p+t_q<2^{130}$ (also true if $p$ and $q$ are swapped), we have $$[t_q,p+t_q)=[t_q,t_q+2^{130})\cup [2^{130},2^{254})\cup ([2^{254},2^{254}+2^{130})\cap [p+t_q-2^{130},p+t_q)).$$

We may assume that $k=\alpha +t_q(\mathrm{mod}p)$.

(This is true for the use of variable-base scalar mul in Orchard, where we know that $\alpha <p$. If is also true if we swap $p$ and $q$ so that we have $p>q$. It is not true for a full-width scalar $\alpha \ge p$ when $p<q$.)

Therefore, $\begin{array}{rcl}k\in [t_q,p+t_q)& \iff & (k\in [t_q,t_q+2^{130})\vee k\in [2^{130},2^{254}))\vee \\ & & (k\in [2^{254},2^{254}+2^{130})\wedge k\in [p+t_q-2^{130},p+t_q))\\ & & \\ & \iff & ({\mathbf{k}}_{254}=0⟹(k\in [t_q,t_q+2^{130})\vee k\in [2^{130},2^{254})))\wedge \\ & & ({\mathbf{k}}_{254}=1⟹(k\in [2^{254},2^{254}+2^{130})\wedge k\in [p+t_q-2^{130},p+t_q)))\\ & & \\ & \iff & ({\mathbf{k}}_{254}=0⟹(\alpha \in [0,2^{130})\vee k\in [2^{130},2^{254})))\wedge \\ & & ({\mathbf{k}}_{254}=1⟹(k\in [2^{254},2^{254}+2^{130})\wedge (\alpha +2^{130})\mathrm{mod}p\in [0,2^{130})))Ⓐ\end{array}$

Given $k\in [2^{254},2^{254}+2^{130})$, we prove equivalence of $k\in [p+t_q-2^{130},p+t_q)$ and $(\alpha +2^{130})\mathrm{mod}p\in [0,2^{130})$ as follows:

• shift the range by $2^{130}-p-t_q$ to give $k+2^{130}-p-t_q\in [0,2^{130})$;
• observe that $k+2^{130}-p-t_q$ is guaranteed to be in $[2^{130}-t_p-t_q,2^{131}-t_p-t_q)$ and therefore cannot overflow or underflow modulo $p$;
• using the fact that $k=\alpha +t_q(\mathrm{mod}p)$, observe that $(k+2^{130}-p-t_q)\mathrm{mod}p=(\alpha +t_q+2^{130}-p-t_q)\mathrm{mod}p=(\alpha +2^{130})\mathrm{mod}p$.

(We can see in a different way that this is correct by observing that it checks whether $\alpha \mathrm{mod}p\in [p-2^{130},p)$, so the upper bound is aligned as we would expect.)

Now, we can continue optimizing from $Ⓐ$:

$\begin{array}{rcl}k\in [t_q,p+t_q)& \iff & ({\mathbf{k}}_{254}=0⟹(\alpha \in [0,2^{130})\vee k\in [2^{130},2^{254}))\wedge \\ & & ({\mathbf{k}}_{254}=1⟹(k\in [2^{254},2^{254}+2^{130})\wedge (\alpha +2^{130})\mathrm{mod}p\in [0,2^{130})))\\ & & \\ & \iff & ({\mathbf{k}}_{254}=0⟹(\alpha \in [0,2^{130})\vee {\mathbf{k}}_{\mathrm{253..130}}\text{ are not all }0))\wedge \\ & & ({\mathbf{k}}_{254}=1⟹({\mathbf{k}}_{\mathrm{253..130}}\text{ are all }0\wedge (\alpha +2^{130})\mathrm{mod}p\in [0,2^{130})))\end{array}$

Constraining ${\mathbf{k}}_{\mathrm{253..130}}$ to be all-$0$ or not-all-$0$ can be implemented almost "for free", as follows.

Recall that ${\mathbf{z}}_i={\sum }_{h=i}^n({\mathbf{k}}_h\cdot 2^{h-i})$, so we have:

$\begin{array}{rcl}{\mathbf{z}}_{130}& =& {\sum }_{h=130}^{254}({\mathbf{k}}_h\cdot 2^{h-130})\\ {\mathbf{z}}_{130}& =& {\mathbf{k}}_{254}\cdot 2^{254-130}+{\sum }_{h=130}^{253}({\mathbf{k}}_h\cdot 2^{h-130})\\ {\mathbf{z}}_{130}-{\mathbf{k}}_{254}\cdot 2^{124}& =& {\sum }_{h=130}^{253}({\mathbf{k}}_h\cdot 2^{h-130})\end{array}$

So ${\mathbf{k}}_{\mathrm{253..130}}$ are all $0$ exactly when ${\mathbf{z}}_{130}={\mathbf{k}}_{254}\cdot 2^{124}$.

Finally, we can merge the $130$-bit decompositions for the ${\mathbf{k}}_{254}=0$ and ${\mathbf{k}}_{254}=1$ cases by checking that $(\alpha +{\mathbf{k}}_{254}\cdot 2^{130})\mathrm{mod}p\in [0,2^{130})$.

Overflow check constraints

Let $s=\alpha +{\mathbf{k}}_{254}\cdot 2^{130}$. The constraints for the overflow check are:

$$\begin{array}{rl}{\mathbf{z}}_0& =\alpha +t_q(\mathrm{mod}p)\\ {\mathbf{k}}_{254}=1⟹({\mathbf{z}}_{130}& =2^{124}\wedge s\mathrm{mod}p\in [0,2^{130}))\\ {\mathbf{k}}_{254}=0⟹({\mathbf{z}}_{130}& \ne 0\vee s\mathrm{mod}p\in [0,2^{130}))\end{array}$$

Define $inv0(x)=\{\begin{array}{ll}0,& \text{if }x=0\\ 1/x,& \text{otherwise.}\end{array}$

Witness $\eta =inv0({\mathbf{z}}_{130})$, and decompose $s\mathrm{mod}p$ as ${\mathbf{s}}_{\mathrm{129..0}}$.

Then the needed gates are:

$$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 2& q_{\text{mul\_overflow}}\cdot \left(s-(\alpha +{\mathbf{k}}_{254}\cdot 2^{130})\right)=0\\ 2& q_{\text{mul\_overflow}}\cdot \left({\mathbf{z}}_0-\alpha -t_q\right)=0\\ 3& q_{\text{mul\_overflow}}\cdot \left({\mathbf{k}}_{254}\cdot ({\mathbf{z}}_{130}-2^{124})\right)=0\\ 3& q_{\text{mul\_overflow}}\cdot \left({\mathbf{k}}_{254}\cdot (s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}\right)=0\\ 5& q_{\text{mul\_overflow}}\cdot \left((1-{\mathbf{k}}_{254})\cdot (1-{\mathbf{z}}_{130}\cdot \eta )\cdot (s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}\right)=0\end{array}$$ where $(s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}$ can be computed by another running sum. Note that the factor of $1/2^{130}$ has no effect on the constraint, since the RHS is zero.

Running sum range check

We make use of a $10$-bit lookup range check in the circuit to subtract the low $130$ bits of $\mathbf{s}$. The range check subtracts the first $13\cdot 10$ bits of $\mathbf{s},$ and right-shifts the result to give $(s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}.$

Overflow check (general)

Recall that we defined ${\mathbf{z}}_j={\sum }_{i=j}^n({\mathbf{k}}_i\cdot 2^{i-j})$, where $n=254$.

${\mathbf{z}}_j$ cannot overflow for any $j\ge 1$, because it is a weighted sum of bits only up to and including $2^{n-j}$. When $n=254$ and $j=1$ this sum can be at most $2^{254}-1$, which is smaller than $p$ (and also $q$).

However, for full-width scalar mul, it may not be possible to represent ${\mathbf{z}}_0$ in the base field (e.g. when the base field is Pasta's ${\mathbb{F}}_p$ and $p<q$). In that case ${\mathbf{z}}_0=\alpha +t_q$ can overflow $[0,p)$.

So, we need to special-case the row that would mention ${\mathbf{z}}_0$ so that it is correct for whatever representation we use for a full-width scalar.

Our representation for $k$ will be the pair $({\mathbf{k}}_{254},k^{\prime }=k-2^{254}\cdot {\mathbf{k}}_{254})$. We'll use $k^{\prime }$ in place of $\alpha +t_q$ for ${\mathbf{z}}_0$, constraining $k^{\prime }$ to 254 bits so that it fits in an ${\mathbb{F}}_p$ element.

Then we just have to generalize the overflow check used for variable-base scalar mul in the Orchard circuit to work for $k^{\prime }\in [0,2\cdot t_q)$ (because the maximum value of $\alpha +t_q$ is $q-1+t_q=2^{254}+t_q-1+t_q$).

Note: the bits ${\mathbf{k}}_{\mathrm{254..0}}$ do not represent a value reduced modulo $q$, but rather a representation of the unreduced $\alpha +t_q$.

Overflow can only occur in the final step that constrains ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1+{\mathbf{k}}_0$, and only if ${\mathbf{z}}_1$ has the bit with weight $2^{253}$ set (i.e. if ${\mathbf{k}}_{254}=1$). If we instead set ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1-2^{254}\cdot {\mathbf{k}}_{254}+{\mathbf{k}}_0$, now ${\mathbf{z}}_0$ cannot overflow and should be equal to $k^{\prime }$.

It is then sufficient to also check that ${\mathbf{z}}_0+2^{254}\cdot {\mathbf{k}}_{254}=\alpha +t_q$ as an integer where $\alpha \in [0,q)$.

Represent $\alpha$ as $2^{254}\cdot {\mathbf{\alpha }}_{254}+2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$ where we constrain ${\alpha }^{\prime \prime }\in [0,2^{253})$ and ${\mathbf{\alpha }}_{253}$ and ${\mathbf{\alpha }}_{254}$ to boolean. For this to be a canonical representation we also need ${\mathbf{\alpha }}_{254}=1⟹({\mathbf{\alpha }}_{253}=0\wedge {\alpha }^{\prime \prime }\in [0,t_q))$.

Let ${\alpha }^{\prime }=2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$.

If ${\mathbf{\alpha }}_{254}=1$:

• constrain ${\mathbf{k}}_{254}=1$ and ${\mathbf{z}}_0={\alpha }^{\prime }+t_q$. This cannot overflow because in this case ${\alpha }^{\prime }\in [0,t_q)$ and so ${\mathbf{z}}_0\in [0,2\cdot t_q)$.

If ${\mathbf{\alpha }}_{254}=0$:

• we should have ${\mathbf{k}}_{254}=1$ iff ${\alpha }^{\prime }\in [2^{254}-t_q,2^{254})$, i.e. witness ${\mathbf{k}}_{254}$ as boolean and then
  • If ${\mathbf{k}}_{254}=0$ then constrain ${\alpha }^{\prime }\notin [2^{254}-t_q,2^{254})$.
    • This can be done by constraining either ${\mathbf{\alpha }}_{253}=0$ or ${\alpha }^{\prime \prime }+t_q\in [0,2^{253})$. (${\alpha }^{\prime \prime }+t_q$ cannot overflow.)
  • If ${\mathbf{k}}_{254}=1$ then constrain ${\alpha }^{\prime }\in [2^{254}-t_q,2^{254})$.
    • This can be done by constraining ${\alpha }^{\prime }-(2^{254}-t_q)\in [0,2^{130})$ and ${\alpha }^{\prime }-2^{254}+2^{130}\in [0,2^{130})$.

Overflow check constraints (general)

Represent $\alpha$ as $2^{254}\cdot {\mathbf{\alpha }}_{254}+2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$ as above.

The constraints for the overflow check are:

$$\begin{array}{rl}& {\alpha }^{\prime \prime }\in [0,2^{253})\\ & {\mathbf{\alpha }}_{253}\in \{0,1\}\\ & {\mathbf{\alpha }}_{254}\in \{0,1\}\\ & {\mathbf{k}}_{254}\in \{0,1\}\\ {\mathbf{\alpha }}_{254}=1⟹& {\mathbf{\alpha }}_{253}=0\\ {\mathbf{\alpha }}_{254}=1⟹& {\alpha }^{\prime \prime }\in [0,2^{130})❁\\ {\mathbf{\alpha }}_{254}=1⟹& {\alpha }^{\prime \prime }+2^{130}-t_q\in [0,2^{130})❁\\ {\mathbf{\alpha }}_{254}=1⟹& {\mathbf{k}}_{254}=1\\ {\mathbf{\alpha }}_{254}=1⟹& {\mathbf{z}}_0={\alpha }^{\prime }+t_q\\ {\mathbf{\alpha }}_{254}=0\wedge {\mathbf{\alpha }}_{253}=1\wedge {\mathbf{k}}_{254}=0& ⟹{\alpha }^{\prime \prime }+t_q\in [0,2^{253})\\ {\mathbf{\alpha }}_{254}=0\wedge {\mathbf{k}}_{254}=1& ⟹{\alpha }^{\prime }-2^{254}+t_q\in [0,2^{130})❁\\ {\mathbf{\alpha }}_{254}=0\wedge {\mathbf{k}}_{254}=1& ⟹{\alpha }^{\prime }-2^{254}+2^{130}\in [0,2^{130})❁\end{array}$$

Note that the four 130-bit constraints marked $❁$ are in two pairs that occur in disjoint cases. We can therefore combine them into two 130-bit constraints using a new witness variable $u$; the other constraint always being on $u+2^{130}-t_q$:

$$\begin{array}{rl}{\mathbf{\alpha }}_{254}=1⟹& u={\alpha }^{\prime \prime }\\ {\mathbf{\alpha }}_{254}=0\wedge {\mathbf{k}}_{254}=1⟹& u={\alpha }^{\prime }-2^{254}+t_q\\ & u\in [0,2^{130})\\ & u+2^{130}-t_q\in [0,2^{130})\end{array}$$

($u$ is unconstrained and can be witnessed as $0$ in the case ${\mathbf{\alpha }}_{254}=0\wedge {\mathbf{k}}_{254}=0$.)

Cost

• 25 10-bit and one 3-bit range check, to constrain ${\alpha }^{\prime \prime }$ to 253 bits;
• 25 10-bit and one 3-bit range check, to constrain ${\alpha }^{\prime \prime }+t_q$ to 253 bits when ${\mathbf{\alpha }}_{254}=0\wedge {\mathbf{\alpha }}_{253}=1\wedge {\mathbf{k}}_{254}=0$;
• two times 13 10-bit range checks.