译自 halo2 book:https://zcash.github.io/halo2/design/gadgets/ecc/var-base-scalar-mul.html

变基标量乘(Variable-base scalar multiplication)

在 Orchard 电路中,我们需要检查 $\mathsf{p}{\mathsf{k}}_{\mathsf{d}}=[\mathsf{ivk}]{\mathsf{g}}_{\mathsf{d}}$,其中 $\mathsf{ivk}\in [0,p)$,且标量域(scalar field)为 ${\mathbb{F}}_q$,$p<q$。

我们有 $p=2^{254}+t_p$ 和 $q=2^{254}+t_q$,其中 $t_p,t_q<2^{128}$。

见证标量(Witness scalar)

我们试图计算 $[\alpha ]T$,其中 $\alpha \in [0,q)$。设 $k=\alpha +t_q$ 且 $n=254$。那么我们可以计算

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

前提是 $\alpha +t_q\in [0,2^{n+1})$,即 $\alpha <2^{n+1}-t_q$,这覆盖了我们需要的整个范围,因为事实上 $2^{255}-t_q>q$。

因此,给定一个标量 $\alpha$,我们见证 $k=\alpha +t_q$ 的布尔分解(boolean decomposition)。(为便于输入到变基标量乘算法中,我们使用大端(big-endian)位序。)

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

变基标量乘(Variable-base scalar multiplication)

我们使用一个优化过的倍加(double-and-add)算法,从 《Faster variable-base scalar multiplication in zk-SNARK circuits》 复制而来,并做了一些变量名修改:

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

剩下要检查的是,每对要相加的点的 x 坐标都互不相同。

当在素数阶群(prime-order group)中相加点时,我们可以依赖 Halo 论文 附录 C 中的定理 3,它表明:如果我们有两个这样的点,它们相对于给定的奇素数阶基有非零索引(index),且这些索引取在 $-(q-1)/2..(q-1)/2$ 范围内时,忽略符号是互不相同的,那么它们就有不同的 x 坐标。这很有帮助,因为对标量乘算法中出现的点的索引进行推理,比直接对它们的 x 坐标进行推理要容易。

因此,所需的检查等价于说,上述算法的下列"带索引版本"永远不会触发 assert:

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
}

acc 的最大值是:

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

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

标记为 X 的 assert 显然不可能失败,因为 $p\ne 0$。可以看出,除了最后那个条件分支外,acc 是单调递增的。它在 $k$ 取最大值时达到其最大值,即 $2^{n+1}+2^n-1$。

所以,为了完全避免例外情形(exceptional cases),我们将需要 $2^{n+1}+2^n-1<(q-1)/2$。但如果最后 $c$ 次迭代使用完全加法(complete addition),我们就可以把 $n$ 增大 $c$。

仅使用不完全加法(incomplete addition)时算法第一个失败的 $i$ 将是 $252$,因为 $2^{252+1}+2^{252}-1>(q-1)/2$。我们需要 $n=254$ 才能使上述环绕(wraparound)技巧奏效。

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

所以循环的最后三次迭代($i=\mathrm{2..0}$)需要使用完全加法(complete addition),末尾的条件减法也是如此。用 ⸭ 表示不完全加法(如我们在规范中所做),把它写出来,我们有:

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)

定义一个移动求和(running sum)${\mathbf{z}}_{\mathbf{j}}={\sum }_{i=j}^n({\mathbf{k}}_i\cdot 2^{i-j})$,其中 $n=254$ 且:

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

辅助函数 $\text{bool\_check}(x)=x\cdot (1-x)$。 在代入 $x_{P,i},y_{P,i},x_{R,i},y_{A,i}$ 和 $y_{A,i-1}$ 之后,这变为:

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

这里,$y_{A,3}^{\text{witnessed}}$ 被分配到一个单元格(cell)中。这与之前的各个 $y_{A,i}$ 不同,后者是从 ${\lambda }_{1,i},{\lambda }_{2,i},x_{A,i},x_T$ 隐式推导出来的,但从未真正被分配过。

位 ${\mathbf{k}}_{3\dots 1}$ 被用于另外三个步骤中,使用完全加法(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}$

如果最低有效位(least significant bit)${\mathbf{k}}_0=1,$ 我们置 $B=\mathcal{O},$ 否则我们置 $B=-T$。然后我们使用完全加法返回 $A+B$。

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

输出 $(x_{A,0},y_{A,0})+B$。

(注意 $(0,0)$ 表示 $\mathcal{O}$。)

不完全加法(Incomplete addition)

