Original title: "How to design an exquisite proof recursion scheme" Original author: Lin Yanxi, Fox Tech CTO; Meng Xuanji, Fox Tech Chief Scientist Foreword: Almost all the problems encountered in the zkRollup and zkEVM tracks are essentially algorithmic problems. The main reason why ZKP hardware acceleration is repeatedly mentioned is that the current algorithms are generally slow. In order to avoid falling into the embarrassing situation of "not enough algorithms, hardware to make up", we should solve the problem from the essential algorithm. Designing an exquisite recursive proof scheme is the key to solving this problem. With the continuous development of smart contracts, more and more web3 applications have gradually come out, and the transaction volume of traditional Layer1 such as Ethereum has risen rapidly and may be congested at any time. How to obtain higher efficiency while ensuring the security provided by Layer1 has become an urgent problem to be solved. For Ethereum, zkRollup uses the zero-knowledge proof algorithm as the underlying component to move the expensive calculations that originally needed to be performed on Layer1 to the off-chain, and provide proof of execution correctness to the chain. The main projects in this track include StarkWare, zkSync, Scroll and Fox Tech. In fact, in the design of zkRollup, there are very high requirements for efficiency: it is hoped that the submitted proof value is small enough, so as to reduce the amount of calculation of Layer1. In order to obtain a small enough proof length, various zkRollup projects are improving algorithms and architectural designs. For example, Fox has developed its own proof algorithm FOAKS in combination with the latest zero-knowledge proof algorithm to obtain the optimal proof time and proof length. In addition, in the stage of verifying proofs, the most common means is to generate proofs linearly and verify them in sequence. In order to improve efficiency, the first thing that comes to mind is to package multiple proofs into one proof, which is usually referred to as proof aggregation. Intuitively speaking, verifying the proof generated by zkEVM is a linear process, and the verifier needs to verify each generated proof value in turn. However, this verification method is relatively inefficient and has a relatively large communication overhead. For the zkRollup scenario, higher verifier-side overhead means more Layer1 calculations, which will also lead 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 newspaper of the day on each day from the 1st to the 7th, and these 7 photos will be packaged into a proof. Figure 1: General proof aggregation scheme In the above example, putting 7 photos directly into an envelope is proof aggregation in the intuitive sense. In actual practice, this corresponds to connecting different proofs together and verifying them linearly in sequence, that is, verifying the first proof first, then verifying the second proof and subsequent proofs. The problem is that this approach will neither change the size of the proof nor the time of proof, and the effect is the same as proving and verifying one by one. If you want to achieve logarithmic space compression, you must use the recursive proof (Proof Recursion) mentioned below. Proof recursion scheme used by Halo2 and STARK To better illustrate what recursive proof is, let's go back to the above example. Alice's 7 photos are actually 7 proofs. Now consider merging them together, so Alice can take a photo on the 1st, take a photo with the photo and the newspaper of the 2nd on the 2nd, and take a photo with the photo taken by the 2nd and the newspaper of the 3rd on the 3rd. Similarly, Alice takes the last photo on the 7th with the photo of the 6th and the newspaper of the 7th, and other friends can verify that Alice went to the park from the 1st to the 7th when they see the last photo of the 7th. It can be seen that the previous seven proof photos have been compressed into one. A key technique in this process is "photos containing photos", which is equivalent to recursively nesting the previous photos into the later photos. This is different from putting many photos together and taking a photo. The recursive proof technique of zkRollup can greatly compress the proof size. Specifically, each transaction will generate a proof. We assume that the original transaction calculation circuit is C0, P0 is the correctness proof of C0, V0 is the calculation process of verifying P0, and the prover (Prover) also converts V0 into the corresponding circuit, recorded as C0'. At this time, for the proof calculation process C1 of another transaction, the circuits of C0’ and C1 can be merged. In this way, once the correctness proof P1 of the merged circuit is verified, it is equivalent to verifying the correctness of the above two transactions at the same time, which means compression is achieved.Looking back at the above process, we can find that the principle of compression is to convert the process of verifying the proof into a circuit, and then generate a "proof of the proof". So from this perspective, it is an operation that can be continuously recursive downward, so it is also called a recursive proof. Figure 2: Recursive proof scheme used by Halo2 and Stark The Proof Recursion scheme used by Halo2 and STARK can generate proofs in parallel and merge multiple proofs, so that the correctness of multiple transaction executions can be verified while verifying a proof value, which can compress the computational overhead and greatly improve the efficiency of the system. However, such optimization still remains at the level above the specific zero-knowledge proof algorithm. In order to further improve efficiency, we need more basic optimization and innovation. The FOAKS algorithm designed by Fox achieves this by applying the idea of ​​recursion to the inside of a proof. The proof recursion scheme used by FOAKS is a zkEVM-based zkRollup project at Fox Tech. In its proof system, the recursive proof technique is also used, but the connotation is different from the above recursive method. The main difference is that Fox uses the idea of ​​recursion within a proof. In order to express the core idea of ​​the recursive proof used by Fox, which is to continuously reduce the problem to be proved until the reduced problem is simple enough, we need to give another example. In the above example, Alice took a photo to prove that she went to Fox Park on a certain day, so Bob made a different suggestion. He believed that the problem of proving that Alice had been to the park could be reduced to proving that Alice's mobile phone had been to the park, and proving this could be reduced to proving that the location of Alice's mobile phone was within the range of the park. Therefore, in order to prove that Alice had been to the park, she only needed to send a location with her mobile phone when she was in the park. In this way, the size of the proof is changed from the original photo (a very high-dimensional data) to a 3-dimensional data (latitude, longitude and time), which effectively saves costs. This example is not completely appropriate, because some people may question that Alice's mobile phone has been to Fox Park does not mean that Alice herself has been there, but in actual situations, this reduction process is rigorous in mathematical form.Specifically, Fox's recursive proof uses recursion at the circuit level. When performing zero-knowledge proofs, we write the problem to be proved into a circuit, and then use the circuit to calculate some equations that need to be satisfied. Instead of showing that these equations are satisfied, we write these equations into circuits again, and so on, until the equations to be proved to be satisfied become simple enough, and we can easily prove them directly. From this process, we can see that doing so is closer to the meaning of "recursion". It is worth mentioning that not all algorithms can use this recursive technique. Suppose that each recursion will transform a proof of complexity O(n) into a proof of complexity O(f(n)), and the computational complexity of the recursive process itself is O(g(n)), then after one recursion the total computational complexity becomes O1(n)=O(f(n))+O(g(n)), after two recursions it is O2(n)=O(f(f(n)))+O(g(n))+O(g(f(n))), after three recursions it is O3(n)=O(f(f(f(n))))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))), ..., and so on. Therefore, only when the functions of the two corresponding algorithmic characteristics of f and g satisfy Ok(n) for a certain k, the proof complexity has always been one of the most important keys in the application of zero-knowledge proof. The property of proof complexity becomes more and more important as the things to be proved become more and more complex, especially in giant ZK application scenarios like zkEVM, where the complexity of proof will have a decisive impact on the performance of the product and the user experience. Among the many methods to reduce the complexity of the final proof, the optimization of the core algorithm is the most important. Fox has designed an exquisite recursive proof scheme based on the most cutting-edge algorithm, and used this technology to create the ZK-FOAKS algorithm that is most suitable for zkEVM, which is expected to become the performance leader in the zkRollup world. References https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 This article is from a contribution and does not represent the views of BlockBeats