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

撰文：康水跃，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，则流水线处理方式可以用下图来表示。

接下来我们来简单分析一下两种方式的时间开销，并讨论一下在什么情况下使用流水线方式会有更高的效率。为了简化起见，这里的讨论没有考虑 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 采用线性时间证明算法的重要性。

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

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

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

1. 交易收集：收集待处理的交易，并将其存储在一个交易池中。这些交易可能是用户提交的交易，或者是其他系统或合约产生的交易。
2. 交易排序：对交易池中的交易进行排序，以确定打包的顺序。通常，可以使用基于优先级、时间戳或其他因素的排序算法。排序的目标是最大化交易的整体吞吐量和效率。
3. 交易分配：将排序后的交易分配到合适的区块中。在 zkRollup 中，通常会创建一个新的区块来容纳一定数量的交易。分配的过程可以使用贪婪算法或其他分配策略，以最大化每个区块的容量利用率。
4. 区块打包：对已分配的交易进行打包，形成一个完整的区块。在 FOX 的 Layer2 架构当中，这个区块实际上只包含了交易的摘要信息，这个摘要信息可以是交易的哈希或其他形式的紧凑表示，而不是交易的详细内容，详细的交易信息会被存储在 FOX 的 Ringer 当中，从而实现数据可用性（DA）。
5. 证明生成：对打包后的区块生成相应的证明。这个证明应该能够证明区块中每个交易的有效性，以及整个区块的一致性。FOX 的流水线模式主要应用于这个环节，用来更高效地利用 Folder 算力，将一个区块当中的交易分批地传送给 Folder 进行证明生成。Folder 分别对每批交易计算正确性证明，最后再聚合起来。通常，这个证明是基于 FOAKS 这种快速有针对性的零知识证明算法，通过将区块中的交易与状态转换规则进行比对，验证它们是否遵循了系统的规则和约束。
6. 证明验证：接收方可以使用证明来验证区块的有效性，而无需重新计算整个区块。这个验证过程可以是高度有效的，因为它只涉及对证明的检查，而不需要对交易进行复杂的计算。

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

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

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

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

结语

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