我们需要六个 advice 列来见证 $(x_T,y_T,{\lambda }_1,{\lambda }_2,x_{A,i},{\mathbf{z}}_i)$。然而,由于 $(x_T,y_T)$ 是相同的,我们可以在一行中执行两次不完全加法,复用相同的 $(x_T,y_T)$。我们把不完全加法中使用的标量位分成 $hi$ 和 $lo$ 两半并行处理。这意味着我们实际上有两个 for 循环:

• 第一个,覆盖 $hi$ 半部分,$i$ 从 $254$ 到 $130$,在 $i=130$ 处有一个特殊情形;以及
• 第二个,覆盖 $lo$ 半部分,即剩余的 $i$ 从 $129$ 到 $4$,在 $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}$$

对于每个 $hi$ 和 $lo$ 半部分,我们有三组门(gate)。注意 $i$ 是从 $\mathrm{255..}=3$ 取值;$i$ 不是对行做索引。

$q_1=1$

这个门仅用于第一行(在 for 循环之前)。我们检查 ${\lambda }_1,{\lambda }_2$ 被初始化为与初始 $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}$$ 其中 $$\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$

这个门用于对应 for 循环的所有行,除最后一行外。

$$\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}$$ 其中 $$\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$

这个门用于 for 循环的最后一次迭代,处理特殊情形,其中我们检查输出 $y_A$ 被正确见证。 $$\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}$$ 其中 $$\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)

我们复用完全加法(complete addition)约束来实现倍加的最后 $c$ 轮。这需要每轮两行,因为每次完全加法都需要 9 个 advice 列。在第 10 个 advice 列中,我们暂存为正确实现倍加所需的其他单元格:

• 基点的 $y$ 坐标,这样我们可以对它进行条件取负,作为其中一次完全加法的输入。
• 移动求和(running sum),我们在两行上而非顺序地对它进行约束。

布局(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)

除了完全加法约束之外,我们定义以下门(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}$$ 其中 ${\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}$$ 其中 ${\mathbf{k}}_0={\mathbf{z}}_0-2{\mathbf{z}}_1$。

溢出检查(Overflow check)

对于任何 $i\ge 1$,${\mathbf{z}}_i$ 都不会溢出,因为它是仅到 $2^{n-1}=2^{253}$ 为止的若干位的加权求和,而 $2^{253}$ 小于 $p$(也小于 $q$)。

然而,${\mathbf{z}}_0=\alpha +t_q$ 可能会溢出 $[0,p)$。

注:对于全宽标量乘,可能无法在基域中表示 ${\mathbf{z}}_0$(例如当基域是 Pasta 的 ${\mathbb{F}}_p$ 且 $p<q$ 时)。 在这种情况下,我们需要对涉及 ${\mathbf{z}}_0$ 的那一行进行特殊处理,使其对于我们用于全宽标量的任何表示都是正确的。 我们对 $k$ 的表示将是这个对:$({\mathbb{k}}_{254},k^{\prime }=k-2^{254}\cdot {\mathbb{k}}_{254})$。 我们将用 $k^{\prime }$ 代替 $\alpha +t_q$ 作为 ${\mathbf{z}}_0$,并把 $k^{\prime }$ 约束到 254 位,使它能放入一个 ${\mathbb{F}}_p$ 元素。 然后我们只需把下面的论证推广到适用于 $k^{\prime }\in [0,2\cdot t_q)$(因为 $\alpha +t_q$ 的最大值是 $q-1+t_q=2^{254}+t_q-1+t_q$)。

由于溢出只可能发生在约束 ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1+{\mathbf{k}}_0$ 的最后一步,我们有 ${\mathbf{z}}_0=k(\mathrm{mod}p)$。那么只需再检查 ${\mathbf{z}}_0=\alpha +t_q(\mathrm{mod}p)$(使得 $k=\alpha +t_q(\mathrm{mod}p)$)以及 $k\in [t_q,p+t_q)$ 即可。这些条件合在一起就意味着 $k=\alpha +t_q$ 作为整数成立,因此如所需有 $2^{254}+k=\alpha (\mathrm{mod}q)$。

注:位 ${\mathbf{k}}_{\mathrm{254..0}}$ 并不表示一个对 $q$ 取模归约后的值,而是表示未归约的 $\alpha +t_q$ 的一个表示。

对 $k\in [t_q,p+t_q)$ 的优化检查(Optimized check)

由于 $t_p+t_q<2^{130}$(若 $p$ 和 $q$ 互换也成立),我们有 $$[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)).$$

我们可以假设 $k=\alpha +t_q(\mathrm{mod}p)$。

