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

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

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

## new structure for the repository
- benchmarks are in `./benchmarks/` and can be run with either `cargo run --package benchmarks --bin <bench>` or the commands in `./benchmarks/README.md`
```
├── Cargo.toml
├── README.md
└── src
    └── bin
        ├── commit.rs
        ├── fec.rs
        ├── linalg.rs
        ├── operations
        │   ├── curve_group.rs
        │   └── field.rs
        ├── recoding.rs
        ├── setup.rs
        └── setup_size.rs
```

- examples are now in `./bins/` as standalone binaries and can be run either with `cargo run --package <pkg>` or with the help of the `cargo bin` command from `.nushell/cargo.nu`
```
├── curves
│   ├── Cargo.toml
│   ├── README.md
│   └── src
│       └── main.rs
├── inbreeding
│   ├── build.nu
│   ├── Cargo.toml
│   ├── consts.nu
│   ├── mod.nu
│   ├── plot.nu
│   ├── README.md
│   ├── run.nu
│   └── src
│       ├── environment.rs
│       ├── main.rs
│       └── strategy.rs
├── rank
│   ├── Cargo.toml
│   └── src
│       └── main.rs
└── rng
    ├── Cargo.toml
    └── src
        └── main.rs
```

- Nushell modules are now located in `./.nushell/`

## changelog
apart from the changes to the general structure of the repo:
- `binary.nu` -> `.nushell/binary.nu`
- new `cargo bin` command from `.nushell/cargo.nu`
- `error throw` is now defined in `.nushell/error.nu`
- main TOML has been greatly simplified because the dependencies of "examples" have been moved to the associated crates
- the rest is basically the same but in the new structure

this will use PLNK version 0.7.0 with prettier progress bars.

this MR:
- refactors the "inbreeding" example into `examples/inbreeding/`
- adds `--strategy` and `--environment`
  - `Strategy::draw` will draw the number of shards to keep for recoding
  - `Environment::update` will update the pool of shards by losing some of them

this MR adds `examples/inbreeding.rs` which allows to do two things
- _naive recoding_: in order to generate a new random shard, we first $k$-decode the whole data and then $1$-encode a single shard
- _true recoding_: to achieve the same goal, we directly $k$-recode shards into a new one

## the scenario
regardless of the _recoding strategy_, the scenario is the same
1. data is split into $k$ shards and $n$ original shards are generated
2. for a given number of steps $s$, $k$ shards are drawn randomly with replacement and we count the number of successful decoding, given a measure of the _diversity_, $$\delta = \frac{\#success}{\#attempts}$$
3. create a new _recoded shard_ and add it to the $n$ previous ones, i.e. $n$ increases by one
4. repeat steps 2. and 3. as long as you want
 
## results
![inbreeding](/uploads/b81614abcae01b7c915435aa87ccaec0/inbreeding.png)

this MR adds
- `examples/benches/bench_fec.rs` to the list of example benches
- instructions on how to run the new benchmark and plot the results

## results
![encoding](/uploads/d474aa6f39ea20c6b346fb17d2e7ecdc/encoding.png)
![decoding](/uploads/061944e49f02541ea93ac0de9547ce37/decoding.png)
![e2e](/uploads/bb27f4bb6290c4697a65faa59a0ac4e0/e2e.png)

this MR
- moves the last "recoding" benchmark to `examples/benches/`
- moves the README, which is now all alone, to `examples/benches/`
- adds a mention to `examples/benches/README.md` in `README.md`
- some minor improvements to the bench README

## TODO
- [x] find a way to plot the "recoding" results (thanks to !90)

## changelog
- benchmarks
  - _commit_ has been removed in favor of `examples/benches/commit.rs`
  - _linalg_ has been migrated to `examples/benches/` as `bench_linalg`
  - _setup_ has been migrated to `examples/benches/` as `bench_setup`
- `read-atomic-ops` command has been moved to `scripts/parse.nu` module
- `scripts/plot/bench_commit.py` has been made more general and renamed to `scripts/plot/plot.py`
- `scripts/plot/benches.py` has been removed because it's not required anymore => `plot.py` and `multi_bar.py` are general enough

this MR
- bumps PLNK to 0.6.0
- update all existing code
- uses the PLNK lib in `examples/benches/commit.rs`
- fixes the y label of the plot in `scripts/plot/bench_commit.py`: was _ns_, should be _ms_

i've basically refactored the whole "bench" framework that was inlined in  `examples/benches/operations/field.rs` and `examples/benches/operations/curve_group.rs` into a new repo called [PLNK](https://gitlab.isae-supaero.fr/a.stevan/plnk).

nothing effectively changes on the side of Komodo but now the code is much simpler here :)

this idea is to not use `criterion` and measure exactly what we want

## results
![simple_field](/uploads/c114cee9ef4b0e56e9ab290d1cbbab2e/simple_field.png)
![complex_field](/uploads/7bc8ea613793718f6460438f1df6fd24/complex_field.png)
![simple_curve_group](/uploads/a9f8642fc1f1fa558c2bee366622646f/simple_curve_group.png)
![complex_curve_group](/uploads/76a3fbe2430959e20150070beeb196a5/complex_curve_group.png)

