用AI优化密码学：一场速度与安全性的平衡实验

使用 AI 优化密码学

越来越清楚的是，如果方法得当，使用 AI 编程可以显著提高生产力。有些任务本质上是启发式的，比如生成图像或总结文章。具体来说，成功标准更接近“看起来不错”和“它很有用”，而不是其他任何标准。在编程中，你通常可以做得更好。例如，你可以编写测试来保证程序的流程按特定方式运行：一个函数接收特定输入，产生预期输出。当操作纯函数时，即那些不与更大系统的其他部分交互、也不会影响它们的函数，测试就很可靠。你可以修改和优化一个纯函数，而无需太过担心是否破坏了系统。在一般软件中，这些测试在局部范围内很有价值。当你面对的是一个与数据库、网络、存储等众多组件交互的更大系统时，你需要全局保证，这可以借助跨越整个系统的集成测试等方法来实现。

那么密码学呢？密码学中的 API 通常是无状态且简单的，尽管背后的数学可能很难。例如，签名大致如下：

• GenerateKeys()→(sk,pk)：生成一个私钥和一个公钥。
• Sign(sk,msg)→σ：对消息进行签名。
• Verify(pk,msg,σ)：验证消息的签名。

这对于 ECDSA、Schnorr、BLS 以及许多其他方案来说看起来都差不多。

优化多项式承诺方案

让我们谈谈基于多项式承诺方案（PCS）的现代证明系统。PCS 包含两个主要阶段：

• Commit(p)→C：对一个多项式进行承诺。
• Evaluate(C,x)→(z,π)：计算 C 中承诺的多项式在点 x 处的取值，并返回计算值 z 及证明 π。

在许多现代证明系统中，多项式承诺占据了大部分工作量，因此优化它们很重要。例如，我们（Andrija、Ron 和我）在研究 Bolt 时就在做这件事，探索权衡空间中的一个点：以更大的（尽管仍然可行）证明大小为代价，换取最快的承诺速度。

那么一个问题出现了——在这种情况下，你能安全地使用 AI 进行优化吗？答案是肯定的！但有一些注意事项。

我们来看看基于纠错码的方案的承诺阶段。一般模式是：先对多项式进行编码，再对编码结果进行承诺，然后对已承诺的编码查询足够多次，以证明该承诺唯一对应一个多项式（或一小部分多项式）。这个过程的安全性主要取决于码的距离，这是你在实现之外需要分析的属性。它还涉及查询点的随机选择，通常使用 Fiat-Shamir 变换来实现非交互性。

鉴于此，一个好的测试是：生成一个正确的编码，保存得到的承诺，然后开始优化。只要承诺保持不变，就没问题！你知道你的编码是正确的。这种方法的风险在于，如果你把这个任务交给 AI 却不够小心，它可能会对这个特定任务“过拟合”，从而用不正确但很快的方式生成同样的承诺，例如直接预先计算一次并将结果保存在文件里。

所以你可以做得更好。你可以准备一个缓慢但明显正确的实现，让它动态地为你生成测试用例，这能增加你对优化版本每次都正确编码的信心。

理论上听起来不错……实际可行吗？

在 Bolt 中，情况就是这样。最初有一个基于 Andrija 在 Ligerito 上的原创工作的 Julia 实现，后来他将其扩展为 Bolt 的承诺。

首先，我们以这个实现为基础，用 AI 先把它转换成 Rust，并在此过程中为所有我们能够覆盖的组件生成双向等价测试，比如有限域实现和 FFT。所谓双向等价，我的意思是：Julia 为这些组件生成测试用例，Rust 必须正确复现；反过来，Rust 也生成测试用例，Julia 必须正确复现。这最终奏效了，包括 Bolt 承诺本身。整个过程需要人工验证，至少在一定程度上是这样，因为测试可能做出错误的断言。我过去就遇到过这种情况，测试甚至没有 assert_eq。

顺便说一下，Bolt 承诺是 LDPC 码和 RS 码的组合。LDPC 码本质上就是数据矩阵中随机采样向量的一组线性组合。RS 码则广为人知。

凭借这个坚实的基础，我们继续向 AI 抛出能想到的各种想法，同时确保承诺保持不变。这个方法非常奏效。我们得以尝试比亲自动手时更多的想法，而且我们有信心实现是正确的，因为承诺产生的结果与慢速实现相同。这并不总是有效，因为我们的直觉并不总是正确的，AI 的直觉也不总是正确的。在少数情况下，AI 会说“是的，这会非常棒”，但最终对性能几乎没有影响。

最成功的策略最终如下，我们的目标机器是一台搭载 M 系列处理器的 Mac：

