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

`fs` was using hardcoded `COMPRESS` and `VALIDATE`, now it uses values passed by the caller 👍 

thanks @n.dissoubray 😉

as per title

## changelog
- add a `setup.rs` benchmark which measures
  - the creation of a random setup
  - the serialization of a setup
  - the deserialization of a setup
- refactor `plot.py` a bit to
  - use `argparse`
  - take `--bench` to plot either _linalg_ or _setup_ results
  - write a complete `plot_setup` function
  - add a bit of documentation here and there

## example results
![Figure_1](/uploads/ea4bddc5c0c426d0824bad55e2e2e5aa/Figure_1.png)

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

> **Note**  
> waiting for !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

@n.dissoubray found a bug when not passing `--fec-params` to `komodo prove` where
- `null` cannot be accessed
- invalid keys in `$fec_params` might be accessed and crash the command

this MR adds runtime checks for the type of `--fec-params`, to make sure it's
- non `null`
- has a valid shape

as per title

this MR also adds `nu --version` to the output of `make show`, to allow better debugging in the CI.

this MR is purely cosmetic and only changes the way matrices look when displayed to the standard output.

## changelog
- the `Display` implementation for `linalg::Matrix` now takes format parameters to adapt the way matrices look in the standard output => see the documentation of `Display::fmt` for `linalg::Matrix` for more information and examples

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 `linalg.rs` benchmark file
- makes the following function `pub`lic
  - `Matrix::transpose`
  - `Matrix::invert`
  - `Matrix::mul`
- creates a new `benches/` directory containing
  - a README with commands
  - a `plot.py` file to plot results
  - a `linalg.rs` file with the benchmarks

## example results
![Figure_1](/uploads/f352a6f411662361fa9ca381710271d5/Figure_1.png)

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 |

this is a followup to !46.

this MR splits the `fmt` rule of the `Makefile` into `fmt-check` and `fmt`, where `fmt` does the actual formatting and `fmt-check` only checks for bad format.

!39 and !40 changed the CI to use a _toolchain_ file.

however, having `default` as the `$.profile` causes extra useless components to be installed.

this MR sets the `$.profile` to `minimal` in the _toolchain_ file and the `$.components` to `rustfmt` and `clippy`.

as per title

the idea is to only rely on the `rust-toolchain.toml` file.

tries to address #5 

## changelog
- the `rank.rs` example now only returns the _rank_ to `stdout`
- two tests have been added
  - one that asserts $\text{r}(M^T) = \text{r}(M)$
  - one that asserts $\text{r}(M) \leq \min(n, m)$ when $n$ and $m$ are the heigth and the width of $M$ respectively
- `Matrix::rank` has been rewritten thanks to ChatGPT, the full prompt can be found in the body of 384d9559 and the algorithm has been refactored and simplified in the following few commits

> **Note**  
> the two new tests do not pass on e27561bb but do pass on the tip of this MR branch, which indicates that the bugs have been solved

fix the toolchain version of Rust with `rust-toolchain.toml`.

this is to avoid having things like `cargo clippy` behaving differently locally and in the remote CI.
> **Note**  
> see https://gitlab.isae-supaero.fr/dragoon/komodo/-/jobs/12875 which fails with Rust 1.72 but works locally with Rust 1.75

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

this MR
- implements the `Display` trait for `Matrix` to allow to show it
- makes `from_vec_vec` and `rank` public
- add `rank.rs`

## example
> **Note**  
> - this has been run with Nushell
> - a `-1` is an impossible value and thus will generate a random element instead
>
```bash
cargo run --example rank -- ...[
    "1,0,-1"
    "0,0,-1"
    "0,1,-1"
    "0,0,-1"
    "0,0,-1"
]
```
will output
```
/1 0 314995448938783965509764369801440879676\
|0 0 236699644179594774251145667390896459418|
|0 1 187004145196223910655928022134499908037|
|0 0 273500202756822505549423242088598868403|
\0 0 286599222098418496365691949902317095505/

m: 5
n: 3
r: 5
```

