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

定基标量乘(Fixed-base scalar multiplication)

Orchard 协议中有 $6$ 个定基(fixed base):

• ${\mathcal{K}}^{\mathsf{Orchard}}$,用于推导 nullifier;
• ${\mathcal{G}}^{\mathsf{Orchard}}$,用于 spend authorization(花费授权);
• $\mathcal{R}$ 基,用于 ${\mathsf{NoteCommit}}^{\mathsf{Orchard}}$;
• $\mathcal{V}$ 和 $\mathcal{R}$ 基,用于 ${\mathsf{ValueCommit}}^{\mathsf{Orchard}}$;以及
• $\mathcal{R}$ 基,用于 ${\mathsf{Commit}}^{\mathsf{ivk}}$。

分解标量(Decompose scalar)

我们支持三种类型标量(scalar)的定基标量乘:

全宽标量(Full-width scalar)

一个来自 ${\mathbb{F}}_q$ 的 $255$ 位标量。我们把一个全宽标量 $\alpha$ 分解为 $85$ 个 $3$ 位窗口(window):

$$\alpha =k_0+k_1\cdot (2^3{)}^1+\cdots +k_{84}\cdot (2^3{)}^{84},k_i\in [\mathrm{0..}{2}^3).$$

对于表示 $[0,2^{255})$ 范围内任意整数的 $k_{\mathrm{0..84}}$,标量乘都将被正确计算——也就是说,允许标量是非规范(non-canonical)的。

我们使用一个多项式范围检查约束(polynomial range-check constraint)对标量分解的每个 $3$ 位字(word)进行范围约束: $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 9& q_{\text{mul\_fixed\_full}}\cdot \text{range\_check}(\text{word},2^3)=0\end{array}$$ 其中 $\text{range\_check}(\text{word},\text{range})=\text{word}\cdot (1-\text{word})\cdots (\text{range}-1-\text{word}).$

基域元素(Base field element)

我们支持使用一个基域元素(base field element)作为定基乘法中的标量。例如,这出现在 Action 电路 nullifier 计算的标量乘中:$\mathsf{DeriveNullifie}{\mathsf{r}}_{\mathsf{nk}}={\mathsf{Extract}}_{\mathbb{P}}\left(\left[(\mathsf{PR}{\mathsf{F}}_{\mathsf{nk}}^{\mathsf{nfOrchard}}(\rho )+\psi )\mathrm{mod}{q}_{\mathbb{P}}\right]{\mathcal{K}}^{\mathsf{Orchard}}+\mathsf{cm}\right)$:这里,标量 $$\left[(\mathsf{PR}{\mathsf{F}}_{\mathsf{nk}}^{\mathsf{nfOrchard}}(\rho )+\psi )\mathrm{mod}{q}_{\mathbb{P}}\right]$$ 是一次基域加法的结果。

把基域元素 $\alpha$ 分解为三位窗口,并对每个窗口进行范围约束,使用严格模式(strict mode)下的短范围分解(short range decomposition) gadget,其中 $W=85,K=3.$

如果 $k_{\mathrm{0..84}}$ 是直接见证的,那么不会出现规范性(canonicity)问题。然而,因为这里标量是作为一个基域元素给出的,必须谨慎确保规范表示,因为 $2^{255}>p$。也就是说,我们必须检查 $0\le \alpha <p,$ 其中 $p$ 是 Pallas 基域模数 $$p=2^{254}+t_p=2^{254}+45560315531419706090280762371685220353.$$ 注意 $t_p<2^{130}.$

为此,我们把 $\alpha$ 分解为三段:$$\alpha ={\alpha }_0\text{ (252 bits) }||{\alpha }_1\text{ (2 bits) }||{\alpha }_2\text{ (1 bit) }.$$

我们通过以下方式检查此分解的正确性: $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 5& q_{\text{canon-base-field}}\cdot \text{range\_check}({\alpha }_1,2^2)=0\\ 3& q_{\text{canon-base-field}}\cdot \text{bool\_check}({\alpha }_2)=0\\ 2& q_{\text{canon-base-field}}\cdot \left(z_{84}-({\alpha }_1+{\alpha }_2\cdot 2^2)\right)=0\end{array}$$ 如果最高有效位(MSB)${\alpha }_2=0$ 未被置位,那么 $\alpha <2^{254}<p.$ 然而,在 ${\alpha }_2=1$ 的情况下,我们必须检查:

