Halo 及和更多：探索无需配对的增量验证与SNARKs技术

特别感谢Justin Drake和Sean Bowe提供的细致入微且深思熟虑的反馈和审核，以及Pratyush Mishra的讨论，他们为原始IPA阐述做出了贡献。

一直在紧跟ZK-SNARK领域动向的读者应该对ZK-SNARK的工作原理有了初步了解。ZK-SNARK基于检查方程，其中输入方程的元素是像多项式（或者在rank-1约束系统中用于矩阵和向量）这些可以承载大量数据的数学抽象。有三大类密码学技术能够简洁地表示这些抽象：Merkle树（用于FRI）、常规椭圆曲线（用于内积论证（IPA））和带配对及可信设置的椭圆曲线（用于KZG承诺）。这三种技术分别导致了三种类型的证明：FRI导致STARKs，KZG承诺导致“常规”SNARKs，基于IPA的方案则导致保密证明（bulletproofs）。这三种技术具有非常不同的权衡：

到目前为止，第一种和第三种得到了最多关注。这与表中第二行恼人的右列有关：基于椭圆曲线的内积论证具有线性的验证时间。这意味着尽管证明的大小很小，但验证证明所需的时间总是比自己运行计算所需的时间更长。这使得IPA在与可扩展性相关的ZK-SNARK用例中不可行：使用基于IPA的论证来证明以太坊区块的有效性毫无意义，因为验证证明所需的时间会超过只需检查区块所需的时间。另一方面，基于KZG和FRI的证明确实比自己运行计算快得多，因此其中的一种似乎是显而易见的选择。

然而，最近有大量关于将多个IPA证明“合并”为一个的研究。 这些初步工作的很大一部分是作为设计Halo协议的一部分进行的，该协议正被集成到Zcash中。这些合并技术便宜，合并后的证明的验证时间与其所合并的单个证明相同。这为IPA变得有用开辟了一条新路：与其用花费O(n)时间验证一个大小为n的计算的证明，不如将该计算拆分为较小的大小为k的步骤，为每个步骤制作nk个证明，并将它们合并，使得验证者的工作减少到稍微超过O(k)。这些技术还允许我们进行增量验证：如果有新的事物需要被证明，可以不断将现有证明与新声明的证明混合，以生成新的组合声明的证明。这对于验证比如整个区块链的完整性非常有用。

这些技术是如何工作的？它们能做些什么？这正是本文的主题。

背景：内积论证是如何工作的？

内积论证是一种可以在许多数学结构上运作的证明方案，但通常我们关注的是基于椭圆曲线点的IPA。IPA可以在简单的椭圆曲线上被构建，理论上甚至包括比特币和以太坊的secp256k1（不过一些特殊属性会更有利于让FFT更高效）；不需要那种极其复杂的配对方案，尽管我写过解释文章和实现代码，但我依旧难以理解。

我们将从承诺方案开始，通常称为Pedersen向量承诺。为了能够承诺于度小于n的多项式，首先我们需要公开选择一组基点，G0...Gn−1。这些点可以通过一种伪随机程序生成，任何人都可以重新执行（例如，Gi的x坐标可以是hash(i,j)对于产生有效点的最小整数j≥0）；这不是可信设置，因为它不依赖于任何特定方进行秘密信息的引入。

为了承诺一个多项式P(x)=∑icixi，证明者计算com(P)=∑iciGi。例如，com(x²+4)将等于G²+4∗G0（请记住，这里的+和∗是椭圆曲线加法和乘法）。密码学家通常还会增加一个额外的r⋅H隐蔽参数以保护隐私，但为了简单起见，我们暂时忽略隐私；一般来说，在所有这些方案中增加隐私并不是那么困难。

现在，让我们来看看证明是如何工作的。我们的最终目标将是一个多项式评估证明：给定某个z，我们想生成一个证明，即P(z)=a，其中该证明可以被任何拥有承诺C=com(P)的人验证。但首先，我们将关注一个更简单的任务：证明C是对任何多项式的有效承诺 - 即证明C是通过取线性组合∑iciGi的形式构建的，而没有其他内容混合。

