Scaling Verifiable Computation via Proof Aggregation and Folding

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2334 papers526 conceptsfrozen 2026-10-04

In traditional cryptography, the cost of verifying a computation scales linearly with the size of the computation itself. If a blockchain needs to verify 1,000 transactions, the network typically performs 1,000 verification checks. As decentralized systems scale, this linear relationship becomes a fundamental bottleneck.

The research direction emerging from these papers focuses on Proof Aggregation and Folding, a suite of techniques designed to decouple verification costs from the number of operations. By mathematically "squashing" multiple proofs into one, researchers are moving toward a world where verifying a million transactions costs nearly the same as verifying one.

The Intuition of Amortization

The simplest way to improve efficiency is batch verification. Instead of checking each proof in isolation, we can combine them into a single mathematical statement.

As Jonathan Bootle and Benedikt Bünz demonstrate in Bulletproofs, multiple range proofs can be aggregated into one. The core intuition here is multi-exponentiation: by using a shared set of generators and random challenges, a verifier can validate $N$ proofs using a single operation that is only slightly more expensive than a single check. This reduces the marginal cost per proof to a near-constant value, as also seen in the work of Bin Xiao on lattice-based confidential transactions.

From Linear to Logarithmic: The Sum-Check Protocol

While simple batching helps, it often still leaves the verifier with a workload that grows with the number of inputs. To achieve true scalability, researchers like Bin Xiao and Shang Gao 0006 utilize the Sum-Check protocol.

In Σ-Check, the authors replace traditional linear amortization with a dual-phase sum-check. The sum-check protocol works by reducing a claim about a high-degree polynomial over a large space into a claim about a single point. By applying this recursively, the communication overhead drops from linear ($O(N)$) to logarithmic ($O(\log N)$). This is the same mechanism that allows HyperPlonk to eliminate the memory-heavy Fast Fourier Transform (FFT) bottleneck, enabling provers to run in linear time while keeping verifiers efficient.

Folding Schemes and Incremental Accumulation

The most recent breakthrough in this field is the shift from "batching" (processing many proofs at once) to "folding" (merging proofs incrementally).

Think of folding like a snowball. In a system like Verdict or SnarkFold, you don't wait for all transactions to arrive to create a batch. Instead, as each new state transition occurs, you "fold" the new proof into a running accumulator.

Justin Drake and Ariel Gabizon showed in Halo Infinite that this can be done without a trusted setup. The "magic" of folding is deferred verification: instead of fully checking the expensive cryptographic pairings at every step, the system only checks that the "folding" was done correctly. The actual, heavy verification is performed only once, at the very end of the chain. This allows for Incrementally Verifiable Computation (IVC), where the proof size remains constant regardless of how many steps the computation has taken.

Recursive Composition: Proofs of Proofs

To reach the "holy grail" of constant-time verification, researchers use recursive proof composition. If a verifier's logic is itself a computation, why not write a proof for it?

In ZEBRA, Tiancheng Xie and Dawn Song use a two-layer recursion where an untrusted aggregator collects many user proofs and wraps them in a single "outer" proof. Similarly, Abhiram Kothapalli and Bryan Parno demonstrate in Poppins that by composing proofs, one can reduce a logarithmic-time verifier to a constant-time verifier.

This recursive structure is what enables cross-chain state synchronization and validating bridges. A light client doesn't need to download the entire history of a blockchain; it only needs to verify a single, succinct proof that represents the valid accumulation of every block header and transaction that came before it.

Papers in this version

Showing 60 of 334 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 190 papers
  2. Version 1 · 2026-10-04 · 334 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_amortized_verification_cost_23b27c1d,
  title = {amortized verification cost},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/amortized-verification-cost/rdr_23b27c1d42fc4fb28871ce3702390cca},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_verifiable_computation_via_proof_23b27c1d_v1,
  title = {Scaling Verifiable Computation via Proof Aggregation and Folding},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-verifiable-computation-via-proof-aggregation-and-folding/rdr_23b27c1d42fc4fb28871ce3702390cca/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}