1. 缓存优化——智能地把即将使用的元素加载到较小的 L1 缓存中，更关键的是，把后续需要的元素提前预加载到较大的 L2 缓存，从而让 L1 缓存加载更快。
2. 使用 SIMD 向量指令，这很有效，因为我们正在对整列进行加法和标量乘法。
3. 使用 Metal 进行编码和哈希的 GPU 加速，我们在此之前并没有太多实际经验。
4. 汇编优化，使用无进位乘法和其他指令。
5. 用于哈希的硬件加速指令。例如，对于 SHA256，可以通过 ring 库来实现；其底层有诸如 SHA256H 之类的指令，实现了 SHA256 哈希的部分功能。
6. 在编码和承诺之间进行流水线操作，因为 Bolt 的码是系统码，这意味着编码的很大一部分工作就是对消息本身进行哈希。

经过多轮提示和审查，最终性能比 Julia 实现提高了一个数量级以上。

人在回路中仍然很重要。例如，AI 提出的一个优化很棒，但当时我没有仔细审查，结果因此栽了个跟头。这个优化是关于如何将一个 8 位域元素嵌入到具有特定表示的 32 位域元素中。不深入细节，正确的做法是：在仍然保持我们码的距离的同时，使用 32 位域的一种表示（把 32 位域看成四个 8 位元素组成的向量）与目标表示之间的同构。AI 的建议是把 8 位元素的位直接重新解释成 32 位元素的位，但这样做会损害码的距离，而它并不知道这一点。这勉强算是一种嵌入，但它基本上让这个元素变成了和其他任何 32 位元素一样的东西，而不是保留它来自 8 位元素的独特属性。

听起来很棒，这总是有效吗？

不幸的是，并非如此。这种类型的承诺特别适合优化，其他类型的系统可能不适合。例如，ZK 电路可能会以非常微妙的方式出错。你想通过减少约束来优化证明者的性能，但电路中缺少一个约束仍然会产生相同的功能结果，却可能被完全攻破。即使是一个缺失的约束也可能导致完全攻破，这在审计和真实攻击中屡见不鲜。

该策略还可以用来在保持可靠性（soundness）的同时优化密码协议，但要小心操作，因为这更加微妙。如果你有一个缓慢且正确的实现，能逐位产生相同的元素，这就有效。在交互式公开币协议中（这些协议随后使用 Fiat-Shamir 转换为非交互式协议），这表现为重现 transcript，即协议期间证明者和验证者彼此发送的消息集合。如果这些保持不变，并且你的抽象足够严密，能保证没有其他侧信道，你就可以确信这些优化是净收益。

你可以进一步推广这个思路。只要你能定义一个保证可靠性的验证者，并且在优化过程中它始终有效，那你就处于安全的境地。请注意，其他属性如完备性或零知识仍可能受到影响，除非你也有办法对它们的验证进行建模。这尤其敏感，因为优化后的代码可能不完备。对于基准测试来说没问题，对于生产代码则不行。

程序不按规范运行的风险可以通过形式化验证等方法缓解，但这需要付出不小的努力。更具体地说，Gregor 和团队在过去几年里一直在研究 Clean，它将形式化验证引入 ZK 电路。我们现在在几个不同的项目中都在使用它。

现在，假设你在 Clean 中定义了一个 SHA256 电路，你能回去专注于优化它而不担心破坏可靠性吗？能！这正是 Clean 给你的保证。无论你如何优化，规范都会保证可靠性得以保持。

因为这是一个如此强大的机制，Giorgio 和 Mathias 发起了一项竞赛，来优化在 Clean 中指定的 ZK 电路。你想手工完成？请便。用一群 AI？也很好。只要确保它仍然符合规范，就万事大吉 :)

点击这里查看，看看你能走多远。目前已经为这些电路做出了很大的优化——既涉及素数域上的哈希和标量乘法，也涉及二进制域上的哈希。

其他一些很酷的努力包括 snark.fast 和 lighter.fast，它们遵循同样的思路：在保持验证者不变的情况下优化证明者。

有什么通用的经验可以借鉴吗？

我最主要的建议是：找出正确的锚点，确保你的 AI 在解决正确的问题。对于承诺方案，可以是承诺哈希。对于 ZK 电路，可以是验证者或形式化规范。对于 AI 模型，可以是损失指标。你可以在这方面发挥创意，只要确保锚点是有效的。我们在最近一期与 Benedikt Bünz 的 ZKPodcast 中稍微讨论了这一点，其中 Benedikt、Ron 和 William 大量使用 AI 来优化他们新论文 Flock 的实现，这是一个用于位运算哈希、能够极速证明的证明系统。我们还更广泛地讨论了 AI 辅助工作。

致谢

感谢 Mathias 就验证者所提供的保证提出了看法。感谢 Stefanos 对等价测试可靠性和硬件加速的修正与评论。感谢 Ron 和 Andrija 阅读全文。

• 原文链接： blog.zksecurity.xyz/post...
• 鸿途知科网 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～