当然，技术上讲，_任何_点都是G0的某个倍数，因此理论上它是某个东西的有效承诺，但我们关心的是证明证明者_知道_某个{c0...cn-1}，使得∑iciGi=C。一个承诺C不能承诺于多个独立的多项式证明者已知，因为如果可以， 那就意味着椭圆曲线是破碎的。

证明者_当然_可以直接提供{c0...cn−1}，让验证者检查承诺。但这占用的空间过大。因此，我们试图将问题简化为更小、大小为一半的问题。证明者提供两个点，L和R，代表该图中的黄色和绿色区域：

你可能会看到这指向什么：如果将C+L+R合在一起（请记住：C是原始承诺，即蓝色区域），新的组合点可以表达为_四个_平方的和，而不是八个。因此，现在，证明者可以仅提供四个和，各新平方的宽度。重复这个协议两次，我们就能减少到一个完整的平方，证明者可以通过提供一个表示其宽度的单一值来证明。

但有一个问题：如果C在某种方式上不正确（例如，证明者将某个额外的点H添加进来），则证明者可以通过从L或R中减去H来进行补偿。我们填补这个漏洞，通过在证明者提供L和R后随机缩放我们的点：

选择一个随机因子α（通常，我们设置α为所有添加到证明的数据的哈希，包括L和R，以确保验证者也可以计算α）。每个偶Gi点通过α缩放，每个奇Gi点则向下缩放。每个奇系数向上缩放，每个偶系数向下缩放。现在，注意以下几点：

• 黄色区域（L）的面积乘以α²（因为每个黄色正方形的两个维度都有扩大）
• 绿色区域（R）的面积除以α²（因为每个绿色正方形的两个维度都有缩小）
• 蓝色区域（C）保持不变（因为它的宽度增加了但高度减少了）

因此，我们可以通过一些简单的变换生成我们新的一半大小的问题实例：

• Gi′=αG2i+G2i+1α
• ci′=c2iα+αc2i+1
• C′=C+α²L+Rα²

（注意：在一些实现中，你可以改为使用Gi′=αG2i+G2i+1和ci′=c2i+αc2i+1，而不将奇点除以α。这将使方程C′=αC+α²L+R，这样的表达形式较少对称，但确保计算任何G′的函数在协议的任何轮次成为无除法的多项式。又一种替代方案是做Gi′=αG2i+G2i+1和ci′=c2i+c2i+1α，这样也避免任何α²项。）

然后我们重复这个过程，直到得到一个点：

最后，我们有一个大小为1的问题：证明最终修改后的C∗（在该图中为C‴，因为我们执行了三次迭代，但通常是log(n)次迭代）等于最终修改后的G0∗和c0∗。在这里，证明者只需在明文中提供c0∗，验证者检查c0∗G0∗=C∗。计算c0∗需要能够计算{c0...cn−1}的线性组合，而这些组合在一开始并不知道，所以提供它并验证会说服验证者，证明者确实知道构成承诺的所有系数。这就完成了证明。

简要回顾：

• 我们正在证明的声明是C是使用商定的基点{G0...Gn−1}承诺于_某个_多项式P(x)=∑icixi。
• 证明包含log(n)对(L,R)值，代表每个步骤中的黄色和绿色区域。证明者还提供最终的c0∗。
• 验证者逐步遍历证明，在每一步中使用与证明者相同的算法生成α值并计算新的C'和Gi'值（验证者不知道ci值，因此无法计算任何ci'值）
• 最后，他们验证c0∗G0∗=C∗

总体而言，证明包含2∗log(n)个椭圆曲线点和一个数字（对于挑剔的人来说：一个域元素）。验证证明在每一步所需的时间是对数时间，除了一个问题：计算新的Gi′值。这一步，不幸的是是线性的。

另见：Dankrad Feist关于内积论证的更详细解释。

