How to improve the efficiency of generating proofs through the "pipeline model"?

Written by: Kang Shuiyue, CEO of Fox Tech; Meng Xuanji, Chief Scientist of Fox Tech

Proofread by: Lin Yanxi, CTO of Fox Tech

Introduction

In today's digital age, with the rapid development of blockchain technology, people's concerns about data privacy and security are increasing. To achieve more efficient and scalable blockchain applications, many solutions have been proposed, one of which is Zero-Knowledge Proof (ZKP) technology. As a powerful cryptographic tool, Zero-Knowledge Proof can verify the truthfulness of a statement without revealing sensitive information.

In recent years, zkRollup has emerged as one of the important innovations in blockchain scalability technology, attracting widespread attention. zkRollup significantly improves the throughput and scalability of blockchain by bundling a large number of transactions, executing them off-chain, and utilizing the properties of Zero-Knowledge Proof to verify the correctness of these transactions. In the implementation of zkRollup, how to allocate and bundle transactions and generate proofs has become a crucial component of the zkRollup system.

In Layer 1 systems, transactions are packaged in blocks and computed by miners. In Layer 2 systems, how transactions are packaged, or how a Layer 2 block is generated, needs to be considered separately.

FOX is a Layer 2 zkRollup scalability project based on zkEVM. To address this issue, FOX is exploring a pipelined processing approach to batch process transactions, which is expected to significantly enhance efficiency.

This article will delve into the application of pipelined generation of Zero-Knowledge Proofs in zkRollup. First, we will analyze the basic transaction packaging methods. Then, we will focus on the technology of pipelined generation of Zero-Knowledge Proofs, detailing its principles and application scenarios.

Conventional Transaction Packaging Methods

In traditional blockchain systems, the confirmation and packaging of transactions is a time-consuming and resource-intensive process. Typically, transactions are verified one by one and added to a block, followed by consensus algorithms to reach agreement, allowing the blockchain state to be updated. However, this one-by-one verification and packaging method has obvious limitations, including low throughput and high latency.

In the conventional transaction packaging process, first, a batch of pending transactions is collected, which may include user-submitted transactions or transactions from other chains. Then, these transactions are verified to ensure their legality and validity. This verification includes checking transaction signatures, validating transaction validity and consistency, etc. Once the transactions pass verification, they are packaged into a batch, forming a block ready for submission.

In the zkRollup system, user-submitted transactions are similarly placed in a transaction pool awaiting processing. In the FOX system, the Sequencer periodically fetches transactions from the transaction pool, executes and sorts them locally, forming a transaction package, which is a block. At this point, the execution results of the transactions are submitted to Layer 1, and the results along with transaction data are submitted to the Folder node that generates proofs.

According to our basic understanding of Zero-Knowledge Proof algorithms (readers can refer to previous series articles from FOX), if the Folder wants to generate proofs, it must obtain the inputs and the execution results. This means that if done conventionally, it would require waiting for the Sequencer to execute all transactions before handing them over to the Folder. To make more efficient use of computational resources, we hope to allow the Sequencer to hand over results to the Folder for proof generation immediately after executing a portion of the transactions.

FOX's Exploration of Pipelined Processing Model

To achieve the above goal, we need the Sequencer to execute transactions in batches and immediately send the intermediate results to the Folder after executing a batch.

Specifically, suppose the total number of transactions in a transaction package is 100, and the number of transactions per batch is 10. The pipelined processing method can be represented as follows.

Next, we will briefly analyze the time overhead of the two methods and discuss under what circumstances using the pipelined method would be more efficient. For simplicity, this discussion does not consider the time taken for the Sequencer to send data to the Folder.

Let the number of transactions in the transaction package be n, the number of batches be k, the execution time function of the Sequencer be exe(), the proof generation time function of the Folder be prove(), and the aggregation proof time function be aggr(). The total time for the conventional method is Sum1, and the total time for the pipelined method is Sum2.

Thus, according to the above process, the conventional method relies on the Sequencer executing first and then the Folder generating proofs, requiring a total time of

Sum1=exe(n)+prove(n)

While the time for the pipelined method should include the execution time of the Sequencer for the first batch of transactions, as well as the maximum of the proof generation time for subsequent batches and the last aggregation time.

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

Therefore, comparing the total durations of both methods, the execution time function exe() can be approximated as a linear function, and for prove(), since the proof generation time of the FOX system's proof algorithm is a linear function, prove() is also a linear function.

We can conclude:

