Paper 2025/865

UltraProofs: Scalable Reed-Solomon Code Commitment

Abstract

Reed–Solomon (RS) codes underpin a wide range of cryptographic protocols, from verifiable secret sharing (VSS) to blockchain data availability (DA). An RS code commitment enables a prover to distribute codeword fragments among many parties while allowing each recipient to verify that its fragment is consistent with a RS code. Existing constructions either rely on homomorphic polynomial commitments, which incur redundant commitments and expensive group operations, or use FRI-based interactive proofs, which achieve fast proving but suffer from prohibitively large communication. We present UltraProofs, a new RS code commitment framework that achieves linear-time proof generation while remaining compatible with any multilinear polynomial commitment. Our key technical contribution is an evaluation-consolidation protocol that reduces $n$ evaluation proofs at distinct RS points to a single randomized evaluation, eliminating redundant commitments and removing the need for homomorphic structure. We further design a tailored multilinear PCS, LightLigero, which achieves $O(\lambda \log n)$ proof size and maintains $O(n \log n)$ prover time. UltraProofs attains asymptotically optimal prover complexity with concrete speedups in practice: in VSS, it reduces prover time by $2.4\times$ and proof size by $4\times$ compared to HydraProofs (S&P'25); in DA, it cuts per-node communication by up to $2{\sim}5\times$ relative to FRIDA (Crypto'24) while retaining similar prover cost. By decoupling verifiable RS encoding from any specific PCS instantiation, UltraProofs provides a flexible, efficient, and modular foundation for large-scale verifiable storage and distributed cryptographic systems.