as per title

this MR adds two now benchmarks:
- `field_operations` in `benches/operations/field.rs`
- `curve_group_operations` in `benches/operations/curve_group.rs`

as well as `scripts/plot/multi_bar.py` to plot the results, see `benches/README.md` for the commands to run.

## results
![curve_group](/uploads/0a27dcdc7965090b0429867e1822a40c/curve_group.png)

![field](/uploads/461455568a0a637f78f9c2b6d1a68f59/field.png)

## changelog
- rename the `encode` function to `prove` and have it take _shards_ instead of an _encoding matrix_: this is to isolate the "encoding" process inside the `fec` module and leave the main `komodo::prove` only compute the "proof", i.e. the commits of the data

from
```rust
fn encode<F, G, P>(
    bytes: &[u8],
    encoding_mat: &Matrix<F>,
    powers: &Powers<F, G>,
) -> Result<Vec<Block<F, G>>, KomodoError>
```
to
```rust
fn prove<F, G, P>(
    bytes: &[u8],
    powers: &Powers<F, G>,
    k: usize,
) -> Result<Vec<Commitment<F, G>>, KomodoError>
```
- rename `fec::Shard.combine` to `fec::Shard.recode_with` to get rid of "combine"
- rename `fec::recode` to `fec::recode_with_coeffs` to show that this version takes a list of coefficients
- rename `Block.commit` to `Block.proof`: "commit" should be "commits" and it's usually refered to as "proof"
- split `prove` further into `prove` and `build`: `prove` now outputs a `Vec<Commitment<F>>`, `build` simply takes a `Vec<Shard<F>>` and a `Vec<Commitment<F>>` and outputs a `Vec<Block<F>>`
- add `fec::recode_random` that does the "shard" part of `recode` to wrap around `fec::recode_with_coeffs`
- remove `R: RngCore` from the signature of `zk::setup`, to avoid having to pass a generic `_` annotation everywhere `zk::setup` is used, same change has been applied to `recode` and the `generate_random_powers` in `main.rs`

from
```rust
fn setup<R: RngCore, F: PrimeField, G: CurveGroup<ScalarField = F>>(
    max_degree: usize,
    rng: &mut R,
) -> Result<Powers<F, G>, KomodoError> {
```
to
```rust
fn setup<F: PrimeField, G: CurveGroup<ScalarField = F>>(
    max_degree: usize,
    rng: &mut impl RngCore,
) -> Result<Powers<F, G>, KomodoError> {
```

### some extra minor changes
- remove some useles generic type annotations, e.g. `prove::<F, G, P>` can become a simpler `prove` most of the time, i.e. when there is at least one generic annotation somewhere in the scope

i ended up adding a bunch of changes to the benchmarks 😊 

## changelog
* 805a2454 reduce the number of loops and the warmup time
* f7ce05c3 don't serialize for real to save time
* 37a2a7e2 don't try to compress with validation
* 409f3e3c don't multiply degree by 1_024
* 610024a9 fix setup
* 3d5e7c58 fix setup
* 3d3167fb run benchmarks on BLS12-381, BN-254 and PALLAS
* da2a71a1 pass name of the curve as parameter
* 954fd6d3 plot commit for all curves
* f980b30f plot all curves in linalg
* 5e41df1d rename `labels` to `keys` in commit
* 8bb64f99 filter setup by curves
* 0163c8f9 plot all curves in setup
* 8c91c6d8 split the setup of Komodo and the serde benchmarks
* 0784f294 add a manual benchmark to measure the commit
* 608a3fd1 move the "example benches" to `examples/benches/`
* 10f9a37c add a script to plot results from `bench_commit`
* 6d512fa6 move plot script from `benches/` to `scripts/plot/`
* a4e6ffbc measure VESTA

this MR adds a benchmark for
- the KZG10 trusted setup creating of `ark-poly-commit`
- the KZG10 commit of `ark-poly-commit`
- our own implement of the commit in `zk::commit`

there is also a slight improvement to the previous benchmarking of our `zk::setup`: the degree of the _trusted setup_ is now computed once and for all before the benchmarking loop starts, because it's not what is of interest, let's not benchmark it.

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

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)

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 |

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

# changelog
- add a `one_less` argument to `field::merge_elements_into_bytes` to mirror the `one_more` from `field::split_data_into_field_elements`
- add a `linalg` module which defines
  - a `pub LinalgError` enum
  - a `pub(super) Matrix` structure implement for any `ark_ff::Field`, e.g. `<Bls12_381 as Pairing>::ScalarField`
  - `pub(super) Matrix::vandermonde`
  - `pub(super) Matrix::from_vec_vec`
  - `pub(super) Matrix::invert`
  - `pub(super) Matrix::mul`
  - `pub(super) Matrix::transpose`
  - everything is tested extensively
- modify `fec.rs` to use `linalg::Matrix` instead of `reed-solomon-erasure` => tests still pass
- remove the dependency to [`reed-solomon-erasure`](https://github.com/jdetchart/reed-solomon-erasure) completely