- Jul 23, 2024
-
-
STEVAN Antoine authored -
STEVAN Antoine authored
-
STEVAN Antoine authored
-
- 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` >
-
- 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 >
-
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
-
- 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
-
- 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
-
STEVAN Antoine authored
in this MR, i define the following two functions in `linalg::tests` - `vec_to_elements<T: Field>(elements: Vec<u128>) -> Vec<T>` - `mat_to_elements<T: Field>(mat: Vec<Vec<u128>>) -> Vec<Vec<T>>` the idea is to help see what the matrices and vectors are at a glance, without too much processing. the end result is that all `Fr::from(<some number>)` are gone # example - a full matrix ```rust Matrix::from_vec_vec(vec![ vec![Fr::from(2), Fr::zero(), Fr::zero()], vec![Fr::zero(), Fr::from(3), Fr::zero()], vec![Fr::zero(), Fr::zero(), Fr::from(4)], vec![Fr::from(2), Fr::from(3), Fr::from(4)], ]) ``` becomes ```rust Matrix::<Fr>::from_vec_vec(mat_to_elements(vec![ vec![2, 0, 0], vec![0, 3, 0], vec![0, 0, 4], vec![2, 3, 4], ])) ``` which is hopefully easier to read and understand what the matrix is. - a diagonal one ```rust Matrix::<Fr>::from_diagonal(vec![Fr::from(2), Fr::from(3), Fr::from(4)]) ``` becomes ```rust Matrix::<Fr>::from_diagonal(vec_to_elements(vec![2, 3, 4])) ```
-
- Jan 25, 2024
-
-
STEVAN Antoine authored
-
- Jan 23, 2024
-
-
STEVAN Antoine authored
## changelog - add `--encoding-method` to `komodo prove` - pass the encoding matrix to `encode` and `fec::encode` instead of `k` and `n`, these two parameters can be extracted without further check by looking at the shape of the encoding matrix - the global recoding vector is now extracted from the encoding matrix instead of recomputing it (see new `Matrix::get_col` implementation) - `linalg` and `Matrix::{random, vandermonde}` have been made public (see new `Matrix::random` implementation) - the computation of `Matrix::vandermonde` has been optimized
-
- Jan 19, 2024
-
-
STEVAN Antoine authored
should close #2 this MR - uses the matrix representation of FEC encoding to create both `Shard`s and `Block`s - `fec::encode` will encode shards with a Vandermonde matrix - `encode` will use `fec::encode` - use of `Matrix::transpose` has been reduced in `fec::encode` thanks to swapping the encoding matrix product (thanks @j.detchart for findind this) - `fec::encode` does not require `transpose: bool` anymore as the encoding process has been homogenize throughout the code base - useless `field::build_interleaved_polynomials` have been removed - `prove` has been merged into `encode`
-
STEVAN Antoine authored
this MR combines the encoding and the recoding processes into a single one, expressed as the shard linear combination. this allows to not recompute the encoding matrix each time, whether it's explicit during decoding or implicit during shard verification.
-
STEVAN Antoine authored
now, when combining blocks that are incompatible, e.g. from different files, a proper error will be shown to the user.
-
STEVAN Antoine authored
as per title, now a block will be called `<hash>` inside `blocks/` and the trusted setup will be stored in `powers`
-
- Jan 17, 2024
-
-
STEVAN Antoine authored
## changes to the API of `komodo.nu` - there is no `--powers-file` anymore => the location of the blocks and the powers is controlled via the `$env.KOMODO_HOME` environment variable which defaults to `$env.XDG_DATA_HOME/komodo/` and then `~/.local/share/komodo/` - a new `komodo clean` command to empty the `$env.KOMODO_HOME` directory - a new `komodo` command to get some basic help - `komodo setup` now expects a number of bytes rather than a filename to build a trusted setup
-
STEVAN Antoine authored
in this MR - all `unwrap`s and `expect`s have been removed from any `.rs` module that is not `main.rs` => the goal is to never panic from inside the library and let `main.rs` handle the errors - in `main.rs` the new `throw_error` function is used to return a message on `stderr` and exit the runtime with a code => then `komodo.nu` picks it up and gives a nicer error to the user - the internals of `komodo.nu` also have been greatly simplified without feature changes > **Note** > because `throw_error` does not return anything and some of the places where there might be errors in `main.rs` need to return a value, some `unwrap_or_else` need to have an `unreachable!` statement in them to show the compiler it's ok if there's no value on the `Err` branch > > it would be nice to find a better way of doing this
-
- Jan 16, 2024
-
-
STEVAN Antoine authored
in this MR - only the hashes of blocks are shown and `komodo ...` expects hashes and not full paths to the blocks - completion has been added for the `komodo` command - a `komodo ls` command has been added to help with listing blocks > **Note** > everything happens in `blocks/` for now and it's hardcoded
-
