https://eprint.iacr.org/2024/248

<aside> 💡

For DAS to function effectively, two conditions must be met:

1. Correct Encoding Verification: The sampled data must be provably correctly encoded.
2. Sufficient Sampling: A sufficient number of nodes must participate in the sampling process to ensure data reconstructability. </aside>

The ****FRIDA construction improves upon existing DAS techniques by merging sampling for both proximity and availability verification. It combines RS encoding, Merkle tree commitments, and FRI proofs to ensure data correctness efficiently.

Protocol Overview

1. Encoding & Commitment: The prover encodes block data using a RS code and commits to the encoded data using a Merkle tree.
2. Proof of Proximity (PoP): The prover generates a non-interactive FRI proof to confirm that the encoded vector belongs to a unique RS codeword. The proof consists of $\lambda$ queries to ensure a given security level. (For 80-bit security $\lambda = 128$)
3. Data Availability Sampling: Each light node:
   • Downloads the Merkle commitment and the non-interactive FRI proof.
   • Verifies the proof to establish encoding correctness.
   • Makes additional random queries, which are validated using the FRI verification procedure.
   • Aggregates samples to reconstruct the original data.

By proving proximity before running DAS, FRIDA ensures that all sampled symbols originate from the same unique codeword, significantly improving efficiency.

Leveraging Interaction for Efficiency

A key optimization in FRIDA is interactive sampling:

• Instead of providing all light nodes with the same non-interactive proof, each node makes independent queries and runs FRI verification.
• This approach reduces redundancy in sampled symbols and enhances reconstructability.
• With interactive queries, the probability of redundant samples decreases from $O(1/k)$ in the non-interactive case to $O(1/k^2)$, requiring fewer light nodes to achieve the same security level.

Comparison and Trade-offs

Advantages of FRIDA over prior DAS methods:

• Combines proximity and availability sampling, reducing overhead.
• Eliminates reliance on fraud proofs or KZG commitments, removing trust assumptions and expensive cryptographic operations.
• Interactive sampling increases efficiency, reducing the required number of nodes for the same security level.

Potential trade-offs: