Skip to content
Snippets Groups Projects
  • STEVAN Antoine's avatar
    202d8bcc
    add FRI (dragoon/komodo!175) · 202d8bcc
    STEVAN Antoine authored
    FRI protocol from [`dragoon/fri`](https://gitlab.isae-supaero.fr/dragoon/fri)
    
    ## changelog
    - add binary assets to be used as inputs
    - add `fri` and `fri_test_utils` as local dependencies until [`dragoon/fri`](https://gitlab.isae-supaero.fr/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
    ```rust
    struct Block<F: PrimeField, H: Hasher>
    ```
    
    ```rust
    fn evaluate<F: PrimeField>(bytes: &[u8], k: usize, n: usize) -> Vec<Vec<F>>
    ```
    
    ```rust
    fn encode<F: PrimeField>(
        bytes: &[u8],
        evaluations: Vec<Vec<F>>,
        k: usize,
    ) -> Vec<fec::Shard<F>>
    ```
    
    ```rust
    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]>,
    ```
    
    ```rust
    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]>,
    ```
    
    ```rust
    fn decode<F: PrimeField, H: Hasher>(blocks: Vec<Block<F, H>>, n: usize) -> Vec<u8>
    ```
    
    ## results
    
    ### times
    
    ![evaluating](/uploads/69607a2f987e26c23dd172d469c682c5/evaluating.png)
    ![encoding](/uploads/540ac15c21ba7500ad34b068c5d9d7dc/encoding.png)
    ![proving](/uploads/a694525c7d1277fe0b53dd87b6443900/proving.png)
    ![verifying_single](/uploads/8f03a3a0abca329eea396f3ba8b76512/verifying_single.png)
    ![decoding](/uploads/ba2cb0aa54f2ecff16340333121f16ca/decoding.png)
    
    ### sizes
    
    ![commits_single](/uploads/59a96661482fb1d918efc098e060cd45/commits_single.png)
    ![commits_single_normalized](/uploads/11398ed3f37ab4917b717cb717c9070d/commits_single_normalized.png)
    ![proofs](/uploads/17da07f4ef4ee637236deba7835cc022/proofs.png)
    ![proofs_normalized](/uploads/b2aae9491c56767ad1bf5674cf980361/proofs_normalized.png)
    202d8bcc
    History
    add FRI (dragoon/komodo!175)
    STEVAN Antoine authored
    FRI protocol from [`dragoon/fri`](https://gitlab.isae-supaero.fr/dragoon/fri)
    
    ## changelog
    - add binary assets to be used as inputs
    - add `fri` and `fri_test_utils` as local dependencies until [`dragoon/fri`](https://gitlab.isae-supaero.fr/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
    ```rust
    struct Block<F: PrimeField, H: Hasher>
    ```
    
    ```rust
    fn evaluate<F: PrimeField>(bytes: &[u8], k: usize, n: usize) -> Vec<Vec<F>>
    ```
    
    ```rust
    fn encode<F: PrimeField>(
        bytes: &[u8],
        evaluations: Vec<Vec<F>>,
        k: usize,
    ) -> Vec<fec::Shard<F>>
    ```
    
    ```rust
    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]>,
    ```
    
    ```rust
    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]>,
    ```
    
    ```rust
    fn decode<F: PrimeField, H: Hasher>(blocks: Vec<Block<F, H>>, n: usize) -> Vec<u8>
    ```
    
    ## results
    
    ### times
    
    ![evaluating](/uploads/69607a2f987e26c23dd172d469c682c5/evaluating.png)
    ![encoding](/uploads/540ac15c21ba7500ad34b068c5d9d7dc/encoding.png)
    ![proving](/uploads/a694525c7d1277fe0b53dd87b6443900/proving.png)
    ![verifying_single](/uploads/8f03a3a0abca329eea396f3ba8b76512/verifying_single.png)
    ![decoding](/uploads/ba2cb0aa54f2ecff16340333121f16ca/decoding.png)
    
    ### sizes
    
    ![commits_single](/uploads/59a96661482fb1d918efc098e060cd45/commits_single.png)
    ![commits_single_normalized](/uploads/11398ed3f37ab4917b717cb717c9070d/commits_single_normalized.png)
    ![proofs](/uploads/17da07f4ef4ee637236deba7835cc022/proofs.png)
    ![proofs_normalized](/uploads/b2aae9491c56767ad1bf5674cf980361/proofs_normalized.png)
Code owners
Assign users and groups as approvers for specific file changes. Learn more.