Moving prover cost off the large polynomial

Polynomial commitment schemes let a prover commit to a large polynomial and later prove its value at a chosen point. They sit inside most efficient SNARKs, and the cost of the evaluation phase feeds directly into prover time — which is the number that decides whether a proving system is deployable.

Reed-Solomon based schemes already give small proofs and fast verification. The expensive part is producing an evaluation proof for a large polynomial. LiftWHIR attacks that step by combining interleaved coding with the DEEP technique, reducing the problem to two smaller ones: a proximity test on a shorter codeword, and the evaluation of a smaller polynomial. Both are then proved with WHIR, which keeps verification and communication small.

The measured effect, at a polynomial of size two to the twentieth over a 255-bit prime field:

• At code rate one half — evaluation phase of 167 ms, a 4.4x speedup over WHIR, and total prover time of 808 ms, 1.61x overall.
• At code rate one quarter — evaluation phase of 169 ms, a 6.7x speedup, and total prover time of 1,474 ms, 1.55x overall.

The trade is explicit and small. Verification rises from 0.55 ms to 0.76 ms at rate one half, and from 0.40 ms to 0.51 ms at one quarter. Proof size grows to 1.46 and 1.33 times that of WHIR respectively.

Instantiating Spartan with LiftWHIR rather than WHIR speeds up proving by 1.9 times. That is the figure worth carrying: an asymptotic improvement in a commitment scheme only matters if it survives being placed inside a real proof system, and here it does.

The direction is the same one this desk has been reporting for a year. Verifier time and proof size were solved well enough for production some time ago; prover cost is what still decides which applications are possible.