The first folding round costs the most

Hash-based polynomial commitments built on FRI achieve short proofs by recursively folding Reed-Solomon codes. The cost sits in a predictable place: the first few folding rounds operate on the largest codewords, and they dominate prover work.

ReedWeave, posted this week, attacks that first round directly by combining interleaving with folding rather than choosing between them. A polynomial of degree d is decomposed into m smaller components, each Reed-Solomon encoded over a common domain. Under the decomposition the authors define, a random linear combination of those codewords is exactly an m-ary folding — so the scheme opens with one wide fold and then continues with ordinary binary folding as in FRI.

The saving is that the expensive opening step becomes interleaved encoding rather than full Reed-Solomon encoding. Prover cost falls from order d log d to order d log(d divided by m) at constant code rate, while verification stays polylogarithmic.

A second property matters for implementers more than the asymptotics. The construction works for arbitrary m, which relaxes the smoothness requirement on the underlying field by a factor of m — meaning the scheme does not force a particular field choice on the system built around it. The authors benchmark a Rust implementation over Goldilocks using 32 threads.

This is the third result on this desk in as many months pointing at the same target, after a scheme that moved evaluation cost off the large polynomial and a folding construction that dropped the SIMD requirement. Verification and proof size were solved well enough for production some time ago; prover cost is where the work is, and it is where the field keeps finding room.