Written by: Fox Tech CTO Lin Yanxi, Fox Tech Chief Scientist Meng Xuanji

Introduction:

In the zkRollup and zkEVM space, almost all encountered challenges are fundamentally algorithmic problems. The frequent mention of ZKP hardware acceleration is primarily due to the generally slow algorithms currently in use. To avoid the awkward situation of "insufficient algorithms, compensating with hardware," we should address the problem at the level of the fundamental algorithms. Designing a brilliantly ingenious recursive proof scheme is key to solving this issue.

With the continuous development of smart contracts, more and more web3 applications are gradually emerging, and the transaction volume of traditional Layer 1s like Ethereum is rapidly increasing, potentially leading to congestion at any moment. How to achieve higher efficiency while ensuring the security provided by Layer 1 has become an urgent problem to solve.

For Ethereum, zkRollup uses zero-knowledge proof algorithms as underlying components, moving the expensive computations that originally needed to be executed on Layer 1 off-chain, while providing proof of execution correctness on-chain. This space mainly includes projects like StarkWare, zkSync, Scroll, and Fox Tech.

In fact, the design of zkRollup places a high emphasis on efficiency: it hopes that the submitted proof values are small enough to alleviate the computational load on Layer 1. To achieve sufficiently small proof lengths, various zkRollup projects are improving their algorithms and architectural designs. For example, Fox has developed its own proof algorithm FOAKS by combining the latest zero-knowledge proof algorithms to achieve optimal proof time and proof length.

Moreover, during the proof verification stage, the most straightforward method is to generate proofs linearly and verify them sequentially. To improve efficiency, the first thought is to package multiple proofs into one, which is commonly referred to as proof aggregation.

Intuitively, verifying the proofs generated by zkEVM is a linear process, where the verifier needs to sequentially verify each generated proof value. However, this verification method is relatively inefficient, and the communication overhead is significant. In the context of zkRollup, higher costs on the verifier's end mean more computations on Layer 1, leading to higher gas fees.

Let's look at an example: Alice wants to prove to the world that she went to Fox Park from the 1st to the 7th of this month. To do this, she can take a photo in the park with the day's newspaper each day from the 1st to the 7th, and these 7 photos will be packaged into one proof.

Figure 1: General proof aggregation scheme

In the example above, putting the 7 photos directly into one envelope is the intuitive meaning of proof aggregation. In practical situations, this corresponds to connecting different proofs together and verifying them linearly, i.e., verifying the first proof, then the second proof, and so on. The problem is that this approach neither changes the size of the proof nor the time taken for the proof, resulting in the same effect as proving and verifying each one individually. To achieve logarithmic space compression, we need to use the recursive proof mentioned below.

Recursive Proof Schemes Used by Halo2 and STARK

To better illustrate what recursive proofs are, let's return to the example above.

Alice's 7 photos are actually 7 proofs. Now consider merging them together; Alice can take a photo on the 1st, then on the 2nd, take a photo with the 1st photo and the 2nd day's newspaper, and on the 3rd, take a photo with the 2nd photo and the 3rd day's newspaper. Continuing this way, on the 7th, Alice takes the last photo with the 6th photo and the 7th day's newspaper, and others can verify from this last photo taken on the 7th that Alice went to the park from the 1st to the 7th. It can be seen that the previous seven proof photos have been compressed into one. A key technique in this process is the "photo of a photo," which is equivalent to recursively embedding the previous photos into the subsequent photos. This is different from just putting many photos together and taking another photo.

The recursive proof technique of zkRollup can significantly compress proof sizes. Specifically, each transaction generates a proof. Let's denote the original transaction computation circuit as C0, P0 as the correctness proof of C0, and V0 as the verification process of P0. The prover transforms V0 into the corresponding circuit, denoted as C0'. At this point, for the proof computation process C1 of another transaction, we can merge the circuits of C0' and C1. Once the correctness proof P1 of the merged circuit is verified, it is equivalent to simultaneously verifying the correctness of the two transactions, thus achieving compression.

