this is a refactor to prepare the addition of other cryptographic methods.

## changelog
- moves Semi-AVID code from `lib.rs` to `semi_avid.rs`

add "unchecked" versions of `Matrix::{vandermonde,from_vec_vec}` and test both matrices (dragoon/komodo!75)

## changelog
- replace `Matrix::vandermonde` with `Matrix::vandermonde_unchecked`
- add a new `Matrix::vandermonde` which calls `Matrix::vandermonde_unchecked` after checking the seed points are distinct, otherwise, gives a `KomodoError::InvalidVandermonde` error
- same with `Matrix::from_vec_vec` and `Matrix::from_vec_vec_unchecked`
- add documentation tests for the two "checked" functions
- run the main lib tests on both a random and a Vandermond matrix, just to be sure we do not take advantage of the Vandermonde structure

## changelog
- rename the `encode` function to `prove` and have it take _shards_ instead of an _encoding matrix_: this is to isolate the "encoding" process inside the `fec` module and leave the main `komodo::prove` only compute the "proof", i.e. the commits of the data

from
```rust
fn encode<F, G, P>(
    bytes: &[u8],
    encoding_mat: &Matrix<F>,
    powers: &Powers<F, G>,
) -> Result<Vec<Block<F, G>>, KomodoError>
```
to
```rust
fn prove<F, G, P>(
    bytes: &[u8],
    powers: &Powers<F, G>,
    k: usize,
) -> Result<Vec<Commitment<F, G>>, KomodoError>
```
- rename `fec::Shard.combine` to `fec::Shard.recode_with` to get rid of "combine"
- rename `fec::recode` to `fec::recode_with_coeffs` to show that this version takes a list of coefficients
- rename `Block.commit` to `Block.proof`: "commit" should be "commits" and it's usually refered to as "proof"
- split `prove` further into `prove` and `build`: `prove` now outputs a `Vec<Commitment<F>>`, `build` simply takes a `Vec<Shard<F>>` and a `Vec<Commitment<F>>` and outputs a `Vec<Block<F>>`
- add `fec::recode_random` that does the "shard" part of `recode` to wrap around `fec::recode_with_coeffs`
- remove `R: RngCore` from the signature of `zk::setup`, to avoid having to pass a generic `_` annotation everywhere `zk::setup` is used, same change has been applied to `recode` and the `generate_random_powers` in `main.rs`

from
```rust
fn setup<R: RngCore, F: PrimeField, G: CurveGroup<ScalarField = F>>(
    max_degree: usize,
    rng: &mut R,
) -> Result<Powers<F, G>, KomodoError> {
```
to
```rust
fn setup<F: PrimeField, G: CurveGroup<ScalarField = F>>(
    max_degree: usize,
    rng: &mut impl RngCore,
) -> Result<Powers<F, G>, KomodoError> {
```

### some extra minor changes
- remove some useles generic type annotations, e.g. `prove::<F, G, P>` can become a simpler `prove` most of the time, i.e. when there is at least one generic annotation somewhere in the scope

## changelog
* eb1b1381 don't use a T in the lib `run_template` test
* fbd503c6 remove the useless unwrap and TODO
* b550d712 remove some pub
* 339c3038 remove useless `.iter()`
* 537993f0 remove useless `.add(...)`
* d7720907 remove hiding_bound from timer in commit
* eecab5a6 move `commit` to inlined `zk::batch_commit`

should address #8 

## changelog
- move the internal `rng` to an argument of type `R: RngCore` for the following functions
  - `recode` in `lib.rs`
  - `linalg::Matrix::random`
  - `generate_random_setup` in `main.rs`
- make sure
  - `ark_std::test_rng` is only used in tests modules
  - `rand::thread_rng` is used in benchmarks, examples and `main.rs`

there was some missing parts from recent commits and also a dead link to `setup::setup` which is now `zk::setup`.

this is a minor proposition, get rid of the `UniPoly12_381` or `UniPoly381` type aliases that are just `DensePolynomial<Fr>`.

now, it's enough to just change the import of `Fr` to another crate / another curve, without having an inconsistent mention to BLS-12-381 in the name of the _dense polynomial_.

as per title, this is a minor MR that just makes sure the imports are consistent across modules.

in order
- `std`
- `ark_...`
- others
- `komodo` or `crate` or `super`

## changelog
- remove `ark-poly-commit` from the dependencies
- remove the old `setup.rs`
- add temporary `foo.rs` which define (some details are ommited for brevity)
  - `struct Powers<F, G>` 
  - `struct Commitment<F, G>`
  - `fn build_powers<F, G>(...) -> Powers<F, G>`
  - `fn commit<F, G, P>(powers: &Powers<F, G>, polynomial: &P) -> Commitment<F, G>`
  - tests
- `foo.rs` is then renamed to `setup.rs`
- two new `KomodoError` variants have been created to replace `ark_poly_commit::Error`
  - `DegreeIsZero`
  - `TooFewPowersInTrustedSetup(usize, usize)`
- finally, all the past mentions to `E: Pairing` and `setup::random` have been replaced with `F, G` and `setup::build_powers` respectively

