1. Introduction

Recursive Zero-Knowledge Proof (Recursive ZKP) is a type of zero-knowledge proof that utilizes the concept of recursion to generate proofs that are more efficiently verifiable. In some cases, it can even combine multiple proofs into a single proof. This is particularly important in blockchain systems, where efficiency and scalability are crucial.

1.1 Zero-Knowledge Proof

A Zero-Knowledge Proof is a cryptographic protocol that allows one party (the prover) to convince another party (the verifier) that they know a specific piece of information (such as a secret) without revealing the actual content of that information. A zero-knowledge proof guarantees the following three key properties:

• Completeness: If the statement is true, an honest prover can convince the verifier.
• Soundness: If the statement is false, a fraudulent prover cannot convince the verifier.
• Zero-Knowledge: The verifier learns nothing other than the fact that the statement is true (i.e., the verifier does not gain any information about the secret).

1.2 Recursive Zero-Knowledge Proof

In a Recursive Zero-Knowledge Proof, the proof itself can serve as part of another proof. In other words, the prover can use one proof to demonstrate the validity of another proof, enabling the construction of complex proofs in a recursive manner. Specifically, using the circuit \(Circuit\) to represent the zkSNARK verification algorithm \(Verify\), the proof \(Proof\) and verification key \(VK\) are used as inputs to generate a new proof \(Proof\)'.

In recursive zero-knowledge proofs, the concept can be understood as “proving the validity of a proof” and then continuing to prove the next statement, and so on. Recursion here means “the proof of a proof.” Simply put, this means proving that you are truthful while also proving that other proofs are valid, and recursively building more complex proofs.

1.3 Key Components of Recursive Zero-Knowledge Proofs

• External and Internal Proofs: Recursive zero-knowledge proofs include an external proof, which relies on other internal proofs. The external proof can be seen as a “proof of validity,” while the internal proofs form part of the external proof.
• Recursive Composition: The core idea of recursive zero-knowledge proofs is that multiple independent zero-knowledge proofs can be aggregated into one compact proof. Through recursive composition, multiple computations, validations, or processes (such as multiple transactions or contract executions) can be verified in a single proof.
• Efficiency and Scalability: Recursive zero-knowledge proofs are particularly useful when verifying many independent proofs, such as in blockchain systems, where many transactions may occur. Unlike verifying each proof individually, recursive proofs can combine multiple proofs into a single one, significantly improving verification efficiency and reducing computational overhead. # 2. The Principle of Plonky2 Recursive Zero-Knowledge Proof

2. Plonky2 Recursive zk

2.1 Generating the First Layer Proof

The first layer zero-knowledge proof, commonly referred to as the inner/bottom layer proof (Inner Product), mainly ensures the correctness of the following 5 items:

(1). Hash of public inputs: Verifies that the commitment to the public inputs is correct.

(2). Polynomial verification: Verifies whether the circuit constraints hold at the verification point, focusing on the following aspects:

· Circuit constraint polynomial:

• Each zero-knowledge proof represents a circuit, which is encoded as polynomial constraints.
• Verifies whether these constraints hold at a specific point.

· Vanishing polynomial:

• Checks whether the polynomial of the bottom layer proof is “vanished” (i.e., satisfies the circuit constraints) at the verification point \(\zeta\).
• The formula for the vanishing polynomial is similar to: $ Z_H() = ^d - 1 $, where d is the degree of the circuit.

· Quotient polynomial:

• The quotient polynomial is used to decompose and verify the result of the vanishing polynomial.
• Verifies whether the quotient polynomial correctly decomposes the constraint polynomial into part of the vanishing polynomial.

(3). FRI verification: Low-degree test

· Merkle tree verification:

• Verifies that the hash path of the polynomial commitment is correct.
• Checks whether the root hash of the Merkle tree matches the committed hash.

· FRI folding consistency:

• Verifies whether the folded result of the polynomial satisfies the consistency requirements.
• The folded polynomial is recursively calculated, with each fold reducing the degree of the polynomial.

· Opening point verification:

• Checks whether the value of the polynomial at a specific point matches the commitment provided by the bottom layer proof.

(4). Merkle tree path verification: Merkle proof 

• Verifies the Merkle tree path for the polynomial commitment. 
• Checks whether the hash calculations at each node in the path are correct.

(5). Random challenge values Ensures that the generated random challenge values are derived from the correct public coin and hashed, mainly including: 

