## 论文速递 ### 文章信息 - **题目**：Fast elliptic curve scalar multiplications in SN(T)ARK circuits - **作者**：Liam Eagen, Youssef El Housni, Simon Masson, Thomas Piellard - **关键词**：SNARK, STARK, 椭圆曲线, 标量乘法, 格约简, 扩展欧几里得算法 ### 摘要 该文针对 SNARK/STARK 等零知识证明系统中，椭圆曲线标量乘法电路证明效率低的问题，提出了两种基于整数格约简和复数域（半）扩展欧几里得算法的标量分解技术。作者在不同曲线（含小判别与通用）和两种主流电路模型（Groth16、PLONK）下实现优化，实验结果显示证明时间相比现有方法提升了 22%–53%。 ### 核心贡献 1. **格约简分解方法** 利用整数格在 $\mathbb{Z}$ 中对给定 $n$ 位标量 $k$ 和提示点 $Q=[k]P$ 进行分解，将原本的 $n$ 位标量乘法 $ [k]P \;\stackrel{?}{=}\; Q $ 转化为一次 $n/2$ 位的双标量乘法 $ [k_1]P - [k_2]Q \;\stackrel{?}{=}\; 0_E. $ 2. **复数域扩展欧几里得算法** 在具有复整数环结构（如 Eisenstein 整数）的曲线上，使用半扩展欧几里得算法进行有理重构，可将 $n$ 位乘法转化为 $n/4$ 位的四重标量乘法，在不依赖额外 hint 的场景下加速 witness 生成。 3. **通用与多标量乘法推广** 即便在无高效本源映射的通用曲线上，仍可应用整数格方法进行分解，并推广至多标量乘法场景（如多公钥签名验证）。 4. **Golang + gnark 实现** 提供了对多条曲线和两种证明系统的优化电路实现，实测在 Groth16 和 PLONK 下均取得显著加速。 ### 技术细节 - **电路代数化**：传统 $n$ 位标量乘法需执行 $ (N-1)\,\text{Add} + (N-1)\,\text{Dbl} $ 优化后主要执行一次半位宽多标量乘法，显著减少乘法门数量。 - **格约简**：构造四维格，求解 $ x + \lambda y - k(z + \lambda t) \equiv 0 \pmod r $ 的最短向量，得到子标量 $(k_1,k_2)$。 - **本源映射**：小判别曲线利用高效映射 $\psi(P)=[\lambda]P$，减少点加次数。 - **复数域重构**：在 $O$ 中执行有理重构，以换取更少的证明阶段门数。 ### 实验结果 | 曲线类型 | Groth16 加速 | PLONK 加速 | | -------------- | ------------ | ---------- | | 仿真小判别 | 24% | 42% | | 仿真通用 | 52% | 50% | | 原生小判别 | 48% | 53% | | 原生通用 | 22% | 28% | ### 结论与展望 本文所提分解技术既兼容多种零知识证明框架，又能显著降低椭圆曲线标量乘法的证明开销，为区块链大规模应用中的电路优化提供新思路。后续可进一步探索递归证明下的多层压缩、其他代数域的分解策略及与循环证明结合的可能性。