this is to avoid having to change the toolchain in the CI everytime.

`rust-toolchain.toml` and `.gitlab-ci.yml` will have to be updated in pairs when bumping / changing the Rust toolchain.

this is an attempt at making benchmarks easier to work with
- `benchmarks run` will read benchmarks from NUON data and run them
- `benchmarks plot` will plot benchmark results
- the output format will be something 
  - a directory whose name is the hash of the CPU spec and the Komodo commit hash
  - contains `cpu.json` with the CPU info
  - contains `komodo.txt` with the Komodo commit hash
  - contains NDJSON result files

> 💡 **Note**
>
> results will typically be uploaded to https://gitlab.isae-supaero.fr/dragoon/komodo-benchmark-results

> 💡 **Note**
>
> this MR goes alongside the [`komodo-benchmark-results@restart`](https://gitlab.isae-supaero.fr/dragoon/komodo-benchmark-results/-/compare/main...restart) branch

## changelog
- bump Nushell to 0.101.0
  - parallel `$in` => remove useless `let input = $in` when possible, e.g. still required when using the function's `$in` in a `for` loop
  - `group-by` changed => `group-by x --to...

the idea is to make the installation of Nushell easier to maintain, especially regarding versions, currently pinned to `0.95.0`

> successful run on GitHub: [13032726635](https://github.com/dragoon-rs/komodo/actions/runs/13032726635)

this is also to allow easier testing locally with the same Nushell version as in the CI, e.g.
```bash
# install in `~/.local/bin/` and have multiple versions
make install-nu

hash=$(/tmp/nu --no-config-file --commands 'version | get commit_hash')
nu_bin=$"$HOME/.local/bin/nu-$hash"
cp /tmp/nu $nu_bin

make NU=$nu_bin show test
```
or
```bash
# install in the repo and overwrite each time
make NU_DEST=. install-nu
make NU=./nu show test
```

# changelog
- Makefile
  - split the global `.PHONY` rule into _atomic_ rules next to each _phony_ rule
  - define `NU` and `NU_FLAGS` to allow changing which and how Nushell runs
  - define `NU_ARCH`, `NU_VERSION`, `NU_BUILD` and `NU_DEST` for Nushell installation
  - ...

mainly fixes a few typos and improves `algebra` and `semi_avid` tests

## changelog
- fix some typos and notes in the documentation
- test more cases for `algebra::split_data_into_field_elements` and `algebra::merge_elements_into_bytes`, more data lengths and more modulus respectively
- remove a useless `::<Vec<_>>` on a `collect` in `fec`
- `semi_avid::tests`
  - refactor `bls12-381` into a constant
  - write an "_attack_" function to alter a particular block, `attack<F, G>(block: Block<F, G>, c: usize, base: u128, pow: u64) -> Block<F, G>`
  - pass a list of attacks, i.e. `attacks: Vec<(usize, usize, u128, u64)>`, to `verify_with_errors_template`, use the same as the previous hardcoded one
  - pass a list of "_recodings_", i.e. `recodings: Vec<Vec<usize>>`, to `verify_recoding_template` and assert the number of blocks, e.g. `vec![vec![2, 3], vec![3, 5]]` means that recoding 2 and 3 together should verify, and same with 3 and 5, and also ...

this should avoid the following error when trying to rust the LSP in a toolchain which does not have the `rust-analyzer` component and without running `rustup component add rust-analyzer` manually:
```
error: Unknown binary 'rust-analyzer' in official toolchain 'stable-x86_64-unknown-linux-gnu'.
```

in order to help catch issues with the various Nushell scripts and modules in the source base, i propose to add a CI script that will check them all.

below is an example error, e.g. when introducing a syntax error in `.env.nu`:
```
Error:   × Failed to parse content:
  │     file: .env.nu
  │     err:  Expected keyword.
```

## changelog
- add more snippets and instructions
- add missing imports
- update the "atomic operations" section
- add a table of contents

this replaces the "_nothing to do_" messages from Nushell commands with more explicite errors.

DETCHART Jonathan authored 4 months ago and STEVAN Antoine committed 4 months ago

This MR adds an option to perform erasure coding using FFT rather than using a matrix. It also adds the field FP128 in the list of curves

Note that there is a redundant function `random_loss` into benchmarks/bin/fec.rs and examples/fec.rs

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)

see the successful CI on GitHub: https://github.com/dragoon-rs/komodo/actions/runs/11950087413/job/33310881686

this MR adds two new badges to the README
- the crate (links to the [Komodo crate](https://crates.io/crates/komodo))
- the documentation (links to the [doc](https://docs.rs/komodo/latest/komodo/))

this adds three badges to the README:
- the latest release (links to the [release page](https://gitlab.isae-supaero.fr/dragoon/komodo/-/releases))
- the GitLab CI status (links to the [GitLab pipeline dashboard](https://gitlab.isae-supaero.fr/dragoon/komodo/-/pipelines))
- the GitHub CI status (links to the [GitHub workflow runs dashboard](https://github.com/dragoon-rs/komodo/actions))

This MR enables by default `kzg` and `aplonk`. By doing that, both modules should be visible in the doc.

## changelog
- _semi\_avid_, _kzg_ and _aplonk_ examples have been added
- the `fs` module has been hidden behind an `fs` feature
- the `conversions` module has been properly hidden behind the `test` config feature
- the documentation has been completed
- some error messages have been improved

> **Note**
>
> the documentation of aPlonK has been left as-is for now

`algebra`, `field` and `linalg` were doing extremely similar things before...

this MR merges them into a single module `algebra`
- old `algebra` and `field` are at the root of the new `algebra`
- old `linalg` is now `algebra::linalg`

all references to these have been fixed in the rest of the codebase and the features have been tuned to work fine.

in dragoon/komodo!162 and dragoon/komodo!163, i did only run `cargo ... --all-features` without checking the individual features...

this MR adds some `cargo check --features ...` to the `Makefile` and makes sure the imports make sense when compiling a single feature.

> ❗ **Important**
>
> the other notable change here is that `kzg::commit` has been moved to `zk::ark_commit` and is re-exported from `kzg` as `kzg::commit`.

this adds the aPlonK cryptographic method alongside Semi-AVID and KZG+.

## changelog
- new feature `aplonk`:
  - the `algebra` module is compiled when either `kzg` or `aplonk` features are enabled
  - `algebra::scalar_product_polynomial` compiles only with `kzg`
  - the other `algebra::*` functions compile with `aplonk`
- `u32_to_u8_vec` has been moved to new `conversions` module which compiles when either `kzg` or `aplonk` features are enabled
- new `aplonk` module which compiles only when the `aplonk` feature is enabled
  - public structures
    - `Block`
    - `Commitment`
    - `SetupParams`
    - `VerifierKey`
  - public functions
    - `setup`
    - `commit`
    - `prove`
    - `verify`
  - internals
    - `ipa::Params`
    - `ipa::Proof`
    - `ipa::prove`
    - `ipa::verify`
    - `polynomial::compute_g`
    - `transcript::initialize`
    - `transcript::reset`
    - `transcript::hash`

this adds the KZG+ cryptographic method alongside Semi-AVID.

## changelog
- the Makefile now uses `--all-features` to compile everything
- a new module `algebra` has been added, with tests for all functions
  - `algebra::scalar_product_polynomial` computes a linear combination of polynomials $(P_i)$
  - `algebra::powers_of` computes $n$ successive powers of a number $r$
- a new function `zk::trim` has been added from [`gitlab.isae-supaero.fr:a.stevan/poly-commit@19fc0d4a/src/kzg10/mod.rs#L513-L538`](https://gitlab.isae-supaero.fr/a.stevan/poly-commit/-/blob/19fc0d4ad2bcff7df030c952d09649918dba7ddb/src/kzg10/mod.rs#L513-L538)
- a new feature `kzg` has been added, with an optional dependency on [`gitlab.isae-supaero.fr:a.stevan/poly-commit@19fc0d4a`](https://gitlab.isae-supaero.fr/a.stevan/poly-commit/-/tree/19fc0d4ad2bcff7df030c952d09649918dba7ddb)
- a new module `kzg` has been added and exposes the following publicly
  - structures
      - `Block`
  - functions
    - `commit`
    - `prove`
    - `verify`
    - `batch_verify`
  - tests when block are left as-is and when one of them is corrupted

## changelog
- `src/main.rs` has been moved to a new crate: `bins/saclin` which stands for **S**emi-**A**VID **CLI** in **N**ushell
- dependencies of `komodo` have been fixed
- Nushell and Rust tests have been split in the Makefile: by default, only Rust tests will run locally and Nushell tests and examples can be run manually if desired. The CI will still run everything.
- the README has been updated
- test images have been moved to `assets/`
- the majority of the old `./nu-utils/` module have been moved to internals of `./benchmarks/` and imports have been fixed
- `cargo.nu` has been moved to `./bins/` and a new `./bins/README.md` mentions it
- `./bins/saclin/` has been created and should be a self-contained Rust crate + Nushell module

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

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

- 1c9077f6 add documentation to the errors
- c388cbbb better FEC doc
- 8d58278d doc of `zk.nb_elements_in_setup`

this MR is two-fold
- it restructures the two main Nushell modules so that they are easier to read and use
- it improves the "run" and "plot" modules for the benchmarks

## changelog
- `.nushell/` is now renamed to `nu-utils/`
- `benchmarks/` is now a valid Nushell module which exports a bunch of modules
  - `benchmarks linalg`: measure and plot linear algebra operations
  - `benchmarks setup`: measure and plot trusted setup building
  - `benchmarks commit`: measure and plot crafting commitments
  - `benchmarks recoding`: measure and plot the recoding of shards
  - `benchmarks fec`: measure and plot FEC operations, such as encoding and recoding, and allow combining these results with the pure recoding ones
- the submodules of `benchmarks` typically have a `run` and a `plot` command, whith the exception of `benchmarks fec` which has a `run` module and multiple "plot" commands in `benchmarks fec plot`
- the "run" commands will create a random temp file by default and ask for confirmation otherwise if the output file already exists, unless `--force` is used
- snippetds in `benchmarks/README.md` have been updated

## results
![setup](/uploads/1f3a383689d3c8fd5a3f1331deabdec0/setup.png)
![commit](/uploads/bcf3bfdd991725abb97cbe4f8890840b/commit.png)
![inverse](/uploads/35316c887c6b2347baa86c4db119f762/inverse.png)
![mul](/uploads/262c27e99d7f2b5c8fb45761607a8717/mul.png)
![transpose](/uploads/2378460cb687d0a9320a24a840ed2eef/transpose.png)

see the changelogs of
- [Nushell `0.94.0`](https://www.nushell.sh/blog/2024-05-28-nushell_0_94_0.html)
- [Nushell `0.94.1`](https://www.nushell.sh/blog/2024-05-30-nushell_0_94_1.html)
- [Nushell `0.94.2`](https://www.nushell.sh/blog/2024-06-03-nushell_0_94_2.html)

i also removed the `bytes encode` and `bytes decode` commands from `.nushell/binary.nu` because... well they did not work anymore and they were not used anywhere 👀

## results
> 💡 **Note**
>
> using the improved plots from dragoon/komodo!153

![inverse](/uploads/9368bc1b23a8f8772a05b8c8bab85b96/inverse.png)
![mul](/uploads/62b9633f47360c01ffbc92fdf15afcbe/mul.png)
![transpose](/uploads/c6892261d27306037a0a2a614f93d584/transpose.png)

this adds a new custom field to the `benchmarks::fields` new module and fixes the "linalg" commands to run the benchmarks

## results
> 💡 **Note**
>
> using the data from dragoon/komodo!156

![inverse](/uploads/9368bc1b23a8f8772a05b8c8bab85b96/inverse.png)
![mul](/uploads/62b9633f47360c01ffbc92fdf15afcbe/mul.png)
![transpose](/uploads/c6892261d27306037a0a2a614f93d584/transpose.png)

## results
![setup](/uploads/4db08ea6e0f34717137b655604381ea7/setup.png)
![commit](/uploads/4542097789129beafc1deb3319da5198/commit.png)

adds a `.env.nu` file to load Nushell modules automatically thanks to the `nuenv` hook from the `nu-hooks` package.

- show the log of the degree for high values
- don't show the "time" Y label because the units are in the times
  values
- don't rotate the X tick labels

## results
![setup](/uploads/75dfd2033801a88e446e0ce8cae24167/setup.png)
![commit](/uploads/cca5bdfabb8f4242d21bf68079a5566a/commit.png)