DAOrayaki ｜Halo以及未来：探索无需pairings的增量验证以及SNARKs技术

Zero-knowledge and layer2

a year ago • 18 min read • Loading Views

DAOrayaki DAO研究奖金池：

资助地址: DAOrayaki.eth

投票进展：DAO Committee 3/7 通过

赏金总量：150USDC

研究种类：Blcokchain, ZK

原文作者：Vitalik

贡献者：Zeo THUBA, DAOctor @DAOrayaki

原文：Halo and more: exploring incremental verification and SNARKs without pairings

DAOrayaki 是一个去中心化的研究者组织和去中心化媒体，通过 DAO的形式去中心化地资助世界各地的研究者进行研究、翻译、分析等工作。DAOrayaki 由早期的 DAO 组织 DAOONE 核心成员发起，得到了Dora Factory基础设施的支持。欢迎通过文末方式提交DAO的研究，瓜分10000USDC赏金池！了解去中心化自治组织（DAO），探讨最新治理话题，关注DAO的发展趋势，欢迎加入DAOrayaki社区！

特别感谢Justin Drake和Sean Bowe的精彩和周到的反馈和审查，以及Pratyush Mishra的讨论，为原版的IPA的解释做出了贡献。

一直密切关注ZK-SNARKs领域的读者应该已经对ZK-SNARKs[1]的工作原理非常熟悉了。ZK-SNARKs的验证基于检查等式是否成立，其中进入等式的元素是数学抽象，如多项式2，可以保存大量数据。主要有三类的加密技术允许我们简洁地表示这些抽象：默克尔树(用于FRI[4])

1/默克尔树(用于FRI[4])

2/常规椭圆曲线(用于内积参数(IPAs)[5])

3/带pairing和可信启动的椭圆曲线(用于KZG承诺[6])

这三种技术带来了三种类型的证明：FRI带来了STARKs, KZG承诺带来了“常规”SNARKs，基于ipa的方案带来了防弹证明。这三种技术有非常不同的权衡：

到目前为止，第一种和第三种受到了最多的关注。原因与表中第二行最右列有关：IPA需要线性的验证时间。这意味着，即使证明的大小很小，验证证明所需的时间总是比自己运行计算所需的时间要长。这使得IPAs完全无法与扩展性强的ZK-SNARK抗衡：使用基于IPA的参数来证明以太坊块的有效性是没有意义的，因为验证证明将花费比自己检查块更长的时间。另一方面，基于KZG和FRI的证明，确实比自己做重复计算更快，所以显而易见应该选择这两个中的一个。

然而，最近有大量的研究将多个IPA证明合并为一个证明的技术。这方面的大部分初始工作是作为设计Halo协议[7]的一部分完成的，该协议将进入大零币[8]。这些合并技术的开销不大，并且一个合并的证明所花费的验证时间并不比一个单独的证明所花费的时间长。

这使得我们在使用IPAs的路上更进一步：相较于花费 O(n) 的时间去检验复杂度为 n 的计算及附带的证明，我们可以将复杂度为 n 的计算拆分为更小的复杂度为 k 的计算，生成 n/k 个证明，然后将这些证明合并，使得验证者的工作复杂度下降到比 O(k) 稍微多一点。

这些技术还允许我们进行增量验证：如果不断引入需要证明的新内容，你可以继续使用现有的证明，将其与新命题的证明混合，得到新的混合证明。这对于验证整个区块链的完整性非常有用。

那么这些技术是如何工作的，它们能做什么呢?这正是这篇文章的主题。

背景:内积参数IPA是如何工作的?

内积参数是一种可以适用于许多数学结构的证明方案，但通常我们关注的是椭圆曲线点[9]上的IPAs。IPAs可以通过简单的椭圆曲线实现，理论上甚至可以通过比特币和以太币的secp256k1[10]（尽管一些特殊的属性可以使FFTs[11]更高效）；不需要极其复杂的pairing方案，尽管我已经写了一篇解释文章[12]和一个实现[13]，但我自己仍然很难理解这些方案。

我们从承诺方案开始，也就是通常称为的Pedersen vector commitments。为了承诺阶小于 n 的多项式，我们首先公开选择一系列基础点，G0,…,Gn-1。这些点可以用伪随机算法产生，任何人可以重新执行来验证（例如，Gi的x坐标可以是hash(i, j)，对于最小的能得出合法点的整数 j）；请注意，这并不算是可信启动，因为并不依赖于任何特定的参与方引入隐私信息。

