《关于防范以“虚拟货币”“区块链”名义进行非法集资的风险提示》

Layer2扩容关键技术:递归零知识证明剖析

网络转载 11743 2021-03-30 17:10

在Layer2扩容赛道上,ZkRollup方案以完美的数据可用性以及与Layer1同等级的安全性,备受青睐;以单个Block为处理单元,用零知识证明算法来保证此区块引起的世界状态变化的有效性,大幅降低了每笔交易的上链成本,同时也增长了系统的吞吐效率。然而,在实际的落地过程中,研究者们发现,简单的ZkRollup方案带来的扩容效果,并不能满足真实的场景需求;这和很多因素有关,电路参数的限制,零知识证明算法的效率等等;研究者们做了很多努力,比如对零知识证明算法进行加速,配备超高配置机器,优化电路规模等,虽带来了一定的性能提升,但仍难以满足需求。

研究者们当然希望,链上一次处理的交易越多越好。朝着这个目标出发,研究者们首先发现了聚合证明(Aggregation proof)技术,该技术已经被ZKSwap推出的ZKSpeed扩容方案采用。在前面的文章中,已经解释了聚合证明(Aggregation proof)的原理和思想,简单来说就是把多个区块的证明聚合成一个证明,使得链上一次就可以完成多个区块的验证,大大的降低了交易的平均成本,其原理如下图所示:

零知识证明 该方案虽然有优势,可实现多个区块的证明的一次验证,但也有其一定的局限性:

1. 一次聚合的区块是有上限的,受限于电路参数的限制;

2. 聚合的区块越多,电路就越大,直到其规模的上限;这种电路生成的证明时间要更长,证明密钥和验证密钥也会占用更大的存储空间;

3. 目前可支持的最大聚合粒度是20个区块,也就是凑齐20个区块后,才会开始聚合处理。如果生成证明的效率比较低,这会导致这些区块被确认的时间拉长,尤其是最早生成的那些区块;

受限于证明计算(Proof computation)和CRS生成复杂度的限制,上述的零知识证明算法是不可扩展的。因此,研究者们也在努力寻找一个可扩展的零知识证明算法,即Scalable zk-SNARKs

Scalable zk-SNARKs 可拓展的zk-SNARKs

在论文《Scalable Zero Knowledge via Cycles of Elliptic Curves》中,Eli Ben-Sasson等给出了Scalable zk-SNARKs的定义:

1. Key generation is cheap:即,Key生成的时间和计算复杂度没有关系(如果是Scalable zk-STARKs,可能不需要);

2. Proof generation is carried out incrementally:即,证明生成过程既包含了当前执行步骤的正确性又包含了在此之前所有计算的正确性,这种zk-SNARKsincrementally computable

为了方便大家理解,用一张图来表示上述思想:

零知识证明上图表示意思是:证明着证明一个递归计算过程,即:初始状态为S0,经过t次函数F迭代计算后的结果为St(像极了区块链里区块更新的过程)。

第一个计算方式,Monolithic option:证明方P把t次计算过程全部写成电路,然后一次性证明,正如我们前面所列举的一样,存在相同的局限性,很高的时间复杂度和空间复杂度;

第二个计算方式,Recursive option:递归计算,其过程如下:

1. 首先对于初始状态S0=>S1,证明方P对于S1 = F(S0)计算过程生成一个证明π1;

2. 对于S1=>S2的转换,由图中可以得知,证明方P证明了两部分:{S2 = F(S1), V(S1, π1) = 1},前半部分保证了当前计算的有效性,后半部分保证了上一步计算过程的有效性;由于在zk-SNARKs里,证明生成的时间比原始计算要快一些,因此,对于验证过程进行证明是合理的;

由此可以看出, Recursive option满足Scalable zk-SNARKs了基本要求:

1. Key的生成和循环次数没有关系,取决于单次F的复杂度,如果是general zk-SNARKs,只取决于安全参数;

2. 证明满足incrementally computable,每个证明都包含了在此之前所有计算的有效性;

3. 证明的大小固定,和迭递归次数t没有关系;

