zk-ECDSA: zkSNARKs for ECDSA (Part 1)
circom-ecdsa 是 circom 中基于ECDSA 算法的 zkSNARK 电路概念验证（Proof-of-Concept）的有效实现。
在过去几年中，以太坊和比特币网络依靠自身网络的力量已经进行了大量的公钥身份注册，使数百万人参与到构建用户可控数字身份的活动中，任何人都可以创建公钥对和私钥对以持有数字资产，并使用签名和身份验证工具参与到去中心化应用程序的生态系统中。
但是，仅靠公钥密码学还不足以构建富有表达力的完整身份系统。应用程序开发者和基础设施构建者需要更丰富的加密工具，来帮助用户证明和书写有关私钥知识、组中成员身份、拥有证明等任意声明。这些声明可能如下所示：
我是“黑暗森林行星”（Dark Forest planet） NFT 的所有者，但我不透露我具体拥有哪一个 NFT。即，我知道一个私钥与已知高信誉帐户中的 1024 个公钥之一相对应。
我已经获得了足够的选票以通过一个 DAO 资助的提案，但我不会展示出完整的投票信息。即，我获得了 5 个公钥中的 3 个 “赞成” 投票的消息签名。
实现此类声明的一种方法是在 zkSNARK 中实现以太坊的密钥生成和数字签名算法。zkSNARKs 是一种新的加密原语，允许用户证明执行任意计算的声明。从理论上讲，这将允许开发人员将任意身份声明嵌入到其应用程序中。
在 zkSNARKs 中实现现有签名算法需要克服许多挑战。当前的 zkSNARK 证明系统通常使用特定的椭圆曲线，这些椭圆曲线只能对特定素数进行模运算。这将 zkSNARK 证明中使用的最大寄存器位数位限制在 254-bit 。但像以太坊和比特币这样的网络使用的 ECDSA（Elliptic Curve Digital Signature Algorithm）和 secp256k1 曲线，是一条 NIST 标准曲线，并不是 SNARK 友好的。对 secp256k1 椭圆曲线点的操作涉及对 256 位数字的算术运算，这会使 SNARK 系统中的 254-bit 寄存器发生溢出。在内部实现 ECDSA 算法需要我们使用 254-bit 寄存器为 BigInt 算法和 secp256k1 操作构建 ZK 电路；所以说，我们必须想办法执行非原生的有限域代数算法。
在本系列文章中，我们将介绍 circom 中 ECDSA 电路的概念验证实现。circom 是一种用于特定 ZK 电路的编程语言，这些 ZK 电路可用于生成 zkSNARKs。我们详细介绍用于优化非原生的有限域代数算法的技术，并为基于 ECDSA 寄存器的 ZK 身份声明创建了一条产品级的工具栈路径。
我们的主要贡献是 circom-ecdsa 代码，其中包括一组可用于以下操作的 ZK 电路（未经审计）：
bigint：用于大整数和非原生有限域代数的电路。
secp256k1：用于 secp256k1 曲线运算的电路。
Secp256k1AddUnequal使用椭圆曲线群加法定律将两个不同的点相加
Secp256k1Double将一个点加倍
Secp256k1ScalarMult将一个点乘以一个标量
Secp256k1PointOnCurve检查曲线上的点是否在曲线上。
ecdsa：ECDSA 算法的电路。
ECDSAPrivToPub计算并约束与私钥关联的公钥。
ECDSAVerifyNoPubkeyCheck检查给定消息和公钥的签名是否有效。为了减少约束的数量，电路不会验证公钥本身是否有效。如果用户需要处理公钥，则必须额外检查其有效性。
目前尚未实现扩展验证或 ecrecover 算法，但基于上述工作可知它们相对容易实现。
eth_addr：一个用于证明以太坊地址私钥的电路。
PrivKeyToAddr计算并约束与私钥关联的以太坊地址。
我们采用适合 zkSNARKs 的 little-endian 形式来表达私钥、公钥坐标和其他 256 位以上的大数字。例如，我们通常使用包含三个元素的数组（各为 86 位数）来表示 256 位的数字。该数组可以被解读为：arrarr[0] + 2**86 * arr[1] + 2**172 * arr[2]。
README 中包含有关构建代码的说明和一些其他的使用说明。其中还包括一个小型的 "群签名" 命令行演示以供展示使用。这些电路是未经审计的，不适于生产级别规模的使用。目前我们也在探索半自动的验证方法。
我们使用了一些技术来优化电路，并使其缩减到可实用的大小，包括 xJsnark 的多项式乘法技巧和发生点有用倍数的预计算。私钥的证明可以在浏览器中运行，而签名验证通常需要一个专门的服务器。还有一些优化措施可以用来进一步减少证明密钥的所需的大小和时间。
| ECDSAPrivToPub | PrivKeyToAddr | ECDSAVerifyNoPubkeyCheck | |
| Constraints | 416883 | 568823 | 9480361 |
| Circuit compilation | 90s | 115s | 324s |
| Witness generation | 8s | 7s | 150s |
| Trusted setup phase 2 key generation | 150s | 167s | 5569s |
| Trusted setup phase 2 contribution | 28s | 47s | 767s |
| Proving key size | 254MB | 347MB | 5.8GB |
| Proving key verification | 157s | 185s | 6211s |
| Proving time | 12s | 17s | 239s |
| Proof verification time | <1s | <1s | <1s |
所有的基准测试都基于在一台 20 核 3.3GHz、64G 内存的机器上使用 Groth16，并运行 circom 和 snarkjs 工具栈。
由于 ECDSA 是以太坊中帐户的签名方案，因此 zkSNARKS （PrivKeyToAddr, ECDSAVerify）允许用户用零知识方法来证明其拥有某个帐户的所有权。所以 zk-ECDSA 是以下应用程序设想的核心原语：
组成员身份证明：加密社区通常会为特定组中的以太坊地址提供某些访问权限（例如，已被验证拥有某个 NFT 的人的私人 Discord 频道）。在这些情况下，所有权证明由 Collab.Land 等工具通过 ECDSA 签名验证进行检查。zk-ECDSA 可在不损害隐私的情况下，通过将 ECDSA 签名替换为一个给定组中地址的 zkSNARK 知识签名。这方面的早期实验包括“Proof of Dark Forest Winner ”（黑暗森林赢家证明）和 Vocdoni 的设计，都强调了实现 zk-ECDSA 是一个关键挑战。
隐私空投：Token 分配的一个常见模式是可追溯的空投，预先指定的地址列表可以根据先前对协议的使用情况申请 Token，同时要求用户证明他们的地址包含在 Merkle 树中，以获得 Token。通过将此公共 Merkle 证明替换为与 Merkle 树中的地址相对应的 zkSNARK 知识签名，zk-ECDSA 可实现保护隐私的空投申请。StealthDrop 是基于我们的 zk-ECDSA 工作构建的早期原型。
链上快照投票聚合：DAO 中的治理投票通常使用链下平台（如 Snapshot）上的签名来完成，以节省 gas 费。一旦投票结束，链上实施则取决于治理的执行。Ludens 建议构建一个使用 zk-ECDSA 作为原语的 zkSNARK，以证明有足够的投票来通过提案并验证 SNARK 中的签名。这样的 zkSNARK 可以在链上验证，并以去信任的方式对链下治理的决策进行实施。Vocdoni 是该设计方向上的提案。
我们的 zk-ECDSA 结构是未经审计的，并不打算在生产环境中使用，这也是 ZK 领域的一个普遍难题。我们认为需要完成以下步骤，才能够让 zk-ECDSA 进入生产环境的使用。
审计、测试和电路的形式化验证：为了对我们的 zk-ECDSA 电路更有信心，我们必须验证（1）witness 生成是正确的，（2）没有遗漏的约束。我们对（1）使用了传统的单元测试，但对（2）建立信心仍然需时日。除了传统的审计外，我们正在建立自动验证（2）的工具。
特定电路的可信设置或者 PLONK 移植：我们目前使用 Groth16 作为我们的证明系统，以利用其强大的工具栈。这需要为每个电路进行可信设置仪式来确保安全性，这意味着我们需要找到一组去中心化的可信设置参与者来部署我们的当前电路。若改用基于 PLONK 的证明系统将则无需如此操作，因为 PLONK 具有通用的可信设置。但这受限于具有良好性能够达到生产级的 PLONK 实现的可行性，这些实现于该本文书写时已初见端倪。
证明基础设施的可使用性：我们的 zk-ECDSA 结构具有大量的约束，生成证明时需要繁重的计算（我们的测试机器具有 20 个内核和 64G内存），这超出了大多数用户的能力。所以完成部署需要开发一个强大的远程证明基础设施，或者优化我们的电路以使验证更容易获得。切换到基于 PLONK 的基础设施可以通过像 plookup 这样的结构实现此类优化。
敬请期待我们 zk-ECDSA 的技术实现与优化的第二部分。
zCloak Network 是基于波卡生态的隐私计算服务平台，使用 zk-STARK 虚拟机为通用计算进行零知识证明的生成与验证。基于独创的自主权数据和自证明计算技术，可以让用户在无需对外发送数据的情况下，实现对数据的分析和计算。通过波卡跨链消息传递机制，可以为波卡生态内的其它平行链以及其它公链提供数据隐私保护支持。项目会采用“零知识证明即服务”的商业模式，打造一站式的多链隐私计算基础设施。
原文出自 OxPARC，原文链接见“阅读原文”
转载请注明原文与本文出处及翻译团队 zCloak Network
【免责声明】市场有风险，投资需谨慎。本文不构成投资建议，用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。
来源链接
