Proof system
Also: Proving system
The whole machinery that produces and checks a cryptographic proof — arithmetisation, commitment scheme and argument — judged on prover time, verifier time and proof size together.
A proof system is a stack rather than an algorithm: a way of expressing a computation as constraints, a commitment scheme for the resulting polynomials, and an interactive argument made non-interactive. Replacing any layer moves all three of the numbers that matter, which is why a result that improves one in isolation often worsens another.
The three costs, and which one still binds
Verifier time and proof size have been good enough for production for some time. Prover cost is what decides which applications are possible, which is why the results worth reading attack it. ReedWeave opens with an m-ary fold and cuts prover cost from order d log d to order d log(d/m) at constant code rate. LiftWHIR splits the evaluation into a proximity test on a shorter codeword and a smaller evaluation, reaching a 169-millisecond evaluation phase for a 2^20 polynomial, a 6.7-times speedup, in exchange for verification rising from 0.40 to 0.51 milliseconds.
Why the system matters more than the scheme
An asymptotic improvement counts only if it survives being placed inside one. Instantiating Spartan with LiftWHIR rather than WHIR sped up proving by 1.9 times, and the AG skip was measured inside the Flock proof system rather than in isolation. Work that reports no baseline and no timings cannot be compared on this axis at all.
Questions
- What is a proof system?
- The full stack that produces and verifies a cryptographic proof: an arithmetisation of the computation, a commitment scheme and an argument built over them. It is judged on three costs at once — prover time, verifier time and proof size.
- Which of the three costs is the bottleneck?
- Prover time. Verifier time and proof size have been adequate for production for some time, so prover cost is what decides which applications are feasible.