add FRI

FRI protocol from dragoon/fri

changelog

• add binary assets to be used as inputs
• add fri and fri_test_utils as local dependencies until dragoon/fri becomes public
• add fri feature and module (see section below for the public definitions)
• fix bug in 32bd6566
• bump Rust in e7a2c244
• add a versatile example
• add Nushell pipeline to run benchmarks and plot results
• add some tests

fri module API

struct Block<F: PrimeField, H: Hasher>

fn evaluate<F: PrimeField>(bytes: &[u8], k: usize, n: usize) -> Vec<Vec<F>>

fn encode<F: PrimeField>(
    bytes: &[u8],
    evaluations: Vec<Vec<F>>,
    k: usize,
) -> Vec<fec::Shard<F>>

fn prove<const N: usize, F: PrimeField, H: Hasher, P>(
    evaluations: Vec<Vec<F>>,
    shards: Vec<fec::Shard<F>>,
    blowup_factor: usize,
    remainder_plus_one: usize,
    nb_queries: usize,
) -> Result<Vec<Block<F, H>>, KomodoError>
where
    P: DenseUVPolynomial<F>,
    for<'a, 'b> &'a P: Div<&'b P, Output = P>,
    <H as rs_merkle::Hasher>::Hash: AsRef<[u8]>,

fn verify<const N: usize, F: PrimeField, H: Hasher, P>(
    block: Block<F, H>,
    domain_size: usize,
    nb_queries: usize,
) -> Result<(), KomodoError>
where
    P: DenseUVPolynomial<F>,
    for<'a, 'b> &'a P: Div<&'b P, Output = P>,
    <H as rs_merkle::Hasher>::Hash: AsRef<[u8]>,

fn decode<F: PrimeField, H: Hasher>(blocks: Vec<Block<F, H>>, n: usize) -> Vec<u8>

results

times

sizes