(对于 Orchard 中变基标量乘的使用而言这是真的,在那里我们知道 $\alpha <p$。如果我们互换 $p$ 和 $q$ 使得 $p>q$,这也成立。 但对于一个全宽标量 $\alpha \ge p$ 且 $p<q$ 时,它不成立。)

因此, $\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}$

给定 $k\in [2^{254},2^{254}+2^{130})$,我们如下证明 $k\in [p+t_q-2^{130},p+t_q)$ 与 $(\alpha +2^{130})\mathrm{mod}p\in [0,2^{130})$ 的等价性:

• 把该区间平移 $2^{130}-p-t_q$,得到 $k+2^{130}-p-t_q\in [0,2^{130})$;
• 观察到 $k+2^{130}-p-t_q$ 保证落在 $[2^{130}-t_p-t_q,2^{131}-t_p-t_q)$ 内,因此对 $p$ 取模时既不会溢出也不会下溢;
• 利用 $k=\alpha +t_q(\mathrm{mod}p)$ 这一事实,观察到 $(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$。

(我们可以用另一种方式看出这是正确的:观察到它检查的是 $\alpha \mathrm{mod}p\in [p-2^{130},p)$,所以上界如我们所预期地对齐。)

现在,我们可以从 $Ⓐ$ 继续优化:

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

把 ${\mathbf{k}}_{\mathrm{253..130}}$ 约束为全 $0$ 或非全 $0$,几乎可以"免费"实现,方法如下。

回想 ${\mathbf{z}}_i={\sum }_{h=i}^n({\mathbf{k}}_h\cdot 2^{h-i})$,所以我们有:

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

所以 ${\mathbf{k}}_{\mathrm{253..130}}$ 全为 $0$ 当且仅当 ${\mathbf{z}}_{130}={\mathbf{k}}_{254}\cdot 2^{124}$。

最后,我们可以通过检查 $(\alpha +{\mathbf{k}}_{254}\cdot 2^{130})\mathrm{mod}p\in [0,2^{130})$,把 ${\mathbf{k}}_{254}=0$ 和 ${\mathbf{k}}_{254}=1$ 两种情形的 $130$ 位分解合并起来。

溢出检查约束(Overflow check constraints)

设 $s=\alpha +{\mathbf{k}}_{254}\cdot 2^{130}$。溢出检查的约束为:

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

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

见证 $\eta =inv0({\mathbf{z}}_{130})$,并把 $s\mathrm{mod}p$ 分解为 ${\mathbf{s}}_{\mathrm{129..0}}$。

那么所需的门(gate)为:

$$\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}$$ 其中 $(s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}$ 可以由另一个移动求和计算得到。注意 $1/2^{130}$ 这个因子对约束没有影响,因为右边为零。

移动求和范围检查(Running sum range check)

我们在电路中利用一个 $10$ 位查找范围检查(lookup range check)来减去 $\mathbf{s}$ 的低 $130$ 位。该范围检查减去 $\mathbf{s}$ 的前 $13\cdot 10$ 位,并把结果右移,得到 $(s-\sum _{i=0}^{129}{2}^i\cdot {\mathbf{s}}_i)/2^{130}.$

溢出检查(通用版)(Overflow check (general))

回想我们定义了 ${\mathbf{z}}_j={\sum }_{i=j}^n({\mathbf{k}}_i\cdot 2^{i-j})$,其中 $n=254$。

对于任何 $j\ge 1$,${\mathbf{z}}_j$ 都不会溢出,因为它是仅到并包括 $2^{n-j}$ 为止的若干位的加权求和。当 $n=254$ 且 $j=1$ 时,此求和至多为 $2^{254}-1$,小于 $p$(也小于 $q$)。

然而,对于全宽标量乘,可能无法在基域中表示 ${\mathbf{z}}_0$(例如当基域是 Pasta 的 ${\mathbb{F}}_p$ 且 $p<q$ 时)。在这种情况下,${\mathbf{z}}_0=\alpha +t_q$ 可能会溢出 $[0,p)$。

所以,我们需要对涉及 ${\mathbf{z}}_0$ 的那一行进行特殊处理,使其对于我们用于全宽标量的任何表示都是正确的。

我们对 $k$ 的表示将是这个对:$({\mathbf{k}}_{254},k^{\prime }=k-2^{254}\cdot {\mathbf{k}}_{254})$。我们将用 $k^{\prime }$ 代替 $\alpha +t_q$ 作为 ${\mathbf{z}}_0$,并把 $k^{\prime }$ 约束到 254 位,使它能放入一个 ${\mathbb{F}}_p$ 元素。

