Data Availability Sampling

This document traces the complete DAS flow from block production through light client verification.

Overview

DAS ensures block data is available without requiring light clients to download full blocks. The chain uses Reed-Solomon erasure coding to split blocks into chunks, then light clients randomly sample chunks to verify availability with high confidence.

Block produced --> Erasure encode --> Chunks distributed via gossip -->
Light client samples random chunks --> Verify proofs --> Accept/reject block

Key Properties

Property	Value
Coding scheme	Reed-Solomon with SHA256 commitments
Production config	64-of-128 shards (50% redundancy)
Sample count	30 random samples
Confidence	99.99% (if >50% hidden, detection probability > 1 - 10^-9)
Sample timeout	500ms per sample
Total timeout	5s for full DAS verification

---

1. Erasure Coding

BlockChunkProducer

Encodes blocks into shards:

pub struct BlockChunkProducer {
    scheme: ReedSolomon<Sha256>,
    config: CodingConfig,
}

impl BlockChunkProducer {
    pub fn encode_block(&self, block: &Block) -> Result<BlockChunkBundle, ...> {
        let bytes = borsh::to_vec(&BlockEnvelope::from(block))?;
        self.encode_bytes(&bytes)
    }

    pub fn encode_bytes(&self, data: &[u8]) -> Result<BlockChunkBundle, ...> {
        let (commitment, chunks) = self.scheme.encode(data)?;
        Ok(BlockChunkBundle { commitment, chunks })
    }
}

BlockChunkVerifier

Validates and reconstructs:

pub struct BlockChunkVerifier {
    scheme: ReedSolomon<Sha256>,
}

impl BlockChunkVerifier {
    // Verify single chunk against commitment
    pub fn check_chunk(&self, commitment: &Hash, chunk: &BlockChunk)
        -> Result<CheckedBlockChunk, ...>;

    // Reconstruct block from minimum_shards checked chunks
    pub fn decode_block(&self, commitment: Hash, chunks: Vec<CheckedBlockChunk>)
        -> Result<Block, ...>;
}

Configuration

// Dev/test (current)
CodingConfig {
    minimum_shards: 2,   // k: minimum for reconstruction
    extra_shards: 2,     // redundancy shards
}
// Total: 4 shards

// Production target
CodingConfig {
    minimum_shards: 64,
    extra_shards: 64,
}
// Total: 128 shards, 50% availability threshold

Chunk Format

pub type BlockChunk = <ReedSolomon<Sha256> as Scheme>::Shard;

pub struct BlockChunkBundle {
    pub commitment: Hash,        // Merkle root of all chunks
    pub chunks: Vec<BlockChunk>, // n encoded shards with proofs
}

Each chunk includes a Merkle proof allowing verification against the commitment.

---

2. DA Commitment in Block Headers

During block construction, the DA commitment is computed and included in the header:

// In build_block_preview()
let data_availability_root =
    crate::data_availability::compute_default_da_commitment(&execution)
        .unwrap_or_else(|e| {
            tracing::warn!(error = ?e, "failed to compute DA commitment");
            Hash::empty()
        });

let header = BlockHeader {
    // ...
    data_availability_root,  // Merkle root of erasure-coded chunks
    // ...
};

pub struct BlockHeader {
    pub height: BlockHeight,
    pub parent_hash: Hash,
    pub state_root: Hash,
    pub exec_payload_root: Hash,
    pub data_availability_root: Hash,  // <-- DAS commitment
    pub timestamp: u64,
    // ...
}

This commitment is signed by consensus, binding validators to the availability of the data.

---

3. Chunk Distribution (Gossip)

Gossip Message Types

pub enum ChunkGossipMessage {
    Request(ChunkRequest),
    Response(ChunkResponse),
    Announce(ChunkAnnounce),
}

pub struct ChunkAnnounce {
    pub block_hash: Hash,
    pub commitment: Hash,
    pub available_indices: Vec<u16>,
    pub total_chunks: u16,
}

pub struct ChunkRequest {
    pub block_hash: Hash,
    pub indices: Vec<u16>,
}

