How data availability sampling works: erasure coding and light node sampling
Post430 words
Walks through DAS: light nodes sample random chunks of erasure coded blocks, with Celestia's 2D Reed-Solomon 1/4 rate expanding 1MB to 4MB. Contrasts Celestia fraud proofs with Avail validity proofs.
Key claims
Celestia's 2D Reed-Solomon coding turns a 1MB block into 4MB
25% availability is enough to recover the remaining 75%
Sampling gives probabilistic data availability guarantees of 99.999...%
How does Data Availability Sampling (DAS) work?
Initially a block producer publishes a block header. Subsequently, light nodes will start to request random chunks of data from that block from the block producer. If data has been made available, the producer releases data chunks as light nodes request.
DA solutions like @AvailProject or @CelestiaOrg, which are pioneering DAS, also uses a mathematical primitive called erasure coding prior to performing data availability sampling and light clients probabilistically determine the entirety of a block has been published by randomly sampling small portions of the erasure coded block.
At a high level, erasure coding adds redundancy to a string of data. The key property is that, if the redundant data is available, the original data can be reconstructed in the event some part of the data gets lost. Even more importantly though, it doesn鈥檛 matter which part of the data is lost. As long as X% (tolerance threshold) of the data is available, the full original data can be reconstructed.
@CelestiaOrg for example uses 2D Reed-Solomon erasure codes with a 1/4 code rate. So validators erasure code blocks prior to publishing, turning a 1MB block of data into a 4MB block. Hence, if at least 25% of the txs in a block are available to the network, it can recover the remaining 75%. This makes it very hard for a block producer to hide data unnoticed. Thanks to erasure coding, honest full node in the network can recover the original block from the broadcast chunks if light nodes collectively sample >25% of the erasure-coded block.
If the block producer is malicious and withholds data, the light nodes notice as their sampling test fails and the network can be halted / recovered (ultimately through social consensus if needed).
So, through sampling small chunks of erasure coded blocks, light nodes can reach a probabilistic security guarantee (99.999...%) for data availability, with more DASing nodes increasing the capacity of the network to securely ensure DA for larger block sizes. While, there is a minimum number of light nodes required for this data sampling to work, it allows light nodes to function under almost the same security guarantees as full nodes (if at least one honest full node exists).
By verifying that all tx data has been made available, light nodes can now fully rely on fraud proofs (in the case of Celestia) or validity proofs (in the case of Avail), knowing that any single honest full node can generate these proofs for them.
Stay tuned for more insights on data availability, DAS, erasure coding and more!馃憖