A key problem in highly distributed consensus protocol is distributing the data (on which consensus is reached) to all nodes in the consensus and even to nodes that do not directly participate in the consensus but are interested in its outcome. In the blockchain lense of consensus, we can focus on distributing the block content (as opposed to the header of the block) to the consensus “full” nodes as well as light clients that follow the blockchain but don’t directly participate in consensus.
This post discusses several techniques and insights that can significantly accelerate this process. Most of these techniques involve using a redundant encoding of the data and then splitting it among the nodes. A block producer does this encoding and splitting. One challenge is that the block producer may be malicious and incorrectly encode this data. We will discuss several techniques that try to prevent or handle incorrectly encoded block data. We also lay out why Espresso is switching from AVID to dispersed ledger (also sometimes referred to as AVID-M) and what the challenges/advantages of this are.
Verifiable information dispersal and data availability sampling
There are two related but orthogonal settings for the distribution of block data, also known as data availability (DA). Verifiable information dispersal or VID, handles the distribution of block data to consensus full nodes. In Espresso we call this the base or Savoiardi layer of our DA. In VID, the block is encoded and split amongst consensus nodes, such that honest nodes can use their shares to recover full and correct blocks. Honest nodes will only sign and accept a block if they received a valid share.
Data availability sampling (DAS), deals with a similar but orthogonal problem. What if consensus nodes delete their data or don’t make it available to non-consensus light clients? In rollup systems, for instance, this could lead to a loss of liveness and even a loss of funds. DAS solves this by letting light-clients query full nodes for small chunks of data. If enough light-clients have queried valid data samples, then they can recover the entire block. If full-nodes do not respond to DAS sample queries then these light-clients will complain publicly and distrust the consensus (aka “Social Consensus”).
Interestingly, the schemes for DAS and VID are very similar and often identical. A key difference is that in VID you generally have significantly fewer nodes (e.g. the full nodes of a consensus), that have known public keys vs. DAS assumes a large, unbounded number of nodes (all light clients). In general, for both DAS and VID, there exists a commitment to a committed block. The difference is simply how (many) nodes sample from this commitment. For this blog post, since it is mainly focussed on the VID/DAS commitments itself, we will treat these schemes as one, but will note how it scales for different number of nodes.
Schemes
AVID (with KZG) https://eprint.iacr.org/2022/775.pdf
The idea of asynchronous verifiable information dispersal or VID is that the block producer sends each node in the consensus their share of the encoded data, along with a proof that it is a valid share of correctly encoded data. Espressos DA, Eigen DA and Danksharding all rely on some variant of the so-called AVID scheme that relies on KZG proofs (also called AVID-Z).
The idea is as follows. The block data is interpreted as a polynomial commitment of some degree d. Each chunk of the block is mapped to a coefficient of the polynomial:
$$
p(X)=\mathsf{block}_0+\mathsf{block}_1\cdot X+\mathsf{block}_2 \cdot X^2…+\mathsf{block}_d \cdot X^d
$$
This polynomial $p$ is then committed to using a KZG polynomial commitment. For simplicity assume that there is $n>d$ nodes (if not just give more shares to each node). The $i$th node receives $y_i=p(i)$ as a share of the data, along with a KZG proof that $y_i$ was indeed correctly derived from $p$.
The key insight is that any $d+1$ nodes can successfully recover the polynomial $p$ and thus the entire block using interpolation.
The reason is that any $d+1$ points uniquely define the polynomial. This is related to the so-called Reed-Solomon encoding.
Note that computing these KZG opening proofs naively is expensive. Each proof takes time $\Omega(d)$ to compute so computing all $n$ proofs would naively take time $\Omega(d\cdot n)$. Fortunately, if the points are well structured then we can take advantage of a faster FFT-style algorithm by Feist an Khovratovich (Fast amortized KZG proofs) that enables computing all n proofs in time $O(n\log(n))$.
There are many further optimizations possible. In our implementation of Espresso DA, we, for instance, use multiple polynomials in order to take advantage of parallelism during the proof generation and thus the data dispersal. A key downside of AVID schemes is that the proof generation needs to happen before the data can be dispersed to all nodes. It is, thus, on the critical path of the consensus, i.e. any delay leads to increased latency in the overall consensus and system. Additionally, another challenge with all VID-based systems is that while recovery is possible with d+1 nodes, it is a tedious and slower process.
Danksharding
Danksharding DAS arranges data into a $L\times k$ matrix, interprets it as a bivariate polynomial, and 2D-RS encodes it into an $m \times n$ evaluation matrix.
notation: the encoded matrix is wider than a perfect square matrix ($m>n$), but we view it as a $n\times n$ square matrix where each row are chunked up into sample with shape: $(1, m/n)$ each containing $m/n$ cells.
Each validator chunk, $O(L+k)$ in size, consists of two columns and two rows of the evaluation matrix
together with a list of evaluation proofs, one for every cell. Limitations of this approach include expensive evaluation proof generation for all $m\times n$ cell; a fairly large commitment which includes $L$ PCS commitments, one from each data row; and the reliance on KZG requires a trusted setup.
Danksharding, a VID or DAS? As we explained earlier, VID and DAS share the same underlying building block: the ability to commit to a codeword and later on open symbols (part of the codeword) with opening proofs. Danksharding is the technique that can be applied to both use cases. When running as a VID among consensus validators, each validator receive two columns and two rows and a few samples scattered across the encoded matrix, before sending out their votes. The fact that VID validators also “sample” makes the terminology slightly confusing. When running as a DAS, each light client queries a random sample (recall $(1\times\frac{m}{n})$-sized) from full nodes. These schemes are designed to meet their security and efficiency requirements, but the verifiability for both VID validators and DAS clients both come from the same technique.
FRIDA
FRIDA extends the idea of AVID to use a hash-based commitment. The block producer encodes the block using Reed-Solomon (RS) codes, i.e., evaluations of the block-data polynomial . These evaluations are then committed to using a Merkle Tree. Then, the idea is to use the FRI protocol to show that the committed data is, in fact, a valid RS codeword. Further, we want to convince each party that they get a valid evaluation, such that, again, a sufficient number of honest parties can recover and, thus, the encoded block. The approach has a couple of advantages but also challenges (some of which are addressed by FRIDA).
A key advantage is that unlike AVID-M and Danksharding, FRIDA relies on hash-based commitments. These can be a) faster than group-based commitments like KZG, b) do not rely on a trusted setup and c) are resistant to quantum computers.
The major challenge is that, naively, each node needs to receive a separate FRI proof, ensuring that their evaluation is correct. This is where FRIDA comes in. The authors proved that the same FRI proof, can essentially be reused for all nodes. Only a single merkle path opening will be different per user. Still, these different FRI proofs can guarantee that each node gets a correct evaluation of $p(X)$. FRIDA also efficiently enables committing to many data-polynomials in parallel and ensuring that each one can be recovered.
Another challenge with FRIDA is that the FRI proofs are relatively large and need to be dispersed to each node in the system. This is mainly a challenge when the number of users is large and each user only receives a small share of the data. Finally, FRIDA, like AVID and Danksharding puts the proof generation on the critical path, i.e. any proof generation time will increase the latency of the overall consensus.
ZODA
DA and VID solutions generally send a data share, along with a correctness proof to each node. Zero-Overhead Data Availability(ZODA, ZODA: Zero-Overhead Data Availability), combines the share and the proof. That is, the data share itself is enough to assert the correctness of the encoded data. ZODA uses a so-called two-dimensional tensor code. The code extends a block written as a matrix of data into a slightly larger matrix. Rows and columns of the matrix are then committed to using Merkle Trees. Each light client then receives a random subset of columns and rows from the block producer, along with the respective Merkle proofs. The light client can perform consistency checks between the rows and columns in order to ensure that the encoding is correct.
The key advantage of ZODA over FRIDA is that each node does not need to receive an additional FRI proof. A key disadvantage is that each node needs to receive approximately $\lambda$ rows and $\lambda$ columns of the encoded data. This means that the scheme is only zero-overhead if there are $\sqrt{|\mathsf{block}|}$ nodes. If there are significantly more nodes then each of them still receives the same amount of data, even if significantly less data would suffice for reconstructing.
Dispersed Ledger
One complete different approach to VID was introduced in the dispersed ledger (aka AVID-M) paper (DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks | USENIX). VID, generally, encodes the data and the produces some sort of proof of correct encoding. The somewhat surprising insight of dispersed ledger is that instead of generating an expensive proof you can simply do nothing. How does this work? The idea is to move the proof generation out of the critical path. The block producer still encodes the block using an arbitrary error-correcting code (it does not need to be a Reed-Solomon code or even a linear error-correcting code; any code will do). Then, the producer commits to it using a Merkle tree and disperses a share of the encoded block to each node.
What, however, if the encoding isn’t correct for a block and nodes cannot recover the block? The idea of AVID-M is that such an incorrect encoding is detectable. Sufficiently many nodes can use their share to attempt to decode a candidate block. They can then re-encode that block and see whether it matches with the Merkle Tree commitment. If not, then the block is skipped, i.e. is treated as an empty block. Note that even if just one share is inconsistent with a correct encoding then this recovery process will detect it and lead to a skipped block. Honest nodes, post recovery, should thus be able to determine post-hoc whether an encoding was valid (happy path) or incorrect (sad-path). The key benefit of this approach is that the correctness check (and proving) is moved of the critical path. The block producer can generate the block and the encoding and directly disperse it to each node. Even if it post-hoc generates a proof of correct encoding this proof is not part of the disperse operation and thus not blocking the consensus. AVID-M is, thus, truly zero-overhead as it requires no proof generation (on the critical path), works with an arbitrary number of nodes, and can use any encoding scheme. The only influence that the encoding scheme has is that sufficiently many honest nodes (e.g. 1/3rd) need to be able to run a deterministic decoding algorithm. We detail the scheme and how it would interplay with Espresso and rollups that run on Espresso in this blog post: Faster VID on Espresso’s critical path.
Thanks to Alex for helping write the post and Chengyu and Binyi for helpful comments