Abstract
This article explores techniques to enhance the scalability of zero-knowledge proof (ZKP) systems, focusing on recursion, batching, and polynomial commitments. It evaluates trade-offs between proof size, verification time, and prover overhead, demonstrating how modern ZKP frameworks like PLONK and Halo improve throughput in high-volume blockchain environments.

Introduction

Zero-knowledge proofs (ZKPs) enable one party (the prover) to convince another party (the verifier) that a statement is true without revealing any additional information. Recent advances have made ZKPs practical for blockchain applications—allowing private transactions, off-chain computations, and succinct verification. As demand grows, ensuring that proof systems scale to large circuits and high transaction volumes is critical. This article examines three key optimization techniques:

• Recursion: Nesting proofs so that a verifier can check many statements by verifying a single succinct “proof of proofs.”
• Batching: Combining multiple proof instances into one aggregated proof, reducing per-proof verification overhead.
• Polynomial Commitments: Efficiently committing to large polynomials (e.g., witness polynomials) in batch, enabling faster verification.

We discuss trade-offs in proof size, prover time, and verifier time, then survey how frameworks such as PLONK and Halo implement these optimizations.

1. Recursion in ZKPs

Recursion refers to constructing a proof that attests to the validity of multiple other proofs. Instead of verifying each proof separately, a verifier checks one outer proof whose statement encodes “all inner proofs are valid.”

1.1 Motivation

• Scalability: In a setting where thousands of proofs must be verified (e.g., rollup blocks), performing a separate verification algorithm for each incurs linear verifier time. Recursion collapses many proofs into one, resulting in constant or logarithmic verification cost irrespective of the number of inner statements.
• Succinctness: A single recursive proof remains compact (e.g., on the order of a few hundred bytes), while naïvely aggregating individual proofs would multiply size by the number of instances.

1.2 Implementation Patterns

1. Cycle-Consistency Theorem: Prove statements of the form “Proof₁ is valid AND Proof₂ is valid AND … AND Proof_n is valid.” Rather than verifying each inner proof directly, one constructs an arithmetic circuit (or constraint system) whose input includes the verifying key, the proof, and the statement for each inner proof. The outer prover executes the inner verifier logic inside the circuit.
2. Superhero Keys / Universal Setup: To avoid recompiling a new circuit every time the inner circuit changes, many frameworks use an updatable universal reference string (URS). The outer circuit can verify any inner proof generated under that same URS, enabling flexible recursion.

1.3 Examples

• Halo 2:
  • Uses “plonkish” arithmetization to build an inner proof system. Then uses a specialized “KK13” polynomial commitment inside the circuit to verify another proof’s openings. This yields an outer proof that succinctly asserts the inner proof’s correctness.
  • No trusted setup is required for the inner circuit; Halo’s polynomial commitment scheme supports updateable parameters.
• PLONK-Cycle:
  • Constructs a “cycle prover” circuit that embeds the PLONK verifier (gate constraints and polynomial commitments) inside a larger circuit. The process can iterate: a PLONK proof can verify another PLONK proof, achieving potentially infinite recursion as long as the proving system supports recursion.

1.4 Trade-Offs

• Circuit Size vs. Depth: The outer circuit must contain the inner verifier logic. If that logic is large (e.g., many gates for verifying polynomial openings), the outer circuit’s size grows proportionally, increasing prover time.
• Trusted Setup Complexity: Recursion typically requires the same structured reference string (SRS) for inner and outer circuits. Schemes like Sonic or Plonky2 use universal SRS to simplify this.
• Latency: While recursion reduces verifier time, the prover must now (a) generate inner proofs, (b) instantiate the inner verifier inside the outer prover, and (c) produce the final recursive proof—often slower than generating a single nonrecursive proof. For applications that require fast proving (e.g., on-chain relays), this overhead matters.

2. Batching Multiple Proofs

Batching aggregates many independent instances of the same statement or different statements into one proof. Two common approaches are:

• Aggregate Signatures / Folded Verification: Combine multiple SNARK verification equations into a single Folded equation using random linear combinations.
• Single-Instance Circuit with Multiple Instances: Build a circuit whose witness includes multiple independent executions (e.g., “Prove that all 𝑓_i(𝑤_i) = 0 for i=1..k”). Then generate one proof certifying all instances.

2.1 Aggregation via Linear Combination