pub struct ChunkResponse {
    pub block_hash: Hash,
    pub chunks: Vec<(u16, Vec<u8>)>,  // (index, encoded_chunk)
}

Application Actor Integration

After block finalization:

// Encode block into chunks
let bundle = self.chunk_producer.encode_block(&block)?;

// Cache for serving via gossip
self.pending_chunks.put(block_hash, bundle);

tracing::debug!(
    block_hash = %block_hash,
    commitment = %bundle.commitment,
    num_chunks = bundle.chunks.len(),
    "cached block chunks for DA"
);

---

4. Light Client DAS Verification

Sampling Configuration

pub struct DasSamplingConfig {
    pub sample_count: u16,        // Default: 30
    pub min_valid_samples: u16,   // Default: 0 (all must be valid)
    pub max_invalid_samples: u16, // Default: 0 (strict mode)
    pub sample_timeout: Duration, // Default: 500ms
    pub total_timeout: Duration,  // Default: 5s
}

Random Index Generation

pub fn generate_random_indices(
    sample_count: u16,
    total_chunks: u16,
    entropy: &[u8; 32],
) -> Vec<u16> {
    // SHA256-based PRNG seeded with entropy
    // entropy = block_hash XOR local_randomness
    // Generates unique random indices without replacement
}

Sample Verification

pub fn verify_sample(
    verifier: &BlockChunkVerifier,
    commitment: Hash,
    index: u16,
    chunk_bytes: &[u8],
) -> Result<(), DasError> {
    let chunk = decode_chunk(chunk_bytes)?;
    verifier.check_chunk(&commitment, &chunk)?;
    Ok(())
}

Main Verification Function

pub async fn verify_availability<F: ChunkFetcher>(
    config: &DasSamplingConfig,
    coding_config: &CodingConfig,
    block_hash: Hash,
    commitment: Hash,
    entropy: &[u8; 32],
    fetcher: &F,
    verifier: &BlockChunkVerifier,
) -> DasResult {
    let total_chunks = coding_config.total_shards();
    let indices = generate_random_indices(config.sample_count, total_chunks, entropy);

    let mut outcomes = Vec::new();

    for index in indices {
        match timeout(config.sample_timeout, fetcher.fetch_chunk(...)).await {
            Ok(Ok(bytes)) => {
                match verify_sample(verifier, commitment, index, &bytes) {
                    Ok(()) => outcomes.push(SampleOutcome::Valid),
                    Err(_) => outcomes.push(SampleOutcome::Invalid),
                }
            }
            Ok(Err(_)) => outcomes.push(SampleOutcome::Invalid),
            Err(_) => outcomes.push(SampleOutcome::Timeout),
        }
    }

    aggregate_das_results(&outcomes, config)
}

Result Aggregation

pub enum DasResult {
    Available,
    Unavailable { valid: u16, invalid: u16, timeout: u16 },
    Timeout,
}

pub fn aggregate_das_results(
    outcomes: &[SampleOutcome],
    config: &DasSamplingConfig,
) -> DasResult {
    let valid = outcomes.iter().filter(|o| matches!(o, Valid)).count();
    let invalid = outcomes.iter().filter(|o| matches!(o, Invalid)).count();
    let timeout = outcomes.iter().filter(|o| matches!(o, Timeout)).count();

    if invalid > config.max_invalid_samples as usize {
        return DasResult::Unavailable { ... };
    }
    if valid < config.min_valid_samples as usize {
        return DasResult::Unavailable { ... };
    }

    DasResult::Available
}

---

5. Block Recovery

When a full block is needed (not just availability verification):

ChunkRecoveryHandle

pub struct ChunkRecoveryHandle {
    config: CodingConfig,
    request_tx: mpsc::Sender<ChunkGossipCommand>,
    request_timeout: Duration,
}

impl ChunkRecoveryHandle {
    pub async fn recover_block(&self, block_hash: Hash) -> Result<Block, ...> {
        // 1. Fetch chunk announce
        let announce = self.fetch_announce(block_hash).await?;

        // 2. Validate config matches
        if announce.total_chunks != self.config.total_shards() {
            return Err(ChunkRecoveryError::ConfigMismatch);
        }

        // 3. Fetch and decode
        recover_block(block_hash, announce.commitment, ...).await
    }
}

