谷歌零知识证明钱包 libZK 亮点

原文：https://nmohnblatt.github.io/libzk-highlights/

作者：Nicolas Mohnblatt

译者：Kurt Pan

上个月，谷歌宣布更新 Google Wallet，启用“快速私密年龄验证”。正如预期，该系统底层采用了零知识证明（ZKP）。这无疑是个好消息！首先，这些隐私保护原语将获得更广泛的传播，并有望被广泛采用。其次，令人欣喜的是，高性能、生产级的零知识证明正在区块链/Web3 行业之外得到开发。最后，看到各国政府和谷歌等大型科技公司对零知识证明表现出兴趣，清楚地表明了我们钟爱的隐私增强技术正迎来发展契机。

• https://blog.google/products/google-pay/google-wallet-age-identity-verifications/

匿名凭证协议是 Matteo Frigo 和 Abhi Shelat 在论文“Anonymous credentials from ECDSA”中提出的匿名凭证方案的实现。底层的零知识证明系统及其实现技术也在名为 libZK 的 IETF 草案中进行了记录。

• https://eprint.iacr.org/2024/2010
• https://www.ietf.org/archive/id/draft-google-cfrg-libzk-00.html

在本文中，我想重点介绍 libZK 证明系统中的一些创新、观察和见解，我认为我们——“ZK 社区”——都应该关注并借鉴。这篇文章并非对该证明系统的完整解释或教程，而是希望能起到引导作用，激发你阅读论文，或收听即将播出的 ZKPodcast 节目，在节目中我们将采访 Matteo 和 Abhi。以下是四大类讨论要点的简要概述，文章其余部分将在此基础上进一步展开。

libZK 的亮点

1. 证明系统：
• 与“客户端证明”的趋势类似，libZK 优先考虑快速证明者和具体的小型证明，而非渐近的证明大小和验证者时间。
• 该系统通过组合证明（内部使用类似 GKR 的证明，外部使用 Ligero 证明）来降低承诺成本并保持零知识属性。
• 该系统组合交互式证明（IP），而非 SNARK，以避免对 Fiat–Shamir 挑战进行算术化，并使安全性证明更为简洁。
2. 算术化：
• 该系统实现了“双电路算术化”：部分约束在 secp256r1 曲线的基域  上定义（用于验证 ECDSA 签名），部分约束在 16 位二进制域  上定义（用于验证 SHA-256 并解析 JSON/CBOR 等二进制格式）。
• 双电路范式需要额外约束以确保两个电路中的见证值保持一致；这是通过在每个电路内计算 MAC 并将其与公共输入进行比较来实现的。
3. 实现技术：
• Ligero 外部证明需对见证进行 Reed–Solomon 编码。libZK 并未采用常规的插值-求值方法，而是通过卷积计算实现编码，可在任何域中以  域运算完成（使用 Nussbaumer 算法），若可用 FFT，则为  运算。
• https://ieeexplore.ieee.org/document/1163372
• 在使用域扩展时，卷积编码可选择将插值和求值域设为子域，从而使 RS 码字也位于子域中，将证明大小减少常数倍。
• 可以在 secp256r1 基域的二次扩展  中高效计算 FFT，开销最小（这一技术最早在 Virgo 中提出，后被 Circle STARK 采用）。
• 在二进制域中，可使用加法 FFT 计算 FFT，该技术同样在 Binius 中得到应用。
4. 电路设计：
• 内部证明系统类似 GKR，因此要求“分层”电路。对于 CBOR 解析电路，通过硬件域常用的并行前缀技术保持电路深度较低。
• https://en.wikipedia.org/wiki/CBOR

证明系统

优先考虑证明者时间

libZK 系统专为智能手机生成匿名凭证（即“客户端证明”）的场景设计。主要限制因素是设备算力和带宽：前者要求 ZKP 的证明者高效，后者要求证明尺寸足够小。

与行业趋势类似，这些限制促使我们采用：

1. 对尽可能少的数据进行承诺；
2. 拥有高效的证明者；
3. 避免昂贵的“公钥”操作。

需求 1 和 2 指向基于 sumcheck 的证明系统，尤其是类似 GKR 的方案，以最小化承诺成本；需求 3 通常指向仅依赖哈希函数的证明系统。

那么，如何高效地将零知识添加到类似 GKR 的基于哈希的证明系统？libZK 的答案是将类似 GKR 的内部证明与完整的 Ligero ZKP 组合。请注意，这里指的是完整的 Ligero ZKP，而不仅仅是多项式承诺部分。