可以看出来：如果将 C+L+R 加一起（C是原来的承诺，蓝色部分），新组合的点表现为4个点的和而不是原来8个点。现在，证明者可以只提供四个和，表示每个新方块的宽度。再重复这个协议两次，我们就得到了一个完整的平方，验证者可以通过发送一个表示其宽度的值来证明它。

但是这里有个问题：如果 C 在某些地方有问题（例如证明者增加额外的点 H），攻击者可以从L 或者 R 中间减去 H 来消除这一点。我们通过在证明者提供 L 和 R 之后随机扩展点，来解决这个问题。

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

复习一下几个要点：

扩展到多项式计算

那么，我们如何合并这些证明呢?

https://ssimg.frontenduse.top/article/2021/11/17/e6ad711558bef984c09cf5e25417fdcc.png?x-oss-process=image/format,webp

https://ssimg.frontenduse.top/article/2021/11/17/354812e1d10d7db7841f43df349e9f06.png?x-oss-process=image/format,webp

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

现在，我们进入到Halo协议[7]的核心机制，Halo已经集成到ZCash中。Halo使用这种证明合并技术来创建一个递归证明系统。启动很简单：假设你有一个链，其中每个块都有一个对应的基于IPA的SNARK来证明它的正确性(参见这里[2]关于多项式承诺的一般SNARKs如何工作)。您希望创建一个新块，构建在前面的链之上。新区块应该有自己的基于IPA的SNARK来证明该区块的正确性。事实上，这个证明应该既包括新区块的正确性，也包括前一个区块对之前整个链正确性的证明。

基于IPA的证明本身无法做到这一点，因为验证一个命题的证明需要比检查该命题本身花费更长的时间，所以验证一个证明的证明需要比两个证明单独验证花费更长的时间。但是证明合并可以做到！

https://ssimg.frontenduse.top/article/2021/11/17/ae547b07ede8b30964c430eafb6f97bc.png?x-oss-process=image/format,webp

本质上，我们使用通常的“递归SNARK”技术来验证证明，除了“证明的证明”的部分只是证明工作的对数部分。我们添加了一个额外的聚合证明链，使用类似于上面的证明合并方案的技巧，来处理线性部分的工作。为了验证整个链，验证者只需要验证链最后的一个线性时间证明。

由于效率的原因，具体的细节与前一节中具体的结合证明技巧有些不同。我们不是用组合证明的技巧来组合多个证明，而是将该技巧用在单个证明上，只是为了重新随机化这个多项式需要计算图片的点。然后，我们使用相同的新选择的评估点来评估多项式的证明块的正确性，这允许我们在一个单一的IPA中一起证明多项式的评估。

https://ssimg.frontenduse.top/article/2021/11/17/9e800ccddff0fea320b23b5865d4c618.png?x-oss-process=image/format,webp

更加泛化的增量证明

每个“步骤”的大小不需要是一个完整的块验证；它可能小到虚拟机中的一个步骤。步骤越小越好：它确保了验证者最终必须做的线性工作更少。唯一的下限是，每个步骤必须足够大，以包含一个SNARK来验证每一步中log(n)部分的工作。

但忽略掉细节,这种机制允许我们做出简洁和容易证明的SNARKs，包括简单支持递归的证明，允许你随着计算的扩展实时扩展证明，甚至有不同的证明者完成证明工作的不同部分，这些还不需要pairing或可信启动！相比于“简单”的基于多项式的证明（例如基于KZG的证明），主要的缺点是一些额外的技术复杂性。

https://ssimg.frontenduse.top/article/2021/11/17/b4d95b0e49a1548f20091013bd46cf55.png?x-oss-process=image/format,webp

不只是多项式！合并R1CS证明

在多项式游戏「译者注：密码学中很多协议称为一次游戏」中构建SNARKs的一个常见替代方法是在矩阵向量乘法中构建SNARKs。多项式和向量+矩阵都是SNARK协议的天然基础，因为它们是数学抽象，可以同时存储和计算大量的数据，并且允许验证者快速检查方程的承诺方案。

R1CS(这里[3]有更详细的描述)，一个游戏的实例包括三个矩阵A, B, C和一个向量Z表示的解决方案使得(A·Z)\circ(B·Z)=C·Z（问题是经常在实践中进一步要求验证方公开Z的一部分以及要求Z的最后一项为1)。

