优化ECDSA签名验证：在Sei Giga区块链中探索零知识证明

随着 Sei Protocol 最近的 Giga 公告概述了在 EVM 上实现每秒 5 个 Giga 的路径，我们确定了几个关键的优化领域。在现有 Sei Giga 协议原型中，突出的一个瓶颈是签名恢复和验证的问题。我们想知道，考虑到必须保持 ECDSA 以与以太坊钱包兼容，我们能否使用 ZK 来解决这个瓶颈？我们是否能够让区块生产者恢复公钥，验证区块并提交证明，以便执行者只需验证一个证明，而不是 N 个签名？让我们首先在 Sei 区块链的上下文中定义 ECDSA 签名，使用 NIST [Che+23] 符号。

签名内容

曲线：secp256k1 在 Fp 上，p=2256−232−977。

生成器：G 的素数阶 n。

私钥：d{1,,n−1}。

公钥：Q=dG。

输入：消息 m，散列 z=Hash(m)modn，私钥 d。

输出：签名 ( r,s,v )。

签名

1. z=Hash(m)modn。
2. 随机选择 k{1,,n−1}。
3. R=kG=xR,yR。
4. r=xRmodn（如果 r=0，重试）。
5. s=k−1(z+rd)modn（如果 s=0，重试）。

v{27,28} 通常在以太坊中选择 yR 的符号。签名为 (r,s,v)。

恢复

给定 (r,s,v) 和 z。

1. 使用 v 构造 R=r,yR 以选择符号。
2. Q=r−1(sR−zG) mod n。
3. 通过验证 (r,s) 的正确性来检查。

验证

输入: m,Q,(r,s,v)。

目标: 检查 (r,s,v) 对于消息 m 的有效性。

1. z=Hash(m) mod n。
2. 检查 r,s{1,,n−1}。
3. w=s−1modn。
4. u1=(zw)modn, u2=(rw) mod n。
5. X=u1G+u2Q=xX,yX。

如果 xX mod n=r，则有效。

如果这让你感到困惑，可能值得阅读这篇关于 ECDSA 的非常好的介绍 [Cor15]，但理解它并不是阅读本文其余部分的必要条件。那么这一切对 Sei 网络来说意味着什么？是什么导致了问题？在 Sei 区块链中，像许多区块链一样，我们从签名中恢复公钥以用于验证，而不是将其与签名一起发送。

为什么要那样做？传统上，减少数据开销被视为明智之举，考虑到 ECDSA 签名为 65 字节，而公钥的压缩形式又是 33 字节，所以在所有交易中，最坏的情况下可以节省 33 字节的数据开销。而这种权衡的缺点是我们必须为每笔交易恢复公钥以便对此进行验证。于是我们回到了最初的问题：我们能否在 ZK 中更快地完成所有这些，然后让执行者验证一个证明，而不是多个签名？

尝试在 ZK 中做这种事情并不是全新的想法 [Sun+21, 0Da22, Per22b, Har24, mat19]，很多人之前对此表现出了很大的兴趣，但我们在这里并不需要一个独特的方法，只需要一个可行的方法。

在 ZK 中验签的方法有几种。我们可以像其他许多项目一样编写自定义电路（或者只是重用他们的工作），或者可以为 zkVM（例如 SP1 [suc24]）编写一些代码。编写自定义电路非常复杂，我们稍后会深入探讨。考虑到不需要太多开发时间，zkVM 方法感觉像一个简单的起点。zkVM 允许你编写或编译在专门的执行环境中运行的普通程序（例如，Rust 或 C 代码），并自动生成程序正确执行的证明。这可以显著减少开发复杂性，因为你不需要将每个加密细节自定义为约束条件。

然而，这种方法的缺点是，zkVM 可能会对非原生域的低级操作（如椭圆曲线算术）施加更高的开销，并且 zkVM 的通用性质可能导致与高度专业化、手工调优的电路相比，证明生成速度较慢。在几个小时内，我们用 Rust 编写了一个能够在几秒钟内验证签名并生成证明（只是验证而非恢复的证明）的工作原型。这个性能很不错，这充分表明了 zkVM 在未来是多么有用，但对我们来说仍然不足。这意味着如果有前进的方向，那就必须是使用自定义电路... 在我们讨论这个之前，先来简要了解 ZK 。

我们究竟是什么意思 ZK？零知识证明（ZK 证明）允许一方（证明者）向另一方（验证者）表明某个陈述是真实的，而不透露其如何真实或披露该陈述底层的敏感细节。正式来说，设 RXW 为一个二元关系，其中 X 是声明空间（例如，“这个 ECDSA 签名是有效的”），而 W 是见证者空间（例如，证明正确性所需的秘密数据）。在 LR 语言中，声明 xX 是合法的，当且仅当存在一个见证 wW，使得 (x,w)R。ZK 证明是在证明者 P（知道 w）和验证者 V 之间的协议，具有以下核心属性：

1. 完备性：如果 (x,w)R，那么诚实的证明者可以说服验证者 xLR。
2. 安全性：如果 (x,w)R，任何作弊的证明者都无法虚假地说服验证者 xLR。
3. 零知识：验证者除了知道 x LR 之外不会获得任何其他信息；特别是，他们不会获取关于秘密见证者 w 的任何额外信息。

在实践中，通常通过构造和验证代数约束（例如，关于群元素或多项式的约束）来实现，这些约束证明对 w 的知识，而不揭示它。

