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

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();
```

related to
- !13

## description
in !13, i noticed that decoding can be pretty sensitive to the order of the shards...
this is why i thought testing all possible permutations of the shards could be beneficial 🤔

see the [run attached to this MR](https://gitlab.isae-supaero.fr/dragoon/komodo/-/jobs/11281#L1120) to see all the combinations of shards used in the tests, e.g. `[0, 2, 3]` means that shards `0`, `2` and `3` have been used and shards `1` and `4` have been "_lost_" 

## changelog
this MR
- adds an inline `math` module to `tests/cli.nu` which defines
  - `choose` which computes all the sets of $k$ choose $n$ in $[|0, ..., n - 1|]$
  - `perm` which computes all the permutations on $[|0, ..., n - 1|]$
  - see the inline `_test_choose` and `_test_perm` commands for concrete examples of their behaviours
- compute all the permutation of $k'$ choose $n$ shards, where $k'$ ranges from $k$ to $n$
- run the reconstruction test on all these cases
- moves the CLI example from `README.md` to `examples/cli.nu`

> **Note**  
> also removes the newline added to the stdout of `komodo` commands, so that the output is prettier, without spurious empty lines

this MR
- uses the Nushell script in the README to test the application in a real CLI context
- bumps the Rust toolchain to 1.72.1
- installs Nushell version 0.89.0 into the CI
- runs the test script

related to
- https://github.com/nushell/nushell/pull/11289

this is to make the passing of bytes easier as `cargo run` wants strings.

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

should fix #1 

## changelog
- don't transpose back the decoded shard matrix
- pad the field elements in the test
- run the tests from the min number of bytes to the full length

this should simplify the `fec.rs` test module by removing the long hardcoded vector of bytes.

# changelog
- refactor $k$ and $n$ into variables
- run the decoding FEC test in a loop from $(k - 1) \rho + 1$ to $k \rho$, where $\rho$ is the curve number of bytes per scalar field element, e.g. $31$ for _BLS-12-381_
- add a _NOTE_ about having too few bytes and elements, i.e. below $(k - 1) \rho + 1$
- add a _FIXME_ about having too many bytes and elements, i.e. above $k \rho$

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

follow up to !3

## description
in !3, to make Clippy happy, `expect` was replace with `unwrap_or_else`, but that suppresses the message of the underlying error, which is not great...

this MR reverts this part of !3 and allows `clippy::expect_fun_call`.