Looking back at the above process, we can see that the principle of compression lies in transforming the proof verification process back into a circuit, generating "proof of the proof." Therefore, from this perspective, it is an operation that can be recursively applied, hence it is called recursive proof.

Figure 2: Recursive proof schemes used by Halo2 and STARK

The proof recursion scheme adopted by Halo2 and STARK can generate proofs in parallel and merge multiple proofs, allowing the verification of one proof value while simultaneously verifying the correctness of multiple transaction executions, thus compressing computational overhead and greatly improving system efficiency.

However, such optimizations still remain at the level of specific zero-knowledge proof algorithms. To further enhance efficiency, we need lower-level optimizations and innovations. The FOAKS algorithm designed by Fox achieves this by applying the idea of recursion within a single proof.

Recursive Proof Scheme Used by FOAKS

Fox Tech is a zkEVM-based zkRollup project. In its proof system, it also employs the technique of recursive proofs, but the connotation differs from the aforementioned recursive methods. The main difference is that Fox uses the idea of recursion within a single proof. To express the core idea of continuously reducing the problem to be proven until it becomes simple enough, we need to provide another example.

In the previous example, Alice proves she went to Fox Park on a certain day by taking a photo. Bob suggests a different approach; he believes that proving Alice went to the park can be reduced to proving that Alice's phone was at the park, and proving this can be further reduced to proving that Alice's phone's location was within the park's range. Therefore, to prove that Alice went to this park, she only needs to send a location from her phone while she is in the park.

In this way, the proof size reduces from one photo (a high-dimensional data) to a 3-dimensional data (latitude, longitude, and time), effectively saving costs. This example may not be entirely appropriate, as some may question that Alice's phone being at Fox Park does not necessarily mean Alice herself was there. However, in practical situations, this reduction process is mathematically rigorous.

Specifically, Fox's use of recursive proofs is at the circuit level. When performing zero-knowledge proofs, we write the problem to be proven as a circuit and then compute some equations that need to be satisfied through the circuit. Instead of demonstrating that these equations are satisfied, we rewrite these equations as circuits, and this process continues until the equations we need to prove become simple enough for us to prove directly.

From this process, we can see that this approach is closer to the meaning of "recursion." It is worth mentioning that not all algorithms can use this recursive technique. Suppose each recursion transforms a proof of complexity O(n) into a proof of O(f(n)), and the computational complexity of the recursion process itself is O(g(n)). After one recursion, the total computational complexity becomes O1(n) = O(f(n)) + O(g(n)); after two recursions, it becomes O2(n) = O(f(f(n))) + O(g(n)) + O(g(f(n))); after three recursions, it becomes O3(n) = O(f(f(f(n)))) + O(g(n)) + O(g(f(n))) + O(g(f(f(n)))) and so on. Therefore, this recursive technique can only be effectively utilized when the functions f and g corresponding to the algorithmic characteristics satisfy O_k(n) < O(n) for some k. Fox effectively employs this recursive technique to compress proof complexity.

Figure 3: Recursive proof scheme used by ZK-FOAKS

Conclusion

The complexity of proofs has always been one of the most important keys in the application of zero-knowledge proofs. The property of proof complexity becomes increasingly important as the matters to be proven become more complex, especially in large-scale ZK application scenarios like zkEVM, where proof complexity can have a decisive impact on product performance and user experience. Among the many methods to reduce the final proof complexity, optimizing the core algorithm is the most crucial. Fox has designed a brilliantly ingenious recursive proof scheme based on cutting-edge algorithms and utilized this technology to create the ZK-FOAKS algorithm, which is expected to become a performance leader in the zkRollup space.

References

1. https://blog.csdn.net/weixin_44383880/article/details/126338813
2. https://blog.csdn.net/freedomhero/article/details/126727033