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-table` will now produce a table with columns `x` and `items` instead of `group` and `items` as in 0.95.0
- add link to results repo
- the Nushell benchmarks lib
  - rename `--force` to `--no-confirm (-y)`
  - add `--append` 
  - reject columns that GPLT will complain about, e.g. `$.points.k` for the FRI plots
  - add `--save` to the FRI plot
- move the "field" and "curve group" benchmarks from `benchmarks/src/bin/operations/` to `benchmarks/src/bin/`
- remove `benchmarks/params/fri.nu` because it's been uniformized with the other methods
- rewrite the README
- add main function to `benchmarks/` that runs the benchmarks from a NUON record specification
- simplify the output of FRI run

## TODO
- [x] fix "_atomic operations_" (done in 4f69a1d6)
- [x] check that _plotting_ still works

## images

### Field
![complex_curve_group_operations](/uploads/57b36926cce041cf405a9b44f190b8b8/complex_curve_group_operations.png)
![complex_field_operations](/uploads/0747c85dbaff8980561aa9d922fcd5e7/complex_field_operations.png)
![simple_curve_group_operations](/uploads/974cf70fed68f8d8ac898d54be3f27be/simple_curve_group_operations.png)
![simple_field_operations](/uploads/a3d4d0dcdeb35d4c434eaa38fb51e7b5/simple_field_operations.png)

### Linear algebra
![linalg-inverse](/uploads/bc290ffa39459ce0f9bbd393b50b7b98/linalg-inverse.png)
![linalg-mul](/uploads/96d8c2a63ed48d6a0d3508b4a948153b/linalg-mul.png)
![linalg-transpose](/uploads/128e35eca91497d8aadb0130c05aeee3/linalg-transpose.png)

### FEC
![encoding](/uploads/405c4d3ef9ec5135ebdd7ce2e6c96bfe/encoding.png)
![decoding](/uploads/d793234d44e9fc6f34f0c2a9372863cd/decoding.png)
![recoding](/uploads/413021de997c86d45b1287fcfe7804c7/recoding.png)
![combined](/uploads/6d1c3ae6d3bf5547434ca29ae80b5536/combined.png)
![ratio](/uploads/6cebd7a0bcef57d1b1256bc3941c1b0a/ratio.png)

### ZK
![setup](/uploads/1feb169452aa3274dc924edf772c9a5b/setup.png)
![commit](/uploads/0a2775c2116ca7d3fa7b956b934d1565/commit.png)

### FRI
![commits_single](/uploads/4602725e551a025d42815183a61d11b2/commits_single.png)
![commits_single_normalized](/uploads/2ffebea940af1cbbe9bd64499343e0e9/commits_single_normalized.png)
![end_to_end](/uploads/46917abd2f5976dfa6d3039cc0ab2c0e/end_to_end.png)
![evaluating](/uploads/cf4dc496cd5144615bf5f9b06d27dccd/evaluating.png)
![proofs](/uploads/b0828bfa62c2226c8d63c9ecd387049f/proofs.png)
![proofs_normalized](/uploads/8fbf0d713884e2e147c62313a001f379/proofs_normalized.png)
![proving](/uploads/161539dc412330be1878cdda82c3d966/proving.png)
![verifying_single](/uploads/2df7e777481d7789478386f8e83e0783/verifying_single.png)

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
  - tweak the output of `make show` a bit
  - add `print-%` rules to print `Makefile` variables, e.g. `make print-NU_FLAGS` would print `--no-config-file`
  - add `make install-nu` to replace the ones from the CIs
- GitLab CI
  - use `make install-nu`
  - export `PATH` with `make print-NU_DEST`
- GitHub CI 
  - use `make install-nu` instead of [github.com:hustcer/setup-nu](https://github.com/hustcer/setup-nu)
  - export `PATH` with `make print-NU_DEST` and `GITHUB_ENV`

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 that there must be at least 6 blocks
  - pass a list of "_recodings_", i.e. `recodings: Vec<(Vec<Vec<usize>>, bool)>`, to `end_to_end_with_recoding_template` and assert the number of blocks and the number of source shards, e.g. `vec![(vec![vec![0, 1], vec![2], vec![3]], true)]` means that trying to decode with blocks 2, 3 and a recoded block from 0 and 1 should work, and also that there must be at least 4 blocks and at most 3 source shards
  - pass `k` and `n` to `run_template`

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

see [`dragoon/nc-diversity`](https://gitlab.isae-supaero.fr/dragoon/nc-diversity)

this will
- recode for $\#steps \in [10, 20, 100]$
- at $t = 0$, $k$ random shards among the $n$ encoded will be selected at random
- at $t \geq 1$, all $k$ shards will be used to recode $k$ brand new shards
- make sure the last set of $k$ shards recoded $\#steps$ together can decode the data

## example with $(k, n) = (3, 5)$ and $\#steps = 3$
- $(s_i)_{1 \leq i \leq k}$ are the $k$ source shards
- $(e_j)_{1 \leq j \leq n}$ are the $n$ encoded shards
- $(m_i)_{1 \leq i \leq k}$ are the $k$ randomly selected shards
- $(n_i)_{1 \leq i \leq k}$ are the shards after step $1$
- $(o_i)_{1 \leq i \leq k}$ are the shards after step $2$
- $(p_i)_{1 \leq i \leq k}$ are the shards after step $3$
- the $(p_i)_{1 \leq i \leq k}$ will be used for decoding

```mermaid
graph TD;

    s1 --> e1; s1 --> e2; s1 --> e3; s1 --> e4; s1 --> e5;
    s2 --> e1; s2 --> e2; s2 --> e3; s2 --> e4; s2 --> e5;
    s3 --> e1; s3 --> e2; s3 --> e3; s3 --> e4; s3 --> e5;

    e1 --> m1;
    e3 --> m2;
    e4 --> m3;

    m1 --> n1; m1 --> n2; m1 --> n3;
    m2 --> n1; m2 --> n2; m2 --> n3;
    m3 --> n1; m3 --> n2; m3 --> n3;

    n1 --> o1; n1 --> o2; n1 --> o3;
    n2 --> o1; n2 --> o2; n2 --> o3;
    n3 --> o1; n3 --> o2; n3 --> o3;

    o1 --> p1; o1 --> p2; o1 --> p3;
    o2 --> p1; o2 --> p2; o2 --> p3;
    o3 --> p1; o3 --> p2; o3 --> p3;
```