然后我们只需把 Orchard 电路中变基标量乘所使用的溢出检查 推广到适用于 $k^{\prime }\in [0,2\cdot t_q)$(因为 $\alpha +t_q$ 的最大值是 $q-1+t_q=2^{254}+t_q-1+t_q$)。

注:位 ${\mathbf{k}}_{\mathrm{254..0}}$ 并不表示一个对 $q$ 取模归约后的值,而是表示未归约的 $\alpha +t_q$ 的一个表示。

溢出只可能发生在约束 ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1+{\mathbf{k}}_0$ 的最后一步,并且只有在 ${\mathbf{z}}_1$ 设置了权重为 $2^{253}$ 的那一位时(即 ${\mathbf{k}}_{254}=1$ 时)才会发生。如果我们改为设置 ${\mathbf{z}}_0=2\cdot {\mathbf{z}}_1-2^{254}\cdot {\mathbf{k}}_{254}+{\mathbf{k}}_0$,那么现在 ${\mathbf{z}}_0$ 就不会溢出,并且应当等于 $k^{\prime }$。

那么只需再检查 ${\mathbf{z}}_0+2^{254}\cdot {\mathbf{k}}_{254}=\alpha +t_q$ 作为整数成立(其中 $\alpha \in [0,q)$)即可。

把 $\alpha$ 表示为 $2^{254}\cdot {\mathbf{\alpha }}_{254}+2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$,其中我们约束 ${\alpha }^{\prime \prime }\in [0,2^{253})$,并约束 ${\mathbf{\alpha }}_{253}$ 和 ${\mathbf{\alpha }}_{254}$ 为布尔值。为使这是一个规范表示,我们还需要 ${\mathbf{\alpha }}_{254}=1⟹({\mathbf{\alpha }}_{253}=0\wedge {\alpha }^{\prime \prime }\in [0,t_q))$。

设 ${\alpha }^{\prime }=2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$。

如果 ${\mathbf{\alpha }}_{254}=1$:

• 约束 ${\mathbf{k}}_{254}=1$ 且 ${\mathbf{z}}_0={\alpha }^{\prime }+t_q$。这不会溢出,因为在这种情况下 ${\alpha }^{\prime }\in [0,t_q)$,因此 ${\mathbf{z}}_0\in [0,2\cdot t_q)$。

如果 ${\mathbf{\alpha }}_{254}=0$:

• 我们应当在 ${\alpha }^{\prime }\in [2^{254}-t_q,2^{254})$ 时且仅在此时有 ${\mathbf{k}}_{254}=1$,即把 ${\mathbf{k}}_{254}$ 见证为布尔值,然后
  • 如果 ${\mathbf{k}}_{254}=0$,则约束 ${\alpha }^{\prime }\notin [2^{254}-t_q,2^{254})$。
    • 这可以通过约束 ${\mathbf{\alpha }}_{253}=0$ 或 ${\alpha }^{\prime \prime }+t_q\in [0,2^{253})$ 二者之一来完成。(${\alpha }^{\prime \prime }+t_q$ 不会溢出。)
  • 如果 ${\mathbf{k}}_{254}=1$,则约束 ${\alpha }^{\prime }\in [2^{254}-t_q,2^{254})$。
    • 这可以通过约束 ${\alpha }^{\prime }-(2^{254}-t_q)\in [0,2^{130})$ 和 ${\alpha }^{\prime }-2^{254}+2^{130}\in [0,2^{130})$ 来完成。

溢出检查约束(通用版)(Overflow check constraints (general))

如上把 $\alpha$ 表示为 $2^{254}\cdot {\mathbf{\alpha }}_{254}+2^{253}\cdot {\mathbf{\alpha }}_{253}+{\alpha }^{\prime \prime }$。

溢出检查的约束为:

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

注意标记为 $❁$ 的四个 130 位约束分成两对,出现在不相交(disjoint)的情形中。因此我们可以用一个新的见证变量 $u$ 把它们合并为两个 130 位约束;另一个约束始终是对 $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$ 是无约束的,在 ${\mathbf{\alpha }}_{254}=0\wedge {\mathbf{k}}_{254}=0$ 的情况下可以见证为 $0$。)

成本(Cost)

• 25 次 10 位范围检查和一次 3 位范围检查,用于把 ${\alpha }^{\prime \prime }$ 约束到 253 位;
• 25 次 10 位范围检查和一次 3 位范围检查,用于在 ${\mathbf{\alpha }}_{254}=0\wedge {\mathbf{\alpha }}_{253}=1\wedge {\mathbf{k}}_{254}=0$ 时把 ${\alpha }^{\prime \prime }+t_q$ 约束到 253 位;
• 两次 13 个 10 位范围检查。