另一个重要之处在于，通过组合可实现比单独运行 Ligero 更低成本的整体协议。Ligero 需要将断言表示为 R1CS 电路，并对完整的 R1CS 见证（包括所有中间变量）进行承诺；而通过 GKR 和组合，证明者仅需提交较小的 GKR 见证和一些额外的随机掩码。Frigo 和 Shelat 报告称，与单独运行 Ligero 相比，证明者速度提高了约 20 倍。

组合交互式证明而非 SNARK

通常，我们在非交互式论证层面进行证明组合：先将交互式协议通过 Fiat–Shamir 变换（或对交互式预言机证明，先用 Merkle 树承诺预言机消息，再应用 Fiat–Shamir （BCS 变换）。）转换为内部 SNARK，然后再生成针对“内部 SNARK 验证通过”这一断言的外部证明。此过程需要对 SNARK 的完整验证流程（包括 Fiat–Shamir 挑战的生成）进行算术化。

而 libZK 则将 GKR 协议和 Ligero 组成为交互式证明（IP），并对 GKR 脚本添加掩码以确保整体零知识性。你可以通过下图了解该组合方式：

组合 IP 而非 SNARK 的两个主要好处

1. 外部证明电路无需强制执行 Fiat–Shamir 挑战正确推导的约束。
2. 协议安全性既可作为标准模型中的交互式证明来保证，也可作为 ROM 中的非交互式证明来保证，而这在 SNARK 组合中通常无法实现。

与往常一样，通过应用 Fiat–Shamir 变换可以将上述交互式协议转为非交互式。

然而，其缺点在于无法获得 SNARK 组合所提供的“证明压缩”效果。实际上，通过这种方式组合 IP，完整协议的转录是 GKR 与 Ligero 脚本的串联。应用 Fiat–Shamir 后，得到的非交互式证明包含了内外部协议的所有消息，而非仅外部协议消息。

双电路算术化

域选择

由于在匿名凭证系统中的应用，libZK 侧重于验证 ECDSA 签名并解析签名消息。标准的 ECDSA 签名基于 secp256r1 曲线，其基域是特征为  的素数域：

在  上使用电路来强制执行约束，可以用极少的约束表达 ECDSA 验证算法。

然而，ECDSA 签名还需要对签名消息进行 SHA-256 哈希。此外，匿名凭证系统使用的消息通常以 CBOR 格式序列化；这是一种类 JSON 的二进制数据格式。因此，验证哈希并解析 CBOR 消息主要是按位或按字节操作。受 Binius 启发，libZK 使用 16 位二进制域来高效地执行这些约束。注意，libZK 并未像 Binius 那样使用多层二进制域，这方面的比较留待作者日后研究。

使用 MAC 实现跨电路一致性

使用两个电路的缺点是，证明系统需要确保这些电路相互关联，并且即便见证值在每条电路中的表示方式不同，也必须保持一致。libZK 的解决方案是在两个电路中对共享的见证元素计算消息认证码（MAC），然后将这些电路内的 MAC 与单一公共输入进行比较。

需注意，此技术引入了一个微妙问题：如果验证者知道 MAC 密钥，则协议不再具备零知识性；但如果证明者知道 MAC 密钥，则 MAC 无法保证抗伪造性（且 ZKP 不再可靠）。libZK 通过让证明者与验证者共同采样 MAC 密钥来解决这一矛盾。更多细节请参见论文第 3.4 节。

• https://eprint.iacr.org/2024/2010

实现技术

使用卷积在每个域中进行快速 Reed–Solomon 编码

Ligero 证明系统要求使用 Reed–Solomon（RS）码对见证进行编码。通常的做法是：先将见证向量视为多项式在一组单位根上的取值；然后对该多项式进行插值；最后在更大的一组单位根上对其进行求值。我将这种基于 FFT 的传统方法称为“纯 FFT 方法”。该方法依赖单位根的存在，并分别使用逆 FFT（和正向 FFT）来完成多项式的插值和求值。

为了兼容各类已部署的数字签名标准曲线，libZK 必须在无法使用单位根和 FFT 的环境下仍保持高性能。直接对多项式进行插值和求值对于证明者来说过于低效。在此情境下，Frigo 和 Shelat 借鉴了 Cormode、Mitzenmacher 和 Thaler（2012）的观察：RS 编码可以通过计算卷积来完成，而无需插值和求值。关键在于，使用 Nussbaumer 算法可以在任意域中以  次域运算高效计算卷积；若可用 FFT，则可降至  次运算。不论是否使用 FFT，我都将该方法称为“卷积方法”。