this MR adds
- a new `rank` implementation to `Matrix`
- some tests


> **Note**  
> the algorithm is basically the same as in the matrix inversion from `invert`, i.e. transform the matrix into _echelon_ form and then count the number of non-zero rows

> **Note**  
> the row-rank of a matrix is the same as its column-rank, so we can safely count the number of rows

in this MR, i define the following two functions in `linalg::tests`
- `vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T>`
- `mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>>`

the idea is to help see what the matrices and vectors are at a glance, without too much processing.
the end result is that all `Fr::from(<some number>)` are gone

# example
- a full matrix
```rust
Matrix::from_vec_vec(vec![
    vec![Fr::from(2), Fr::zero(), Fr::zero()],
    vec![Fr::zero(), Fr::from(3), Fr::zero()],
    vec![Fr::zero(), Fr::zero(), Fr::from(4)],
    vec![Fr::from(2), Fr::from(3), Fr::from(4)],
])
```
becomes
```rust
Matrix::<Fr>::from_vec_vec(mat_to_elements(vec![
    vec![2, 0, 0],
    vec![0, 3, 0],
    vec![0, 0, 4],
    vec![2, 3, 4],
]))
```
which is hopefully easier to read and understand what the matrix is.

- a diagonal one
```rust
Matrix::<Fr>::from_diagonal(vec![Fr::from(2), Fr::from(3), Fr::from(4)])
```
becomes
```rust
Matrix::<Fr>::from_diagonal(vec_to_elements(vec![2, 3, 4]))
```

## 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.

as per title, now a block will be called `<hash>` inside `blocks/` and the trusted setup will be stored in `powers`

this should save some CI time.

goes from around [14min](6070c11a) to [a bit over 2min](e6248176)

`examples/cli.nu` was not working anymore...

this MR
- updates it
- adds it to the CI

as per title, run `komodo clean` in `tests/cli.nu` before running the actual tests.

> **Note**  
> this is mainly for testing locally

## changes to the API of `komodo.nu`
- there is no `--powers-file` anymore => the location of the blocks and the powers is controlled via the `$env.KOMODO_HOME` environment variable which defaults to `$env.XDG_DATA_HOME/komodo/` and then `~/.local/share/komodo/`
- a new `komodo clean` command to empty the `$env.KOMODO_HOME` directory
- a new `komodo` command to get some basic help
- `komodo setup` now expects a number of bytes rather than a filename to build a trusted setup

wait for !17

## changelog
- add `bytes from_int: [int -> binary, list<int> -> binary]` to `binary.nu`
- add `bytes to_int: binary -> list<int>` to `binary.nu`
- add `tests/binary.nu` to test `binary.nu`
- run `tests/binary.nu` in the CI
- for clarity
  - rename `BYTES` to `FILE` in `tests/cli.nu`
  - rename `bytes` to `input` in `komodo.nu`

in this MR
- all `unwrap`s and `expect`s have been removed from any `.rs` module that is not `main.rs` => the goal is to never panic from inside the library and let `main.rs` handle the errors
- in `main.rs` the new `throw_error` function is used to return a message on `stderr` and exit the runtime with a code => then `komodo.nu` picks it up and gives a nicer error to the user
- the internals of `komodo.nu` also have been greatly simplified without feature changes

> **Note**  
> because `throw_error` does not return anything and some of the places where there might be errors in `main.rs` need to return a value, some `unwrap_or_else` need to have an `unreachable!` statement in them to show the compiler it's ok if there's no value on the `Err` branch
>
> it would be nice to find a better way of doing this 🤔

in this MR
- only the hashes of blocks are shown and `komodo ...` expects hashes and not full paths to the blocks
- completion has been added for the `komodo` command
- a `komodo ls` command has been added to help with listing blocks


> **Note**  
> everything happens in `blocks/` for now and it's hardcoded

## 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))