> **Note**  
> this MR is best reviewed commit by commit, it's hopefully clear enough.

> **Note**  
> waiting for dragoon/komodo!47 to land

## changelog
- add missing format to the `KomodoError`s
- rename `fec::Shard::bytes` to `fec::Shard::data` because these are no _bytes_
- rename the `blocks: Vec<Shard<E>>` argument of `fec::decode` to `shards`
- refactor the tests of `fec` and `lib.rs`
- remove the `batch_verify` function entirely as it's pretty useless
- simplify the `linalg::Matrix::random` function
- add tests for the function in the `setup` module
- add documentation where it was missing

DISSOUBRAY Nathan authored 1 year ago and STEVAN Antoine committed 1 year ago

## Description

Those functions in the main could be useful later as they are operations that an external user might actually want to do directly (instead of just rewriting the functions in the main).

## List of changes
- Create a dump function (to be be used by both dump_blocks and generate_powers as they write to disk)
- Created a fs mod for actions related to writing on disk
- moved functions into their relevant module (though some might be up to discussion, as noted in some commits)
- Use anyhow to be able to return Result from functions with multiple error types (since before they just threw errors in the main)

## Additional notes

Should I include the example that I was working on (ie writing blocks of files recursively), which was the thing that prompted me to actually move the functions from the main to the lib (as I noticed I was rewriting what was in the main to be able to do that) ?

this MR
- adds `criterion` as a dependency
- creates a new `benches/recoding.rs` benchmark file
- makes the following `pub`lic
  - `fec::combine`
  - `field` and `field::split_data_into_field_elements`

## example results
| bytes   | shards | k  | mean (us) |
| ------- | ------ | -- | --------- |
| 1       | 2      | 2  | 0.127     |
| 1       | 2      | 4  | 0.179     |
| 1       | 2      | 8  | 0.283     |
| 1       | 2      | 16 | 0.504     |
| 1       | 4      | 2  | 0.346     |
| 1       | 4      | 4  | 0.506     |
| 1       | 4      | 8  | 0.823     |
| 1       | 4      | 16 | 1.451     |
| 1       | 8      | 2  | 0.789     |
| 1       | 8      | 4  | 1.155     |
| 1       | 8      | 8  | 1.89      |
| 1       | 8      | 16 | 3.383     |
| 1       | 16     | 2  | 1.669     |
| 1       | 16     | 4  | 2.478     |
| 1       | 16     | 8  | 4.023     |
| 1       | 16     | 16 | 7.147     |
| 1024    | 2      | 2  | 1.02      |
| 1024    | 2      | 4  | 1.076     |
| 1024    | 2      | 8  | 1.172     |
| 1024    | 2      | 16 | 1.395     |
| 1024    | 4      | 2  | 2.981     |
| 1024    | 4      | 4  | 3.15      |
| 1024    | 4      | 8  | 3.453     |
| 1024    | 4      | 16 | 4.089     |
| 1024    | 8      | 2  | 6.907     |
| 1024    | 8      | 4  | 7.244     |
| 1024    | 8      | 8  | 7.969     |
| 1024    | 8      | 16 | 9.452     |
| 1024    | 16     | 2  | 15.169    |
| 1024    | 16     | 4  | 16.14     |
| 1024    | 16     | 8  | 17.086    |
| 1024    | 16     | 16 | 20.266    |
| 1048576 | 2      | 2  | 1470.966  |
| 1048576 | 2      | 4  | 1097.899  |
| 1048576 | 2      | 8  | 1091.298  |
| 1048576 | 2      | 16 | 1091.544  |
| 1048576 | 4      | 2  | 3274.852  |
| 1048576 | 4      | 4  | 3272.68   |
| 1048576 | 4      | 8  | 3251.877  |
| 1048576 | 4      | 16 | 3272.872  |
| 1048576 | 8      | 2  | 7582.074  |
| 1048576 | 8      | 4  | 7599.012  |
| 1048576 | 8      | 8  | 7584.59   |
| 1048576 | 8      | 16 | 7569.575  |
| 1048576 | 16     | 2  | 16274.986 |
| 1048576 | 16     | 4  | 16303.905 |
| 1048576 | 16     | 8  | 16313.429 |
| 1048576 | 16     | 16 | 16310.305 |

it appears this field is never used 👀 

i think we can simply remove it entirely and thus simplify a bit the `Block`s 🙂

this MR allows to give any number of blocks to recode them.
this is a convenience to avoid combining the blocks pair-wise and create intermediate and useless blocks, e.g. by defining the following Nushell command with the `komodo.nu` module
```bash
def "komodo full-recode" []: list<string> -> string {
    let blocks = $in
    match ($blocks | length) {
        0 => { return null },
        1 => { return $blocks.0 },
    }

    $blocks | skip 1 | reduce --fold $blocks.0 {|it, acc| komodo combine $it $acc}
}
```
one can now do directly
```bash
komodo combine ...(komodo ls)
```
which will create a single new fully recoded block!

