_____ _ ____ _ __ __ | ___ | _ _ | | _____ / ___ | | \ \ / / | | _ / _` | |/ / _ \ | | _| | \ \ / /| _| (_| | < __/ | |_| | |__\ 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：