Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients

Computer Science > Cryptography and Security [Submitted on 17 Apr 2026] Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients Rachit Anand Srivastava, Vikram Bhattacharjee, Will Arnold, Toufeeq Pasha 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. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2604.16559 [cs.CR]   (or arXiv:2604.16559v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.16559 Focus to learn more Submission history From: Rachit Anand Srivastava [view email] [v1] Fri, 17 Apr 2026 08:50:12 UTC (742 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)