LOADING...
LOADING...
LOADING...
当前位置: 玩币族首页 > 币圈百科 > 如何通过“流水线模式”提高生成证明的效率?

如何通过“流水线模式”提高生成证明的效率?

2023-06-16 Fox Tech 来源:区块链网络

撰文:康水跃,Fox Tech CEO;孟铉济,Fox Tech 首席科学家;校对:林彦熹,Fox Tech CTO

前言

在当今的数字时代,随着区块链技术的迅猛发展,人们对于数据隐私和安全性的关注越来越高。为了实现更高效、可扩展的区块链应用,诸多解决方案被提出,其中之一便是零知识证明(Zero-Knowledge Proof)技术。零知识证明作为一种强大的密码学工具,可以在不泄露敏感信息的前提下,验证某个陈述的真实性。

近年来,zkRollup作为区块链扩容技术的重要创新之一,引起了广泛关注。zkRollup通过将大量交易打包,在链下执行,并利用零知识证明的特性来验证这些交易的正确性,从而显著提高了区块链的吞吐量和可扩展性。而在zkRollup的实现中,如何对交易进行分配打包,并生成证明,成为了zkRollup系统的重要组成部分。

在Layer1系统当中,交易以区块的形式被打包并由矿工来计算。而在Layer2系统当中,交易如何打包,或者说如何产生一个Layer2的块,需要单独的考量。

FOX是基于zkEVM的Layer2 zkRollup扩容的项目,对于这个问题,FOX正在探索使用流水线形式的处理方式来对交易分批处理,预期能够对效率产生很大提升。

本文将深入探讨流水线方式生成零知识证明在zkRollup中的应用。首先,我们将分析基本的交易打包方式。随后,我们将重点聚焦于流水线方式生成零知识证明的技术,详细分析其原理和应用场景。

常规的交易打包方式

在传统的区块链系统中,交易的确认和打包是一个耗时且资源密集型的过程。通常情况下,交易被逐个验证并添加到区块中,然后通过共识算法达成一致,使得区块链的状态得以更新。然而,这种逐个验证和打包的方式存在着明显的局限性,包括低吞吐量和高延迟等问题。

在常规的交易打包流程中,首先,一批待处理的交易会被收集起来,可以是用户提交的交易或者来自其他链上的交易。然后,这些交易会被验证,以确保其合法性和有效性。这些验证包括检查交易的签名、验证交易的有效性和一致性等。一旦交易通过了验证,它们将被打包成一个批次,形成一个待提交的区块。

而在zkRollup系统当中,用户提交的交易同样首先会被放在交易池中等待,在FOX系统当中,Sequencer会定期抓取交易池中的交易并本地执行以及排序,形成一个交易包,也就是区块,这个时候会将交易执行结果提交到Layer1,同时还要将这个结果以及交易数据提交给产生证明的Folder节点。

根据我们对零知识证明算法的基本了解(读者可以参考之前FOX的系列文章),Folder如果想要生成证明必须要得到输入以及执行完毕的结果,这就使得如果按照常规的方式进行,需要等待Sequencer将所有交易全都执行完毕再交给Folder。为了更加有效利用计算资源,我们希望让Sequencer在执行完一部分交易以后马上交给Folder进行证明生成。

FOX正在探索中的流水线处理模式

为了实现上述目标,我们需要让Sequencer对于交易分批执行并在执行完一批之后马上将中间结果发送给Folder。

具体来讲,假设交易包交易总数为100,单个批次交易数量为10,则流水线处理方式可以用下图来表示。

图1:流水线模式生成交易证明

接下来我们来简单分析一下两种方式的时间开销,并讨论一下在什么情况下使用流水线方式会有更高的效率。为了简化起见,这里的讨论没有考虑Sequencer将数据发送给Folder的时间。

设交易包的交易数量为n,批次数量为k,Sequencer的执行时间函数为exe(),Folder的证明生成时间函数为 prove(),聚合证明时间函数为aggr(),常规方式总时间为Sum1,流水线方式总时间为Sum2。

于是按照上述过程,常规方式依赖于Sequencer先进行执行然后Folder进行证明生成,所需要的总时间为

Sum1=exe(n)+prove(n)

而流水线方式的时间应该包括Sequencer对于第一批交易的执行时间,以及后边生成证明的时间和后续批次执行时间的较大者,还有最后的聚合时间。

Sum2=exe(n/k)+max{k*prove(n/k),(k-1)*exe(n/k)}+aggr(k)

所以比较二者总时长,执行时间函数exe()基本可以近似于线性函数,而对于prove(),由于FOX系统的证明算法证明生成时间为线性函数,故prove()也为线性函数。

可以得出结论:

若exe(n)>prove(n),则当prove(n)>aggr(k)时,Sum1>Sum2.

