Paper 2026/1367

SoK: Hash-Based Polynomial Commitments and Low-Degree Tests: From FRI to Basefold, STIR, and WHIR

Abstract

Hash-based low-degree tests and polynomial commitment schemes have become the cryptographic engine of a large fraction of deployed succinct-argument systems. Unlike pairing-based commitments such as KZG, they require no trusted setup, rely only on a collision-resistant hash, are plausibly post-quantum, and operate over any sufficiently large field, unlocking small fields whose arithmetic is fast on commodity hardware. Between 2017 and 2025 this design space evolved rapidly along two intertwined lineages: the Reed-Solomon proximity-test line (FRI, DEEP-FRI, STIR, WHIR) and the linear-code tensor-commitment line (Ligero, Brakedown), which Basefold and WHIR ultimately merge. Yet the primary sources report their guarantees under different, and frequently conflated, soundness regimes: unique decoding, the Johnson list-decoding bound, and (conjecturally) capacity. The folklore surrounding these schemes has drifted from what the papers actually prove. We systematize this line of work. We organize the seven core schemes along a taxonomy of committed object, code class, and testing mechanism; we trace the evolutionary chain in which each scheme answers a concrete limitation of its predecessor; and we ground the theory in a survey of production zero-knowledge systems, showing how field choice and soundness regime jointly explain real engineering decisions, including a sumcheck-based multilinear prover reaching mainnet in 2026. We make two systematizing corrections. First, the DEEP folklore: the out-of-domain trick that survives in deployment (DEEP-ALI, on the constraint side) is distinct from the low-degree-test modification it is usually conflated with. That modification was superseded for FRI soundness by the Proximity Gaps analysis, which also proves Johnson-bound FRI soundness and is itself routinely misattributed to the original FRI paper. Second, and more consequential: the capacity-soundness conjectures on which nearly all deployed systems set their parameters had their strongest, up-to-capacity forms, including the mutual-correlated-agreement conjecture behind the newest schemes, disproved over large fields in late 2025. Soundness up to the Johnson bound is unaffected and the practical repricing is modest, but the discount the ecosystem had tacitly taken was, in its optimistic form, wrong. Our central thesis is that this proven-versus-conjectured soundness axis, not asymptotic query complexity, is the load-bearing and least-consistently-reported dimension of the design space, and the field has now had to reprice it.