A Rust implementation of data availability sampling using Fast Reed-Solomon Interactive Oracle Proofs (FRI), inspired by the FRIDA paper.
Data Availability (DA) is a critical property in blockchain scaling solutions. It ensures that sufficient information about state transitions is published, allowing network participants to reconstruct the full state if needed. Data Availability Sampling (DAS) allows resource-constrained clients to probabilistically verify data availability without downloading the entire dataset.
FRIEDA implements the FRIDA scheme, which offers several theoretical improvements over previous approaches:
- Polylogarithmic overhead for both prover and verifier
- No trusted setup requirement (unlike polynomial commitment schemes based on pairings)
- Practical sampling efficiency and tight security bounds
In decentralized systems, particularly Layer 2 scaling solutions like rollups, participants need assurance that transaction data has been published without downloading all data. Sampling-based approaches allow light clients to verify availability with high probability by requesting random fragments of the data.
FRIDA establishes a connection between Data Availability Sampling and Interactive Oracle Proofs of Proximity (IOPPs). It demonstrates that any IOPP meeting a specific consistency criterion can be transformed into an erasure code commitment scheme suitable for data availability sampling.
The paper shows that FRI (Fast Reed-Solomon Interactive Oracle Proofs) satisfies these properties, leading to an efficient DAS scheme with:
- Reed-Solomon Encoding: Data is encoded with an expansion factor to ensure erasure resilience
- FRI Protocol: Provides low-degree proximity testing with logarithmic proof size
- Merkle Commitments: Authenticates erasure-encoded data efficiently
FRIEDA is structured with the following components:
- Field Arithmetic (
field.rs): Operations over the M31 prime field (2³¹ - 1) - Polynomial Operations (
polynomial.rs): FFT, IFFT, and Reed-Solomon encoding - FRI Protocol (
fri.rs): Low-degree testing mechanisms - Data Availability Layer (
da.rs): High-level data commitment and verification - Sampling (
sampling.rs): Probability-based sampling strategy - Utilities (
utils.rs): Merkle tree implementation and other helpers
The library provides a straightforward API for the core operations:
use frieda::api::{commit, sample, verify};
// Data provider commits to the data
let commitment = commit(&data)?;
// Light client samples the committed data
let sample_result = sample(&commitment)?;
// Data provider generates proof for the requested samples
// (In a real implementation, this would use the original data)
let proof = generate_proof(&commitment, &sample_result)?;
// Light client verifies the samples
let is_available = verify(&commitment, &proof)?;The FRIDA scheme has distinct advantages over other approaches:
| Scheme | Overhead | Trusted Setup | Limitations |
|---|---|---|---|
| KZG-based | O(log n) | Required | Limited polynomial degree, setup complexity |
| Merkle-based | O(n) | Not required | Linear sampling overhead, not friendly commitments for ZK rollups |
| Tensor codes | O(√n log n) | Not required | Limited to two-dimensional construction |
| FRIDA (FRI-based) | O(log² n) | Not required | More complex protocol |
git clone https://github.com/AbdelStark/frieda.git
cd frieda
cargo run --release# Run all tests
cargo test
# Run with all features enabled
cargo test --all-featuresThe project uses criterion for benchmarking key operations:
# Run all benchmarks
cargo bench
# Run specific benchmark suite
cargo bench --bench fri
cargo bench --bench field_and_poly
cargo bench --bench libfrieda/
├── benches/ # Criterion benchmark suites
│ ├── lib.rs # High-level API benchmarks
│ ├── field_and_poly.rs # Field and polynomial ops benchmarks
│ └── fri.rs # FRI protocol benchmarks
├── .github/
│ └── workflows/ # CI/CD GitHub Actions workflows
│ ├── rust.yml # Tests and linting
│ ├── coverage.yml # Code coverage
│ └── benchmark.yml # Performance benchmarks
├── src/
│ ├── field.rs # M31 field arithmetic
│ ├── polynomial.rs # FFT and polynomial operations
│ ├── fri.rs # FRI protocol implementation
│ ├── da.rs # Data availability layer
│ ├── sampling.rs # Sampling strategies
│ ├── utils.rs # Merkle trees and utilities
│ ├── lib.rs # Core library definitions
│ └── main.rs # Demo application
├── codecov.yml # Coverage configuration
├── Cargo.toml # Rust package manifest
├── LICENSE # MIT License
└── README.md # Project documentation
This implementation is primarily for educational and research purposes. Several limitations should be noted:
- The implementation focuses on the core concepts rather than optimizations
- The proof generation is partially implemented
- Security audits have not been performed
- The library should not be used in production without further development
MIT License - Copyright (c) 2024 AbdelStark
- Hall-Andersen, M., Simkin, M., & Wagner, B. (2024). "FRIDA: Data Availability Sampling from FRI." IACR Cryptology ePrint Archive, 2024/248.
- Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). "Fast Reed-Solomon Interactive Oracle Proofs of Proximity." Electronic Colloquium on Computational Complexity, Report No. 134.
- Hall-Andersen, M., Simkin, M., & Wagner, B. (2023). "Foundations of Data Availability Sampling." IACR Cryptology ePrint Archive, 2023/1079.