see a.stevan/nob.rs@26548f75

This is to complete the `check-mirror.nu` script with information about the CI runs.

The current output of
```bash
nu scripts/check-mirror.nu ...[
    https://gitlab.isae-supaero.fr/dragoon/komodo
    https://github.com/dragoon-rs/komodo
    main
]
```
is
```
[INF] adding remotes
[INF] fetching
[INF] cleaning
[ OK] mirror is up to date
[INF] pulling mirror runs
#─┬────id─────┬────────────────head_sha────────────────┬─status──┬conclusion┬run_started_at
0 │11950217125│de4266c0│completed│success   │4 months ago
1 │11950604920│202d8bcc│completed│success   │4 months ago
2 │11950873603│702cd5eb│completed│success   │4 months ago
3 │12028360471│57a96c02│completed│success   │4 months ago
4 │12028432364│07602875│completed│success   │4 months ago
5 │12028781541│f2a76fbb│completed│success   │4 months ago
6 │12631165433│11a5b59d│completed│success   │2 months ago
7 │13008608156│cc412625│completed│success   │2 months ago
8 │13033206333│5511404f│completed│success   │2 months ago
9 │13113244065│ab0d9a8b│completed│success   │2 months ago
10│13679188387│3c8afac4│completed│success   │3 weeks ago
11│14191103891│b5381fda│completed│success   │a day ago
12│14214853530│b7e2d99d│completed│success   │an hour ago
13│14215431531│0d7a5cd6│completed│success   │32 minutes ago
──┴───────────┴────────────────────────────────────────┴─────────┴──────────┴──────────────
```

this should close #17.

SACLIN has been moved to [`gitlab.isae-supaero.fr:dragoon/komodo.nu`](https://gitlab.isae-supaero.fr/dragoon/komodo.nu).

## usage
```bash
nu scripts/check-mirror.nu ...[
    https://gitlab.isae-supaero.fr/dragoon/komodo
    https://github.com/dragoon-rs/komodo
    main
]
```
will
- check the Nushell version and throw a warning if mismatch
- add temporary remotes with random names
- fetch the temporary remotes
- get the revision of the `$branch` for both temporary remotes
- clean the temporary remotes
- show a message if the two revisions are not the same and how many commits they are different

> **Note**
>
> this does not conflict with #17

HEME Clement authored 1 month ago and STEVAN Antoine committed 1 month ago

Added a html header files, an added metadata line in Cargo.toml and some formatting changes in the doc to have Latex formulas in docs.rs. It works locally, should work online

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-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 5 months ago and STEVAN Antoine committed 5 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.