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

详情请参考:

Dora Factory支持去中心化DAO研究组织DAOrayaki

历史文章:

DAO的构建与设计

DAO治理中的同构性

什么是社区贡献机会(CCO)?

DAOrayaki解读|8步实现去中心化

DAOrayaki|GitcoinDAO 群体思维正在崛起

DAOs的设计再思考:信任与决策权、风险、剩余索取权的分配

如何DAO化|基于社区贡献机会(CCO)机制的去中心化治理

通证工程共享(Token Engineering Commons):分析权益持有者、通证和治理过程

DAO 治理策略

DAOrayaki | Gas成本和选民参与

DAOrayaki|PoolHAUS与去中心化流动性供应

API3 DAO | DAO和质押的意义

Part 1D2D:面向去中心化的谈判协议

联合曲线设计脑洞大全及参数大典

Synthetix:去中心化治理结构

DAO 联盟|Open DeFi DAO 治理结构

DAO 投票治理

DAOrayaki|Vitalik Buterin:超越代币投票的治理

可选用的DAOs投票机制汇总

DAOrayaki解读|价格敞口和投票权

DAOrayaki | 去中心化仲裁:Kleros、Aragon、Jur

DAO代币治理

DAOrayaki|如何利用社交代币实现长期增长

DAOrayaki |代币经济学导论

Farming机制是否代表着代币分配的进步?

DAOrayaki|DAO 国库多元化的范围代币

DAOrayaki|DAO 通过财政多元化为下一个加密冬天做准备

DAOrayaki| DAO:扩展资本协调能力

Social token与DAO思潮下微观经济体的崛起

$WORK 奖励、利益相关者经济学和就业共享的代币化

海外最新研讨:数字货币与货币体系的未来

DAO治理攻击

DAOrayaki|DAO 的漏洞:自治的假想与治理弹性评估模型

DAOrayaki|公地弹性:去中心化技术社区治理中的“弹性”

DAOrayaki|算法治理实验:DAO治理动态、韧性及崩溃

DAOrayaki |加密市场操纵:威科夫方法及模式

DAOrayaki |加密货币里的吸血鬼攻击

DAOrayaki |依靠钱包追踪鲸鱼活动

DAOrayaki|全面综述:女巫攻击和防御方法

二次方融资(Quadratic Funding)的攻击与防守

一份前瞻性暂停使用The DAO的呼吁(2016.5.27)

二次方投票、融资资助

DAOrayaki|二次方投票与公共物品

DAOrayaki|二次方投票和区块链治理

DAOrayaki|关于改善配对协调补贴的一个方法探讨

DAOrayaki|二次方投票:机制设计如何使民主激进化

「激进市场」和二次方投票 | 用市场本身去监管市场

二次方资助V2协议: 抗女巫攻击、公平和规模化的链上二次方投票累进税系统提高二次方资助的公平性

二次方融资(Quadratic Funding)的攻击与防守

预测市场

预测市场的力量

万字解读| Upshot One 对等预测协议

买单投票:一种新型的混合代币投票/Futarchy

DAOrayaki|针对高度不可能事件押注的预测市场设计

Futarchy | 价值投票,对赌信仰,用钱说话,口说无凭

基于 Futarchy治理的案例:Amoveo、Tezos、Gnosis

罗宾·汉森经典论文(一)|Futarchy:我们应该价值投票、对赌信仰吗?

罗宾·汉森经典论文(二)|Futarchy:我们应该价值投票、对赌信仰吗?

罗宾·汉森经典论文(三)|Futarchy:工程设计25个问题

罗宾·汉森经典论文(四)|Futarchy:工程设计25个问题

公共物品、奥斯特罗姆

DAOrayaki|连续性公共物品资助

DAOrayaki|可追溯公共物品融资

DAOrayaki|二次方投票与公共物品

DAOrayaki|“可追溯公共物品融资”进展分析

DAOrayaki|公地弹性:去中心化技术社区治理中的“弹性”

自动化奥斯特罗姆(Ostrom)以实现有效的DAO管理

DAOrayaki 解读|奥斯特罗姆:公共事务的治理之道

NFT、NFT DAO

极客与画家 | 开源项目、NFT和简化的哈伯格税

DAOrayaki|全面概述NFT DAOs 的出现

价格发现的艺术,嵌套的策展市场,当联合曲线遇到NFT

策展市场|一种构建联合关注网络的机制

DAOrayaki|NFT 市场:去中心化的创造力还是 1990 年代的电子商务?

DAO 行业发展

加密技术的全面论述—开放金融系统

DAOrayaki解读|DAO与全球经济秩序-新自由主义的黄昏(一)

DAOrayaki首发| SEC.gov代币安全港提案2.0

DAOrayaki|DAO:可能的演变路径

DAOrayaki|去中心化自治组织(DAO)行业发展月报(2021.6)

DAOrayaki | DAO 行业9月上旬发展一览

DAO 媒体

DAOrayaki|Web3 中的声誉:乘风破浪

DAOrayaki|新媒体结构:所有权经济

DAOrayaki|文艺复兴时期的创造者和下一个媒体模式的崛起

DAOrayaki|去中心化媒体:web 3.0时代民主、隐私与价值共享的机遇

DAOrayaki|打破媒体第四面墙:观众和创作者的融合

DAOrayaki 生态合作

Muse Museum率先加入DAOrayaki Funders MolochDAO并开展联合研究