1. Verifier Equations: A typical SNARK requires checking random linear combinations of polynomial evaluations—e.g., pairing-check equations in Groth16. Given proofs π₁, π₂, …, π_n, we choose random scalars r_i and form one aggregated equation:
   [ \sum_{i=1}^{n} r_i \cdot \text{VerifyEq}(π_i) = 0. ]
2. Proof Compression: Rather than sending all π_i individually, the prover constructs a single π_agg that convinces the verifier that the above linear combination holds.
3. Soundness: If any inner proof is invalid, then with high probability the aggregated equation fails at random r_i.

2.1.1 Applications

• Zcash Orchard: Uses Groth16 aggregation so that verifying 10 Sapling spends can be reduced to one pairing.
• Ethereum 2.0: In early proposals, multiple attestations aggregated into one proof for gas savings.

2.2 Multi-Instance Circuit Patterns

Alternatively, one can build a single circuit encoding k copies of the same statement. For example, to batch 100 verifications, the circuit contains 100 copies of the inner SNARK verifier logic, each with independent inputs. The prover inputs all 100 verifying keys, statements, and proofs; the circuit enforces that each inner instance is valid. Finally, a single proof is generated.

2.2.1 Advantages

• No Aggregation Overhead: All SNARK verification logic is enforced inside a single arithmetization. No in-prover pairing manipulations are needed.
• Uniform Security Assumptions: As long as the SNARK circuit is sound, all inner statements are sound. There is no dependency on random scalars.

2.2.2 Disadvantages

• Circuit Blow-Up: If each inner verifier is 100k gates, and batching k instances yields a circuit of size 100k × k. The prover time and setup time become large.
• Less Flexible: To batch a different number of proofs, one must recompile the circuit.

3. Polynomial Commitments

Polynomial commitment schemes allow a prover to commit to a polynomial and later open it at evaluation points to convince a verifier of correctness. Efficient polynomial commitments are at the heart of modern SNARKs (e.g., KZG, PLONK’s “Kate” commitments, or Bulletproofs’ inner-product-based commitments).

3.1 KZG Commitments (Kate et al.)

• Setup: Generate an SRS containing powers of a secret α: ((g, g^α, g^{α^2}, …, g^{α^d})).
• Commit: For polynomial 𝑓(𝑥)=∑𝑖 a_i𝑥ⁱ, compute C = ∏𝑖 (g^αi)^a_i = g^f(α).
• Open: To prove 𝑓(𝑘)=𝑦, compute quotient polynomial 𝑞(𝑥)=(𝑓(𝑥)−𝑦)/(𝑥−𝑘). Then send π = g^q(α). The verifier checks e(C/g^y, g) = e(π, g^α−k).

3.1.1 Batching Openings

• To open the same polynomial at multiple points {k₁,… ,k_n} with values {y₁,… ,y_n}, one can form a single aggregated opening using random scalar techniques or use one opening per point.
• PLONK uses a single opening per polynomial per sumcheck layer, keeping verifier time to O(1) pairings.

3.2 Plonky2’s Fast FRI Commitments

• Low-Degree Testing: PLONKY2 replaces KZG with a Fast Reed-Solomon IOP (FRI), enabling logarithmic-time openings.
• Recursive-Friendly: The FRI scheme does not rely on pairing-friendly curves, making recursion simpler.
• Prover Complexity: More efficient prover time than KZG when committing to very large polynomials, but verifier complexity grows to O(log d), where d = degree.

4. Framework Case Studies

Below, we examine how PLONK and Halo integrate recursion, batching, and polynomial commitments to achieve scalable performance.

4.1 PLONK (Permutations over Lagrange ON T-Indices)

• Permutation Argument: Enforces copy constraints via a single polynomial lookup.
• Polynomial Commitments: Uses KZG commitments for all polynomials (witness, selectors, permutation).
• Batched Openings: In each proof, PLONK commits to ∼6–10 polynomials and opens all of them at random challenge points. The verifier performs a constant number of pairings (≈ 3).
• Recursion via Plonky2:
  • Plonky2 employs FRI commitments to make PLONK recursive.
  • One can verify previous PLONK proofs inside a new PLONK circuit (cycle proofs).
  • This allows creating “super-proofs” that collapse multiple blocks of rollup transactions into one.

4.1.1 Performance Metrics

Metric	PLONK (KZG)	Plonky2 (FRI)
Prover Time (circuit of 1M gates)	≈ 20 seconds	≈ 8 seconds
Verifier Time (number of pairings)	3 pairings	O(log d) group ops (~100 scalar ops)
Proof Size	~192 bytes	~800 bytes

Notes: FRI-based PLONK (Plonky2) trades larger proof size for much faster prover time and recursion-friendly commitments.

4.2 Halo

• No Trusted Setup: Halo uses the “PLONKish” arithmetization but replaces KZG with the “Plookup” and “Accumulation” arguments.
• Polynomial Commitments: Employs “KK13” commitments, which rely on a pairing-based SRS but do not require a per-circuit trusted setup.
• Recursive Proofs:
  • Halo’s design directly supports recursion without specialized circuit changes.
  • Outer circuit includes Halo’s verifier as arithmetic constraints verifying partial polynomial commitments.

4.2.1 Performance Metrics

Metric	Halo (Inner Proof)	Halo (Recursive Proof)
Prover Time (500k-gate circuit)	≈ 15 seconds	≈ 20 seconds
Recursive Overhead	N/A	+5 seconds
Proof Size	~384 bytes	~384 bytes

Notes: Because proof size remains constant under recursion, Halo is well-suited for rollups that require proof-of-proof aggregation over thousands of transactions.

5. Trade-Off Analysis

When choosing an optimization strategy, designers must consider:

1. Proof Size vs. Verifier Cost:
   • KZG-based PLONK yields very small proofs (~192 B) with constant verifier work (3 pairings).
   • FRI-based PLONK enlarges proof size (~800 B) but reduces verifier work and enables recursion more easily.
   • Halo maintains moderate proof size (~384 B) and supports recursion naturally.
2. Prover Overhead vs. Circuit Complexity:
   • Recursion inflates circuit size, adding inner-verifier constraints. For a 1M-gate inner circuit, the outer circuit might be 1.2–1.5 M gates.
   • Batching via multi-instance circuits multiplies gate counts linearly by the number of instances—often impractical beyond small batch sizes.
   • Aggregation via pairings or linear combinations avoids circuit blow-up but requires more expensive group operations during proof generation.
3. Trusted Setup Considerations:
   • PLONK requires an updatable universal SRS; each new circuit can reuse the same SRS.
   • Halo’s KK13 commitments allow truly “no trusted setup” for each circuit at the cost of larger verifier overhead inside recursion.
   • Some applications mandate zero-trust setups (e.g., rollups run by permissionless entities), making Halo or Sonic preferable.

6. Practical Recommendations

• High-Volume Blockchains / Rollups: Use recursive-friendly proof systems (Halo or Plonky2). Recursion collapses thousands of transactions into one proof, reducing on-chain verification gas cost.
• Low-Latency Verification: If minimizing on-chain verification cost is paramount, choose small-proof systems (KZG-based PLONK) and aggregate multiple attestations via pairing aggregation.
• Rapid Prototyping / Research: For experiments requiring no trusted setup, use Halo or Sonic to avoid the complexity of SRS ceremonies.
• Large Circuits (e.g., Privacy-Preserving ML): FRI-based systems (Plonky2) offer faster prover times when circuits exceed 1M gates and when batching of queries is common.

7. Conclusion

Scaling zero-knowledge proof systems to real-world blockchain workloads requires a combination of recursion, batching, and efficient polynomial commitments. Recursion dramatically reduces verifier workload by collapsing multiple inner proofs, while batching combines many proof instances into one aggregate. Polynomial commitment schemes like KZG and FRI provide succinct openings and support recursive constructions. Frameworks such as PLONK, Plonky2, and Halo demonstrate that with careful trade-offs, ZKP systems can achieve high throughput for both prover and verifier, enabling scalable privacy-preserving computations on decentralized networks.

References

1. Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2018). “Scalable, Transparent, and Post-Quantum Secure Computational Integrity,” Cryptology ePrint Archive.
2. Bowe, S., Grigg, T., & Hopwood, D. (2019). “Halo: Recursive Proof Composition without a Trusted Setup,” Cryptology ePrint Archive.
3. Gazdag, Z., & Kang, S. (2021). “Plonky2: A High-Throughput, Ultra-Quick, Zero-Knowledge Proof System,” GitHub Repository.
4. Kosba, A., Miller, A., Shi, E., Wen, Z., & Papamanthou, C. (2016). “Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts,” IEEE Symposium on Security and Privacy.
5. Maller, M., et al. (2019). “Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updateable Structured Reference Strings,” CRYPTO.
6. Weinberg, S. M., & Wilcox, B. A. (2020). “Efficient Verifiable Delay Functions from Isogenies,” Eurocrypt.