How to improve the efficiency of proof generation through the "pipeline mode"?
TechFlow Selected TechFlow Selected
How to improve the efficiency of proof generation through the "pipeline mode"?
This article will delve into the application of pipelined zero-knowledge proof generation in zkRollups.
Navigating Web3 tides with focused insightsAuthor: Kang Shuiyue, CEO of Fox Tech; Meng Xuanji, Chief Scientist of Fox Tech
Proofreading: Lin Yanxi, CTO of Fox Tech
Preface
In today's digital era, with the rapid development of blockchain technology, growing attention is being paid to data privacy and security. To enable more efficient and scalable blockchain applications, various solutions have been proposed—one of which is zero-knowledge proof (ZKP) technology. As a powerful cryptographic tool, zero-knowledge proofs allow verification of the truthfulness of a statement without revealing sensitive information.
In recent years, zkRollup has emerged as a key innovation in blockchain scalability and has attracted widespread attention. zkRollup significantly improves blockchain throughput and scalability by batching large numbers of transactions, executing them off-chain, and using zero-knowledge proofs to verify their correctness. In implementing zkRollup, how to allocate and batch transactions and generate proofs becomes a critical component of the system.
In Layer 1 systems, transactions are packaged into blocks and computed by miners. In Layer 2 systems, however, how transactions are packaged—or how a Layer 2 block is generated—requires separate consideration.
FOX is a zkRollup project based on zkEVM for Layer 2 scaling. For this challenge, FOX is exploring a pipelined approach to batch transaction processing, which is expected to greatly improve efficiency.
This article will delve into the application of pipeline-style zero-knowledge proof generation in zkRollup. First, we will analyze conventional transaction batching methods. Then, we will focus on the pipelined approach to generating zero-knowledge proofs, detailing its principles and use cases.
Conventional Transaction Batching Methods
In traditional blockchain systems, transaction confirmation and packaging is a time-consuming and resource-intensive process. Typically, transactions are validated one by one and added to a block, then consensus algorithms are used to agree on the state update of the blockchain. However, this sequential validation and packaging method has clear limitations, including low throughput and high latency.
In the standard transaction batching process, a batch of pending transactions is first collected—these may be user-submitted transactions or those from other chains. These transactions are then validated to ensure legality and validity, including checks on signatures, validity, and consistency. Once validated, they are grouped into a batch to form a block ready for submission.
In zkRollup systems, user-submitted transactions are similarly placed in a mempool to await processing. In the FOX system, the Sequencer periodically fetches transactions from the mempool, executes them locally, and orders them to form a transaction batch—essentially a block. At this point, the execution results are submitted to Layer 1, while the results and transaction data are also sent to the Folder node responsible for generating proofs.
Based on our basic understanding of zero-knowledge proof algorithms (readers can refer to previous articles by FOX), the Folder must receive both input and final execution results to generate a proof. This means that in a conventional setup, the Folder must wait until the Sequencer finishes executing all transactions before it can begin. To make better use of computational resources, we aim to let the Sequencer hand over partial execution results to the Folder immediately after completing a subset of transactions, enabling concurrent proof generation.
The Pipelined Processing Model Under Exploration by FOX
To achieve this goal, we need the Sequencer to execute transactions in batches and send intermediate results to the Folder immediately after finishing each batch.
Specifically, suppose a transaction batch contains 100 transactions and each sub-batch contains 10 transactions. The pipelined process can be illustrated as follows:
Figure 1: Pipeline mode for generating transaction proofs
Next, we briefly analyze the time costs of both approaches and discuss under what conditions the pipeline method achieves higher efficiency. For simplicity, the following discussion does not account for the time required for the Sequencer to transmit data to the Folder.
Let the total number of transactions in a batch be n, the number of sub-batches be k, the Sequencer’s execution time function be exe(), the Folder’s proof generation time function be prove(), the aggregation time function be aggr(), the total time for the conventional method be Sum1, and that for the pipeline method be Sum2.
Thus, under the conventional method, where the Folder must wait for the Sequencer to complete all executions before starting proof generation, the total time is:
Sum1 = exe(n) + prove(n)
For the pipeline method, the total time includes the Sequencer’s execution time for the first batch, the maximum of the subsequent proof generation times and remaining execution times across batches, plus the final aggregation time:
Sum2 = exe(n/k) + max{k × prove(n/k), (k−1) × exe(n/k)} + aggr(k)
Therefore, comparing the two total durations: the execution time function exe() can be approximately linear. In the FOX system, since the proof generation algorithm runs in linear time, prove() is also approximately linear.
We can draw the following conclusions:
-
If exe(n) > prove(n), then Sum1 > Sum2 when prove(n) > aggr(k).
-
If exe(n) < prove(n), then Sum1 > Sum2 when (k−1) × exe(n/k) > aggr(k).
Therefore, if the aggregation time aggr(k) is sufficiently small and the proof generation time is linear, adopting the pipeline method greatly enhances system efficiency and reduces total proof generation time.
The above analysis applies only to proof algorithms with linear time complexity, highlighting the importance of FOX’s choice of a linear-time proof algorithm.
Figure 2: Proof computation flowchart
The reason this pipeline method is still under exploration is that analysis reveals a trade-off: the more sub-batches a transaction package is divided into, the more data the Sequencer must record and transmit to the Folder, increasing overhead. While the Folder’s per-batch computational load decreases slightly, the aggregation process becomes more complex. Therefore, determining the optimal partitioning strategy requires balancing multiple factors and depends specifically on the computational capabilities of the Sequencer and Folder.
Efficient Transaction Allocation and Batched Proof Generation Are Key Optimization Points
In zkRollup implementations, efficiently allocating and batching transactions for incremental proof generation is a crucial optimization. FOX continues to refine its approach in search of more efficient solutions. Below is the basic workflow adopted by FOX:
-
Transaction Collection: Collect pending transactions and store them in a mempool. These may include user-submitted transactions or those generated by other systems or smart contracts.
-
Transaction Ordering: Order transactions in the mempool to determine the execution sequence. Sorting may be based on priority, timestamps, or other criteria, aiming to maximize overall throughput and efficiency.
-
Transaction Allocation: Assign ordered transactions to appropriate blocks. In zkRollup, a new block is typically created to hold a certain number of transactions. Allocation strategies such as greedy algorithms may be used to maximize block capacity utilization.
-
Block Packaging: Package allocated transactions into a complete block. In FOX’s Layer 2 architecture, the block contains only summary information—such as transaction hashes or compact representations—rather than full details. The complete transaction data is stored in FOX’s Ringer system, ensuring data availability (DA).
-
Proof Generation: Generate corresponding proofs for the packaged block. The proof must demonstrate the validity of each transaction and the consistency of the entire block. FOX’s pipeline model primarily applies here, enabling more efficient use of Folder computing power by sending batches of transactions incrementally for proof generation. The Folder computes correctness proofs for each batch separately, which are later aggregated. Typically, these proofs are based on FOAKS—an optimized, fast zero-knowledge proof algorithm developed by FOX—that verifies whether transactions comply with system rules and state transition logic.
-
Proof Verification: The recipient uses the proof to verify the block’s validity without re-executing all transactions. This verification process is highly efficient, involving only checks on the proof rather than complex recomputations.
FOX’s “pipeline model” primarily operates during the proof generation phase. During transaction collection and ordering, the Sequencer gathers pending transactions and sorts them according to predefined rules to determine execution order. Then, during batched execution, the Sequencer processes sorted transactions in batches. Each group of transactions is sent to an execution engine, which simulates their execution and records intermediate state transition results. After each batch completes, the Sequencer sends the intermediate results to the Folder.
This can be achieved via a communication channel that encodes and transmits intermediate results—such as state updates or transaction hashes—to the Folder in batches. Upon receiving these intermediate results, the Folder uses them to generate proofs incrementally. These proofs are built upon FOX’s proprietary FOAKS zero-knowledge proof algorithm, using the intermediate results as inputs to prove transaction validity and block-wide consistency.
The final step is proof verification. The generated proof is sent to the verifier—a smart contract deployed on Ethereum called Verifier—to confirm the block’s validity. The Verifier applies a verification algorithm to check the proof for correctness and legitimacy.
Through this pipeline approach, the Sequencer can continuously send intermediate results to the Folder while executing transactions, enabling incremental proof generation. This improves overall system efficiency and throughput while reducing proof generation latency.
Conclusion
This article introduced a novel approach in zkRollup for batched transaction processing and proof generation—the pipeline method—and provided a detailed analysis of its time complexity. For proof algorithms with linear runtime, judicious use of the pipeline method can effectively reduce total proof generation time. The proof system adopted by FOX achieves linear-time proof generation, which significantly aids in fast proof creation and improved user experience. The FOX team will continue to explore and optimize this approach.
Join TechFlow official community to stay tuned
Telegram:https://t.me/TechFlowDaily
X (Twitter):https://x.com/TechFlowPost
X (Twitter) EN:https://x.com/BlockFlow_News
@foxchain_tech