• ${\alpha }_2=1⟹{\alpha }_1=0;$
• ${\alpha }_2=1⟹{\alpha }_0<t_p$:
  • ${\alpha }_2=1⟹0\le {\alpha }_0<2^{130}$,
  • ${\alpha }_2=1⟹0\le {\alpha }_0+2^{130}-t_p<2^{130}$

为了检查 $0\le {\alpha }_0<2^{130},$ 我们利用三位移动求和(running sum)分解:

• 首先,我们通过强制 ${\alpha }_0$ 的高 $120$ 位全为零,把 ${\alpha }_0$ 约束为一个 $132$ 位值。我们可以从分解中得到 $\text{alpha\_0\_hi\_120}$: $$\begin{array}{rl}{z}_{44}& =k_{44}+2^3{k}_{45}+\cdots +2^{3\cdot (84-44)}{k}_{84}\\ ⟹\text{alpha\_0\_hi\_120}& =z_{44}-2^{3\cdot (84-44)}{k}_{84}\\ & =z_{44}-2^{3\cdot (40)}{z}_{84}.\end{array}$$
• 然后,我们约束 ${\alpha }_0$ 的第 $\mathrm{130..}=131$ 位为零;换句话说,我们约束三位字 $k_{43}=\alpha [\mathrm{129..}=131]={\alpha }_0[\mathrm{129..}=131]\in \{0,1\}.$ 我们利用移动求和分解来得到 $k_{43}=z_{43}-z_{44}\cdot 2^3.$

定义 ${\alpha }_0^{\prime }={\alpha }_0+2^{130}-t_p$。为了检查 $0\le {\alpha }_0^{\prime }<2^{130},$ 我们使用 13 个十位查找(lookups),在其中我们约束查找的 $z_{13}$ 移动求和输出在 ${\alpha }_2=1$ 时为 $0.$ $$\begin{array}{cll}\text{Degree}& \text{Constraint}& \text{Comment}\\ 2& q_{\text{canon-base-field}}\cdot ({\alpha }_0^{\prime }-({\alpha }_0+2^{130}-t_{\mathbb{P}}))=0& \\ 3& q_{\text{canon-base-field}}\cdot {\alpha }_2\cdot {\alpha }_1=0& {\alpha }_2=1⟹{\alpha }_1=0\\ 3& q_{\text{canon-base-field}}\cdot {\alpha }_2\cdot \text{alpha\_0\_hi\_120}=0& \text{Constrain α0 to be a 132-bit value}\\ 4& q_{\text{canon-base-field}}\cdot {\alpha }_2\cdot \text{bool\_check}(k_{43})=0& \text{Constrain α0[130..=131] to 0}\\ 3& q_{\text{canon-base-field}}\cdot {\alpha }_2\cdot z_{13}(\text{lookup}({\alpha }_0^{\prime },13))=0& {\alpha }_2=1⟹0\le {\alpha }_0^{\prime }<2^{130}\end{array}$$

短有符号标量(Short signed scalar)

一个短有符号标量被见证为一个幅值(magnitude)$m$ 和一个符号(sign)$s$,使得 $$\begin{gathered} s\in \{-1,1\} \\ m\in [0,2^{64}) \\ {\mathsf{v}}^{\mathsf{old}}-{\mathsf{v}}^{\mathsf{new}}=s\cdot m. \end{gathered}$$

这用于 $\mathsf{ValueCommi}{\mathsf{t}}^{\mathsf{Orchard}}$。我们想要计算 $\mathsf{ValueCommi}{\mathsf{t}}_{\mathsf{rcv}}^{\mathsf{Orchard}}({\mathsf{v}}^{\mathsf{old}}-{\mathsf{v}}^{\mathsf{new}})=[{\mathsf{v}}^{\mathsf{old}}-{\mathsf{v}}^{\mathsf{new}}]\mathcal{V}+[\mathsf{rcv}]\mathcal{R}$,其中 $$-(2^{64}-1)\le {\mathsf{v}}^{\mathsf{old}}-{\mathsf{v}}^{\mathsf{new}}\le 2^{64}-1$$

