a16z Crypto 推出了两项与 SNARK 相关的技术：Lasso 和 Jolt。它们解决了三个关键问题：效能、开发人员体验和可稽核性。本文源自 a16z Researcher Justin Thaler 所着文章《Boosting Lasso+Jolt through faster commitments – with far-reaching consequences》
（前情提要：a16z：如何用一场魔术理解「零知识证明(ZKP)」是什麽？ ）
（背景补充：V神谈Layer2扩容全文：Rollup与Validiums（有效性验证）两者间权衡 ）
本文目录
其中 Lasso 是一种新的查询引数，可以显着提高证明者成本；Jolt（Just One Lookup Table）是一个专为与以太坊虚拟机器相容的 Rollups 设计的框架，一种利用 Lasso 构建 SNARK VM 的新颖方法。Lasso 和 Jolt 可以显着加快 Web3 中的扩容和构建应用程式，它们共同代表了一种全新的 SNARK 设计方法，可将广泛部署的工具链的效能提高一个数量级甚至更多级。
延伸阅读：科普｜zk-SNARKs是什麽？V神定调零知识证明未来十年「非常重要」
a16z 的研究合夥人、乔治城大学电脑科学系的副教授 Justin Thaler 深入探讨了最新的 SNARK 技术发展，强调了通过改变现有部署的各个元件，包括多项关键技术，以获取具有高效能证明者的 SNARKs 的必要性。Justin 建议使用基於求和检查的多项式 IOPs 和结合更快的证明者、更大证明的方案，如 Ligero/Brakedown，再加上递回，以实现更高效的 SNARK 系统。此外，他强调了对於更简单、易於开发的 SNARK 系统的迫切需求，以提高可审计性和安全性。
今年初，我们推出了 Lasso 和 Jolt，它们不仅效能更强大，而且更易於构建和审计的 SNARK。
Lasso 是一种具有明显更快证明者的新型查询引数。Jolt 基於 Lasso，提供了一种根本上新的设计范例，用於设计所谓的 zkVMs – SNARKs，使证明者能够证明它正确地运行了电脑程式（以某个特定虚拟机器的组合语言指定）。
Lasso 和 Jolt 的核心都是一种称为 sum-check 协议的技术工具，它们使用该协议来最小化证明者必须承诺的资料量（以及每个资料片的「大小」）。承诺资料的成本是 SNARK 证明者效能的关键瓶颈。
今天，Ulvetanna 的 Ben Diamond 和 Jim Posen（以下简称 D&P）释出了一篇改变游戏规则的论文。D&P 的核心贡献是修改了 Ligero/Brakedown 承诺方案，使证明者可以对每个承诺的值「按位」付费。我将解释他们是如何实现这一点的，以及为什麽与 Lasso 结合使用，这导致 SNARK 效能大幅提升。D&P 将他们的实现称为 Binius。
这些发展不仅提高了效能，也表明我们一直在错误地构思 SNARK 设计的关键方面。例如，Jolt 已经表明，当我们手工设计「SNARK-friendly」VMs 时，实际上我们一直在为今天流行的 SNARKs 的人工限制进行订制。D&P 表明，SNARK-friendly hash也是如此。在本文末尾，我还将详细说明关於 SNARK 设计需要发生哪些变化，无论是我们如何思考它还是我们构建什麽。
通过 Lasso 实现更好的 Circuit-SAT SNARK
Jolt 可以看作是将 Lasso 应用於 VM 执行的一种应用，其定义包括一遍又一遍地执行 VM 的简单取指 – 解码 – 执行回圈。然而，Lasso 本身具有更广泛的适用性。
D&P 的第一步是使用 Lasso 为电路可满足性提供更好的 SNARK（更准确地说，支援的「电路」是 Plonkish 约束系统）。这可以看作是将 Lasso 应用於（潜在的）非均匀计算（与 VM 执行不同，後者在本质上是均匀的，因为 VM 反覆执行相同的取指、解码和执行回圈）。这种应用利用了 Lasso 实际上比查询引数更强大：它是一种用於一般稀疏线性关系的引数，用於建立 M⋅t = a 的关系，其中 M 是一个稀疏矩阵（即，其大多数条目为零），而 t 和 a 是（可能已提交的）向量。
与 Jolt 一样，对 Lasso 的这种应用具有重要的特性，即证明者几乎需要进行密码学承诺的所有值都很小，意味着它们在 0 到 2b 之间，其中 b 是一个不是很大的数位（我们将 b 称为每个承诺值的位元复杂度）。例如，在 Jolt 中，对於大多数承诺的值，b ≤ 25。
在另一篇文章中，Srinath Setty 和我提出了一种 Plonkish 泛化的替代 SNARK，我们认为这种替代方法在概念上更简单，但可能不太容易与 D&P 随後的贡献整合。
这些基於 Lasso 的新的 Plonkish 约束系统 SNARK 将使 Lasso 基础技术更容易整合到现有的工具（如 Halo2）中，其中许多工具专门支援 Plonkish。
更快速的小值多项式承诺方案
首先，正如我在之前的文章中解释的那样，大多数 SNARKs 由两个元件组成：一个所谓的多项式 IOP 和一个称为多项式承诺方案的密码原语。关键的证明者瓶颈通常是多项式承诺方案。
如今，有两类广泛使用的多项式承诺方案。一类基於椭圆曲线密码学，其中最流行的例子是 KZG 承诺和 Bulletproofs/IPA。另一类基於 hash，当前最流行的例子是 FRI。
对於基於曲线和基於 hash 的承诺方案，承诺小值比大值更快。但是，就证明者的成本而言，它是一个关於值大小的阶跃函式：随着值的大小增长，成本基本保持不变，偶尔会有显着的跳跃。
在基於曲线的情况下，这是由於 Pippenger 的演算法，它大致允许证明者使用单个群操作对 1 到 20 位值进行承诺，使用两个群操作对 20 到 40 位值进行承诺，使用三个群操作对 40 到 60 位值进行承诺，依此类推。（在这里，20 是「承诺向量长度的对数」的替代，这个长度通常在 20 到 30 之间，并且前述的承诺成本是摊销的。）对於基於 hash 的承诺方案，许多专案今天在扩展域上工作，这些域具有其中一个更小的基础域。如果所有承诺的值都驻留在基础域中，则计算承诺的速度更快，目前常见的基础域大小在 31 到 64 位之间。
然而，当前的承诺方案在受益於小值方面的程度是有限的。在基於曲线的情况下，承诺一个 2 位值（即 {1, 2, 3, 4} 中的值）的速度不比承诺一个 20 位值（即介於 0 和 2^20≈100 万之间的数位）快：两者都需要通过 Pippenger 的演算法进行大致一次群操作。今天流行的基於 hash 的方案也是如此，它们对待所有基础域元素都差不多。
D&P 通过两种技术的组合，使 Ligero/Brakedown 基於 hash 的多项式承诺方案的这种阶跃函式变得更加平滑，允许证明者大致按位元「支付」每个承诺的值。他们通过两种技术的组合实现了这一点。首先，他们在 GF [2^128] 域上工作，这个域的特徵是二（这与今天流行的 SNARKs 有很大的不同，後者的特徵至少为 2^31）。他们将这个域构造为一个塔，意味着 GF [2^128] 被构造为 GF [2^64] 的扩容，GF [2^64] 被构造为 GF [2^32] 的扩容，以此类推。其次，他们使用与程式码串联相关的技术，以确保承诺一个 1 位值的成本真的比承诺一个 2 位值便宜约 2 倍，承诺一个 2 位值的成本大约比承诺一个 4 位值便宜 2 倍，依此类推。（有关这些技术的概述，请参阅我更详细的技术伴随 FAQ。）
这一效果可能是巨大的。在 D&P 目前针对 Keccak 的 SNARK 中，所有的承诺值都是单独的位，他们的改进使得承诺这些一位值的时间缩短了一个数量级以上。举个例子，在 Jolt 中，三分之一到三分之二的承诺值只是一个单一的位。
戏剧性改进的hash SNARKs
前两个贡献在应用於特徵为二的场域上的电路满足性方面，产生了一个更快的 SNARK，可能比以前的工作快一个甚至两个数量级。
然後，D&P 将这个 SNARK 应用於实现 hash 函式 Keccak（以及另一个称为 Grøstl 的函式），为这些 hash 函式产生比以前任何东西都要快得多的 SNARKs。一旦完全优化，我预计他们的 SNARKs 在单执行绪情况下每秒可以证明超过 5,000 个 Keccak-f 排列（在基准测试中使用的机器是 AWS c7i.16xlarge 例项，配备 Intel Sapphire Rapids 8488C 处理器），并且有充足的并行性可用。这意味着 20-25 MiB 的资料可以在约 30 秒的单执行绪处理中进行hash。
影响
更好的用於 hash 的 SNARKs 本身就是强大的，因为 SNARKs 应用於许多密码学语句（如 Merkle 身份验证路径的知识）最终都归结为 hash。事实上，这是 Type-1 zkEVMs 以及递回 hash 基础的 SNARKs 的关键瓶颈。
因此，尽管 Lasso 使 hash 的 SNARKs 更好，它和 Jolt 也从中受益：对 hash 更好的 SNARKs 使 Lasso 和 Jolt 能够与（递回版本的）基於 Ligero/Brakedown hash 的多项式承诺方案结合使用。这些方案的证明者非常快速，但需要验证者执行相当多的hash操作（在承诺的多项式大小的平方根）。这使得使用 Ligero/Brakedown 递回应用 SNARKs 变得困难，因为证明者很难证明它正确执行了验证者的 hash 操作。在使用更快的 hash SNARKs 後，这个困难应该会消失。
具体而言，对於拥有数十亿门的电路，Ligero/Brakedown 证明的大小在 MB 级别，验证者 V 主要执行栏位操作（对於递回而言很便宜）和hash操作。考虑到 SNARKs 可以在 30 秒的单执行绪处理时间内对 20 MB 的资料进行hash（并且具有充分的可并行性），证明者应该需要不到 10 秒的单执行绪处理时间来对该证明系统应用递回。
除此之外，当使用递回时，优化 Ligero/Brakedown 的证明大小并不合理，而应该优化递回证明器的执行时间。由於相比於栏位操作，hash 操作更昂贵，因此应配置 Ligero/Brakedown 让验证者 V 执行更少的 hash 操作，即使这意味着更大的证明和更多的栏位操作。这将加速递回证明，超出了前述 10 秒的估计。
总的来说，将 Lasso 和 Jolt 与 D&P 的承诺方案（递回应用）相结合将进一步提高 Lasso 和 Jolt 的效能。这既因为 Keccak 和 Grøstl 比今天流行的 SNARK 友好的 hash 函式更快，而且无论使用哪种 hash 函式，Ligero/Brakedown 的证明速度都比 FRI 快。
重新审视 SNARK 友好 hash 的观点
Jolt 表明，大多数 zkVM 专案对於什麽是「SNARK-friendly」虚拟机器存在误解。使一条指令「SNARK-friendly」的关键属性是一种被称为可分解性的东西。实际的指令集，而不是为了所谓的 SNARK 友好而手工设计的指令集，自然满足这种属性。我们一直在手工设计虚拟机器，使其适应当今流行的 SNARK 的限制，但这些限制是人为的。D&P 表明 SNARK 友好 hash 也是如此。近期，未来的工作是完全优化 D&P 的 SNARKs 以适应标准hash函式，并在应用於表面上是 SNARK-friendly hash 时将其效能与当今流行的 hash 函式进行比较。
更快的小域求和检查证明程式
D&P 目前的承诺成本已经降低到这样一个程度，在他们目前的 Keccak SNARK 实现中，证明者的瓶颈不再是多项式承诺方案，而是求和检查协议（Lasso 和 Jolt 基础多项式 IOP 的技术核心）。
然而，包括 D&P 在内的现有求和检查证明程式实现并没有被优化，以充分利用被求和的值都是「小」的这一事实。也就是说，现有的求和检查证明程式执行很少的有限域操作，但是大多数这些操作发生在「整个域」GF [2^128] 中，即使大多数被求和的值存在於一个更小的子域中，比如 GF [2]，GF [2^8] 或 GF [2^16]。
在我的另一篇文章中，我已经优化了求和检查证明程式以利用小的值。取决於值的大小，这可以将求和检查证明程式的工作改进大约 2 倍，甚至是多个数量级。
将这些优化纳入 D&P 的实现是短期未来的工作。
在 SNARK 设计中互动的作用
当今被广泛认为具有领先证明效能的 SNARKs 使用最小互动（即常数轮）的多项式 IOP，结合高度互动的多项式承诺方案，即 FRI。（Bulletproofs/IPA 也是高度互动的，尽管不太常与快速证明器联络在一起。）这与设计快速证明器 SNARKs 的方式相反。多项式 IOP 中的互动可以被利用以减少证明器成本，而多项式承诺方案中的互动则被利用以减少验证器成本，通常是以证明器成本为代价。
由於证明器成本是 SNARK 的关键可扩容性瓶颈，多项式 IOP 中的互动是实现更可扩容 SNARK 的关键，而在多项式承诺方案中大量的互动实际上可能会损害可扩容性。
更详细地说，FRI（和 Bulletproofs/IPA）利用互动来最小化证明大小，但这是以证明时间为代价的。相反，我们应该追求可能最快的证明器，即使这意味着仅获得略微次线性大小的证明。然後，我们可以应用递回来减小证明的大小。这正是 Ligero/Brakedown 多项式承诺中所做的，它仅涉及一轮互动，并且具有非常快速的证明器，但具有平方根大小的证明。在 D&P 的工作之前，使用这些承诺方案递回 SNARKs 是困难的，因为 Ligero/Brakedown 验证器必须执行大量 hash 评估。实际上，一些作品，如 Orion，简单地「在递回中留出验证器的hash」，限制了证明大小和验证器工作的减少。但是，由於用於证明 hash 评估的 SNARKs 速度更快，这个问题就消失了。
多轮的多项式 IOP 内的互动确实在很大程度上帮助了证明者。具体而言，求和检查协议利用多轮的互动来最小化证明者的承诺成本。在更低的层次上，求和检查协议使用多变数多项式和多轮的互动，而当今最流行的多项式 IOPs 使用单变数多项式和少量轮次的互动。单变数方法实现了与多变数方法相同的功能，但在关键时刻以要求证明者承诺大量额外资料为代价。
这里发生的情况是，求和检查协议让证明者执行额外的栏位操作（这是快速的），以减少证明者在承诺方案中使用的加密操作的数量（这是慢的）。这对於证明者的时间是一种胜利。相比之下，高度互动的承诺方案让证明者执行额外的加密操作（相对於最小互动方案），并不是为了减少证明者的工作，而是为了降低验证者的成本，比如证明大小和验证者工作。最好使用递回而不是互动，将这些验证者成本转嫁给证明者，而证明者的时间只会略微增加（现在我们有了足够快速的用於杂凑的 SNARKs）。
我们应该利用多项式 IOP 内的互动来最小化证明者需要承诺的资料量。用於承诺资料的多项式承诺方案应该对证明者来说尽可能快，前提是具有次线性的验证成本。只需要一轮互动就足够了。然後，可以通过递回减少验证成本，而不引入新的证明者瓶颈。
新发展概要
D&P 使用 Lasso 提供了更好的电路可满足性（circuit-SAT）SNARK。
这个 SNARK 可以使用任何多线性多项式的承诺方案。另外，他们提供了一个更快的多项式承诺方案（在特徵为二的域上例项化的 Ligero/Brakedown）。简而言之，通过使用二进位制塔场和程式码级联，他们确保对非常小的值进行承诺非常快（至少比以前的工作快一个数量级）。这个方案对於证明者来说非常快，但验证成本相对较高（验证者需要进行大量hash运算）。
这两个进展共同为标准hash函式（如 Keccak）提供了极快的 SNARKs。再次强调，这一验证成本相对较高。
更快的hash SNARKs 使这些 SNARKs 可以进行递回，尽管它们的验证成本相对较高。
递回反过来解决了大量验证成本的问题。
加密学术文章对 SNARK 生态系统的影响
这些新的研究成果意味着，为了获得性能卓越的 SNARK 证明者，我们应该基本上改变今天部署的每个元件，包括：
幸运的是，导致这些变化的同一发展也使 SNARK 变得更简单、更易於构建，尽管仍有进一步改进的空间。特别是，Jolt 消除了为 zkVM 手动设计指令集或手动优化实现这些指令集的电路的需要，因为它用每个原始指令的评估表的简单规范替代了这些电路。这种模组化和通用的架构使得更容易替换领域和多项式承诺方案，实现递回，并且通常减少了错误的表面积和需要维护和稽核的程式码量。
延伸阅读：Layer2蓄势待发，里面有什麽类型的zkEVM？
这种简单性不仅对可用性和开发速度至关重要。它有助於解决一个重要的安全问题。基於 SNARK 的系统由成千上万行程式码组成，需要理解多个订制的约束系统或 DSL，将永远无法足够可审计，以确保数十亿美元的价值的安全。
我希望这篇文章能够说服更多的专案投资於开发符合这一设计范例的 SNARKs。
在不久的将来，我所提出的一些观点仍然需要通过实施进行全面验证（例如，比较 D&P 的 Keccak SNARK 与那些表面上友好的 SNARK hash函式的比较，以及充分实施递回以减小证明大小）。与此同时，我们的初步 Jolt 实现（采用基於曲线的承诺方案）已经接近完成。一旦完成，重新实现 Jolt 以使用 D&P 的基於hash的承诺方案将是值得的。这有些复杂，主要是因为从大素数域切换到二特徵域需要重新定义所有 Lasso 应用的查询表。我还希望基於新的 Lasso 的 Plonkish 电路的 SNARK 能够简化将 Lasso 整合到现有工具中的过程，因为它可以将人们已经编写的电路馈送到其中。
这些是明显的下一步。我很期待看到社群完全吸收求和检查协议以最小化承诺成本的能力後会发生什麽。
📍相关报导📍
StarkNet是什麽？ZK-Rollups能成L2未来？完整生态、空投教学
ZK+DID：ZKID展开隐私安全赋能数位身份的新篇章
IOSG：ZK 协处理器的入门课， 它究竟能做什麽？