https://ssimg.frontenduse.top/article/2021/11/17/c7a3b4e6b3e773bd98e5319deb3b7f11.png?x-oss-process=image/format,webp

只有一个约束的一个R1CS实例（所以A, B, C的宽度为1），有一个符合约束的向量Z，但是注意，这里Z出现在左边，1在顶部位置而不是底部位置。

就像基于多项式的SNARKs，这个R1CS游戏可以通过创建A, B, C的承诺，变成一个证明方案，要求证明者提供向量Z的承诺（隐私部分），然后使用新奇的证明技巧来证明方程,这样乘法,哪里没有完全揭示这些对象。就像IPAs一样，这个R1CS游戏有一个证明合并方案！

https://ssimg.frontenduse.top/article/2021/11/17/d399349da47f94a27a6891a324b1e116.png?x-oss-process=image/format,webp

https://ssimg.frontenduse.top/article/2021/11/17/43e00bf3f84a508a4c4e73126485f827.png?x-oss-process=image/format,webp

再复习一下几个要点

我们不知道一种方法能对规模为n多项式作出承诺，使得可以直接在<O(n)的时间内验证。我们能做的最好的就是做一个大小为log(n)的证明，所有需要验证的工作都是对数复杂度，除了最后一个时间消耗O(n)的部分。

但是我们能做的是合并多个证明。给定m个规模为n的多项式计算的证明，你能生成一个证明包含所有计算，验证需要花费对数时间工作加上一个规模n的多项式证明。

附带一些机智的小技巧，从验证的线形部分拆分出对数部分，我们能利用这个做出递归的SNARKs

这些递归的SNARKs实际上比“直接”进行递归的SNARKs更有效！事实上，即使在直接递归SNARKs是可能的场景中（例如。使用KZG承诺的证明），我们也通常使用halo模式的技术，因为它们更有效率。

这不仅仅是关于多项式;在SNARKs中使用的其他游戏，如R1CS，也能以类似的方式进行聚合。

不需要pairing或可信启动！

ZK-SNARKs正在朝着更快、更高效、更安全的方向前进……

参考文献

[1] https://vitalik.ca/general/2017/02/01/zk_snarks.html

[2] https://vitalik.ca/general/2021/01/26/snarks.html

[3] https://vitalik.ca/general/2016/12/10/qap.html

[4] https://vitalik.ca/general/2017/11/09/starks_part_1.html

[5] https://twitter.com/VitalikButerin/status/1371844878968176647

[6] https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html

[7] https://eprint.iacr.org/2019/1021.pdf

[8] https://electriccoin.co/blog/halo-arc-for-zcash-proposed-for-release-later-this-year/

[9] https://en.wikipedia.org/wiki/Elliptic_curve

[10] https://en.bitcoin.it/wiki/Secp256k1

[11] https://vitalik.ca/general/2019/05/12/fft.html

[12] https://vitalik.ca/general/2017/01/14/exploring_ecp.html

[13]https://github.com/ethereum/py_ecc/blob/master/py_ecc/bls12_381/bls12_381_pairing.py

[14]https://hackernoon.com/what-is-the-math-behind-elliptic-curve-cryptography-f61b25253da3

[15] https://hackmd.io/yA9DlU5YQ3WtiFxC_2LAlg

[16] https://github.com/ethereum/research/blob/master/bulletproofs/ipa_commitments.py

[17]https://ethresear.ch/t/simple-guide-to-fast-linear-combinations-aka-multiexponentiations/7238

[18] https://vitalik.ca/general/2019/09/22/plonk.html#putting-it-all-together

[19] https://eprint.iacr.org/2021/1263.pdf

通过 DAO，研究组织和媒体可以打破地域的限制，以社区的方式资助和生产内容。DAOrayaki将会通过DAO的形式，构建一个满足人们需求，一个民主治理和所有人都可以利用的公共媒体系统，从而实现真正意义上的去中心化。欢迎通过以下方式提交DAO的研究，瓜分10000USDC赏金池！了解去中心化自治组织（DAO），探讨最新治理话题，关注DAO的发展趋势，欢迎加入DAOrayaki社区！

欢迎加入DAOrayaki社区！

官方网站：daorayaki.org

Discord server: https://discord.gg/2UjpmPH9

Medium: https://medium.com/@daorayaki

Email: daorayaki@dorafactory.org

微信助手：DAOrayaki-Media