- Mar 31, 2025
-
-
HEME Clement authored
-
- Mar 19, 2025
-
-
HEME Clement authored
-
- Jan 28, 2025
-
-
STEVAN Antoine authoredmainly 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`
-
- Nov 21, 2024
-
-
STEVAN Antoine authored
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      ### sizes    
-
- Nov 05, 2024
-
-
STEVAN Antoine authored
-
- Sep 23, 2024
-
-
STEVAN Antoine authored
## 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
-
- Aug 06, 2024
-
-
STEVAN Antoine authored
`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.
-
STEVAN Antoine authored
in !162 and !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`. -
STEVAN Antoine authored
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` -
STEVAN Antoine authored
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
-
- Aug 01, 2024
-
-
STEVAN Antoine authored
## 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
-
STEVAN Antoine authored
this is a refactor to prepare the addition of other cryptographic methods. ## changelog - moves Semi-AVID code from `lib.rs` to `semi_avid.rs`
-
- Jul 31, 2024
-
-
STEVAN Antoine authored
- 1c9077f6 add documentation to the errors - c388cbbb better FEC doc - 8d58278d doc of `zk.nb_elements_in_setup`
-
- Jun 07, 2024
-
-
STEVAN Antoine authored
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; ``` -
STEVAN Antoine authored
- 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)`, ...
-
- Jun 06, 2024
-
-
STEVAN Antoine authored
- `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
-
- May 27, 2024
-
-
STEVAN Antoine authored
makes sure - "inbreeding" experiment quits when there are less than $k$ shards - `fec::decode` returns `KomodoError::TooFewShards` when no shards are provided
-
- Apr 15, 2024
-
-
STEVAN Antoine authored
add "unchecked" versions of `Matrix::{vandermonde,from_vec_vec}` and test both matrices (dragoon/komodo!75) ## changelog - replace `Matrix::vandermonde` with `Matrix::vandermonde_unchecked` - add a new `Matrix::vandermonde` which calls `Matrix::vandermonde_unchecked` after checking the seed points are distinct, otherwise, gives a `KomodoError::InvalidVandermonde` error - same with `Matrix::from_vec_vec` and `Matrix::from_vec_vec_unchecked` - add documentation tests for the two "checked" functions - run the main lib tests on both a random and a Vandermond matrix, just to be sure we do not take advantage of the Vandermonde structure
-
- Apr 12, 2024
-
-
STEVAN Antoine authored
## 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
-
- Apr 11, 2024
-
-
-
STEVAN Antoine authored
## changelog * eb1b1381 don't use a T in the lib `run_template` test * fbd503c6 remove the useless unwrap and TODO * b550d712 remove some pub * 339c3038 remove useless `.iter()` * 537993f0 remove useless `.add(...)` * d7720907 remove hiding_bound from timer in commit * eecab5a6 move `commit` to inlined `zk::batch_commit`
-
- Apr 08, 2024
-
-
STEVAN Antoine authored
should address #8 ## changelog - move the internal `rng` to an argument of type `R: RngCore` for the following functions - `recode` in `lib.rs` - `linalg::Matrix::random` - `generate_random_setup` in `main.rs` - make sure - `ark_std::test_rng` is only used in tests modules - `rand::thread_rng` is used in benchmarks, examples and `main.rs`
-
STEVAN Antoine authored
there was some missing parts from recent commits and also a dead link to `setup::setup` which is now `zk::setup`.
-
- Apr 05, 2024
-
-
STEVAN Antoine authored
in 3c91ef12 and !54, a new implementation of the creation of the _trusted setup_ has been introduced, that gets rid of the `E: Pairing` requirement with a more general `<F: PrimeField, G: CurveGroup<_>>`. however, the size of the _trusted setup_ was incorrect. `zk::setup` requires the _maximum degree_ of the _trusted setup_, however, the number of bytes `nb_bytes` was consistently being given to it throughout the code base... this MR - introduces a new `zk::nb_elements_in_setup` that converts a number of bytes to the associated number of _trusted setup_ elements - uses that new `zk` function before calling `zK::setup` in all the code base ## results >
💡 **Note** > !58 is required for the whole table to be used easily >💡 **Note** > here is how to run the benchmarks in Nushell > ```bash > let bad_mr = "3c91ef12" > let fix = "fix-setup-size" > > git co $"($bad_mr)^" > cargo criterion --output-format verbose --message-format json out> benches/results/before.ndjson > cargo run --example bench_setup_size out>> benches/results/before.ndjson > > git co $bad_mr > cargo criterion --output-format verbose --message-format json out> benches/results/after.ndjson > cargo run --example bench_setup_size out>> benches/results/after.ndjson > > git co $fix > cargo criterion --output-format verbose --message-format json out> benches/results/fix.ndjson > cargo run --example bench_setup_size out>> benches/results/fix.ndjson > ``` > and here the script used to generate that table is the following: > ```bash > def "parse bench-file" []: table<reason: string, id: string, mean: any> -> table<id: string, mean: float> { > where reason == "benchmark-complete" > | select id mean > # NOTE: because `bench_setup_size.rs` outputs `record<reason: string, id: string, mean: float>` > | update mean { if ($in | describe) == int { $in } else { $in.estimate } } > # NOTE: addressed in `!58` > | update id {|it| > if ($it.id | str starts-with "recoding") { > $it.id ++ " on some curve" > } else { > $it.id > } > } > | update mean { into int } > | update id { parse "{id} on {curve}" | into record | get id } > } > > let before = open benches/results/before.ndjson | parse bench-file > let after = open benches/results/after.ndjson | parse bench-file > let fix = open benches/results/fix.ndjson | parse bench-file > > $before > | join $after id > | rename --column { mean: "before", mean_: "after" } > | join $fix id > | rename --column { mean: "fix" } > | insert b->a {|it| $it.after / $it.before | math round --precision 2 } > | insert a->f {|it| $it.fix / $it.after | math round --precision 2 } > | insert b->f {|it| $it.fix / $it.before | math round --precision 2 } > | select id before b->a after a->f fix b->f > | to md --pretty > ``` >❗ **Important** > before this very MR, i.e. on `3c91ef12`, there was a factor of 15x between _before_ and _after_, meaning that the _trusted setups_ were 15 times larger and longer to serde👀 > > this can be explained by the following facts > - due to the bad sizes given to the _trusted setup_ building function, the setups were around 30 times larger, 30 being close to the size of a field element on BLS-12-381 > - because the `zk::setup` function only creates half of what its Arkworks counterpart does, the setups were at the same time around 2 times smaller > > combining these two and we get a factor of 15x!! > > now, with this MR, we get rid of the first factor and are left with _trusted setups_ twice as small and twice as fast to serde🎉 | id | before | b->a | after | a->f | fix | b->f | | --------------------------------------------------------------- | ---------- | ------- | ---------- | ------- | ---------- | ------- | | inverse 10x10 | 336359 | 0.93 | 313852 | 1.05 | 329191 | 0.98 | | inverse 15x15 | 811018 | 0.99 | 800064 | 1.01 | 807417 | 1 | | inverse 20x20 | 1511592 | 1 | 1508034 | 1.02 | 1542538 | 1.02 | | inverse 30x30 | 3703750 | 1.01 | 3731380 | 1.02 | 3793071 | 1.02 | | inverse 40x40 | 7163839 | 1 | 7145015 | 1.03 | 7336996 | 1.02 | | inverse 60x60 | 18620089 | 1 | 18625577 | 1.02 | 18922329 | 1.02 | | inverse 80x80 | 37571610 | 1 | 37643906 | 1.02 | 38306236 | 1.02 | | inverse 120x120 | 105404054 | 1 | 105281874 | 1.01 | 106797441 | 1.01 | | inverse 160x160 | 224332257 | 1 | 224092724 | 1.01 | 227066824 | 1.01 | | inverse 240x240 | 671096671 | 1 | 671005055 | 1.01 | 679280010 | 1.01 | | inverse 320x320 | 1487909175 | 1 | 1488534950 | 1.01 | 1506027089 | 1.01 | | transpose 10x10 | 87 | 0.93 | 81 | 1 | 81 | 0.93 | | transpose 15x15 | 175 | 0.96 | 168 | 1 | 168 | 0.96 | | transpose 20x20 | 284 | 1.03 | 293 | 0.95 | 279 | 0.98 | | transpose 30x30 | 759 | 1.22 | 924 | 0.89 | 823 | 1.08 | | transpose 40x40 | 1798 | 1.63 | 2935 | 0.98 | 2887 | 1.61 | | transpose 60x60 | 3830 | 1.67 | 6378 | 1.01 | 6468 | 1.69 | | transpose 80x80 | 7720 | 1.5 | 11548 | 0.99 | 11470 | 1.49 | | transpose 120x120 | 16365 | 1.5 | 24572 | 0.98 | 24059 | 1.47 | | transpose 160x160 | 42764 | 1.18 | 50453 | 1.07 | 54189 | 1.27 | | transpose 240x240 | 119435 | 1.18 | 141357 | 1 | 140752 | 1.18 | | transpose 320x320 | 218674 | 1.13 | 246262 | 1 | 247167 | 1.13 | | mul 10x10 | 15499 | 1 | 15474 | 1 | 15527 | 1 | | mul 15x15 | 51800 | 1 | 51913 | 1 | 51772 | 1 | | mul 20x20 | 122399 | 1 | 122390 | 1.01 | 123248 | 1.01 | | mul 30x30 | 499047 | 0.95 | 474740 | 1.01 | 481756 | 0.97 | | mul 40x40 | 1224755 | 0.98 | 1203588 | 1.01 | 1211995 | 0.99 | | mul 60x60 | 4166589 | 0.99 | 4122003 | 1 | 4139839 | 0.99 | | mul 80x80 | 9942560 | 0.99 | 9870864 | 1 | 9912815 | 1 | | mul 120x120 | 33706366 | 0.99 | 33458234 | 1.01 | 33680802 | 1 | | mul 160x160 | 79645646 | 1 | 79974020 | 1.01 | 80469214 | 1.01 | | mul 240x240 | 277091998 | 0.99 | 274638961 | 1.01 | 276412347 | 1 | | mul 320x320 | 664942845 | 1 | 662229758 | 1.02 | 676065811 | 1.02 | | recoding 1 bytes and 2 shards with k = 2 | 124 | 1 | 124 | 1.02 | 127 | 1.02 | | recoding 1 bytes and 2 shards with k = 4 | 179 | 0.99 | 178 | 1.01 | 180 | 1.01 | | recoding 1 bytes and 2 shards with k = 8 | 284 | 1 | 284 | 1 | 285 | 1 | | recoding 1 bytes and 2 shards with k = 16 | 496 | 1.01 | 499 | 1.01 | 505 | 1.02 | | recoding 1 bytes and 4 shards with k = 2 | 347 | 1.01 | 349 | 0.99 | 347 | 1 | | recoding 1 bytes and 4 shards with k = 4 | 505 | 1 | 505 | 1 | 507 | 1 | | recoding 1 bytes and 4 shards with k = 8 | 821 | 1 | 825 | 1 | 825 | 1 | | recoding 1 bytes and 4 shards with k = 16 | 1451 | 1 | 1454 | 1.01 | 1464 | 1.01 | | recoding 1 bytes and 8 shards with k = 2 | 792 | 1 | 791 | 1 | 792 | 1 | | recoding 1 bytes and 8 shards with k = 4 | 1162 | 1 | 1163 | 1.01 | 1169 | 1.01 | | recoding 1 bytes and 8 shards with k = 8 | 1884 | 1.01 | 1897 | 1 | 1902 | 1.01 | | recoding 1 bytes and 8 shards with k = 16 | 3361 | 1 | 3368 | 1.02 | 3446 | 1.03 | | recoding 1 bytes and 16 shards with k = 2 | 1680 | 1 | 1679 | 1.01 | 1699 | 1.01 | | recoding 1 bytes and 16 shards with k = 4 | 2472 | 1 | 2475 | 1 | 2468 | 1 | | recoding 1 bytes and 16 shards with k = 8 | 4034 | 1 | 4033 | 1.01 | 4060 | 1.01 | | recoding 1 bytes and 16 shards with k = 16 | 7187 | 1 | 7173 | 1.02 | 7331 | 1.02 | | recoding 1024 bytes and 2 shards with k = 2 | 1020 | 1 | 1020 | 1 | 1017 | 1 | | recoding 1024 bytes and 2 shards with k = 4 | 1079 | 1 | 1081 | 0.98 | 1064 | 0.99 | | recoding 1024 bytes and 2 shards with k = 8 | 1186 | 0.98 | 1167 | 1 | 1166 | 0.98 | | recoding 1024 bytes and 2 shards with k = 16 | 1386 | 1 | 1392 | 0.99 | 1383 | 1 | | recoding 1024 bytes and 4 shards with k = 2 | 2978 | 1 | 2968 | 1 | 2970 | 1 | | recoding 1024 bytes and 4 shards with k = 4 | 3120 | 1 | 3113 | 1 | 3113 | 1 | | recoding 1024 bytes and 4 shards with k = 8 | 3438 | 1 | 3445 | 1 | 3447 | 1 | | recoding 1024 bytes and 4 shards with k = 16 | 4056 | 1 | 4071 | 1 | 4051 | 1 | | recoding 1024 bytes and 8 shards with k = 2 | 6905 | 1 | 6879 | 1 | 6861 | 0.99 | | recoding 1024 bytes and 8 shards with k = 4 | 7236 | 1 | 7216 | 1 | 7227 | 1 | | recoding 1024 bytes and 8 shards with k = 8 | 7969 | 1 | 7986 | 1 | 7962 | 1 | | recoding 1024 bytes and 8 shards with k = 16 | 9455 | 1 | 9427 | 1 | 9442 | 1 | | recoding 1024 bytes and 16 shards with k = 2 | 14746 | 1 | 14760 | 0.99 | 14686 | 1 | | recoding 1024 bytes and 16 shards with k = 4 | 15516 | 1 | 15493 | 1 | 15538 | 1 | | recoding 1024 bytes and 16 shards with k = 8 | 17112 | 1 | 17097 | 1 | 17078 | 1 | | recoding 1024 bytes and 16 shards with k = 16 | 20237 | 1 | 20284 | 1 | 20295 | 1 | | recoding 1048576 bytes and 2 shards with k = 2 | 1427516 | 1.01 | 1441658 | 0.99 | 1424866 | 1 | | recoding 1048576 bytes and 2 shards with k = 4 | 1083761 | 1.01 | 1094451 | 1 | 1089954 | 1.01 | | recoding 1048576 bytes and 2 shards with k = 8 | 1087564 | 0.99 | 1076515 | 1.02 | 1094795 | 1.01 | | recoding 1048576 bytes and 2 shards with k = 16 | 1089556 | 0.99 | 1078406 | 1.03 | 1105840 | 1.01 | | recoding 1048576 bytes and 4 shards with k = 2 | 3256507 | 1 | 3250060 | 1.04 | 3370007 | 1.03 | | recoding 1048576 bytes and 4 shards with k = 4 | 3259079 | 1.01 | 3285892 | 1 | 3297768 | 1.01 | | recoding 1048576 bytes and 4 shards with k = 8 | 3235697 | 1 | 3244151 | 1.01 | 3278027 | 1.01 | | recoding 1048576 bytes and 4 shards with k = 16 | 3240586 | 1.01 | 3264910 | 1.01 | 3284101 | 1.01 | | recoding 1048576 bytes and 8 shards with k = 2 | 7580388 | 1 | 7576306 | 1.02 | 7732461 | 1.02 | | recoding 1048576 bytes and 8 shards with k = 4 | 7567385 | 1.01 | 7614250 | 1.01 | 7699032 | 1.02 | | recoding 1048576 bytes and 8 shards with k = 8 | 7589588 | 1 | 7584071 | 1.01 | 7643021 | 1.01 | | recoding 1048576 bytes and 8 shards with k = 16 | 7572517 | 1 | 7596138 | 1.01 | 7637596 | 1.01 | | recoding 1048576 bytes and 16 shards with k = 2 | 16248634 | 1 | 16245477 | 1.01 | 16450530 | 1.01 | | recoding 1048576 bytes and 16 shards with k = 4 | 16253850 | 1 | 16299266 | 1.01 | 16458170 | 1.01 | | recoding 1048576 bytes and 16 shards with k = 8 | 16240827 | 1 | 16265027 | 1 | 16256734 | 1 | | recoding 1048576 bytes and 16 shards with k = 16 | 16229981 | 1 | 16307729 | 1 | 16265882 | 1 | | setup/setup 1024 | 8934763 | 2.12 | 18942383 | 0.11 | 2175852 | 0.24 | | setup/serializing with compression 1024 | 4194 | 15.82 | 66364 | 0.03 | 2100 | 0.5 | | setup/serializing with no compression 1024 | 4953 | 16.04 | 79451 | 0.03 | 2501 | 0.5 | | setup/deserializing with compression and validation 1024 | 3644409 | 15.18 | 55337980 | 0.03 | 1809773 | 0.5 | | setup/deserializing with compression and no validation 1024 | 1065186 | 15.74 | 16762363 | 0.03 | 544255 | 0.51 | | setup/deserializing with no compression and validation 1024 | 2566945 | 15.17 | 38931135 | 0.03 | 1258935 | 0.49 | | setup/deserializing with no compression and no validation 1024 | 6722 | 14.84 | 99769 | 0.03 | 3235 | 0.48 | | setup/setup 2048 | 9092980 | 3.63 | 33024605 | 0.09 | 2909175 | 0.32 | | setup/serializing with compression 2048 | 8240 | 16.32 | 134437 | 0.03 | 4141 | 0.5 | | setup/serializing with no compression 2048 | 9767 | 16.41 | 160306 | 0.03 | 4976 | 0.51 | | setup/deserializing with compression and validation 2048 | 7239787 | 15.32 | 110931280 | 0.03 | 3639477 | 0.5 | | setup/deserializing with compression and no validation 2048 | 2113330 | 15.93 | 33674890 | 0.03 | 1084243 | 0.51 | | setup/deserializing with no compression and validation 2048 | 5081373 | 15.25 | 77482178 | 0.03 | 2537317 | 0.5 | | setup/deserializing with no compression and no validation 2048 | 13079 | 15.14 | 198034 | 0.03 | 6479 | 0.5 | | setup/setup 4096 | 9731992 | 6.14 | 59757543 | 0.07 | 4328023 | 0.44 | | setup/serializing with compression 4096 | 16462 | 16.44 | 270647 | 0.03 | 8407 | 0.51 | | setup/serializing with no compression 4096 | 19654 | 16.4 | 322264 | 0.03 | 9854 | 0.5 | | setup/deserializing with compression and validation 4096 | 14330104 | 15.47 | 221659652 | 0.03 | 7227388 | 0.5 | | setup/deserializing with compression and no validation 4096 | 4214098 | 15.79 | 66537465 | 0.03 | 2137818 | 0.51 | | setup/deserializing with no compression and validation 4096 | 10095359 | 15.33 | 154755178 | 0.03 | 5037809 | 0.5 | | setup/deserializing with no compression and no validation 4096 | 26192 | 14.94 | 391397 | 0.03 | 12862 | 0.49 | | setup/setup 8192 | 9594720 | 11.35 | 108884342 | 0.06 | 6893620 | 0.72 | | setup/serializing with compression 8192 | 33114 | 16.42 | 543855 | 0.03 | 16713 | 0.5 | | setup/serializing with no compression 8192 | 39992 | 16.17 | 646576 | 0.03 | 19983 | 0.5 | | setup/deserializing with compression and validation 8192 | 28578044 | 15.55 | 444525236 | 0.03 | 14337421 | 0.5 | | setup/deserializing with compression and no validation 8192 | 8417684 | 15.93 | 134082205 | 0.03 | 4309633 | 0.51 | | setup/deserializing with no compression and validation 8192 | 20134851 | 15.39 | 309785238 | 0.03 | 10066797 | 0.5 | | setup/deserializing with no compression and no validation 8192 | 51832 | 15.06 | 780369 | 0.03 | 25710 | 0.5 | | setup/setup 16384 | 10096523 | 19.72 | 199105054 | 0.06 | 11317161 | 1.12 | | setup/serializing with compression 16384 | 67050 | 16.28 | 1091282 | 0.03 | 33502 | 0.5 | | setup/serializing with no compression 16384 | 80269 | 16.2 | 1300111 | 0.03 | 40785 | 0.51 | | setup/deserializing with compression and validation 16384 | 56905556 | 15.56 | 885542593 | 0.03 | 28622218 | 0.5 | | setup/deserializing with compression and no validation 16384 | 16829951 | 15.96 | 268660355 | 0.03 | 8607645 | 0.51 | | setup/deserializing with no compression and validation 16384 | 40158772 | 15.44 | 619890738 | 0.03 | 20006634 | 0.5 | | setup/deserializing with no compression and no validation 16384 | 103242 | 15.07 | 1555913 | 0.03 | 51533 | 0.5 | | serialized size with compression and validation 1024 | 3280 | 15 | 49208 | 0.03 | 1640 | 0.5 | | serialized size with compression and no validation 1024 | 3280 | 15 | 49208 | 0.03 | 1640 | 0.5 | | serialized size with no compression and validation 1024 | 6544 | 15.04 | 98408 | 0.03 | 3272 | 0.5 | | serialized size with no compression and no validation 1024 | 6544 | 15.04 | 98408 | 0.03 | 3272 | 0.5 | | serialized size with compression and validation 2048 | 6448 | 15.25 | 98360 | 0.03 | 3224 | 0.5 | | serialized size with compression and no validation 2048 | 6448 | 15.25 | 98360 | 0.03 | 3224 | 0.5 | | serialized size with no compression and validation 2048 | 12880 | 15.27 | 196712 | 0.03 | 6440 | 0.5 | | serialized size with no compression and no validation 2048 | 12880 | 15.27 | 196712 | 0.03 | 6440 | 0.5 | | serialized size with compression and validation 4096 | 12784 | 15.38 | 196664 | 0.03 | 6392 | 0.5 | | serialized size with compression and no validation 4096 | 12784 | 15.38 | 196664 | 0.03 | 6392 | 0.5 | | serialized size with no compression and validation 4096 | 25552 | 15.39 | 393320 | 0.03 | 12776 | 0.5 | | serialized size with no compression and no validation 4096 | 25552 | 15.39 | 393320 | 0.03 | 12776 | 0.5 | | serialized size with compression and validation 8192 | 25456 | 15.45 | 393272 | 0.03 | 12728 | 0.5 | | serialized size with compression and no validation 8192 | 25456 | 15.45 | 393272 | 0.03 | 12728 | 0.5 | | serialized size with no compression and validation 8192 | 50896 | 15.45 | 786536 | 0.03 | 25448 | 0.5 | | serialized size with no compression and no validation 8192 | 50896 | 15.45 | 786536 | 0.03 | 25448 | 0.5 | | serialized size with compression and validation 16384 | 50800 | 15.48 | 786488 | 0.03 | 25400 | 0.5 | | serialized size with compression and no validation 16384 | 50800 | 15.48 | 786488 | 0.03 | 25400 | 0.5 | | serialized size with no compression and validation 16384 | 101584 | 15.48 | 1572968 | 0.03 | 50792 | 0.5 | | serialized size with no compression and no validation 16384 | 101584 | 15.48 | 1572968 | 0.03 | 50792 | 0.5 | -
STEVAN Antoine authored
woopsie, it was missing from !54
-
STEVAN Antoine authored
this is a minor proposition, get rid of the `UniPoly12_381` or `UniPoly381` type aliases that are just `DensePolynomial<Fr>`. now, it's enough to just change the import of `Fr` to another crate / another curve, without having an inconsistent mention to BLS-12-381 in the name of the _dense polynomial_.
-
- Apr 04, 2024
-
-
STEVAN Antoine authored
as per title, this is a minor MR that just makes sure the imports are consistent across modules. in order - `std` - `ark_...` - others - `komodo` or `crate` or `super`
-
STEVAN Antoine authored
-
STEVAN Antoine authored
## 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
-
- Apr 02, 2024
-
-
STEVAN Antoine authored
`fs` was using hardcoded `COMPRESS` and `VALIDATE`, now it uses values passed by the caller
👍 thanks @n.dissoubray😉
-
- Mar 26, 2024
-
-
STEVAN Antoine authored
> **Note** > this MR is best reviewed commit by commit, it's hopefully clear enough. > **Note** > waiting for dragoon/komodo!47 to land ## changelog - add missing format to the `KomodoError`s - rename `fec::Shard::bytes` to `fec::Shard::data` because these are no _bytes_ - rename the `blocks: Vec<Shard<E>>` argument of `fec::decode` to `shards` - refactor the tests of `fec` and `lib.rs` - remove the `batch_verify` function entirely as it's pretty useless - simplify the `linalg::Matrix::random` function - add tests for the function in the `setup` module - add documentation where it was missing
-
STEVAN Antoine authored
this MR is purely cosmetic and only changes the way matrices look when displayed to the standard output. ## changelog - the `Display` implementation for `linalg::Matrix` now takes format parameters to adapt the way matrices look in the standard output => see the documentation of `Display::fmt` for `linalg::Matrix` for more information and examples
-
## 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) ?
-
STEVAN Antoine authored
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 
-
STEVAN Antoine authored
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 |
-
- Mar 20, 2024
-
-
STEVAN Antoine authored
tries to address #5 ## changelog - the `rank.rs` example now only returns the _rank_ to `stdout` - two tests have been added - one that asserts $\text{r}(M^T) = \text{r}(M)$ - one that asserts $\text{r}(M) \leq \min(n, m)$ when $n$ and $m$ are the heigth and the width of $M$ respectively - `Matrix::rank` has been rewritten thanks to ChatGPT, the full prompt can be found in the body of 384d9559 and the algorithm has been refactored and simplified in the following few commits > **Note** > the two new tests do not pass on e27561bb but do pass on the tip of this MR branch, which indicates that the bugs have been solved
-
- Mar 06, 2024
-
-
STEVAN Antoine authored
it appears this field is never used
👀 i think we can simply remove it entirely and thus simplify a bit the `Block`s🙂
-
- Jan 30, 2024
-
-
STEVAN Antoine authored
this MR allows to give any number of blocks to recode them. this is a convenience to avoid combining the blocks pair-wise and create intermediate and useless blocks, e.g. by defining the following Nushell command with the `komodo.nu` module ```bash def "komodo full-recode" []: list<string> -> string { let blocks = $in match ($blocks | length) { 0 => { return null }, 1 => { return $blocks.0 }, } $blocks | skip 1 | reduce --fold $blocks.0 {|it, acc| komodo combine $it $acc} } ``` one can now do directly ```bash komodo combine ...(komodo ls) ``` which will create a single new fully recoded block! ## changelog - new `fec::combine` that takes a list of shards and their coefficients and combines them, returns `None` if the slices are empty or not of the same length ```rust pub(super) combine<E: Pairing>( shards: &[Shard<E>], coeffs: &[E::ScalarField], ) -> Option<Shard<E>> ``` - modified `recode` that takes any number of blocks and returns an `Option` if there is none ```rust pub recode<E: Pairing>(blocks: &[Block<E>]) -> Result<Option<Block<E>>, KomodoError> ``` - the `komodo combine` command from `komodo.nu` can now take any number of blocks, even 0 by giving a nice error -
STEVAN Antoine authored
this MR - implements the `Display` trait for `Matrix` to allow to show it - makes `from_vec_vec` and `rank` public - add `rank.rs` ## example > **Note** > - this has been run with Nushell > - a `-1` is an impossible value and thus will generate a random element instead > ```bash cargo run --example rank -- ...[ "1,0,-1" "0,0,-1" "0,1,-1" "0,0,-1" "0,0,-1" ] ``` will output ``` /1 0 314995448938783965509764369801440879676\ |0 0 236699644179594774251145667390896459418| |0 1 187004145196223910655928022134499908037| |0 0 273500202756822505549423242088598868403| \0 0 286599222098418496365691949902317095505/ m: 5 n: 3 r: 5 ``` -
STEVAN Antoine authored
this MR adds - a new `rank` implementation to `Matrix` - some tests > **Note** > the algorithm is basically the same as in the matrix inversion from `invert`, i.e. transform the matrix into _echelon_ form and then count the number of non-zero rows > **Note** > the row-rank of a matrix is the same as its column-rank, so we can safely count the number of rows
-