有多种 ZK 证明系统，每种都有自己的优点和权衡。SNARK（简洁非交互式知识论证），如 Groth16 或 Plonk，通常具有极小的证明体积和快速的验证时间，但可能需要可信的设置，并且在为大型电路生成证明时可能相对昂贵。STARK（可扩展透明知识论证）消除了对可信设置的需求，并且通常被认为更透明，但其证明体积可能更大，验证有时可能更慢，尽管如基于 FRI 的构造等进展正在缩小这个差距。Bulletproofs 是另一种不需要可信设置的替代方案，通常适用于区间证明；然而，在大规模计算时，Bulletproofs 的验证速度可能较慢。

选择适合在高吞吐量环境中验 ECDSA 的 ZK 系统，取决于平衡这些问题、证明生成速度、证明体积和可信设置要求。与 zkVM 方法相比，构建自定义电路意味着将 ECDSA 验证步骤表示为手工制作的代数约束。如果处理得当，可以带来显著的性能提升，因为电路正好针对重要操作进行了优化：点乘法和加法、模逆和最终检查。它还提供了对证明大小和证明生成时间的更严格控制。

缺点是编写和调试大型专业电路并非简单；它需要对椭圆曲线算术和 ZK 后端（例如 R1CS、PLONK 或其他格式）的内部工作有深刻了解。在 ZK 电路中验证 ECDSA 时，你需要以前所述的算术友好的方式复制每个数学步骤。在 secp256k1 上，这涉及：

• 域算术：在 Fp 中执行模加法、乘法和逆运算，p=2256−232−977。许多流行的证明系统有不同的基域，迫使你使用自定义的大整数门或分解约束来表示每一个 256 位的操作。
• 点操作：以 ZK 约束系统友好的方式实现标准的椭圆曲线点加法公式，对 x1,y1+x2,y2 进行处理。点乘法 kG（对于随机 k）或 u1G+u2Q 也扩展为多个更低级的操作。

在 ECDSA 的上下文中，这意味着直接在 ZK 电路内部实现核心验证关系，

r=?xX mod n  for  X=zs−1G+rs−1Q

通过在 Fp 上强制这些算术约束，证明确认 (r,s) 是在公钥 Q 上对 z（即 m 的哈希值）的有效签名，而不会透露私钥 d 或临时随机数 k。所有这些子步骤都可能为每个签名产生数千个单独的约束，这可能会推高证明生成时间。批量签名可能会使情况变得更糟，除非你巧妙地在多个实例中共享重复的步骤。因此，挑战在于平衡 ECDSA 逻辑的完备性与电路中的计算成本，从而确保证明在链上验证后，你仍然获得整体效率的提升。

如前所述，一些项目 [Per22b] 有现成的实现，已经经过很长时间的调试，并且进行了一些优化，应该使它们相对高效。通过使用“高效 ECDSA” [Per22a]，Spartan 能够从标准实现中删除超过 10,000 个约束，将单个签名的验证时间从我们基准上的大约 1 秒减少到 200 毫秒的证明验证。这相当于在初始基准上提高了 5 倍，但仍然不够。

在 ZK 研究流进行的同时，工程团队继续寻找纯技术解决方案以解决现有的验证瓶颈。我们能否通过基本的代码改进来修复这个问题？结果是，我们可以。因此，尽管取得了初步的好结果，ZK 工作暂时处于次要地位。工程上的解决方案复杂度较低，所需假设和安全论证较简单，因此显然是目前的最佳选择。这是 ZK 所走的尽头吗？也许不是，如果验证再次成为瓶颈，我们将会回来。如果 Sei 区块链转向 PQC 签名方案，则链的性能特征将会发生巨变，因此 ZK 可能会再次变得可行。

加入 Sei 研究倡议

我们邀请开发人员、研究人员和社区成员加入我们的使命。这是一个开放的邀请，欢迎进行开源合作，以构建更可扩展的区块链基础设施。查看 Sei Protocol 的 文档，探索 Sei 基金会的资助机会（ Sei 创作者基金， 日本生态系统基金）。请与我们联系 - collaborate[at]seiresearch[dot]io

参考文献

[Cor15] Andrea Corbellini. Elliptic Curve Cryptography: a gentle introduction. 2015. URL: https://andrea.corbellini.name/2015/05/17/ elliptic-curve-cryptography-a-gentle-introduction/

[mat19] mathcrypto. Question for cryptographers: SNARK friendly signature protocol. 2019. URL: https://ethresear.ch/t/question-for-cryptographers-snark-friendly-signature-protocol/ 4645/8

[Sun+21] Li Sun et al. zk-ECDSA: zkSNARKs for ECDSA (Part 1). 2021. URL: https://0xparc.org/blog/zk-ecdsa-1。

[0Da22] 0DanielTehrani. Efficient ECDSA signature verification using Circom. 2022. URL: https://ethresear.ch/t/efficient-ecdsa-signature-verification-using-circom/13629/1。

[Per22a] Personae. Efficient ECDSA the case for client-side proving. 2022. URL: https://personaelabs.org/posts/efficient-ecdsa-1/。

[Per22b] Personae. spartan-ecdsa. 2022. URL: https://github.com/personaelabs/ spartan-ecdsa。

[Che+23] Lily Chen et al. "Digital signature standard (DSS)". In: (2023)。

[Har24] HarryR. ethsnarks. 2024. URL: https://github . com / HarryR/ ethsnarks。

[suc24] Succinct Labs. SP1. 2024. URL: https://github.com/succinctlabs/ sp1。

• 原文链接： blog.sei.io/optimizing-e...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～