扩展到多项式评估

我们可以通过一个简单的巧妙技巧扩展到多项式评估。假设我们要证明P(z)=a。证明者和验证者可以通过将z的幂附加到基点G0...Gn−1来扩展这些基点：新的基点变为(G0,1),(G1,z)...(Gn−1,zn−1)。这些对可以被视为数学对象（对于挑剔的人：群元素），类似于椭圆曲线点本身；要将它们相加，可以逐元素进行：(A,x)+(B,y)=(A+B,x+y)，使用椭圆曲线加法处理点，使用常规域加法处理数字。

我们可以使用这个扩展的基点制作一个Pedersen承诺！

现在，想想一个难题。假设P(x)=∑icixi，其中P(z)=a，使用我们之前的常规椭圆曲线点作为基点的话，承诺C=∑iciGi。如果我们使用对(Gi,zi)作为基点，那么承诺将是(C,y)的某个y。y的值是多少？

答案是：它必须等于a！这很容易看出来：承诺是(C,y)=∑ici(Gi,zi)，我们可以将其分解为(∑iciGi,∑icizi)。前者等于C，后者就是对P(z)的评估！

因此，如果C是使用{G0...Gn−1}作为基础的P的“常规”承诺，那么要证明P(z)=a，我们只需使用上面的相同协议，但要证明(C,a)是使用(G0,1),(G1,z)...(Gn−1,zn−1)作为基点的有效承诺！

请注意，在实践中，这通常以稍微不同的方式进行优化：不是将数字附加到点上并明确处理(Gi,zi)形式的结构，而是添加一个随机选择的基点H，并将其表示为Gi+ziH。这节省了空间。

请查看这里，了解整个协议的示例实现。

那么，如何合并这些证明？

假设你得到了两个多项式评估证明，它们的多项式和评估点不同，并希望证明它们都是正确的。你有：

• 证明Π1证明P1(z1)=y1，其中P1由com(P1)=C1表示
• 证明Π2证明P2(z2)=y2，其中P2由com(P2)=C2表示

验证每个证明的时间是线性的。我们希望生成一个证明，证明这两个证明都是正确的。这仍然需要线性时间，但验证者只需进行_一次_线性时间的验证，而不是两次。

我们首先做出一个观察。执行证明的验证过程中唯一的线性时间步骤是计算Gi′值。这是O(n)的工作，因为你必须将n²个Gi值组合成Gi'值，然后将n⁴对Gi′值组合成Gi''值，依此类推，总共有n对的组合。但如果你仔细查看算法，你会发现我们实际上不需要任何中间的Gi'值；我们只需最终的G0∗。这个G0∗是初始Gi值的线性组合。这个线性组合的系数是什么？答案是，该Ji值就是对应于以下多项式中的Xi项：

(X+α1)∗(X²+α2) ∗ ... ∗ (Xn²+αlog(n))

这是使用我们上面提到的C′=αC+α²L+R版本。直接计算G0∗作为线性组合的能力，已经使我们的工作减少到O(nlog(n))，因为快速线性组合算法可以使用，但我们可以进一步优化。

上述多项式的度数是n−1，并且有n个非零系数。但它的未展开形式的大小是log(n)，因此你可以在O(log(n))时间内对多项式的任何点进行评估。此外，你可能会注意到G0∗是对此多项式的一个承诺，因此我们可以直接_证明_评估！所以我们这样做：

• 证明者计算上述多项式 لكل个证明；我们称这些多项式为K1，且com(K1)=D1，K2，且com(K2)=D2。在“正常”验证中，验证者会计算D1和D2，因为它们只是各自证明的G0∗值。在这里，证明者提供D1和D2，其余的工作就是证明它们是正确的。
• 为了证明D1和D2的正确性，我们将证明它们在一个随机点上是正确的。我们选择一个随机点t，并评估e1=K1(t)和e2=K2(t)。
• 证明者生成一个随机线性组合L(x)=K1(x)+rK2(x)（验证者可以生成com(L)=D1+rD2）。证明者现在只需要证明L(t)=e1+re2的证明。

