In the world of verifiable computation, "succinctness" is often the headline feature. We want proofs that are small enough to fit in a tweet and fast enough to verify on a smartphone. However, a hidden bottleneck persists: even when a proof is physically small, the computational effort required to generate or verify it often scales linearly with the size of the computation.
As we move toward verifying billion-parameter neural networks or global-scale blockchains, "linear" is no longer fast enough. A new wave of research is focused on breaking this linear wall, moving toward sublinear—and even constant-time—complexity for both provers and verifiers.
The Linear Verification Wall
The classic promise of zero-knowledge proofs, such as Bulletproofs developed by Jonathan Bootle, Benedikt Bünz, and others, is logarithmic proof size. While the data sent over the wire is tiny, the verifier's work often remains proportional to the complexity of the statement. If you are proving a million-gate circuit, the verifier might still need to perform a million group operations.
This linear scaling creates a "computational wall" in decentralized systems. For instance, in group signatures or anonymous blocklists, Giuseppe Ateniese and Dawn Song noted early on that checking a signature against a growing revocation list becomes a bottleneck if the verifier must touch every entry Ateniese et al..
To solve this, researchers are developing "index-efficient" or sublinear verification schemes. A notable example is Cougar, introduced by Hyeonbum Lee and colleagues, which achieves $O(\sqrt[3]{N})$ verifier complexity Lee et al.. By breaking the linear dependency, these systems allow resource-constrained "Lilliputians" to verify the massive computations of a "Gulliver" server without processing the entire input Alon et al..
Moving Beyond Linear Prover Time
The verifier isn't the only one struggling with scale. For the prover, generating a proof for massive operations—like matrix multiplications in large language models—can be prohibitively expensive. Standard zkSNARKs often face superlinear prover complexity, where the work grows faster than the input size.
Recent work like DualMatrix by Mingshu Cong and Tsz Hon Yuen addresses this by achieving prover time that is strictly linear to the number of non-zero elements in a matrix Cong et al.. This allows for the verification of matrices with billions of entries, a feat previously impossible due to memory and time constraints.
Taking this further, Matteo Campanelli, Dario Fiore, and their collaborators have explored polynomial preprocessing to achieve sublinear prover time Campanelli et al.. By shifting some of the computational burden to a one-time setup phase, the prover can generate proofs for specific parts of a large computation without re-processing the entire circuit.
Accumulators and the Recursion Tax
In applications like blockchain state management or machine unlearning, the "computation" isn't a single circuit but a series of updates to a massive dataset. Traditional Merkle trees require proof paths that grow with the number of operations Ozdemir & Wahby.
To scale these systems, researchers use cryptographic accumulators and folding schemes. These tools allow multiple proofs to be "compressed" or "folded" into one. However, even this often incurs a "recursion tax"—a linear cost to verify the aggregation itself.
Quasar, a framework by Bin Xiao and Shang Gao, introduces sublinear accumulation schemes that significantly reduce this overhead Xiao et al.. Similarly, KiloNova uses holographic folding to achieve constant-size proofs for non-uniform computations, ensuring that the complexity of the proof doesn't explode as the set of supported instructions grows Xiao et al..
Intuition: From Scanning to Sampling
Why does this work? The shift from linear to sublinear complexity usually involves moving from scanning to sampling or holography.
- Polynomial Commitments: Instead of checking every data point, we treat the data as a polynomial. We can then "sample" this polynomial at a random point. If the sample matches, the entire polynomial (and thus the data) is likely correct with high probability.
- Preprocessing (Holography): By "encoding" the circuit or the data in advance, the verifier doesn't need to read the whole thing. They only need to check a small, encoded representation.
- Sum-check Protocols: Frameworks like Σ-Check replace expensive linearization with multi-phase protocols that reduce the communication and verification work to logarithmic scales Xiao et al..
By combining these techniques, researchers are transforming verifiable computation from a niche tool for small transactions into a scalable foundation for global data integrity, from verifiable machine unlearning to decentralized storage.