若exe(n)<prove(n),则当(k-1)exe(n/k)>aggr(k)时,Sum1>Sum2.

所以说,如果聚合时间aggr(k)足够小,且证明生成时间为线性函数,则采用流水线方式非常有助于提升系统效率,减少总的生成证明时间。

上述的分析只对线性时间证明算法成立,从这一点也可以看出FOX采用线性时间证明算法的重要性。

图2:证明计算流程图

之所以说流水线方法处于正在探索的状态,是通过对于这种模式的分析我们可以看出,每一个交易包被分成的批次越多,Sequencer需要记录和传输给Folder的数据就越多,开销就越大,但是对于Folder而言,单次处理的计算量会降低一些,聚合的过程会更复杂。所以具体如何分割,是一个需要权衡的问题,也具体地依赖于Sequencer和Folder的计算性能。

对交易进行高效分配打包从而逐批生成证明是关键优化点

在 zkRollup 实现中,高效地对交易进行分配打包并生成证明是关键的优化点。FOX正在不断地优化模式,寻找更加高效的解决方案。下面是FOX采用的基本流程:

交易收集:收集待处理的交易,并将其存储在一个交易池中。这些交易可能是用户提交的交易,或者是其他系统或合约产生的交易。

交易排序:对交易池中的交易进行排序,以确定打包的顺序。通常,可以使用基于优先级、时间戳或其他因素的排序算法。排序的目标是最大化交易的整体吞吐量和效率。

交易分配:将排序后的交易分配到合适的区块中。在 zkRollup 中,通常会创建一个新的区块来容纳一定数量的交易。分配的过程可以使用贪婪算法或其他分配策略,以最大化每个区块的容量利用率。

区块打包:对已分配的交易进行打包,形成一个完整的区块。在FOX的Layer2架构当中,这个区块实际上只包含了交易的摘要信息,这个摘要信息可以是交易的哈希或其他形式的紧凑表示,而不是交易的详细内容,详细的交易信息会被存储在FOX的Ringer当中,从而实现数据可用性(DA)。

证明生成:对打包后的区块生成相应的证明。这个证明应该能够证明区块中每个交易的有效性,以及整个区块的一致性。FOX的流水线模式主要应用于这个环节,用来更高效地利用Folder算力,将一个区块当中的交易分批地传送给Folder进行证明生成。Folder分别对每批交易计算正确性证明,最后再聚合起来。通常,这个证明是基于FOAKS这种快速有针对性的零知识证明算法,通过将区块中的交易与状态转换规则进行比对,验证它们是否遵循了系统的规则和约束。

证明验证:接收方可以使用证明来验证区块的有效性,而无需重新计算整个区块。这个验证过程可以是高度有效的,因为它只涉及对证明的检查,而不需要对交易进行复杂的计算。

FOX的“流水线模式”主要发生在证明生成这个环节。在交易收集和排序中,Sequencer 收集待处理的交易,并按照某种规则对它们进行排序,确定执行的顺序。在此后的交易分批执行中,Sequencer 将排序后的交易分批执行。每批中的一组交易被发送给执行引擎进行处理。执行引擎模拟执行这些交易,并记录状态转换的中间结果。在每批交易执行完之后,Sequencer 将中间结果发送给Folder。

这可以通过将中间结果编码以状态更新、交易哈希等形式逐批发送给Folder的通信通道来完成。Folder在接收到各批中间结果后会使用这些结果,从而逐批地生成相应证明。这些证明的生成基于FOX自研的FOAKS零知识证明的算法,其使用中间结果作为输入,来证明交易的有效性和整个区块的一致性。

最后一步是证明验证。生成的证明被发送给验证方,即部署在Ethereum的智能合约Verifier,以验证区块的有效性。Verifier使用验证算法对证明进行检查,以确保其正确性和合法性。

通过这种流水线方式,Sequencer 可以在执行交易的同时,不断将中间结果发送给Folder,从而逐批地进行证明的生成。这可以提高整个系统的效率和吞吐量,同时减少了证明生成的延迟。

结语

本文介绍了在zkRollup当中,一种比较新颖的对于交易分批次处理生成证明的方案,流水线方式,并且详细分析了这种方式的时间开销,对于线性证明算法而言,合理的使用流水线方式可以有助于减少总的证明生成时间。FOX采用的证明系统就实现了线性证明时间,对于快速生成证明和提升用户体验都有着很大的帮助。FOX团队将会不断探索并优化这个方案。

查看更多

—-

编译者/作者:Fox Tech

玩币族申明:玩币族作为开放的资讯翻译/分享平台,所提供的所有资讯仅代表作者个人观点,与玩币族平台立场无关,且不构成任何投资理财建议。文章版权归原作者所有。

LOADING...
LOADING...