${\mathsf{v}}^{\mathsf{old}}$ 和 ${\mathsf{v}}^{\mathsf{new}}$ 各自已经被约束到 $64$ 位(由于它们被用作 $\mathsf{NoteCommi}{\mathsf{t}}^{\mathsf{Orchard}}$ 的输入)。

把幅值 $m$ 分解为三位窗口,并对每个窗口进行范围约束,使用严格模式下的短范围分解(short range decomposition) gadget,其中 $W=22,K=3.$

我们有两个额外的约束: $$\begin{array}{cll}\text{Degree}& \text{Constraint}& \text{Comment}\\ 3& q_{\text{mul\_fixed\_short}}\cdot \text{bool\_check}(k_{21})=0& \text{The last window must be a single bit.}\\ 3& q_{\text{mul\_fixed\_short}}\cdot \left(s^2-1\right)=0& \text{The sign must be 1 or −1.}\end{array}$$ 其中 $\text{bool\_check}(x)=x\cdot (1-x)$。

加载定基(Load fixed base)

然后,我们为每个窗口预计算定基 $B$ 的若干倍数。这采取窗口表(window table)的形式:$M[\mathrm{0..}W)[\mathrm{0..8})$,使得:

• 对于前 (W-1) 行 $M[\mathrm{0..}(W-1))[\mathrm{0..8})$:$$M[w][k]=[(k+2)\cdot (2^3{)}^w]B$$
• 在最后一行 $M[W-1][\mathrm{0..8})$:$$M[w][k]=[k\cdot (2^3{)}^w-\sum _{j=0}^{83}{2}^{3j+1}]B$$

额外的 $(k+2)$ 项让我们在 $k=0$ 的情况下避免加上无穷远点(point at infinity)。我们通过在最后一个窗口中减去这些累加项来抵消它们,即我们减去 $\sum _{j=0}^{W-2}{2}^{3j+1}$。

注:虽然 $(k+1)$ 的偏移量朴素地看似乎就足够了,但它会在 $k_0=7,k_1=0$ 时引入一个边界情形(edge case)。 在这种情况下,窗口表项求值为同一个点:

• $M[0][k_0]=[(7+1)\ast (2^3{)}^0]B=[8]B,$
• $M[1][k_1]=[(0+1)\ast (2^3{)}^1]B=[8]B.$

在定基标量乘中,我们使用不完全加法(incomplete addition)对每个窗口(除最后一个之外)的 $B$ 的倍数求和。 由于倍点(point doubling)情形不被不完全加法处理,我们通过使用 $(k+2)$ 的偏移量来避免它。

对于每个定基倍数窗口 $M[w]=(M[w][0],\cdots ,M[w][7]),w\in [\mathrm{0..}(W-1))$:

• 定义一个 Lagrange 插值多项式(interpolation polynomial)${\mathcal{L}}_x(k)$,它把 $k\in [\mathrm{0..8})$ 映射到倍数 $M[w][k]$ 的 $x$ 坐标,即 $${\mathcal{L}}_x(k)=\{\begin{array}{ll}([(k+2)\cdot (2^3{)}^w]B{)}_x& \text{for }w\in [\mathrm{0..}(W-1));\\ ([k\cdot (2^3{)}^w-\sum _{j=0}^{83}{2}^{3j+1}]B{)}_x& \text{for }w=84;\text{ and}\end{array}$$
• 找到一个值 $z_w$,使得 $z_w+(M[w][k]{)}_y$ 在域中是一个平方数 $u^2$,但错误符号的 $y$ 坐标 $z_w-(M[w][k]{)}_y$ 不产生平方数。

对全部 $W$ 个窗口重复此操作,我们最终得到:

• 一个 $W\times 8$ 的表 ${\mathcal{L}}_x$,为每个窗口存储 $8$ 个对 $x$ 坐标进行插值的系数。每个 $x$ 坐标插值多项式将具有如下形式 $${\mathcal{L}}_x[w](k)=c_0+c_1\cdot k+c_2\cdot k^2+\cdots +c_7\cdot k^7,$$ 其中 $k\in [\mathrm{0..8}),w\in [\mathrm{0..85})$,且 $c_k$ 是 $k$ 各次幂的系数;以及
• 一个长度为 $W$ 的数组 $Z$,存储各个 $z_w$。

每当我们在电路中进行定基标量乘时,就把这些预计算值加载到固定列(fixed columns)中。

定基标量乘(Fixed-base scalar multiplication)

给定一个分解后的标量 $\alpha$ 和一个定基 $B$,我们如下计算 $[\alpha ]B$:

1. 对于标量分解中的每个 $k_w,w\in [\mathrm{0..85}),k_w\in [\mathrm{0..8})$,见证 $x$ 坐标和 $y$ 坐标 $(x_w,y_w)=M[w][k_w].$
2. 检查 $(x_w,y_w)$ 在曲线上:$y_w^2=x_w^3+b$。
3. 见证 $u_w$,使得 $y_w+z_w=u_w^2$。
4. 对于除最后一个之外的所有窗口,使用不完全加法(incomplete addition)对各个 $M[w][k_w]$ 求和,得到 $[\alpha -k_{84}\cdot (2^3{)}^{84}+\sum _{j=0}^{83}{2}^{3j+1}]B$。
5. 对于最后一个窗口,使用完全加法(complete addition)$M[83][k_{83}]+M[84][k_{84}]$ 并返回最终结果。

注:最后一步需要完全加法,以便正确地把 $[0]B$ 映射到无穷远点的表示 $(0,0)$;并且也用于处理最后一步是倍点的一个极端情形(corner case)。

约束(Constraints): $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 8& q_{\text{mul-fixed}}\cdot \left({\mathcal{L}}_x[w](k_w)-x_w\right)=0\\ 4& q_{\text{mul-fixed}}\cdot \left(y_w^2-x_w^3-b\right)=0\\ 3& q_{\text{mul-fixed}}\cdot \left(u_w^2-y_w-Z[w]\right)=0\end{array}$$

其中 $b=5$(来自 Pallas 曲线方程)。

有符号短指数(Signed short exponent)

回想一下,有符号短指数被见证为一个 $64$ 位幅值 $m$ 和一个符号 $s\in 1,-1.$ 使用上述算法,我们计算 $P=[m]\mathcal{B}$。然后,为了得到最终结果 $P^{\prime },$ 我们使用 $(x,y)\mapsto (x,s\cdot y)$ 对 $P$ 进行条件取负(conditionally negate)。

约束(Constraints): $$\begin{array}{cl}\text{Degree}& \text{Constraint}\\ 3& q_{\text{mul\_fixed\_short}}\cdot \left(P_y^{\prime }-P_y\right)\cdot \left(P_y^{\prime }+P_y\right)=0\\ 3& q_{\text{mul\_fixed\_short}}\cdot \left(s\cdot P_y^{\prime }-P_y\right)=0\end{array}$$

布局(Layout)

$$\begin{array}{cccccccc}{x}_P& y_P& x_{QR}& y_{QR}& u& \text{window}& L_{\mathrm{0..}=7}& \text{fixed\_z}\\ x_{P,0}& y_{P,0}& & & u_0& {\text{window}}_0& L_{\mathrm{0..}=7,0}& {\text{fixed\_z}}_0\\ x_{P,1}& y_{P,1}& x_{Q,1}=x_{P,0}& y_{Q,1}=y_{P,0}& u_1& {\text{window}}_1& L_{\mathrm{0..}=7,1}& {\text{fixed\_z}}_1\\ x_{P,2}& y_{P,2}& x_{Q,2}=x_{R,1}& y_{Q,2}=y_{R,1}& u_2& {\text{window}}_2& L_{\mathrm{0..}=7,1}& {\text{fixed\_z}}_2\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮\end{array}$$

注:这不包括使用完全加法(complete addition)的最后一行。在实现中这是在一个不同的 region 中分配的。