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

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

- pass `n` to `try_all_decoding_combinations` and don't try to decode when shards have been recoded ($\#shards > n$) and there are no recoded shards in the $k$ combination under review ($\max(is) < n$)
- pass `recoding_steps` and `should_not_be_decodable` as arguments to `end_to_end_with_recoding_template`
- fix $n = 5$ => this leads to tests that run in less than 10sec again
- add $(k, n) = (8, 10)$ => tests still run in less than 13sec
- split recoding scenarii into "_simple_" and "_chain_"
- show indices in a "_pretty_" format, i.e. showing indices greater than $n$ as `(n)`, `(n + 1)`, ...

- `komodo::linalg::Matrix::random` is tested
- `komodo::linalg::Matrix::inverse` is tested on more matrix sizes, from $1$ to $20$ random matrices
- `komodo::field` tests have been double-checked
- pure "recoding" tests from `komodo::fec` have been double-checked
- `end_to_end` and `end_to_end_with_recoding` now runs for $k \in [3, 5]$ and $\rho \in [\frac{1}{2}, \frac{1}{3}]$ with $n = \lfloor \frac{k}{\rho} \rfloor$
- all "_$k$ among $n + t$_" combinations are tested with `try_all_decoding_combinations`, possibly with some removals in case recoding is involved with `is_inside`

> ❗ **Important**  
> on my machine, `make test` goes from less than 8sec on latest `main` to around 40sec with this MR

they have been moved to [dragoon/binaries](https://gitlab.isae-supaero.fr/dragoon/binaries).

this is the trivial case where it is always possible to decode the original data, so there is no need to have it here.

this MR
- moves the Nushell modules from `bins/inbreeding/` to `bins/inbreeding/src/.nushell/`
- creates a `NUSHELL` constant in `consts.nu` to allow the following more robust construct
```bash
use consts.nu
use $consts.NUSHELL ...
```
- updates the README

this simply makes "parsing" in the inbreeding modules more robust and centralized.

- early return when format is bad twice
- refactor

wait for
- !134 

## description
assuming !134 has been merged, this MR allows to run something like
```bash
inbreeding list | input list --fuzzy | inbreeding load $in | inbreeding plot
```
which will fuzzy find the available experiments and then plot it after load 👌

this can be used by `plot` without passing extra arguments, i.e. the pipeline becomes
```bash
use bins/inbreeding

let experiment = "..."
```
```bash
inbreeding load $experiment | inbreeding plot
```
instead of having to know the value of `k` and do
```bash
inbreeding load $experiment | inbreeding plot --options { k: $k }
```

- addresses #9 
- needed !133 to work

this MR simply adds `+ Clone` to `rng` and removes the `mut` from the `rng` of the `measure_inbreeding` function.

running the same snippet of code from #9 yields the following two images with a schedule of $1$ and $5$ respectively

![000_1.1](/uploads/ace74e299c6d4374df713ab5004f3c1d/000_1.1.png)
![000_1.2](/uploads/c784f5b62c41004971fd3048f7b5babc/000_1.2.png)

we see that all measurements on $t$ where $t = 0 \mod 5$ are the same in both images 🎉

related to
- #9

in order for the measurements not to influence the experiment, the seeds passed to the runs need to not include the _measurement schedule_ parameters!

EDIT: in the end, it's more than that, we want to only include things related to the environment in its hash, nothing related to the measurements, i.e. we want to either
- exclude `strategies`, `nb_scenarii`, `measurement_schedule`, `measurement_schedule_start`, `nb_measurements` and `max_t`
- include `nb_bytes`, `k`, `n` and `environment`

## output sample
let's say the current seed is `"b239e48345ac457b492cc164f58c010d07292c88e4791e607d91796baec7f334"` and the experiment has ID `fixed:0-single:3-5-50-10240`, and that we are watching both the creation of the first experiment and a few runs, e.g.
- `002d8de28913efbf7dbd111b817ae901fee2d47882ba7aa76d293c2d95d9652c`
- `015672b37c9cf1a6b475937987294f9a503a922ffbcfdfc5d18ef839fac91b8c`
- `080a51a17ac43fcbdf08f77f3bc993983fef589bd9672f04382af4b16dd09b13`

then the output would look like
```
b239e48  fixed:0-single:3-5-50-10240            at 2024-05-30 15:24:12
b239e48  fixed:0-single:3-5-50-10240  002d8de   at 2024-05-30 15:24:14
b239e48  fixed:0-single:3-5-50-10240  015672b   at 2024-05-30 15:24:16
b239e48  fixed:0-single:3-5-50-10240  080a51a   at 2024-05-30 15:24:18
```

we are switching
- _naive recoding_ to _$(k, 1)$-re-encoding_
- _true recoding_ to _$k$-recoding_

this is to have a complete identifier for each run, which does not depend at all on the time at which the experiment runs.

related to
- !122

## description
!122 introduced a `draw_unique_indices` function which uses a `HashSet` to accumulate unique indices in the range `0..<len`.
however, a `HashSet` does not preserve the order of insertion when iterating over the elements of the set... which results in apparent randomness, even though the RNG seed is the same 😮 

this MR switches back to using `shuffle` which used to work, even though a bit less performant 👌   
it's basically a revert of !122, while keeping the refactoring into `random.rs`.

## measuring the performance
i did run the same timing experiment from !122 but with `main` on `bb55005f` and the MR on `fix-shuffle`

| env     | main                   | mr                      | improvement         |
| ------- | ---------------------- | ----------------------- | ------------------- |
| fixed:0 | 6sec 244ms 238µs 45ns | 8sec 734ms 929µs 328ns | -39.88783363238997  |
| fixed:1 | 639ms 720µs 39ns      | 731ms 360µs 261ns      | -14.325051024390373 |

we loose a bit