subspace_erasure_coding/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2
3#[cfg(test)]
4mod tests;
5
6extern crate alloc;
7
8#[cfg(not(feature = "std"))]
9use alloc::string::String;
10use alloc::sync::Arc;
11#[cfg(not(feature = "std"))]
12use alloc::vec::Vec;
13use core::num::NonZeroUsize;
14use kzg::{FFTSettings, PolyRecover, DAS, FFTG1, G1};
15use rust_kzg_blst::types::fft_settings::FsFFTSettings;
16use rust_kzg_blst::types::g1::FsG1;
17use rust_kzg_blst::types::poly::FsPoly;
18use subspace_kzg::{Commitment, Polynomial, Scalar};
19
20/// Erasure coding abstraction.
21///
22/// Supports creation of parity records and recovery of missing data.
23#[derive(Debug, Clone)]
24pub struct ErasureCoding {
25    fft_settings: Arc<FsFFTSettings>,
26}
27
28impl ErasureCoding {
29    /// Create new erasure coding instance.
30    ///
31    /// Number of shards supported is `2^scale`, half of shards are source data and the other half
32    /// are parity.
33    pub fn new(scale: NonZeroUsize) -> Result<Self, String> {
34        let fft_settings = Arc::new(FsFFTSettings::new(scale.get())?);
35
36        Ok(Self { fft_settings })
37    }
38
39    /// Max number of shards supported (both source and parity together)
40    pub fn max_shards(&self) -> usize {
41        self.fft_settings.max_width
42    }
43
44    /// Extend sources using erasure coding.
45    ///
46    /// Returns parity data.
47    pub fn extend(&self, source: &[Scalar]) -> Result<Vec<Scalar>, String> {
48        // TODO: das_fft_extension modifies buffer internally, it needs to change to use
49        //  pre-allocated buffer instead of allocating a new one
50        self.fft_settings
51            .das_fft_extension(Scalar::slice_to_repr(source))
52            .map(Scalar::vec_from_repr)
53    }
54
55    /// Recovery of missing shards from given shards (at least 1/2 should be `Some`).
56    ///
57    /// Both in input and output source shards are interleaved with parity shards:
58    /// source, parity, source, parity, ...
59    pub fn recover(&self, shards: &[Option<Scalar>]) -> Result<Vec<Scalar>, String> {
60        let poly = FsPoly::recover_poly_from_samples(
61            Scalar::slice_option_to_repr(shards),
62            &self.fft_settings,
63        )?;
64
65        Ok(Scalar::vec_from_repr(poly.coeffs))
66    }
67
68    /// Recovery of missing shards from given shards (at least 1/2 should be `Some`) in form of
69    /// normalized polynomial (allows to not do inverse FFT afterwards if polynomial is desired).
70    ///
71    /// Both in input and output source shards are interleaved with parity shards:
72    /// source, parity, source, parity, ...
73    pub fn recover_poly(&self, shards: &[Option<Scalar>]) -> Result<Polynomial, String> {
74        let mut poly = Polynomial::from(FsPoly::recover_poly_coeffs_from_samples(
75            Scalar::slice_option_to_repr(shards),
76            &self.fft_settings,
77        )?);
78
79        poly.normalize();
80
81        Ok(poly)
82    }
83
84    /// Recovery of source shards from given shards (at least 1/2 should be `Some`).
85    ///
86    /// The same as [`ErasureCoding::recover()`], but returns only source shards in form of an
87    /// iterator.
88    pub fn recover_source(
89        &self,
90        shards: &[Option<Scalar>],
91    ) -> Result<impl ExactSizeIterator<Item = Scalar>, String> {
92        Ok(self.recover(shards)?.into_iter().step_by(2))
93    }
94
95    /// Extend commitments using erasure coding.
96    ///
97    /// Returns both source and parity commitments interleaved.
98    pub fn extend_commitments(
99        &self,
100        commitments: &[Commitment],
101    ) -> Result<Vec<Commitment>, String> {
102        // Inverse FFT to interpolate polynomial over source commitments
103        let mut coeffs = self
104            .fft_settings
105            .fft_g1(Commitment::slice_to_repr(commitments), true)?;
106
107        // Double the size
108        coeffs.resize(coeffs.len() * 2, FsG1::identity());
109
110        // FFT to get extended commitments
111        self.fft_settings
112            .fft_g1(&coeffs, false)
113            .map(Commitment::vec_from_repr)
114    }
115}
subspace_erasure_coding/lib.rs

subspace_erasure_coding/
lib.rs