• https://arxiv.org/abs/1105.2003

卷积方法的两大优点

1. 无单位根/FFT 依赖
   即使在没有单位根和 FFT 的域中，该方法仍然可用，对追求最大兼容性并可能成为标准的系统尤为重要。
2. 任意插值与求值域
   卷积方法允许我们为多项式选择任意的插值域和求值域。对于采用小域与较大密码学扩展域的场景尤其有用：可以将插值和求值域都设置在小域，从而使 RS 码字也定义在小域中，进一步将证明大小减少一个常数因子。

当可用 FFT 时，卷积方法（结合 FFT）的理论开销约为纯 FFT 方法的两倍。正如 Matteo 和 Abhi 所言，这一“理论”开销在某些场合可通过已知优化完全消除。但正如作者私下所述，“该系统的核心在于 FFT 的速度并不关键”，因为 FFT 只用于在编码时间中削减一个  因子，而这仅是证明者众多任务之一。

secp256r1 的 FFT

虽然 FFT 并非关键性需求，但它的存在能够加快证明者的运行速度。然而，上述两个域都不是 FFT 友好的。所谓 FFT 友好域，是指存在一个乘法子群，其阶是  的较大幂。等价地，如果域的阶  满足  可被  的较大幂整除，则该域是 FFT 友好的。

secp256r1 椭圆曲线的基域并非 FFT 友好。观察上述给出的  表达式，可将其简化为

该域的乘法子群阶为

换言之，其中仅有一个  因子，乘以某个较大的奇数：显然不是 FFT 友好的。

另一方面，，即  的二次扩展域，是 FFT 友好的。事实上， 的阶为 ，其乘法子群阶为

这里出现了一个较大的  的幂，意味着可以在该二次扩展域中执行 FFT。具体而言，与同等规模的 FFT 友好域相比，这会带来约  的开销；但这仍优于不使用 FFT 或在 FFT 友好域中结合异域算术实现 ECDSA 电路。

与 Virgo 和 Circle STARK 的联系

事实上，该思路可推广至任意素数 ：将其表示为

然后注意到  能整除 ，而  又能整除

后者即  的乘法子群阶。取  则得形如  的素数，即梅森素数，此方法最早用于 Virgo，后被 Circle STARK 采纳。

二进制域的 FFT

对二进制域进行 FFT 同样神奇，它源自 Lin、Chung 和 Han 于 2014 年发表的一篇论文，并在 Binius 中得到运用。由于这项技术在我们的研究和工程界早已为人所知，因此我将在这篇文章中尽量避免讨论它（尤其是因为我还没有研究过它的工作原理）。

• https://ieeexplore.ieee.org/document/6979016

电路设计：我们站在（数字硬件）巨人的肩膀上

我想要强调的最后一项技术是 libZK 的作者如何借鉴数字硬件设计中的技术来降低其 CBOR 解析电路的深度。编写一个能够解析消息并提取特征的高效电路非常困难：约束写得太多，证明者就会永远运行下去；约束写得太少，就会出现可靠性缺陷。

他们用来缩短电路长度的技术被称为“并行前缀”。它最初的设计目的是在对数时间而非线性时间内执行运行和运算。显然，同样的方法也可以应用于输入解析。更多详细信息，我建议你阅读论文的 4.3 节，特别是标题为“降低词法分析深度”的段落。

• https://eprint.iacr.org/2024/2010

编辑历史记录

2025 年 6 月 2 日：在本文的上一版本中，我重点介绍了如何在 secp256r1 基域和二进制域中计算 FFT。这种关注点有些误导。本文的有趣之处在于，如何使用卷积而非通常的“插值求值”方法，高效地计算任意域中的 Reed-Solomon 编码。在某些域中，使用 FFT 可以更快地计算这种卷积。我将在修订后的“实现技术”部分更详细地解释所有这些内容。更新日志：“实现技术”部分和摘要以及“与 Circle STARK 的联系”均已重写；致谢部分现在反映了 Matteo 和 Abhi 给予我的宝贵帮助和讲解。文章的其他所有部分保持不变。

Kurt Pan: 即日起提供有偿「密码学论文代码实现和 benchmarking 服务」，语言侧重Rust / Python / C++，密码学侧重零知识证明系统和格密码方案。欢迎有需要的老师同学以及对密码学感兴趣的朋友联系我，邮箱https://keys.openpgp.org/search?q=kurtpan666%40pm.me，也可关注公众号后留言。