_____ _ ____ _ __ __ | ___ | _ _ | | _____ / ___ | | \ \ / / | | _ / _` | |/ / _ \ | | _| | \ \ / /| _| (_| | < __/ | |_| | |__\ V /|_| \__,_|_|\_\___| \____|_____\_/

在 SNARK 电路中，不需要高效的自同态来实现类似 GLV 的标量乘法

• 介绍
  • 其他应用
• 背景
• 假冒 GLV 伎俩
  • 执行
    • 基准
    • 比较

介绍

P-256，也称为 secp256r1 和 prime256v1，是 NIST 标准化的 256 位素数域 Weierstrass 曲线。它在互联网系统中被广泛采用，这解释了它在 TLS、DNSSEC、Apple 的安全区域、Passkeys、Android Keystore 和 Yubikey 等平台中的大量用例。基于椭圆曲线的密码学中的关键运算是标量乘法。当曲线配备有效的自同态时，可以通过众所周知的GLV算法加速此运算。不幸的是，P-256 没有有效的自同态（参见参数）来享受这种加速。

通过预编译合约（即以太坊协议内置的智能合约（只有 9 个））验证以太坊上的 ECDSA 签名只能使用secp256k1曲线，而不能使用 P-256。
验证 P-256 上的 ECDSA 签名需要在 Solidity 中计算标量乘法，这对于智能合约钱包尤其有用，可实现基于硬件的签名密钥以及更安全、更轻松的自我保管。不同的解决方案可以将 P-256 签名带上链。主要有三种有趣的方法：基于 (zk)-SNARK 的验证器、智能合约验证器（例如[Dubois23] 、 Ledger/FCL （已弃用）、 smoo.th/SCL和daimo/p256verifier ）和本机协议预编译（ EIP/RIP 7212 ）。

使用 SNARK（简洁性）属性，可以很好地降低以太坊上计算的 gas 成本（例如Groth16需要 ~232k gas， PLONK需要 ~285k gas， FFLONK需要 ~185k gas）。这与当前 gas 最优的智能合约验证器相比非常有竞争力（有时甚至更好）。此外，可以在一个证明中批量处理许多 ECDSA 验证，从而摊销 gas 成本。但是在 SNARK 电路中验证 P-256 签名可能非常昂贵，即证明时间很长。这是因为 P-256 曲线上的点所在的字段与通常表达 SNARK 计算的字段不同。为了能够通过 procompile 在链上验证证明，SNARK 字段需要是BN254标量场。不同的团队尝试在 BN254 SNARK 电路中有效地实现 P-256 上的 ECDSA 验证。其中包括： zkwebauthn/webauthn-halo2 、 https://github.com/zkwebauthn/webauthn-circom和PSE/circom-ecdsa-p256 。

如果 P-256 具有有效的自同态，我们就可以大大优化证明时间！

在本文中，我们展示了一种无需有效自同态即可在电路中实现类似 GLV 的标量乘法的方法。

其他应用

• 该技术可应用于任何不具有有效自同态的椭圆曲线（例如Curve25519 、 P-384 、MNT-753（ k=4 、 k=6 ）、 STARK 曲线、 “cycle5” 的\mathcal{B} B ，……）。有关其他曲线，请参阅此数据库。
• 这将对以太坊 Verkle 树选择Bandersnatch （ BLS12-381 上嵌入的具有自同态性的曲线）还是Jubjub （ BLS12-381 上嵌入的不具有自同态性的曲线）产生质疑。
• 这可以加速Starknet和Cairo中的 ECDSA 验证（通过STARK 曲线）。
• 这可以通过 Aurore Guillevic提出的 2 循环原生加速 Ed25519 签名的折叠步骤（à la Nova）。

背景

标准标量乘法

令E E为定义在素数域\mathbb{F}_p F p上的椭圆曲线，令r r为曲线阶为\#E(\mathbb{F}_p) # E ( F p )的素因数（即点的数量）。
令s \in \mathbb{F}_r s ∈ F r且P(x,y) \in E(\mathbb{F}_p) P ( x , y ) ∈ E ( F p ) ，我们感兴趣的是证明E E的r r -扭转子群上的标量乘法s\cdot P s ⋅ P ，记为E[r] E [ r ] （即r r阶点的子集）。

最简单的算法是标准的从左到右双重添加：

 INPUT : s = (s_{t− 1 },..., s_1, s_0), P ∈ E(Fp).OUTPUT: sP. 1 . Q ← ∞. 2 . For i from t− 1 downto 0 do 2.1 Q ← 2 Q. 2.2 If s_i = 1 then Q ← Q + P. 3 . Return (Q).

SNARK 电路中无法进行 if/else 分支，因此它被电路内部的常量窗口表查找所取代。这可以使用在未被选择的常数处消失的多项式来实现，即 1 位表查找Q ← s_i * Q + (1 - s_i) * (Q+P) 。因此，这种加倍和加法算法需要t t次加倍、 t t次加法和t t次 1 位表查找。
这可以扩展到窗口加倍并加法，即使用更大的窗口表每次迭代扫描超过一位，但评估的乘法深度呈指数增加。我们使用仿射坐标来加倍/加点，因为逆运算和乘法一样耗费大量资源，即，我们不是检查1/x 1 / x是否为y y，而是在外部电路提供y y并在内部电路检查x\cdot y = 1 x ⋅ y = 1 。但是由于我们从Q ← ∞ Q ← ∞开始，因此不可能避免条件分支，因为仿射公式是不完整的。相反，我们从右到左扫描位并假设第一位s_0为 1（因此我们从Q ← P开始），在这个算法中，我们将输入点P而不是累加器Q加倍，最后如果s_0为 0，则有条件地减去（使用 1 位查找） P 。

 INPUT : s = (s_{t− 1 },..., s_1, s_0), P ∈ E(Fp).OUTPUT: sP. 1 . Q ← P. 2 . For i from 1 to t− 1 do 2.1 If s_i = 1 then Q ← Q + P. 2.2 P ← 2 P. 3 . if s_0 = 0 then Q ← Q - P 4 . Return (Q).

GLV 标量乘法

然而众所周知，如果曲线具有有效的自同态，那么存在一种更快的算法，称为[GLV] 。

例 1：假设E E具有复数乘法（CM），其判别式为-D=-3 − D = − 3 ，即E E的形式为y^2=x^3+b y 2 = x 3 + b ，其中b \in \mathbb{F}_p b ∈ F p 。这是以太坊中使用的BN254 、 BLS12-381和secp256k1椭圆曲线的情况。存在一个有效自同态\phi: E \rightarrow E ϕ : E → E ，由(x,y)\mapsto (\omega x,y) ( x , y ) ↦ ( ω x , y ) （和\mathcal{O} \mapsto \mathcal{O} O ↦ O ）定义，它作用于P \in E[r] P ∈ E [ r ]，当\phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P时。 \omega ω和\lambda λ分别是\mathbb{F}_p F p和\mathbb{F}_r F r中的单位立方根，即\omega^2+\omega+1 \equiv 0 \pmod p ω 2 + ω + 1 ≡ 0 （模式p )和\lambda^2+\lambda+1 \equiv 0 \pmod r λ 2 + λ + 1 ≡ 0 （模式又） 。

示例 2：假设E E具有复数乘法 (CM)，其判别式为-D=-8 − D = − 8 ，这意味着自同态环为\mathbf{Z}[\sqrt{−2}] Z [ √ − 2 ] 。这是以太坊 Verkle trie 中指定的Bandersnatch椭圆曲线的情况。存在一个有效的自同态\phi: E \rightarrow E ϕ : E → E ，其核由 2 扭转点生成。可以通过查看 2 同质曲线并应用 Vélu 公式来找到该映射。对于 Bandersnatch，它定义为(x,y)\mapsto (u^2\cdot \frac{x^2+wx+t}{x+w},u^3\cdot y\cdot \frac{x^2+2wx+v}{(x+w)^2}) ( x , y ) ↦ ( u 2 ⋅ x 2 + w x + t x + w ， u3⋅y⋅x2 + 2wx + v ( x + w ) 2​ ​​​​​​​ )其中某些常数u,v,w,t u , v , w , t （以及\mathcal{O} \mapsto \mathcal{O} O ↦ O ）作用于P \in E[r] P ∈ E [ r ] ，且\phi(P)=\lambda \cdot P ϕ ( P ) = λ ⋅ P其中\lambda^2+2 \equiv 0 \pmod r λ 2 + 2 ≡ 0 （模式又） 。

GLV 算法首先将s s分解为s = s_0 + \lambda s_1 s = s 0 + λ s 1 ，然后将标量乘法s \cdot P s ⋅ P替换为s_0 \cdot P + s_1 \cdot \phi(P) s 0 ⋅ P + s 1 ⋅ ϕ ( P ) 。由于s_0 s 0和s_1 s 1保证为\leq \sqrt{r} ≤ √ r （有关优化技巧，请参阅[GLV]第 4 节和[FourQ]第 4 节），我们可以将加倍并加法算法中的 for 循环大小减半。然后，我们可以同时扫描s_0 s 0和s_1 s 1的位并应用Strauss-Shamir 技巧。这可以显著提高速度，但前提是存在自同态。例如，从左到右的双重相加将变成：

 INPUT: s and P ∈ E(Fp).OUTPUT: sP. 1. Find s1 and s2 st s = s1 + 𝜆 * s2 mod r 1.1 let s1 = (s1_{t− 1 },..., s1_1, s1_0) 1.2 and s2 = = (s2_{t− 1 },..., s2_1, s2_0) 2. P1 ← P, P2 ← 𝜙(P) and Q ← ∞. 3. For i from t− 1 downto 0 do 3.1 Q ← 2Q. 3.2 If s1_i = 0 and s2_i = 0 then Q ← Q. 3.3 If s1_i = 1 and s2_i = 0 then Q ← Q + P1. 3.4 If s1_i = 0 and s2_i = 1 then Q ← Q + P2. 3.5 If s1_i = 1 and s2_i = 1 then Q ← Q + P1 + P2. 4. Return(Q).

在电路中使用有效的自同态也是可能的（有关短 Weierstrass 曲线，请参阅[Halo，第 6.2 节和附录 C]或[gnark 实现] ，有关扭曲 Edwards 曲线，请参阅 [arkworks]和[gnark]实现）。但应注意分解s = s_0 + \lambda s_1 \mod r s = s 0 + λ s 1的一些额外检查模式r （不是 SNARK 模数）。整数s_0、s_1 s 0 、 s 1可能为负，在这种情况下，它们将在电路中以 SNARK 字段为模减少，而不是r r 。

假冒 GLV 伎俩

请记住，我们正在证明s\cdot P = Q s ⋅ P = Q而不是计算它。我们可以“提示”结果Q Q并在电路中检查s\cdot P - Q = \mathcal{O} s ⋅ P − Q = O 。现在，如果我们能找到u,v \leq \sqrt{r} u , v ≤ √ r使得v\cdot s = u \pmod r v ⋅ s = u （模式r ）那么我们可以检查一下

(v\cdot s)\cdot P - v\cdot Q = \mathcal{O} ( v ⋅ s ) ⋅ P − v ⋅ Q = O

相当于

u\cdot P - v\cdot Q = \mathcal{O} u ⋅ P − v ⋅ Q = O

现在的情况是u u和v v很“小”，我们可以类似 GLV 算法，将加倍并相加循环的大小减半，并应用 Strauss-Shamir 技巧。

解决方案：运行半 GCD 算法（即运行 GCD 一半）足以找到u u和v v 。我们可以应用与 GLV 论文（第 4 节）中完全相同的技巧来查找格基。为了完整起见，我们以后会回顾该算法。
我们应用扩展的欧几里得算法来寻找r r和s s的最大公约数（由于r r为素数，因此该 gcd 为 1。）该算法生成一系列方程

w_i \cdot r + v_i \cdot s = u_i w i ⋅ r + v i ⋅ s = u i

对于i = 0, 1, 2, \dots i = 0 , 1 , 2 , …其中w_0 = 1, v_0 = 0, u_0 = r, w_1 = 0, v_1 = 1, u_1 = s w 0 = 1 , v 0 = 0 , u 0 = r , w 1 = 0 , v 1 = 1 , u 1 = s , 且对所有i i u_i \geq 0 u i ≥ 0 。我们在索引m m处停止，对于该索引，u_m \geq \sqrt{r} u m ≥ √ r并取u = u_{m+1} u = u m + 1和v = -v_{m+1} v = − v m + 1 。
注意：根据构造， u u保证为正整数，但v v可以为负数，在这种情况下，它将在电路中以 SNARK 模数而不是r r为模数进行缩减。为了避免这种情况，我们在提示中返回u u , v v and a \texttt{b}=1 b = 1 （如果v v为负），否则返回\texttt{b}=0 b = 0。在电路中，当\texttt{b}=1 b = 1时，我们对Q Q取反。

执行

gnark 库中的通用实现可在gnark.io (feat/fake-GLV 分支)中找到。对于 Short Weierstrass (例如 P256)，请查看模拟包中的scalarMulFakeGLV 方法；对于 twisted Edwards (例如 Bandersnatch/Jubjub)，请查看本机包中的scalarMulFakeGLV 方法。

基准

当无法获得有效的自同态时，在非原生电路（即电路场≠曲线场）中实现标量乘法的最佳算法是改编自[Joye07] （在此处的 gnark中实现）。
接下来，我们将此标量乘法与我们的假 GLV 在 PLONKish vanilla（即没有自定义门）电路（scs）中在 BN254 曲线（与以太坊兼容）上进行比较。我们还在 R1CS 中给出了基准。

请注意，旧的 ECDSA 验证使用 Strauss-Shamir 技巧来计算[s]P+[t]Q [ s ] P + [ t ] Q ，而新版本仅仅是两个伪 GLV 乘法和一个加法。

比较

p256wallet.org是一个 ERC-4337 智能合约钱包，利用 zk-SNARKs 进行 WebAuthn 和 P-256 签名验证。它使用PSE/circom-ecdsa-p256生成 webAuthn 证明，并在PSE/circom-ecdsa-p256下方生成 P-256 曲线上的 ECDSA 证明。github README 报告了1,972,905 R1CS 。在 R1CS 中编译我们的电路会产生195,266 R1CS 。这减少了10 倍以上，这不仅是由于伪造的 GLV 算法，还归功于 gnark 中优化的非原生字段算法。

其他曲线

对于短韦尔斯特拉斯中的其他曲线（例如 P-384 和 STARK 曲线）也观察到了类似的结果：

还有扭曲的 Edwards，例如 Jubjub vs. Bandersnatch：