ZenGo-X / class

Rust library for building IQC: cryptography based on class groups of imaginary quadratic orders
GNU General Public License v3.0
63 stars 31 forks source link

test(VDF): add bench tests for VDF in rsa group #42

Open 0xmountaintop opened 4 years ago

0xmountaintop commented 4 years ago

This PR adds an exmaple of benchmarking VDF in rsa_group (using RSA-2048 modulus).

environment

how to test it

cargo bench --bench bench-vdf-rsa  --jobs 1

test result

Benchmarking eval with difficulty 1000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 38.2s, or reduce sample count to 10.
eval with difficulty 1000                                                                            
                        time:   [378.84 ms 379.39 ms 380.08 ms]
                        change: [-0.9753% -0.6037% -0.2520%] (p = 0.00 < 0.05)
                        Change within noise threshold.
Found 7 outliers among 100 measurements (7.00%)
  2 (2.00%) high mild
  5 (5.00%) high severe

Benchmarking verify with difficulty 1000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 55.9s, or reduce sample count to 10.
verify with difficulty 1000                                                                            
                        time:   [545.13 ms 545.60 ms 546.16 ms]
                        change: [-7.4577% -6.4547% -5.4789%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
  2 (2.00%) high mild
  5 (5.00%) high severe

Benchmarking eval with difficulty 2000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 5.2s, or reduce sample count to 90.
eval with difficulty 2000                                                                            
                        time:   [51.903 ms 51.967 ms 52.035 ms]
Found 3 outliers among 100 measurements (3.00%)
  2 (2.00%) high mild
  1 (1.00%) high severe

Benchmarking verify with difficulty 2000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 15.0s, or reduce sample count to 30.
verify with difficulty 2000                                                                            
                        time:   [141.99 ms 142.08 ms 142.18 ms]
Found 10 outliers among 100 measurements (10.00%)
  10 (10.00%) high mild

Benchmarking eval with difficulty 5000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 13.2s, or reduce sample count to 30.
eval with difficulty 5000                                                                            
                        time:   [125.14 ms 125.30 ms 125.48 ms]
Found 21 outliers among 100 measurements (21.00%)
  11 (11.00%) high mild
  10 (10.00%) high severe

Benchmarking verify with difficulty 5000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 52.3s, or reduce sample count to 10.
verify with difficulty 5000                                                                            
                        time:   [487.24 ms 487.65 ms 488.12 ms]
Found 9 outliers among 100 measurements (9.00%)
  2 (2.00%) high mild
  7 (7.00%) high severe

Benchmarking eval with difficulty 10000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 25.5s, or reduce sample count to 10.
eval with difficulty 10000                                                                            
                        time:   [252.55 ms 252.86 ms 253.21 ms]
Found 15 outliers among 100 measurements (15.00%)
  6 (6.00%) high mild
  9 (9.00%) high severe

Benchmarking verify with difficulty 10000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 31.9s, or reduce sample count to 10.
verify with difficulty 10000                                                                            
                        time:   [308.68 ms 309.44 ms 310.36 ms]
Found 20 outliers among 100 measurements (20.00%)
  16 (16.00%) high mild
  4 (4.00%) high severe

Benchmarking eval with difficulty 100000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 83.7s, or reduce sample count to 10.
eval with difficulty 100000                                                                            
                        time:   [842.41 ms 847.44 ms 853.19 ms]
Found 12 outliers among 100 measurements (12.00%)
  4 (4.00%) high mild
  8 (8.00%) high severe

Benchmarking verify with difficulty 100000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 96.0s, or reduce sample count to 10.
verify with difficulty 100000                                                                            
                        time:   [948.37 ms 953.38 ms 959.61 ms]
Found 7 outliers among 100 measurements (7.00%)
  3 (3.00%) high mild
  4 (4.00%) high severe

Benchmarking eval with difficulty 1000000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 694.4s, or reduce sample count to 10.
eval with difficulty 1000000                                                                            
                        time:   [6.9406 s 6.9448 s 6.9492 s]
Found 7 outliers among 100 measurements (7.00%)
  7 (7.00%) high mild

Benchmarking verify with difficulty 1000000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 16.1s, or reduce sample count to 30.
verify with difficulty 1000000                                                                            
                        time:   [158.90 ms 159.14 ms 159.43 ms]
Found 8 outliers among 100 measurements (8.00%)
  5 (5.00%) high mild
  3 (3.00%) high severe
omershlo commented 3 years ago

is this PR ready to be merged?

0xmountaintop commented 3 years ago

is this PR ready to be merged?

@omershlo Yes I think so!

Would you mind taking a look again?

0xmountaintop commented 3 years ago

BTW, h_g_inner now converts between bytes and Integer just for better demostrating the logic. This is indeed tedious and unnecessay. We can actually run hashing and concat only using bytes, and convert it to Integer at the end.

I will refactor it in this way once we decide which hash_and_concat way (we mentioned 3 ways above) we want to use.

omershlo commented 3 years ago

let me know when ready to merge

0xmountaintop commented 3 years ago

updated bechmark results:

$ cargo fmt && cargo bench --bench bench-vdf-rsa  --jobs 1
    Finished bench [optimized] target(s) in 0.07s
     Running target/release/deps/bench_vdf_rsa-6a178b6bb8445182
Gnuplot not found, using plotters backend
eval with difficulty 1000                                                                            
                        time:   [7.5328 ms 7.5852 ms 7.6428 ms]
                        change: [+2.8713% +3.8219% +4.7723%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 4 outliers among 100 measurements (4.00%)
  2 (2.00%) high mild
  2 (2.00%) high severe

verify with difficulty 1000                                                                            
                        time:   [944.50 us 948.74 us 953.69 us]
                        change: [-14.040% -10.687% -7.5197%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
  2 (2.00%) high mild
  3 (3.00%) high severe

eval with difficulty 2000                                                                            
                        time:   [13.640 ms 13.719 ms 13.801 ms]
                        change: [-14.981% -11.285% -7.6220%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
  4 (4.00%) high mild

Benchmarking verify with difficulty 2000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 7.0s, enable flat sampling, or reduce sample count to 50.
verify with difficulty 2000                                                                             
                        time:   [1.3749 ms 1.3810 ms 1.3894 ms]
                        change: [+12.347% +13.774% +15.231%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 10 outliers among 100 measurements (10.00%)
  5 (5.00%) high mild
  5 (5.00%) high severe

eval with difficulty 5000                                                                            
                        time:   [34.430 ms 34.672 ms 34.962 ms]
                        change: [-3.8130% -2.1946% -0.5532%] (p = 0.01 < 0.05)
                        Change within noise threshold.
Found 9 outliers among 100 measurements (9.00%)
  5 (5.00%) high mild
  4 (4.00%) high severe

Benchmarking verify with difficulty 5000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 6.6s, enable flat sampling, or reduce sample count to 60.
verify with difficulty 5000                                                                             
                        time:   [1.3095 ms 1.3201 ms 1.3346 ms]
                        change: [+20.283% +21.947% +23.644%] (p = 0.00 < 0.05)
                        Performance has regressed.
Found 8 outliers among 100 measurements (8.00%)
  6 (6.00%) high mild
  2 (2.00%) high severe

Benchmarking eval with difficulty 10000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 6.9s, or reduce sample count to 70.
eval with difficulty 10000                                                                            
                        time:   [65.710 ms 65.900 ms 66.130 ms]
                        change: [-4.7590% -3.6740% -2.6779%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
  4 (4.00%) high mild
  8 (8.00%) high severe

Benchmarking verify with difficulty 10000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 5.1s, enable flat sampling, or reduce sample count to 70.
verify with difficulty 10000                                                                             
                        time:   [1.0345 ms 1.0411 ms 1.0493 ms]
                        change: [-99.746% -99.742% -99.739%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
  5 (5.00%) high mild
  1 (1.00%) high severe

Benchmarking eval with difficulty 100000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 69.8s, or reduce sample count to 10.
eval with difficulty 100000                                                                            
                        time:   [670.80 ms 674.53 ms 678.68 ms]
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) high mild
  1 (1.00%) high severe

Benchmarking verify with difficulty 100000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 6.3s, enable flat sampling, or reduce sample count to 60.
verify with difficulty 100000                                                                             
                        time:   [1.2220 ms 1.2251 ms 1.2302 ms]
Found 21 outliers among 100 measurements (21.00%)
  2 (2.00%) high mild
  19 (19.00%) high severe

Benchmarking eval with difficulty 1000000: Warming up for 3.0000 s
Warning: Unable to complete 100 samples in 5.0s. You may wish to increase target time to 685.1s, or reduce sample count to 10.
eval with difficulty 1000000                                                                            
                        time:   [6.6123 s 6.6311 s 6.6512 s]
Found 22 outliers among 100 measurements (22.00%)
  17 (17.00%) high mild
  5 (5.00%) high severe

verify with difficulty 1000000                                                                            
                        time:   [913.82 us 919.67 us 925.02 us]
Found 11 outliers among 100 measurements (11.00%)
  3 (3.00%) high mild
  8 (8.00%) high severe