Recovery Function

pub async fn recover_block<F: ChunkFetcher>(
    block_hash: Hash,
    commitment: Hash,
    fetcher: &F,
    verifier: &BlockChunkVerifier,
    config: &CodingConfig,
) -> Result<Block, ChunkRecoveryError> {
    let mut checked_chunks = Vec::new();

    // Fetch all chunks (tolerating some failures)
    for index in 0..config.total_shards() {
        match fetcher.fetch_chunk(block_hash, commitment, index).await {
            Ok(bytes) => {
                if let Ok(chunk) = decode_chunk(&bytes) {
                    if let Ok(checked) = verifier.check_chunk(&commitment, &chunk) {
                        checked_chunks.push(checked);
                    }
                }
            }
            Err(_) => continue,  // Skip failed fetches
        }

        // Early exit if we have enough
        if checked_chunks.len() >= config.minimum_shards as usize {
            break;
        }
    }

    // Reconstruct
    verifier.decode_block(commitment, checked_chunks)
}

---

6. Sequence Diagram

BLOCK PRODUCTION (Validator)
    |
    +-- Execute transactions
    |   +-- ExecutionPayload
    |
    +-- compute_default_da_commitment(payload)
    |   +-- ReedSolomon::encode() -> commitment + chunks
    |
    +-- BlockHeader { data_availability_root: commitment }
    |
    +-- Consensus signs block
    |
    +-- BlockChunkProducer.encode_block()
        +-- Cache in pending_chunks[block_hash]


CHUNK GOSSIP (P2P)
    |
    +-- Node A                          Node B
    |     |                               |
    |     | ChunkGossipCommand::Announce  |
    |     |<------------------------------|
    |     |                               |
    |     | ChunkAnnounce {               |
    |     |   commitment,                 |
    |     |   available_indices: [0..n],  |
    |     |   total_chunks: n             |
    |     | }                             |
    |     |------------------------------>|
    |     |                               |
    |     | ChunkGossipCommand::Chunk(i)  |
    |     |<------------------------------|
    |     |                               |
    |     | encoded_chunk[i]              |
    |     |------------------------------>|


LIGHT CLIENT DAS VERIFICATION
    |
    +-- Receive BlockHeader with data_availability_root
    |
    +-- generate_random_indices(30, total_chunks, entropy)
    |   +-- entropy = block_hash XOR local_randomness
    |
    +-- For each sample index i:
    |   |
    |   +-- fetch_chunk(block_hash, commitment, i)
    |   |   +-- timeout: 500ms
    |   |
    |   +-- decode_chunk(bytes)
    |   |
    |   +-- verify_sample(verifier, commitment, i, chunk)
    |       +-- check Merkle proof against commitment
    |
    +-- aggregate_das_results()
    |   +-- valid >= min_valid_samples?
    |   +-- invalid <= max_invalid_samples?
    |
    +-- DasResult::Available -> Accept block
        DasResult::Unavailable -> Reject block


BLOCK RECOVERY (Full node needs block data)
    |
    +-- fetch_announce(block_hash)
    |   +-- Get commitment + total_chunks
    |
    +-- For index in 0..total_chunks:
    |   +-- fetch_chunk(index)
    |   +-- decode_chunk + check_chunk
    |   +-- Collect until >= minimum_shards
    |
    +-- verifier.decode_block(commitment, checked_chunks)
        +-- ReedSolomon::decode() -> Block

---

7. Statistical Guarantee

With 30 random samples and 50% availability threshold:

• If adversary hides >50% of chunks, the block is unrecoverable
• Probability light client fails to detect hidden data:
  • P(all 30 samples hit available chunks) = (0.5)^30 ~ 10^-9
  • Detection probability: >99.99999%

This means an adversary cannot hide data without being detected by light clients with overwhelming probability.

---

Related Documentation

• Light Clients - Light client architecture
• Finalization Flow - Block finalization with BLS signatures