最新快讯
7小时前
以太坊开发者大会 EDCON 2024 年度会议将在日本举办
ChainCatcher 消息,以太坊开发者大会之一 EDCON (Community ETHereum Development Conference )2024 年度会议将在日本举办。 据了解,EDCON 是由 Linktime、De University of Ethereum 和 ETHPlanet 组织的非营利性全球年度以太坊会议,致力于服务以太坊生态系统,促进全球以太坊社区的互动和交流。 自 2017 年开办以来,已汇集了超 10,000 名参会者、2000 多名开发人员、300 多名演讲者、450多个项目、400 多个支持者参与活动,线上活动期间的在线观看量更是突破了 300,000+。(来源链接)
11小时前
香港证监会:虚拟资产交易平台营运营牌照自 6 月 1 日起申领
ChainCatcher 消息,据香港证监会消息,6 月 1 日《适用于虚拟资产交易平台营运者的指引》生效。香港证监会表示欢迎已准备好遵守证监会标准的虚拟资产交易平台营运者申领牌照。无意申领牌照的营运者,则应着手以有序方式结束其于香港的业务。 这标志香港大力推进的全球虚拟资产中心建设获重大进展。业内人士已整装待发。部分迫不及待表示将第一时间提交申请。(来源链接)
12小时前
《侠盗猎车手6》或将引入加密货币奖励
ChainCatcher 消息,知名动作冒险游戏系列《侠盗猎车手》(GTA)或将在其即将推出的游戏升级版本《侠盗猎车手6》(GTA 6)中引入加密货币奖励,这款预计将于2023年或2024年发布的游戏拟整合区块链技术来实施基于加密货币的奖励系统,并且预计将把比特币作为支付方式和奖励代币之一。 截至目前,《侠盗猎车手》游戏开发商Rockstar Games尚未发布有关(添加)加密资产的官方声明,而该公司此前曾表态禁止第三方服务器使用加密货币或NFT。(来源链接)
12小时前
Curve Finance 首席执行官斥资 5925 万美元在澳大利亚购买两处豪宅
ChainCatcher 消息,据澳大利亚《金融评论报》报道,Curve Finance 首席执行官 Michael Egorov 与其妻子 Anna Egorova 在墨尔本购买两处豪宅。 据悉,去年 3 月,他们以 1825 万美元购买名为 Verona 的意大利式豪宅,面积为 1412 平方米。近日,他们又斥资 4100 万美元购买于 1890 年建造的 Avon Court 豪宅,占地面积 4251 平方米。(来源链接)
13小时前
DeFi Hub 项目 Nibiru Chain 宣布其激励测试网 NIT 第三阶段已上线
ChainCatcher 消息,社区驱动的 DeFi Hub 项目 Nibiru Chain 近日宣布,其激励测试网 NIT 第三阶段已经上线,用户参与 Perps、Spot AMM 等相关任务可获得 ATOM 作为奖励。 ChainCatcher 此前报道,Nibiru Chain 以 1 亿美元估值完成 850 万美元种子轮融资,Tribe Capital、Republic Capital、NGC Ventures 和 Original Capital 领投。 据悉,今年夏天,Nibiru 计划推出其部分算法稳定币 NUSDC 以及测试网。NUSD 将由 USDC 和 NIBI 抵押,NIBI 是 Nibiru 的原生代币,用于质押、效用和治理。(来源链接)
查看更多
扫码下载链捕手APP
专业的区块链资讯、数据与研究平台

为什么说 zkRollup 的可行性起源于零知识证明的计算代理思想?

Fox Tech
以太坊扩容动态与分析
2023-04-07 15:15
收藏
zkRollup中使用的零知识证明算法的计算代理程度需要被精心设计,必须恰到好处才能使其整体达到最佳效率。而FOAKS算法通过自身迭代的递归实现了可以调节的计算代理,是为专门为zkRollup所设计的零知识证明算法。

作者:Fox Tech CTO 林彦熹,Fox Tech 首席科学家 孟铉济

 

前言

Prover和Verifier之间的计算代理思想是零知识证明的核心内容之一,是调节证明者和验证者工作量于复杂度之间取舍(trade-off)的工具。不同的零知识证明算法本质的不同在于不同程度的计算代理;高度的代理虽然会使验证的计算容易,但是却可能使得证明的复杂度高,从而导致证明耗时长,或是生成的证明大小较大;反之,低程度的代理会使得验证者的开销较大。

image

图1: 零知识证明的计算代理程度影响

计算代理是什么

随着以太坊上应用和用户的扩展,以太主网上的拥堵程度不断提升,使用zkRollup进行Layer2的扩容成为一个很有吸引力的方案,FOX就是专注于使用FOAKS算法进行zkRollup的项目。而zkRollup的可行性,本质上在于使用的零知识证明算法的原理可行性。简单来说,零知识证明算法实现的功能是使得证明者向验证者证明某件事,但又不透露任何关于这件事的信息。zkRollup的构造就是利用了这个性质,使得Layer2的节点可以执行原本在Layer1进行的计算,同时向Layer1节点提供计算正确性的证明。

从更广义的角度来说,上述的过程我们可以理解为,由于验证者(Layer1节点)计算能力有限,所以将这部分的计算代理给了证明者(Layer2节点)来执行,证明者完成了这个任务,需要返回结果给验证者。从这个角度来说,我们可以说,零知识证明算法使得保障正确性的“计算代理”得以实现。从宏观上这种计算代理的例子可以表现为zkRollup这种形式的应用,具体到零知识算法当中,这种计算代理的思想也有各种应用。

本文主要介绍FOAKS使用的在Orion当中提到的Code-Switching所做的令证明者帮助验证者执行的验证计算过程,以及FOAKS如何应用这种技巧进行递归。从而减少了证明的大小以及验证者的开销。

 

为什么需要计算代理

 

从系统的实用性角度来说,很多情况下计算节点的算力是有限的,或者说计算资源是很宝贵的。例如在Layer1链上的所有计算(包括转账以及合约调用)都需要经过所有节点的共识,并且用户需要为此支付高昂的手续费。所以,在这种情况下,将本来由共识节点来处理的计算“代理出去”交给链下节点来完成,就是一种自然的想法,避免消耗链上资源。而这也正是FOX所专注的链下计算服务。

从密码学理论角度来讲,在GMR模型当中限定了证明者拥有无限计算能力,验证者拥有多项式计算能力。如果验证者也有无限能力,则零知识证明的基本性质无法满足。所以自然地,将计算向证明者一方倾斜,让证明者承担更多的计算就是很多零知识证明算法设计都会考虑的问题。

当然,为了实现这一点,我们需要特别的技巧。

 

Code Switching

 

这一节介绍Orion当中使用的Code Switching技巧。Orion和FOAKS都使用了Brakedown作为多项式承诺方案,而Code Switching是在Orion当中命名的有证明者代替验证者执行验证计算的过程。

在《一文了解FOAKS当中的多项式承诺协议Brakedown》一文当中我们曾经介绍过,验证者的验证计算为以下的过程:

idxI,C0[idx]==<0,C1[:,idx]>and EC(y0)==C0

 idxI,C1[idx]==<r0,C1[:,idx]>and EC(y1)==C1

现在如果令证明者承担这部分计算,则证明者除了执行这些计算,还要附上证明值来证明自己的计算是正确的。

做法是将上述等式同样写成R1CS电路:

Statement:

EC(y0)=C0, EC(y1)=C1

idxI,C0[idx]=<0,C1[:,idx]>and EC(y0)=C0

idxI,C1[idx]=<r0,C1[:,idx]>and EC(y1)=C1

y=<r1, y1>

idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx’s Merkle tree proof is valid.

之后使用Virgo算法进行验证。

 

FOAKS当中的计算代理

在FOAKS当中同样使用类似的技巧完成计算代理,值得一提的是,FOAKS由于使用了Fiat-Shamir heuristic技巧实现了非交互式证明。想要了解更多,读者可以参考《如何将交互式证明改造为非交互式?Fiat-Shamir Heuristic!》。所以FOAKS的挑战生成和Orion所使用的Code Switching方法不同,电路当中也需要加入新的等式:

0=H(C1,R, r0,r1)

I=H(C1,R, r0,r1,c1,y1,c0,y0)

这样之后FOAKS当中的证明者同样生成了代理验证者进行验证的计算证明。而对于验证证明的过程,FOAKS利用算法自身进行迭代,这也是FOAKS实现递归的关键内容。具体内容见《如何设计出一种精妙绝伦的证明递归方案》。

通过一定次数的迭代可以使得证明的大小被压缩,从而极大降低验证者的计算负担以及通信复杂度。这就是FOAKS这个零知识证明方案对FOX这条zkRollup的重大意义。

 

结语

zkRollup中使用的零知识证明算法的计算代理程度需要被精心设计,必须恰到好处才能使其整体达到最佳效率。而FOAKS算法通过自身迭代的递归实现了可以调节的计算代理,是为专门为zkRollup所设计的零知识证明算法。

参考文献

1.Orion: Xie, Tiancheng, Yupeng Zhang, and Dawn Song. "Orion: Zero knowledge proof with linear prover time." Advances in Cryptology–CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022.

以太坊扩容动态与分析
追踪以太坊各大扩容解决方案动态,解读各大扩容方案趋势与未来
链捕手ChainCatcher提醒,请广大读者理性看待区块链,切实提高风险意识,警惕各类虚拟代币发行与炒作,站内所有内容仅系市场信息或相关方观点,不构成任何形式投资建议。如发现站内内容含敏感信息,可点击 “举报”, 我们会及时处理。