• If exe(n) > prove(n), then when prove(n) > aggr(k), Sum1 > Sum2.
• If exe(n) < prove(n), then when (k-1)exe(n/k) > aggr(k), Sum1 > Sum2.

Thus, if the aggregation time aggr(k) is sufficiently small and the proof generation time is a linear function, adopting the pipelined method is very helpful in improving system efficiency and reducing the total proof generation time.

The above analysis holds only for linear time proof algorithms, which also highlights the importance of FOX adopting linear time proof algorithms.

The reason we say the pipelined method is still in exploration is that through the analysis of this model, we can see that the more batches a transaction package is divided into, the more data the Sequencer needs to record and transmit to the Folder, increasing the overhead. However, for the Folder, the computational load per processing instance will decrease, making the aggregation process more complex. Therefore, how to segment is a trade-off that specifically depends on the computational performance of the Sequencer and Folder.

Efficient Allocation and Packaging of Transactions to Generate Proofs in Batches is a Key Optimization Point

In the implementation of zkRollup, efficiently allocating and packaging transactions and generating proofs is a key optimization point. FOX is continuously optimizing the model and seeking more efficient solutions. Below is the basic process adopted by FOX:

1. Transaction Collection: Collect pending transactions and store them in a transaction pool. These transactions may be user-submitted or generated by other systems or contracts.
2. Transaction Sorting: Sort the transactions in the transaction pool to determine the packaging order. Typically, sorting algorithms based on priority, timestamps, or other factors can be used. The goal of sorting is to maximize the overall throughput and efficiency of transactions.
3. Transaction Allocation: Allocate the sorted transactions to appropriate blocks. In zkRollup, a new block is typically created to accommodate a certain number of transactions. The allocation process can use greedy algorithms or other allocation strategies to maximize the capacity utilization of each block.
4. Block Packaging: Package the allocated transactions to form a complete block. In FOX's Layer 2 architecture, this block actually only contains summary information of the transactions, which can be the hash of the transactions or other forms of compact representation, rather than detailed transaction content. Detailed transaction information is stored in FOX's Ringer, thus achieving data availability (DA).
5. Proof Generation: Generate corresponding proofs for the packaged block. This proof should be able to demonstrate the validity of each transaction in the block and the consistency of the entire block. FOX's pipelined model is mainly applied in this stage to more efficiently utilize the computational power of the Folder, sending transactions in batches from a block to the Folder for proof generation. The Folder calculates correctness proofs for each batch of transactions and finally aggregates them. Typically, this proof is based on the FOAKS fast targeted Zero-Knowledge Proof algorithm, which verifies whether the transactions in the block adhere to the system's rules and constraints by comparing them with state transition rules.
6. Proof Verification: The recipient can use the proof to verify the validity of the block without recalculating the entire block. This verification process can be highly efficient since it only involves checking the proof without needing complex calculations on the transactions.

FOX's "pipelined model" mainly occurs in the proof generation stage. In transaction collection and sorting, the Sequencer collects pending transactions and sorts them according to certain rules to determine the execution order. In the subsequent batch execution of transactions, the Sequencer executes the sorted transactions in batches. A group of transactions in each batch is sent to the execution engine for processing. The execution engine simulates the execution of these transactions and records the intermediate results of state transitions. After executing each batch of transactions, the Sequencer sends the intermediate results to the Folder.

This can be accomplished by encoding the intermediate results and sending them in batches to the Folder via a communication channel, such as state updates, transaction hashes, etc. Upon receiving the intermediate results from each batch, the Folder uses these results to generate the corresponding proofs in batches. The generation of these proofs is based on FOX's self-developed FOAKS Zero-Knowledge Proof algorithm, which uses the intermediate results as input to prove the validity of transactions and the consistency of the entire block.

The final step is proof verification. The generated proofs are sent to the verifier, which is a smart contract deployed on Ethereum, to verify the validity of the block. The verifier uses a verification algorithm to check the proofs to ensure their correctness and legality.

Through this pipelined approach, the Sequencer can continuously send intermediate results to the Folder while executing transactions, thereby generating proofs in batches. This can improve the overall efficiency and throughput of the system while reducing the latency of proof generation.

Conclusion

This article introduces a relatively novel approach to batch processing transactions for proof generation in zkRollup, the pipelined method, and provides a detailed analysis of the time overhead of this method. For linear proof algorithms, the reasonable use of the pipelined method can help reduce the total proof generation time. The proof system adopted by FOX achieves linear proof time, which greatly aids in the rapid generation of proofs and enhances user experience. The FOX team will continue to explore and optimize this solution.