Polynomial erasure coding (based on FFT, like v2.2 farmer plotting)

[dariolina]

The correct way to erasure-code chunks is based on FFT, but in a different way than in v2.2 (used coset FFT).
To save time binding c-kzg ourselves, we could initially reuse existing. bindings from rust-kzg, which supports all needed functions.
We need several ingredients:

• representation of FFT domain consistent with the corresponding c-kzg struct and a way to set new FFT domain. For archiving domain scale is 8, for plotting 16.
  Corresponds to c-kzg new_fft_settings and rust-kzg

pub struct FFTSettings{
    pub max_width: usize,
    pub root_of_unity: BlsScalar,
    pub expanded_roots_of_unity: Vec<BlsScalar>,
    pub reverse_roots_of_unity: Vec<BlsScalar>,
}
impl FFTSettings{
   //Create FFTSettings with roots of unity for a selected scale(= log2 of expanded data length)
    fn new(scale: usize) -> Result<FFTSettings, Error>
    ...
}

• erasure coding for chunks with FFT
  Corresponds to c-kzg das_fft_extension and rust-kzg

fn fft_extension(
        source_data: &[BlsScalar],
        fs: &FFTSettings
        ) -> Result<Vec<BlsScalar>, Error> {
        //the result is twice as long as source_data and has source_data at even indices and parity at odd indices
        }

• chunks recovery
  Corresponds to c-kzg recover_poly_from_samples and rust-kzg

fn recover(
            samples: &[Option<BlsScalar>],
            fs: &FFTSettings,
        ) -> Result<BlsScalar, Error> {
       }

See this test for a Rust mock-up of erasure coding and recovery for chunks.

• erasure coding for commitments with FFT
  Requires c-kzg fft_g1 or rust-kzg
  Should implement the same functionality as mocked here

fn fft_commitment_extension(
       source_commitments: &[Commitment]
       ) -> Result<Vec<Commitment>, Error>

Additional function to improve Farming:

• polynomial coefficients recovery #1307
  Similar to the above, but recovers the polynomial in coefficient form for use with KZG, instead of source chunks. Corresponds to recover_poly_from_samples from rust_kzg but without the last FFT in this line. See spec.

fn recover_poly(
            samples: &[Option<BlsScalar>],
            fs: &FFTSettings,
        ) -> Result<Polynomial, Error> {
       }

[nazar-pc]

I have a few questions, @dariolina.

I see that max_width = scale^2 from c-kzg code, why not having max_width as parameter instead then? I mean we can return Err if the argument is not a power of 2.

Wouldn't we want to play with arguments in the future to expand more than 2x since our commitments are fixed size now?

[dariolina]

@nazar-pc max_width = 2^scale, scale is the logarithm of max_width. I used scale because new_fft_settings want scale. I think it's precise, and the log saves a check for a power of 2. You can use max_width if you prefer and pass down the log.

To your second question, these FFTs work so nicely only with powers of 2, so if you want the number of source chunks to be arbitrary in the future, it should get pumped to the next power of 2 (which was happening under the hood in arkworks, and we hated it). Maybe have a separate helper that explicitly determines the correct scale or max_width from the number of chunks and feed the resulting power of 2 to FFT settings?

[nazar-pc]

Thanks, that is sufficient information for me for now

[nazar-pc]

I think I'll go with Arkworks-based implementation in rust-kzg for now.

I hit numerous issues and glad I was able to compile the dependency at last:

• Release 0.8.0 ralexstokes/ssz-rs#51
• Compilation fixes and change to workspace grandinetech/rust-kzg#192

That is in case it provides necessary APIs because otherwise I'll have to fix ckzg Rust integration, which I'd rather not spend time on.

Alternatively we can try blst-from-scratch version, which being Rust only should at least compile without major issues.

A whole other topic is that none of those libraries are no_std compatible, which is a bummer and would make a pure Rust implementation even more desirable and introduction of such support will likely fall on my shoulders.

[sauliusgrigaitis]

blst-from-scratch likely is your best bet as it's the most developed ECC backend in rust-kzg. Unless you need something from more that Arkworks ecosystem provides.

[nazar-pc]

Thanks a lot for suggestion, I'll go with it then

[nazar-pc]

Draft PR: #1214

[dariolina]

Do we want to move the last task to a separate "improvement" issue since it's not necessary but a nice to have so you can close this big issue?

[nazar-pc]

Yes, please. Or we can just create an issue from it and resolve this one anyway.