Folding schemes: where proving cost actually went

Proving that a computation was carried out correctly is expensive for the party doing the proving and cheap for everyone else. That asymmetry is the point of the technology and also its bottleneck: a system that can verify in milliseconds is useless if producing the proof takes an hour. Folding is the main idea the field has found for attacking the expensive half, and over the past year it has produced results concrete enough to compare.

What does folding actually do?

Instead of proving many statements separately and then aggregating the proofs, a folding scheme combines the statements themselves into a single accumulated one, and proves that once. The work of combining is far cheaper than the work of proving, so the cost of a batch approaches the cost of one proof plus a small charge per instance.

In a recursive setting the verifier has to be expressed as a circuit and run inside the next proof, which makes the verifier's own size the floor on recursion overhead. That is why a scheme is judged on what its recursive verifier costs rather than on what a human would call verification time.

Why is prover cost the only number that moved?

Because the others were already good enough. Reed-Solomon based schemes have given small proofs and fast verification for years. Our zero-knowledge desk has reported three separate results in as many months aimed at the same target, and in each case the authors go after prover time while treating verification as a budget to stay inside rather than a number to improve.

The right-hand column is the one to read first. Two of these are engineering results with numbers somebody else can reproduce; three are structural arguments. Both kinds are useful, and treating them as the same kind of evidence is how a team ends up rebuilding a proving stack around a claim that was never a measurement.

Why does the first round dominate?

In a FRI-style construction the proof is produced by recursively folding Reed-Solomon codewords, each round halving the thing being worked on. The first rounds therefore operate on the largest codewords and account for most of the prover's work. ReedWeave attacks exactly that step: it decomposes a polynomial of degree d into m smaller components encoded over a common domain, so that a random linear combination of those codewords is itself an m-ary fold. The scheme opens with one wide fold and then continues with ordinary binary folding.

A second property of that construction matters more to an implementer than the asymptotics: it works for arbitrary m, which relaxes the smoothness requirement on the underlying field by a factor of m. A proving scheme that does not force a field choice on the system around it is a scheme that can be adopted without rewriting everything else.

The lattice branch, and what it is not telling you

A parallel line of work replaces group-based constructions with lattice assumptions, for plausible post-quantum security. Neo and SuperNeo build on Module-SIS with Ajtai commitments and support general constraint systems over arbitrary extension fields; the difference between the pair is that Neo requires SIMD-shaped constraints and SuperNeo does not, which is what makes the second applicable to ordinary circuits. Symphony takes a different route to the same goal and avoids embedding a hash function in the verified circuit, which is the recurring cost in recursive systems because hashing inside a circuit is expensive.

Neither paper publishes timings. The efficiency claims are structural, and until somebody measures them against an existing scheme on the same machine, the honest description is that they are arguments about asymptotics rather than benchmarks.

How should two proving stacks be compared?

• On the same hardware, with the same circuit, at the same code rate — none of which is implied by a published complexity.
• On prover time as the headline, since that is the number deciding feasibility, with verification and proof size as budgets to stay inside.
• On what the recursive verifier costs, not the standalone one, if recursion is in the design at all.
• On whether the result survives being placed inside a real proof system: an evaluation scheme that gives 6.7x on its own step and 1.55x overall is telling you where the rest of the time goes.
• On whether anyone else has built on it. A construction that other researchers have extended has been read carefully by people with an interest in finding fault.

The last point is softer than the others and in practice it discriminates well. Independent reproduction has become a visible norm on this subject: we have covered a case where a result was checked by someone outside the author group before it was accepted, and that is a better signal than any asymptotic.