验证者仍然需要执行一系列额外步骤，但这些步骤的计算复杂度均为O(1)或O(log(n))：评估e1=K1(t)和e2=K2(t)，计算两个Ki多项式的αi系数，进行椭圆曲线加法com(L)=D1+rD2。但这所有的计算工作所需时间远低于线性时间，因此总的来说我们仍然获得了好处：验证者在链条最顶端只需要自己做一次线性时间步骤来计算一个G0∗点。

这个技术可以很容易地推广到合并m>2个签名。

从合并IPA到合并基于IPA的SNARKs：Halo

现在，我们进入Halo协议的核心机制，该协议即将集成在Zcash中，使用这种证明合并技术来创建递归证明系统。设置非常简单：假设你有一个链，每个区块都关联一个基于IPA的SNARK（请参见这里了解基于多项式承诺的常规SNARK是如何工作的），证明它的正确性。你想要创建一个新区块，建立在链条的前一个小节的基础上。新区块应具有自己的基于IPA的SNARK，证明该区块的正确性。实际上，这个证明应同时涵盖新区块的正确性_和_前一区块的证据的正确性，涵盖整个前链。

单独的基于IPA的证明无法做到这一点，因为对一个声明的证明的验证时间大于直接检查该声明的时间，因此“证明的证明”的验证时间则更长。但是证明合并可以做到这一点！

实质上，我们使用常规的“递归SNARK”技术来验证证明，然而“证明的证明”部分仅仅证明了工作中的对数部分。我们添加了一条额外的聚合证明链，使用类似于上面证明合并方案的小技巧，来处理工作中的线性部分。为了验证整个链，验证者只需在链的最顶端验证一个线性时间的证明。

确切的细节在效率上与前一部分的确切证明合并技巧略有不同。我们不是使用证明合并技巧来合并多个证明，而是使用它于_单个_证明，只是为了重新随机化多项式所承诺的 G0∗ 需要评估的点。然后我们使用_相同_新选择的评估点来评估区块正确性证明中的多项式，从而使我们能够在单个IPA中一起证明多项式评估。

以数学形式表示：

• 让P(z)=a成为需要证明的前一个声明
• 证明者生成G0∗
• 证明者通过生成一个PLONK证明证明新区块的正确性以及上一个声明中对数部分的工作：QL∗A+QR∗B+QO∗C+QM∗A∗B+QC=Z∗H
• 证明者选择一个随机点t，并证明对线性组合{G0∗, QL, A, QR, B, QO, C, QM, QC, Z, H}在t的评估。然后我们可以通过用现在经过验证的评估替换每个多项式来检查上述方程，以验证PLONK证明。

更一般的增量验证

每个“步骤”的大小不需要是完整的区块验证；它可以小至虚拟机的单个步骤。步骤越小越好：这确保验证者最终在最后需要做的线性工作更少。唯一的下限是每个步骤必须足够大，以便容纳SNARK验证步骤的log(n)部分的工作。

但无论细节如何，这种机制使我们能够构建简洁且易于验证的SNARK，包括对递归证明的简单支持，使得随着计算的扩展可以实时扩展证明，甚至可以让不同的证明者来执行不同的证据工作，所有这些在没有配对或可信设置的情况下！主要缺点是相较于使用例如KZG基承诺的“简单”基于多项式的证明，还有一些额外的技术复杂性。

不仅限于多项式！合并R1CS证明

构建SNARK的一种常见替代方案是通过矩阵-向量乘法游戏构建SNARK。多项式和向量+矩阵都是SNARK协议的自然基础，因为它们是能够同时存储和计算大量数据的数学抽象，并且承诺方案允许验证者快速检查方程。

在R1CS中（更多详细描述见此处），一个游戏实例由三个矩阵A、B、C组成，解决方案是一个向量Z，满足(A⋅Z)∘(B⋅Z)=C⋅Z（该问题在实践中通常进一步限制，要求证明者使Z的一部分公开，并要求Z的最后一项为1）。

