Paper 2025/1354

Shred-to-Shine Metamorphosis of (Distributed) Polynomial Commitments

Abstract

Succinct non-interactive arguments of knowledge (SNARKs) rely on polynomial commitment schemes (PCSs) to verify polynomial evaluations succinctly. High-performance multilinear PCSs (MLPCSs) from linear codes reduce prover cost, and distributed MLPCSs reduce it further by parallelizing commitment and opening across provers. Employing a fast Reed--Solomon interactive oracle proof of proximity (FRI), we propose PIPFRI, an MLPCS that combines the linear-time proving of linear-time-encodable-code PCSs with the compact proofs and fast verification of Reed--Solomon (RS) PCSs. Reducing fast Fourier transform and hash overhead, PIPFRI is 10× faster to prove than the RS-based DeepFold (USENIX Security '25) while keeping competitive proof size and verifier time. Measured against Orion (CRYPTO '22) from linear-time-encodable codes, PIPFRI proves 3.5× faster and reduce proof size and verifier time by 15×. As a linearly scalable distributed variant, we propose DEPIPFRI, which adds accountability and distributes a single polynomial across provers, enabling the first code-based distributed SNARK for general circuits. Notably, compared with DeVirgo (CCS '22), which lacks accountability and supports only multiple independent polynomials, DEPIPFRI improves prover time by 25× and inter-prover communication by 7×. We identify shred-to-shine as the key insight: partitioning a polynomial into independently handled fragments while maintaining proof size and verifier time. Hitting the pairing regime, this insight yields a group-based MLPCS with a 16× shorter structured reference string (SRS) and a 10× faster opening time than a multilinear variant of Kate--Zaverucha--Goldberg (TCC '13).