Skip to content
Snippets Groups Projects
  1. May 24, 2024
  2. May 23, 2024
    • STEVAN Antoine's avatar
      better check for empty input (dragoon/komodo!105) · 9f7dd2d5
      STEVAN Antoine authored
      check for empty inputs in the `run.nu` scripts
      9f7dd2d5
    • STEVAN Antoine's avatar
      dont' hardcode curves in the benchmarks (dragoon/komodo!99) · d7e84161
      STEVAN Antoine authored
      up until now, elliptic curves have been hardcoded in the benchmarks, forcing to run them on all supported curves...
      
      this MR makes it possible to use only a subset of curves.
      
      > 💡 **Note**  
      > when running the same commands from !104, minus the "inbreeding" ones which are not affected by this MR, the time goes from 12min 33sec to 4min 28sec 🎉 
      
      
      ## TODO
      - [x] setup
      - [x] commit
      - [x] recoding
      - [x] fec
      - [ ] linalg
      - [ ] setup size
      - [ ] field operations
      - [ ] group operations
      
      > 💡 **Note**  
      > because all the unticked bullet points above are far from critical to the paper and do require to measure all curves, i won't change these for now
      d7e84161
    • STEVAN Antoine's avatar
      Refactor plot commands (dragoon/komodo!104) · 0f43be24
      STEVAN Antoine authored
      this MR moves run and plot commands from `examples/benches/README.md` to
      - `scripts/setup/`: `run.nu` and `plot.nu`
      - `scripts/commit/`: `run.nu` and `plot.nu`
      - `scripts/recoding/`: `run.nu` and `plot.nu`
      - `scripts/fec/`: `run.nu` and `plot.nu`
      - `scripts/inbreeding/`: `build.nu`, `run.nu` and `plot.nu`
      
      to generate all the figures at once
      ```bash
      use scripts/setup/run.nu; seq 0 13 | each { 2 ** $in } | run --output data/setup.ndjson
      use ./scripts/setup/plot.nu; plot data/setup.ndjson --save ~/setup.pdf
      
      use scripts/commit/run.nu; seq 0 13 | each { 2 ** $in } | run --output data/commit.ndjson
      use ./scripts/commit/plot.nu; plot data/commit.ndjson --save ~/commit.pdf
      
      use scripts/recoding/run.nu; seq 0 18 | each { 512 * 2 ** $in } | run --ks [2, 4, 8, 16] --output data/recoding.ndjson
      use ./scripts/recoding/plot.nu; plot data/recoding.ndjson --save ~/recoding.pdf
      
      use scripts/fec/run.nu; seq 0 18 | each { 512 * 2 ** $in } | run --ks [2, 4, 8, 16] --output data/fec.ndjson
      use ./scripts/fec/plot.nu; plot encoding data/fec.ndjson --save ~/encoding.pdf
      use ./scripts/fec/plot.nu; plot decoding data/fec.ndjson --save ~/decoding.pdf
      use ./scripts/fec/plot.nu; plot e2e data/fec.ndjson --save ~/e2e.pdf
      
      use ./scripts/fec/plot.nu; plot combined data/fec.ndjson --recoding data/recoding.ndjson --save ~/comparison.pdf
      use ./scripts/fec/plot.nu; plot ratio data/fec.ndjson --recoding data/recoding.ndjson --save ~/ratio.pdf
      
      ./scripts/inbreeding/build.nu
      ./scripts/inbreeding/run.nu --output data/inbreeding.nuon
      ./scripts/inbreeding/plot.nu data/inbreeding.nuon --save ~/inbreeding.pdf
      ```
      
      > 💡 **Note**  
      > this took around 27min 18sec in total on my machine with 14min 45sec for the inbreeding section only and 12min 33sec for the rest
      0f43be24
    • STEVAN Antoine's avatar
      define more complex inbreeding strategies (dragoon/komodo!103) · 61a2320e
      STEVAN Antoine authored
      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
      61a2320e
  3. May 21, 2024
  4. May 13, 2024
    • STEVAN Antoine's avatar
      make figures better (dragoon/komodo!98) · b4e53ac6
      STEVAN Antoine authored
      this MR makes the plot a bit nicer.
      
      ## new figures
      ![setup](/uploads/e6a7ac4e7460d8ff7015906216f9d30b/setup.png)
      ![commit](/uploads/a40700913594771cefeba45a44b2370b/commit.png)
      ![recoding](/uploads/1f3e86763c897dcf034e4b01ba858ada/recoding.png)
      ![decoding](/uploads/dd703ba4af59b4043ae5bb966f8b55ae/decoding.png)
      ![encoding](/uploads/6dbc077bbfe8086357074a0e18c8b530/encoding.png)
      ![e2e](/uploads/9eb92dbb8dc013ef803bde70f3e04f02/e2e.png)
      ![inbreeding](/uploads/9f7dac6a48c24e97448e92a69a506d2f/inbreeding.png)
      b4e53ac6
  5. May 02, 2024
    • STEVAN Antoine's avatar
      add an example to study the _recoding inbreeding_ phenomenon (dragoon/komodo!97) · 7d5fca82
      STEVAN Antoine authored
      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)
      7d5fca82
  6. Apr 29, 2024
  7. Apr 26, 2024
    • STEVAN Antoine's avatar
      add a "fec" bench (dragoon/komodo!93) · 392f640a
      STEVAN Antoine authored
      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)
      392f640a
    • STEVAN Antoine's avatar
      add some minor fixes around the benches (dragoon/komodo!92) · 89c6377d
      STEVAN Antoine authored
      - fix the path to the "bench" readme and remove it from the plot scripts
      - "BLS-12-381" to "BLS12-381" for consistency
      89c6377d
    • STEVAN Antoine's avatar
      use better names in `plot.py` (dragoon/komodo!91) · 2e6398e8
      STEVAN Antoine authored
      this MR goes from
      ```rust
      let xs = seq 0 5 | each { 2 ** $in } | wrap x
      let twice = $xs | insert measurement { 2 * $in.x } | insert error { 0.1 + 0.5 * $in.x }
      let square = $xs | insert measurement { $in.x ** 2 } | insert error { 1 + 1.5 * $in.x }
      
      python scripts/plot/plot.py --title title --x-label x --y-label y --fullscreen ([
          { group: "x ^ 2", items: $square },
          { group: "2 * x", items: $twice }
      ] | to json)
      ```
      to
      ```rust
      let xs = seq 0 5 | each { 2 ** $in }
      let twice = $xs | wrap x | insert y { 2 * $in.x } | insert e { 0.1 + 0.5 * $in.x }
      let square = $xs | wrap x | insert y { $in.x ** 2 } | insert e { 1 + 1.5 * $in.x }
      
      python scripts/plot/plot.py --title title --x-label x --y-label y --fullscreen ([
          { name: "x ^ 2", points: $square },
          { name: "2 * x", points: $twice }
      ] | to json)
      ```
      updates the "bench" README and adds type annotations to the `plot.py` script.
      2e6398e8
    • STEVAN Antoine's avatar
      migrate recoding benchmark to PLNK (dragoon/komodo!89) · 22f7943d
      STEVAN Antoine authored
      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)
      22f7943d
    • STEVAN Antoine's avatar
      add support for _custom style_ in `plot.py` (dragoon/komodo!90) · b3449155
      STEVAN Antoine authored
      > 💡 **Note**  
      > - in the following examples, any part of the `$.style` specification is optional and can either be ommitted or set to `null`
      > - the default values for `$.style` are given in `plot.py --help`
      
      ```rust
      let xs = seq 0 5 | each { 2 ** $in } | wrap x
      let twice = $xs | insert measurement { 2 * $in.x } | insert error { 0.1 + 0.5 * $in.x }
      let square = $xs | insert measurement { $in.x ** 2 } | insert error { 1 + 1.5 * $in.x }
      ```
      and try
      ```rust
      python scripts/plot/plot.py --title title --x-label x --y-label y --fullscreen ([
          { group: "x ^ 2", items: $square },
          { group: "2 * x", items: $twice }
      ] | to json)
      ```
      vs
      ```rust
      python scripts/plot/plot.py --title title --x-label x --y-label y --fullscreen ([
          {
              group: "x ^ 2",
              items: $square,
              style: {
                  color: "red",
                  alpha: 0.5,
                  line: {
                      marker: 's',
                      width: 2,
                      type: "dashed",
                  },
              }
          },
          {
              group: "2 * x",
              items: $twice,
              style: {
                  color: "purple",
                  alpha: 0.1,
                  line: {
                      marker: 'o',
                      width: 5,
                      type: "dotted",
                  },
              }
          }
      ] | to json)
      ```
      b3449155
  8. Apr 25, 2024
    • STEVAN Antoine's avatar
      make plot scripts more powerful and minor tweaks (dragoon/komodo!88) · 72f3cd8a
      STEVAN Antoine authored
      ## changelog
      - use `out> *.ndjson` in the README to simplify running the benchmarks
      - create a `scripts/math.nu` module with `ns-to-ms` and `compute-stats` to refactor some of the most common operations
      - add `--fullscreen` to `plot.py` and `multi_bar.py`
      - add `--x-scale` and `--y-scale` to `plot.py`
      72f3cd8a
    • STEVAN Antoine's avatar
      migrate criterion benchmarks to PLNK (dragoon/komodo!87) · eaa8acbd
      STEVAN Antoine authored
      ## 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
      eaa8acbd
    • STEVAN Antoine's avatar
      bump PLNK to 0.6.0 (dragoon/komodo!85) · 4b193d97
      STEVAN Antoine authored
      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_
      4b193d97
  9. Apr 24, 2024
  10. Apr 23, 2024
  11. Apr 22, 2024
    • STEVAN Antoine's avatar
      improve the _atomic_ benchmark plots (!79) · ed16b5d8
      STEVAN Antoine authored
      this MR improves the "_atomic_" script in `benches/README.md` to allow filtering _species_ to show in the _multibar_ plot.
      
      in addition to this, the warmup time and the number of samples of Criterion have been increased back to 3sec and 100 respectively.
      
      > **Note**  
      > the benchmarks take 15min on my machine, i.e. by running the following two commands in Nushell
      > ```bash
      > cargo criterion --output-format verbose --message-format json --bench field_operations out> field.ndjson
      > cargo criterion --output-format verbose --message-format json --bench curve_group_operations out> curve.ndjson
      > ```
      
      ## results
      ![foo](/uploads/5cdc5af344f4ad0510b3d1993c09389f/foo.png)
      ![bar](/uploads/2563b465727d85b886f77c5574ae616d/bar.png)
      ![baz](/uploads/7a485c61d218c8e065afdd880171a12b/baz.png)
      ed16b5d8
    • STEVAN Antoine's avatar
      measure atomic operations of curve groups and prime fields (dragoon/komodo!78) · 4dcfdfb0
      STEVAN Antoine authored
      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)
      4dcfdfb0
    • STEVAN Antoine's avatar
      measure Arkworks commit in the benchmark (!77) · 7c6f46dc
      STEVAN Antoine authored
      this MR
      - adds an Arkworks bench oneshot function to the `bench_commit` example
      - adapts the `measure!` macro to pass a _pairing-friendly_ curve
      - give different linestyle to curves in the Python script
      
      ## example measurements
      ![Figure_1](/uploads/4b7f52eb3a8c894317cc34057652020f/Figure_1.png)
      7c6f46dc
  12. Apr 15, 2024
    • STEVAN Antoine's avatar
      add "unchecked" versions of `Matrix::{vandermonde,from_vec_vec}` and test both... · 5dc7dd2c
      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
      5dc7dd2c
  13. Apr 12, 2024
    • STEVAN Antoine's avatar
      improve benchmarks documentation (!74) · 750fdbf6
      STEVAN Antoine authored
      750fdbf6
    • STEVAN Antoine's avatar
      update the API (!71) · 6f6647cd
      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
  14. Apr 11, 2024
  15. Apr 10, 2024
  16. Apr 09, 2024
  17. Apr 08, 2024
    • STEVAN Antoine's avatar
      fix random (dragoon/komodo!65) · fc23965a
      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`
      fc23965a
    • STEVAN Antoine's avatar
      improve the benchmark plots (dragoon/komodo!64) · 6015d688
      STEVAN Antoine authored
      ## changelog
      - add `(komodo)` to the benchmark names for commit and setup for easier parsing
      - add `--bench commit` to plot the commit times
      - make the `plot.py` more robust
        - use `ns_to_ms` and `b_to_kb` to convert times and filesizes
        - remove the prefix from bench IDs and always take the first space-separated token as the input data size
      - remove the "bounds" from the labels
      - remove the "mean" from the labels when there's only the mean to show
      - plot the figures in fullscreen
      - add `--save` to save the figures directly to disk with a little message
      - add `--all` to plot / save all the figures at once
      
      ## examples
      ![commit](/uploads/7d5c30dd6387064246e3d83559c9208b/commit.png)
      ![linalg](/uploads/9eaca508c9f16edc667cdaa0e0afdd95/linalg.png)
      ![setup](/uploads/4096cde0be8b33b0ceb60d17dad94e4d/setup.png)
      6015d688
    • STEVAN Antoine's avatar
      benchmark commit step and ark counterparts (dragoon/komodo!63) · 0ed49a36
      STEVAN Antoine authored
      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.
      0ed49a36
    • STEVAN Antoine's avatar
      update the documentation (dragoon/komodo!62) · a229ef38
      STEVAN Antoine authored
      there was some missing parts from recent commits and also a dead link to `setup::setup` which is now `zk::setup`.
      a229ef38
Loading