Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients
2026
Read Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16559.txt.
Introduction
Srivastava and colleagues study polynomial multiproofs for availability in blockchain light clients. Light clients verify availability without blocks, fetching cells from a peer network and checking commitments. Giving each cell its own KZG proof creates bandwidth and verification overhead. Their design verifies cell values with one proof over a micro-domain. It adjusts generation, dissemination, retrieval and verification in the stack. Evaluated in Avail, it cut proof size, verifier CPU and memory use. Costs fell by up to 45 percent against a baseline, while grouped-retrieval trade-offs became clear.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 26676 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16559
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Polynomial Multiproofs for Scalable Data Availability Sampling in Blockchain Light Clients Abstract 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. Rachit Anand Srivastava * , Vikram Bhattacharjee * , Will Arnold, Toufeeq Pasha Avail † † footnotetext: * Both authors contributed equally to this work. 1 Introduction Blockchain systems face a basic scalability problem: strong verification usually requires every node to download and validate full blocks, which imposes substantial communication, storage, and computation costs [ 1 , 2 ] . These costs are especially restrictive for light clients running on mobile devices, browsers, and edge environments [ 4 ] . For light clients to be practical at scale, data availability verification must remain both sound and efficient. A common approach is Data Availability Sampling (DAS), in which block data is erasure coded into cells and clients sample a subset of coordinates to obtain probabilistic assurance that the full data is available [ 3 , 1 ] . Many modern deployments authenticate sampled cells using Kate–Zaverucha–Goldberg (KZG) polynomial commitments [ 5 , 3 ] . In a baseline design, however, each sampled cell carries an independent proof, so the cumulative cost of proof transmission, storage, and verification grows quickly with the number of samples. These costs are amplified in peer-to-peer settings, where cells and proofs are retrieved through a distributed hash table (DHT) [ 7 , 4 ] . We address this bottleneck by studying polynomial multiproofs (PMP) as a mechanism for reducing proof overhead in blockchain light clients [ 6 ] . Instead of verifying each sampled cell with a separate KZG proof, a light client verifies multiple sampled cells with one aggregated proof, while the peer-to-peer layer stores grouped proof-carrying objects rather than per-cell objects. We instantiate this design in Avail as a case study. A key requirement is that aggregation must not weaken DAS security. In our design, grouping changes only the transport unit exposed by the DHT. The light client still reasons about sampled coordinates individually. To make this precise, we bind each aggregated proof to a fixed micro-domain of evaluations and to canonical grouping metadata, so the verifier knows exactly which opened values belong to each proof. The main contributions of this paper are: • identifying per-cell KZG proofs as a bottleneck for DAS light clients in peer-to-peer settings and designing a multiproof retrieval and verification model for grouped sampled cells; • specifying the implementation path from full-node proof generation to fat-client DHT publication and light-client verification; and • implementing and evaluating the design in Avail, showing lower verifier overhead and up to 45% lower infrastructure cost. 2 Related Work Data availability has emerged as a central problem in scalable blockchain verification. Al-Bassam et al. [ 1 ] introduced fraud and data availability proofs for strengthening light-client security, and LazyLedger later proposed an architecture centered on ordering and data availability rather than global execution [ 2 ] . Hall-Andersen et al. [ 3 ] formalized DAS and analyzed its security in relation to erasure coding and commitment schemes. At the networking layer, Król et al. [ 4 ] studied the peer-to-peer requirements of Ethereum-style DAS. Polynomial commitments provide the cryptographic basis for many DAS constructions. Kate, Zaverucha, and Goldberg introduced constant-size commitments with succinct evaluation proofs [ 5 ] . Boneh et al. [ 6 ] showed how multiple polynomial evaluations can be aggregated into a single proof. Our work differs from this prior literature by studying how such multiproofs can be integrated into a peer-to-peer light-client workflow, where proof dissemination, retrieval granularity, and verifier cost all matter at the systems level. A relevant engineering reference point is Ethereum’s EIP-4844 and the broader proto-danksharding effort, which deploy KZG commitments and batch verification in a large-scale production setting. That work focuses on validator-side blob verification, whereas we focus on peer-to-peer dissemination and reuse of proof-carrying objects for DAS light clients. In particular, validator-side systems often batch independent openings using pairing-product checks, which is an important comparison point for our evaluation. Recent work on DAS networking has explored stronger dissemination and robustness models than a conventional DHT. PANDAS [ 8 ] redesigns dissemination around direct, lightweight exchanges to meet consensus-time constraints, while Robust Distributed Arrays pursue stronger end-to-end robustness guarantees. Related measurement work on large peer-to-peer content-routing systems also helps contextualize the assumptions behind DHT-based lookup performance. For example, recent studies of IPFS report meaningful centralization and heterogeneity in peer quality, which can materially affect routing reliability, latency, and lookup behavior in practice [ 9 ] . Our work is complementary: rather than redesigning the dissemination substrate, we optimize the cryptographic and storage paths within a DHT-oriented light-client architecture. 3 Polynomial Multiproof Construction A polynomial commitment scheme (PCS) is defined as a tuple of algorithms or protocols \mathcal{S}=(\textsf{gen},\textsf{com},\textsf{open}). Here gen outputs a structured reference string (SRS), com commits to a polynomial, and open proves correct evaluation on designated sets. 3.1 Generic Multiproof Form The construction used in our case study follows the first scheme of Boneh et al. [ 6 ] , which is designed to optimize opening efficiency. To avoid notation overload, we use U_{i}\subseteq T for the opened subset associated with polynomial f_{i} , where T=\{z_{1},\ldots,z_{t}\} is a common ambient evaluation domain. The prover computes h(X):=\sum_{i\in[k]}\gamma^{i-1}\cdot\frac{f_{i}(X)-r_{i}(X)}{Z_{U_{i}}(X)}, (1) where r_{i} is the interpolation polynomial matching the opened values on U_{i} and \gamma is the verifier challenge. The verifier checks one aggregated pairing equation rather than one equation per opening. 3.2 Shared-Point Specialization Used Here To obtain a design suitable for grouped DAS retrieval, we use the shared-point specialization U_{i}=T_{g}\quad\forall i\in[k], (2) where T_{g} is a fixed micro-domain of size g inside one row- or column-commitment context. Each opened polynomial still satisfies the same degree bound d , but all openings appearing in one aggregated proof are over the same micro-domain T_{g} . Under this specialization, h(X)=\frac{\sum_{i}\gamma^{i-1}\left(f_{i}(X)-r_{i}(X)\right)}{Z_{T_{g}}(X)}. (3) The prover therefore computes the weighted polynomial sum, divides by Z_{T_{g}} , and discards the remainder. This avoids interpolation during proof generation. The verifier computes Z_{i}:=[Z_{T_{g}\setminus U_{i}}(x)]_{2}=[1]_{2}=g_{2}, (4) because U_{i}=T_{g} for every opened polynomial, and then reduces the check to a single aggregated pairing relation: \displaystyle F \displaystyle:=\prod_{i}e\left(\gamma^{i-1}\cdot(c_{i}-[r_{i}(x)]_{1}),Z_{i}\right) (5) \displaystyle=e\left(\sum_{i}\gamma^{i-1}c_{i}-\left[\sum_{i}\gamma^{i-1}r_{i}(x)\right]_{1},g_{2}\right). Operation Open Verify Polynomial interpolation 0 1 \mathbb{G}_{1} scalar multiplication d+1-|T_{g}| N+|T_{g}|+1 \mathbb{G}_{2} scalar multiplication 0 d (cacheable) Pairing 0 2 Table 1: