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

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 cut it further by parallelizing commitment and opening across provers. Employing a fast Reed-Solomon interactive oracle proof of proximity (FRI), we propose PIP FRI , 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, PIP FRI 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 lineartime-encodable codes, PIP FRI proves 3.5× faster and reduces proof size and verifier time by 15×. As a linearly scalable distributed variant, we propose DEPIP FRI , 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, DEPIP FRI improves prover time by 25× and inter-prover communication by 7×. We identify shred-toshine 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).