• \( \beta, \gamma \): Used for polynomial constraints. 
• \(a\): Used to randomize the constraint polynomial. 
• \(\zeta\): The verification point, used to check the value of the polynomial at a specific point.

2.2 Determining the Recursive Circuit

First, the structure of the recursive circuit must be determined, and a virtual target is introduced to represent the data that needs to be verified (since the corresponding inner proof has not been generated before determining the verification circuit).

Role of the virtual target: Since recursive proofs involve multiple layers, and the circuit needs to be determined at the outset, a virtual target is used to pre-allocate space. Specific data will be filled in during the recursive proof at the appropriate rounds.

The main steps include:

· Verification content:

• Verifies the public input of the bottom layer proof.
• Verifies polynomial constraints (vanishing polynomial and quotient polynomial).
• Verifies the FRI proof of the polynomial commitment.

· Constructing the virtual target:

In the recursive verification circuit, a virtual proof target is used to placeholder data representing all the data of the bottom layer proof.

· Verification logic:

The \(verify\_proof\) function is used to nest verification logic within the recursive circuit. It verifies the public input, opening points, FRI proof, and more for the bottom layer proof. 

2.3 Nested Recursive Verification

Recursive embedding of the bottom-layer verification circuit into a higher-layer circuit generates a recursive proof: 

• Embed higher-level verification logic into the recursive circuit. 
• Compress the proof step by step through multiple recursive steps.

2.4 Running Recursive Verification

The recursive verification circuit is used to gradually generate a recursive proof, verifying the correctness of all nested proofs:

• Fill the virtual targets, replacing placeholders with actual bottom-layer proof data.
• Run the recursive verification circuit step by step, generating the recursive proof incrementally.
• After the final step, generate the final recursive proof.

2.5 Optimization Directions

• FRI and Low-Degree Test

Plonky2 uses FRI as a low-cost polynomial commitment scheme for proof generation. Compared to traditional KZG, FRI significantly reduces proof size and verification complexity in recursive scenarios.

• Efficient Field Goldilocks

Goldilocks is an optimized 64-bit prime field that supports fast modular arithmetic, making it ideal for modern CPUs. By constructing constraints within this field, the size of each verification circuit step is reduced, further lowering computational overhead.

• Poseidon Hash Function

Plonky2 uses Poseidon to construct hash functions that are friendly to constraints, reducing the circuit depth and gate count required for hash operations.

3. Advantages and Challenges

3.1 Advantages

• Compactness: Recursive zero-knowledge proofs allow multiple proofs to be compressed into a smaller proof.
• Efficiency: Using recursive zero-knowledge proofs, the speed of verifying many statements or computations is much higher than verifying each proof individually.
• Scalability: They enable systems to handle a large number of proofs (such as blockchain transactions) without encountering performance bottlenecks.

3.2 Challenges

• Complexity: Constructing recursive zero-knowledge proofs is complex, and the cryptographic constructions involved are difficult to implement correctly.
• Computational Overhead: Despite the high verification efficiency of recursive proofs, the creation process (especially in the case of zk-SNARKs) involves significant computational overhead.

4. Applications

• Scalable Blockchain: Recursive zero-knowledge proofs can be used to create efficient blockchain proofs. For example, recursive zk-SNARKs (zero-knowledge succinct non-interactive arguments of knowledge) can prove the validity of a set of transactions without revealing the specific details of the transactions, and can also combine the validation of multiple blocks into a single proof.
• Rollup Technology: Recursive zero-knowledge proofs are the foundation of zk-rollups, a blockchain scaling solution adopted by blockchains like Ethereum. zk-rollups aggregate multiple transactions into a single proof and publish this proof on the Ethereum mainchain, reducing transaction fees and increasing throughput.
• Verifiable Computation: In cloud computing or decentralized computing, recursive zero-knowledge proofs can be used to prove that certain computational processes are correct without revealing any data from the process.
• Privacy-Preserving Protocols: Recursive zero-knowledge proofs enable complex privacy-preserving applications, such as proving that a series of transactions or activities are valid without disclosing specific details.

5. Conclusion

Recursive zero-knowledge proofs combine the power of zero-knowledge proofs with the concept of recursion, allowing for the creation of complex proofs that can be merged into a single proof through recursion. This makes systems more efficient, compact, and scalable. The main advantage is the ability to provide compact proofs for complex computations, making them particularly suitable for blockchain systems, cryptographic protocols, and privacy-preserving applications.