## changelog
- new `fec::combine` that takes a list of shards and their coefficients and combines them, returns `None` if the slices are empty or not of the same length
```rust
pub(super) combine<E: Pairing>(
    shards: &[Shard<E>],
    coeffs: &[E::ScalarField],
) -> Option<Shard<E>>
```
- modified `recode` that takes any number of blocks and returns an `Option` if there is none
```rust
pub recode<E: Pairing>(blocks: &[Block<E>]) -> Result<Option<Block<E>>, KomodoError>
```
- the `komodo combine` command from `komodo.nu` can now take any number of blocks, even 0 by giving a nice error

## changelog
- add `--encoding-method` to `komodo prove`
- pass the encoding matrix to `encode` and `fec::encode` instead of `k` and `n`, these two parameters can be extracted without further check by looking at the shape of the encoding matrix
- the global recoding vector is now extracted from the encoding matrix instead of recomputing it (see new `Matrix::get_col` implementation)
- `linalg` and `Matrix::{random, vandermonde}` have been made public (see new `Matrix::random` implementation)
- the computation of `Matrix::vandermonde` has been optimized

should close #2 

this MR
- uses the matrix representation of FEC encoding to create both `Shard`s and `Block`s
- `fec::encode` will encode shards with a Vandermonde matrix
- `encode` will use `fec::encode`
- use of `Matrix::transpose` has been reduced in `fec::encode` thanks to swapping the encoding matrix product (thanks @j.detchart for findind this)
- `fec::encode` does not require `transpose: bool` anymore as the encoding process has been homogenize throughout the code base
- useless `field::build_interleaved_polynomials` have been removed
- `prove` has been merged into `encode`

this MR combines the encoding and the recoding processes into a single one, expressed as the shard linear combination.

this allows to not recompute the encoding matrix each time, whether it's explicit during decoding or implicit during shard verification.

now, when combining blocks that are incompatible, e.g. from different files, a proper error will be shown to the user.

## changelog
- add an `inspect` command to `komodo` through `main.rs`
- remove the useless `Shard.mul` implementation and tests
- because `i` is a `u128`, use `i.to_le_bytes()` instead of `[i as u8]` in calls to `E::ScalarField::from_le_bytes_mod_order`
- add to `tests/cli.nu` the cases tha should fail
- merge together the tests in `lib.rs`, e.g. `verify_2`, `verify_4` and `verify_6` become a simpler `verification`
- add some documentation and NOTEs
- `impl`ement `Display` for `Block` to dump it to `stdout`
- print more detailed test cases when a test fails

- should close dragoon/komodo#3
- based on top of dragoon/komodo!12

> **Note**  
> - commits containing "_DEBUG_" will be removed once this is done
> - this MR is based on dragoon/komodo!12 and will be rebased on top of `main` once dragoon/komodo!12 lands

i think this is best [reviewed commit by commit](dragoon/komodo!13 (58cec473))

this MR uses a simpler `Vec` of `E::ScalarField` to represent a linear combination.

the rest of the crate has been fixed accordingly.

the goal is to let Arkworks do as much work as possible, fixing part of #2.
- `one_more` removed from `field::split_data_into_field_elements` in 5531b31a
- `one_less` removed from `field::merge_elements_into_bytes` in 5761b784

## examples
let's say we have at most $k = 3$ source shards, called $s_0$, $s_1$ and $s_2$ respectively.
this first means that all linear combinations will be at most of length 3.

if a new shard $s$ is a linear combination of the source shards, e.g. $s = \alpha s_0 + \beta s_1 + \gamma s_2$, where $\alpha$, $\beta$ and $\gamma$ are scalar elements of an elliptic curve, then the linear combination in the code will be
```rust
vec![alpha, beta, gamma]
```
> **Note**  
> the right of the vector can be truncated to remove zero elements that are not part of the linear combination and don't add any extra useful information.  
> the left stays mandatory.

e.g. we create two times a linear combination with a single one set to $1$ and the rest to $0$ with the following snippet
```rust
let mut linear_combination = Vec::new();
linear_combination.resize(i + 1, E::ScalarField::zero());
linear_combination[i] = E::ScalarField::one();
```

# changelog
- add a `transpose` boolean switch to `fec::decode`
- add end to end tests that should reflect the real case scenario of `komodo.nu`

# changelog
- rename `LinalgError` to a more general `KomodoError`
- move `KomodoError` to `error.rs` module
- add a `TooFewShard(usize, usize)` variant

# changelog
- add a `one_less` argument to `field::merge_elements_into_bytes` to mirror the `one_more` from `field::split_data_into_field_elements`
- add a `linalg` module which defines
  - a `pub LinalgError` enum
  - a `pub(super) Matrix` structure implement for any `ark_ff::Field`, e.g. `<Bls12_381 as Pairing>::ScalarField`
  - `pub(super) Matrix::vandermonde`
  - `pub(super) Matrix::from_vec_vec`
  - `pub(super) Matrix::invert`
  - `pub(super) Matrix::mul`
  - `pub(super) Matrix::transpose`
  - everything is tested extensively
- modify `fec.rs` to use `linalg::Matrix` instead of `reed-solomon-erasure` => tests still pass
- remove the dependency to [`reed-solomon-erasure`](https://github.com/jdetchart/reed-solomon-erasure) completely