Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients
For blockchain light clients, this provides a practical method to lower resource costs in data availability sampling, though the improvement is incremental over existing KZG-based approaches.
This work introduces polynomial multiproofs to reduce bandwidth, storage, and verification overhead in blockchain light clients performing data availability sampling. In a case study on the Avail network, the approach achieves up to 45% reduction in infrastructure costs compared to per-cell proofs.
Light clients are essential for scalable blockchain systems because they verify data availability without downloading full blocks. In data availability sampling based systems, sampled cells are retrieved from a peer-to-peer network and verified against cryptographic commitments. A common deployment pattern associates each sampled cell with an independent Kate-Zaverucha-Goldberg (KZG) proof, creating substantial cumulative bandwidth, storage, and verification overhead. This paper studies polynomial multiproofs (PMP) as a mechanism for reducing these costs in blockchain light clients. We present a design in which multiple sampled cell evaluations are verified using a single aggregated proof over a shared evaluation micro-domain and describe the corresponding changes to proof generation, dissemination, retrieval, and verification in a peer-to-peer light-client stack. We instantiate and evaluate the design in Avail, a modular data availability layer for blockchains, as a case study. The results show lower proof bytes, lower verifier CPU and memory usage, and deployment-level infrastructure cost reductions of up to 45% relative to a per-cell baseline, while also clarifying the trade-offs introduced by grouped retrieval.