Paper 2025/1285

FRIttata: A FRI-based Polynomial Commitment Scheme for Distributed Proof Generation

Abstract

We present the first horizontally scalable polynomial commitment scheme (PCS) that is both transparent and plausibly post-quantum (PQ) secure. This PCS can be combined with the distributed polynomial interactive oracle proof (PIOP) introduced in Pianist (IEEE S&P 2024), which achieves linear scalability by encoding witnesses using bivariate polynomials. While Pianist and other scalable SNARK systems offer strong performance profiles, they rely on trusted setup ceremonies and cryptographic assumptions that are not PQ secure, e.g., pairing-based primitives. In contrast, we present a bivariate PCS based on FRI, which, when used to compile the Pianist PIOP, achieves a transparent and plausibly PQ alternative. Distributed FRI has a high communication cost. Therefore, we introduce Fold-and-Batch, a customizable technique that applies partial folding locally before performing batched FRI centrally. We formally prove the security of our constructions and provide an implementation for three variants of distributed FRI, accompanied by thorough performance evaluations. Our results show that Fold-and-Batch reduces communication overhead compared to existing distributed FRI approaches, while preserving scalability and maintaining moderate proof sizes. To our knowledge, this is the first horizontally scalable PCS that simultaneously achieves transparency, plausible PQ security, and a tunable tradeoff between efficiency, verifier cost, and communication.