Paper 2025/2292

FRIVail: A Data Availability Scheme based on FRI Binius

Abstract

Data Availability Sampling (DAS) has emerged as a key scalability technique for blockchain systems, enabling light clients to verify that block data have been fully published without downloading them in their entirety. We introduce FRIVail, a new DAS construction built on top of the FRI-Binius polynomial commitment scheme, designed for datasets composed of many independent single-row payloads that together form a block’s data blob. FRIVail exploits the intrinsic Reed–Solomon structure of FRI, wherein each commitment naturally encodes a codeword that light clients can sample directly. Each row of the blob is assigned an independent FRI proof. These row-level proofs are then combined into a global availability certificate using one of three aggregation strategies. The first constructs a succinct zero-knowledge proof attesting to the correct verification of all row-level FRI proofs, yielding a compact ZK proof of proofs that enables succinct global verification while preserving row independence. The second is a fully post-quantum construction that recursively applies FRI-Binius to build a proof of proofs. In this setting, global verification relies on FRI proximity checks, but reconstruction of the aggregated proof polynomial is required to recover embedded row-level information. The third is a hybrid aggregation based on KZG polynomial commitments, where the aggregated polynomial admits direct algebraic openings but relies on pairing-based assumptions and a trusted setup, and is therefore not post-quantum. In all variants, light clients verify availability via a small number of local opening checks against the header commitment, without downloading entire rows or the full blob. We formalize DAS security in this multi-row, multi-proof setting and show that FRIVail achieves sublinear verification complexity, robustness against adversarial availability equivocation at the row level, and resistance to correlated sampling attacks. FRIVail provides a modular foundation for next-generation blockchain data availability protocols, supporting zero-knowledge-based, fully post-quantum, and hybrid cryptographic deployments.