Layer2 Key Component- An Analysis of Recursive Zero-knowledge Proof

Published in

ZKBase

6 min readApr 12, 2021

Among all Layer 2 solutions, ZK-Rollup is highly recommended for its data availability and same-level security as Layer 1.

ZK-Rollup treats one block as a processing unit, using zero-knowledge proof to verify the validity of the world state changes caused by the block, hence reducing the per-transaction cost of going on-chain while increasing the throughput.

However, in actual implementation, researchers found that the scalability brought by a simple ZK-Rollup scheme could not meet the needs in real use cases. This is caused by many factors, such as the limitation of circuit parameters, and the efficiency of the zero-knowledge proof algorithm. Researchers have made a lot of efforts to improve, such as optimizing the zero-knowledge proof algorithm, using powerful computation servers, and optimizing circuit scale. Although those efforts have brought incremental improvements, there is still a long way to go.

Aggregation Proof and its Limitations

From the researcher's perspective, the more transactions can be processed on-chain at one time, the better. Towards this goal, researchers first discovered Aggregation Proof, which ZKSwap has adopted in its ZKSpeed Protocol. We have introduced the design principle of Aggregation Proof in our previous articles. Simply put, it is to aggregate the proofs of multiple blocks into one proof so that the on-chain verification of multiple blocks can be completed at one time. The average cost of the transaction is greatly reduced, and the principle is shown in the figure below:

Although this scheme has brought substantial performance improvement, it has certain limitations:

Limited by the circuit parameters, there is an upper limit of blocks to be aggregated at one time;
The more blocks aggregated, the larger the circuit, up to the upper limit of the circuit’s scale; and the time to generate proof for such circuit will also be longer, the proof key and verification key will also take up more storage space;
The maximum aggregation currently is 20 blocks, that is, the aggregation process will start only after there are 20 blocks. If generating the proof takes a relatively long time, this will lead to an even longer time for these blocks to be confirmed, especially for those blocks that are generated earliest in the batch;

Limited by the complexity of proof computation and common reference string (CRS) generation, the above zero-knowledge proof algorithm is not scalable. Therefore, researchers are also trying to find a scalable zero-knowledge-proof algorithm, also known as Scalable zk-SNARKs.

Scalable zk-SNARKs

In the paper Scalable Zero Knowledge via Cycles of Elliptic Curves, Eli Ben-Sasson et al. gave the definition of Scalable zk-SNARKs:

Key generation is cheap: the time of Key generation has nothing to do with the computational complexity (if it is Scalable zk-STARKs, it may not be needed);
Proof generation is carried out incrementally: the proof generation process includes both the correctness of the current step and the correctness of all previous calculations. Such zk-SNARKs are incrementally computable;

The above diagram means: the prover is proving in a recursive calculation process. The initial state is S0, and the result of iterative calculation of t times under function F is St, which is very similar to the process of block update in the blockchain.

The first calculation method, the Monolithic option: the prover P writes all t calculations into the circuit, and then proves it at one time. It has the same limitations as we explained above, the higher complexity, the longer time, and larger storage space;

The second calculation method, the Recursive option: the process is as follows:

First, for the initial state S0=>S1, the prover P generates a proof π1 for the calculation process of S1 = F(S0);
For the conversion of S1=>S2, it can be seen from the illustration above that the prover P proved two parts: {S2 = F(S1), V(S1, π1) = 1}. The first half guarantees the validity of the current calculation, and the second half guarantees the validity of the previous calculation process. In zk-SNARKs, the proof generation time is faster than the original calculation, so it is reasonable to prove the verification process;

It can be seen that the Recursive option meets the basic requirements of Scalable zk-SNARKs:

The key generation has nothing to do with the number of cycles, it depends on the complexity of a single F. If it is general zk-SNARKs, it only depends on the security parameters;
The proof is incrementally computable, and each proof contains the validity of all previous calculations;
The size of the proof is fixed, and has nothing to do with the number of iterations t;

It can be seen from the above that Scalable zk-SNARKs adopts the Recursive idea. The current prove step includes the verification circuit of the previous step, as shown in the following diagram:

The P2 verification circuit contains the verification circuit of the previous step P1. Please note that V corresponding to P1 is on the domain Fq, and the proof process of P2 is on Fr. How to represent the arithmetic circuit of V on Fr is a process worth exploring; because Cv can be regarded as a sub-circuit of P, Therefore, q needs to satisfy q = #E(Fr) or q divisible by #E(Fr), that is, q divisible by rk-1, therefore:

Attempt 1. Ideally, if r = q, then in Fr, the arithmetic circuit that can perfectly represent V on Fq, but according to the above principle, r != q always holds;
Attempt 2. For q != r, because it is necessary to simulate the calculation of Fq in Fr, the calculation complexity will increase by log(r) times;
Attempt 3. Using the cycle of elliptic curves, the Recursive process can be perfectly realized;

Specifically, select two large prime numbers, r, and q. Make sure r = #E(Fq) and q = #E(Fr), that is, the domain of the current group is equal to the order of another group, and vice versa. Therefore, the prover P on the domain Fq can perfectly implement the verification circuit of Fr in Fq, and the prover P on the domain Fr can also implement the verification circuit of Fq in Fr; therefore, there will be no defects in Attempt 2.

The following table lists the commonly used cycle of elliptic curves (https://eprint.iacr.org/2014/595.pdf)

*Scalable Zero Knowledge via Cycles of Elliptic Curves* https://eprint.iacr.org/2014/595.pdf

Key Takeaways

By adopting Recursive Proof Composition, zk-SNARKS becomes Scalable zk-SNARKs, becoming a more efficient and concise zero-knowledge proof algorithm, and can be applied in real and complicated use cases.

Mina Protocol, which has recently launched its mainnet, uses this technology to implement a very light blockchain with a fixed size of around 22KB.

Other projects including Matter Labs, starkWare, etc. are also planning to adopt Scalable zk- SNARKs technology to achieve higher scalability of Layer2. The ZKSwap team continues to research and innovate on the Layer2 track and has also made breakthroughs in Scalable zk-SNARKs, which I believe will be applied to the new version soon.

ZKSwap is a layer2 DEX based on ZK-Rollups technology and using the AMM model.