由上可知,Scalable zk-SNARKs采用了Recursive思想,即当前的Prove过程包含上一步的验证过程电路,具体如下图所示:

零知识证明可以看到,P2证明电路里,包含了上一步P1的验证过程电路。需要注意的是,P1对应的V在域Fq上,P2的证明过程在Fr上,如何在Fr上表示V的算术电路,是一个值得探讨的过程;由于Cv可以看作是P的一个子电路,因此,q需要满足 q = #E(Fr)或者 q 整除 #E(Fr),即q 整除rk - 1,因此:

尝试1. 理想的情况下,如果 r = q,那么在Fr上,能完美表示Fq上的V的算术电路,但是根据上述原理,r != q恒成立;

尝试2. 对于q != r,因为需要在Fr上去模拟Fq上的计算,会导致计算复杂度的提高log(r)倍;

尝试3. 采用椭圆曲线循环(cycle of elliptic curves),可以完美实现Recursive过程;

具体的,选取两个大素数,r和q。满足r = #E(Fq)和q = #E(Fr),即,当前群的域等于另外一个群的阶,反之亦然。因此,域Fq上的证明方P可以完美的在Fq上实现Fr上的验证电路,域Fr上的证明方P也可以在Fr上实现Fq上的验证电路;因此不会出现尝试2里面的缺陷。

下面表格列举常用的cycle of elliptic curveshttps://eprint.iacr.org/2014/595.pdf

零知识证明

写在最后

通过采用递归证明组合密码技术(Recursive Proof Composition),zk-SNARKS变成了Scalable zk-SNARKs,实现了更高效、简洁的零知识证明算法,并能真实的落地应用。即将发布主网的Mina就采用了这种技术实现了简洁的区块链,即固定大小的链,保持在22KB左右;同时,其他的技术团队包括Matter Labs、starkWare等也在计划采用Scalable zk-SNARKs技术来实现Layer2更高的扩容。ZKSwap团队在Layer2赛道上持续发力,在Scalable zk-SNARKs上亦有所突破,相信不久就会应用于新的版本上。

声明

1. 本文经授权发布,如若转载,请标注文章来源和作者;

2. 伊甸网登载此文出于传递更多信息之目的,并不意味着赞同其观点或证实其描述;

3. 文章内容仅供参考,不构成投资建议,投资者据此操作,风险自担。

相关文章
速览 BTC、BCH、BSV 三者的分歧处以及各自优劣势
2017 年从 BTC 中分叉出 BCH,2018 年 BCH 分裂为比特大陆系 BCHABC(前者后来拿回 BCH 称号)与 Nchain 系 BCHSV(后来命名为 BSV
Dapper Labs 75亿美元的估值是“玩”出来的?
伊朗男孩和他的75亿美元NFT帝国。
打破科技巨头的垄断,开启一场去中心化互联网的革命
去中心化网络的优势在互联网的未来中逐渐显现。
三分钟读懂 NuCypher 与 Keep Network 合作推出的 tBTC v2
tBTC 即将回归,能撼动 WBTC 的垄断地位吗?
ULIAN榴莲交易所2021年全球战略布局:“产品+市场+合规”三驾马车并行
ULIAN榴莲交易所的合规化运营已经获得了阶段性的巨大成果。ULIAN榴莲交易所于近期获得美国MSB 牌照。
04-21 18:30
详解“比特币”杀手 Chia 及硬盘挖矿操作流程
矿工开始用硬盘挖币,电商库存几乎被一扫而空。
超级空投!狗狗币生下小狗币,会是下一个百倍币吗?
狗哥已经领涨了百倍,小狗币会有什么表现?
5 月 8 日上线 DFINITY 有哪些生态?
本文介绍 DFINITY 已有的生态。
币安销毁近6亿美元BNB意味着什么
4月16日,币安宣布在第15次BNB季度销毁中(2021年1月-3月),共计销毁 1,099,888 BNB,此次销毁的BNB价值 595,314,380 美元。
风投Multicoin:为什么我们下注NFT平台REALY
REALY在币安智能链上推出了他们的产品,并且还将部署在Solana,进一步降低交易成本。
生态系统NFT 04-21 14:18
7x24H 快讯