a16z：Lasso+Jolt如何实现更高效的SNARK系统？

原文标题：《A technical FAQ on Lasso, Jolt, and recent advancements in SNARK design》

原文作者：Justin Thaler

原文编译：Luccy，BlockBeats

编者按： 11 月 20 日，Ulvetanna 的 Ben Diamond 和 Jim Posen（DP）发布了一篇论文，改进了基于求和检查的多项式 IOPs 和结合更快的证明者、更大证明的承诺方案 Ligero/Brakedown，并将其与基于 sum-check 的 SNARKs（如 Lasso）集成在一起。a16z 的研究合伙人 Justin Thaler 对该技术进行了深入解析后，各研究员对文章内容提出疑问。

相关阅读：《a16z：Lasso+Jolt，快速承诺的崭新前景》

这篇 FAQ 整合了 13 个问题，回答包括 Jolt Prover 性能、DP 选择 Keccak 和 Grøstl 哈希函数的原因，以及对基于哈希的承诺方案安全性等多方面问题。此外，该篇回答中还涵盖了 Lasso 和 Jolt 的基础关系、使用 Reed-Solomon 码的性能优势、Ligero/Brakedown 相对于 FRI 的优势，以及 DP 承诺 GF[ 2 ] 元素经济性的解释。

讨论焦点包括整个计算的布尔电路实现、特征二字段的优势，以及通过递归组合 SNARK 证明和结合 DP 承诺方案与基于 elliptic-curve 的 SNARK 的技术和成本问题。最后，文章还提出了使用 DP 的承诺方案的 SNARK 是否可以与折叠方案（如 Nova）结合使用的问题。这些问题的深入研究有望促进该领域的技术创新和进一步改进。

Q1：相对于 RISC-V 程序的本机执行，一旦 Jolt 被重新实现以使用 DP 的承诺，您认为 Jolt prover 的速度会有多快？

A：这里提供一个粗糙且推测性的估计。Jolt prover 预计每个 RISC-V CPU 的步骤将承诺约 800 位的数据，使用 32 位数据类型和乘法扩展。需要注意两点：首先，某些 RISC-V 指令通过多个伪指令处理。例如，除法指令通过让 prover 提供商和余数，并通过乘法、加法和不等式检查对两者进行验证。其次，在我们解析 GF[ 2128 ] 的查找表分解后，这个数字估计可能会略有调整。

使用 DP 的承诺方案，并假设递归不会成为瓶颈，在 T 步计算中，主要的承诺成本如下。

首先，对总共约 200 T 字节的数据应用加法 FFT。更确切地说，Ligero/Brakedown 证明者执行 O(√T) 个大小为 O(√T) 的独立 FFT（这涉及的总工作量较少，且能更好地并行化，而不是执行长度为 O(T) 的单个 FFT）。其次，使用标准哈希函数如 Keccak 或 SHA 2 对大约 200 T 字节进行哈希。

经验上，DP 发现 FFT 和哈希在证明者时间中大致相等。

使用 Keccak 哈希，每字节约需要 70 个 RISC-V 周期的估算表明，这些操作将比仅运行未经证明的 RISC-V 程序慢约 30, 000 倍。换句话说，为了证明 Jolt 证明者正确运行了一个 RISC-V 程序Ψ，证明者本身（在 RISC-V 中实现）将需要至少比Ψ本身多 20, 000 倍的周期。

这些承诺成本足够「快」，表明证明者的瓶颈可能在于其在总检查协议中执行的有限域操作，即使考虑到小特征域的优化。因此，粗略估计，我猜测 Jolt 证明者（在 RISC-V 中实现）将比仅运行 RISC-V 程序慢约 50, 000 倍。

整个计算有点儿荒谬：当 Jolt 部署时，证明者本身不太可能由 RISC-V 实现。但这确实给出了如何估算 zkVM 证明者开销的大致思路。

尽管 50, 000 倍的减速看起来很大，但比我大约 18 个月前乐观估计的 100 万倍开销要快 20 倍。这种改善的主要原因是由 Lasso 和 Jolt 解锁的承诺数据较小（以及每个承诺值的较小大小）。其余的原因归功于更好的承诺方案（例如，改进了使用快速哈希函数和在基于哈希的 SNARKs 中利用承诺值的小规模的能力）。

Q2：DP 提供了 Keccak 和 Grøstl 的快速 SNARKs。为什么选择这些哈希函数？还有哪些哈希函数适合这些技术？BlockBeats 注：Grøstl 是一个加密哈希函数

A：Keccak/SHA 3 是一个明显的选择，因为它是 NIST 标准、以太坊预编译和 Type-1 zkEVM 的关键瓶颈。SHA 3 是官方的 NIST 标准，Keccak 是以太坊预编译，它们在与 SNARK 成本无关。

DP 考虑了 Grøstl，因为它应该导致更快的证明者，同时保持 Keccak 的许多优点。特别是，Grøstl 经受了强大的密码分析审查，尽管最终未被选中，但因为它进入了 NIST 的 SHA-3 竞赛的最后一轮，并且使用了 AES S-box。由于 AES 加速指令 AES-NI，Grøstl 在英特尔芯片上甚至比 Keccak 运行得更快。

DP 的证明者对于 Grøstl 应该比对于 Keccak 更快，因为 Grøstl 基本上是在 GF[ 28 ] 上本地定义的，这意味着 DP 的证明者可以对比 Keccak 更少的域元素进行承诺。（有关这如何使证明者受益的详细信息，详情请参考 Q 9 。）总的来说，Grøstl 应该比 Keccak 更适合（递归）SNARKs，因为它在证明者和芯片上都更快。

DP 的 SNARKs 与 Keccak 和 Grøstl 无关。这些技术应该适用于许多其他哈希函数。例如，DP 认为 SHA 2 也应该和 Keccak 一样好，但尚未详细研究过。

Q3：我以为 Lasso/Jolt 是针对 elliptic-curve 基础的承诺方案？