一个具有单一约束的R1CS实例（因此A、B和C宽度为1）以及满足条件的Z向量，注意这里Z出现在左边，且顶端位置为1而非底部。

与基于多项式的SNARK一样，这个R1CS游戏可以通过对A、B和C创建承诺，要求证明者提供（私有部分）Z的承诺，并使用华丽的证明技巧来证明(A⋅Z)∘(B⋅Z)=C⋅Z的方程来构成证明方案，其中∘表示逐项乘法，而无需完全透露这些对象的任何信息。与IPA一样，这个R1CS游戏也有证明合并方案！

Ioanna Tzialla等人描述了这样的方案，在一篇最新论文中（见第8-9页的描述）。他们首先通过引入扩展方程进行修改：

(A⋅Z)∘(B⋅Z)−u∗(C⋅Z)=E

对于“基本”实例，u=1，E=0，因此可以还原为原始R1CS方程。额外的松弛变量的添加使得聚合成为可能；聚合实例将具有其他的u和E值。现在，假设你有两个不同的u和E变量的同一个实例的解决方案：

(A⋅Z1)∘(B⋅Z1)−u1∗(C⋅Z1)=E1

(A⋅Z2)∘(B⋅Z2)−u2∗(C⋅Z2)=E2

这个技巧涉及到取随机线性组合Z3=Z1+rZ2，使得方程适用于这一新值。首先，我们计算左侧：

(A⋅(Z1+rZ2))∘(B⋅(Z1+rZ2))−(u1+ru2)∗(C⋅(Z1+rZ2))

这展开为以下表达（将1、r和r²的项分组在一起）：

(A⋅Z1)∘(B⋅Z1)−u1∗(C⋅Z1)

r((A⋅Z1)∘(B⋅Z2)+(A⋅Z2)∘(B⋅Z1)−u1∗(C⋅Z2)−u2∗(C⋅Z1))

r²((A⋅Z2)∘(B⋅Z2)−u2∗(C⋅Z2))

第一个项只是E1；第三个项是r²∗E2。中间的项与文首的交叉项（黄色+绿色区域）非常类似。证明者只需提供中间项（不带r因子），就像在IPA证明中，随机化迫使证明者保持诚实。

因此，也可以为基于R1CS的协议创建合并方案。有趣的是，我们甚至不需要在最后证明(A⋅Z)∘(B⋅Z)=u∗(C⋅Z)+E的情况下“简洁”的协议；不过，证明者可以通过直接打开所有承诺来辅助证明！这仍将是“简洁的”，因为验证者仅需验证一个实际上代表任意数量陈述的证明。然而，在实践中，实现最后一步的简洁协议更好，因为这使得证明更小，Tzialla等人的论文也提供了这样的协议（见第10页）。

回顾

• 我们尚未找到创建对大小为n的多项式的承诺的方法，使得该多项式的评估可以在<O(n)的时间内直接验证。我们能做的最好的是创建一个大小为log(n)的证明，其中所有验证它的工作都为对数时间除了最后一块O(n)的时间段。
• 但我们可以合并多个证明。给定m个对大小n的多项式的评估的证明，可以制作一个涵盖_所有_这些评估的证明，其验证所需的时间为对数加上一个大小为n的多项式证明。
• 通过一些巧妙的技巧，分离证明验证中的对数部分和线性部分，我们可以利用这一点构建递归SNARKs。
• 这些递归SNARK实际上比直接执行递归SNARK“直接”的方式更有效！事实上，即使在直接作为递归SNARK可行的情况下（例如，KZG承诺等证明），Halo风格的技术通常也是更有效的。
• 这不仅限于多项式；用于SNARK的其他游戏（如R1CS）也可以以类似智能的方式聚合。
• 无需配对或可信设置！

朝着更快、更高效和更安全的ZK-SNARK前进的步伐还在继续…

• 原文链接： vitalik.eth.limo/general...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～