search

crate-crypto / go-ipa

A Go implementation of cryptographic primitives for Verkle Trees
https://verkle.dev
Apache License 2.0
32 stars 14 forks source link

mod: update gnark-crypto #58

Closed jsign closed 1 year ago

jsign commented 1 year ago

This PR updates gnark-crypto to the current master commit. I'd like to wait until an official release, but I want to include a PR that I did that fixed a significant performance regression, see https://github.com/Consensys/gnark-crypto/pull/441.

As soon as gnark-crypto cuts an official release, we can update it again.

Here's the change in performance in this repo:

name                                  old time/op    new time/op    delta
pkg:github.com/crate-crypto/go-ipa/bandersnatch goos:linux goarch:amd64
MultiExpG1/32_points-16                  481µs ± 8%     376µs ±14%   -21.80%  (p=0.000 n=10+10)
MultiExpG1/64_points-16                  512µs ± 3%     386µs ± 3%   -24.61%  (p=0.000 n=10+10)
MultiExpG1/128_points-16                 626µs ± 6%     493µs ± 2%   -21.32%  (p=0.000 n=10+10)
MultiExpG1/256_points-16                 826µs ± 3%     739µs ±16%   -10.51%  (p=0.019 n=10+10)
MultiExpG1/512_points-16                1.48ms ± 7%    1.06ms ± 3%   -28.20%  (p=0.000 n=10+10)
MultiExpG1/1024_points-16               2.64ms ± 4%    1.94ms ± 2%   -26.50%  (p=0.000 n=10+8)
MultiExpG1/2048_points-16               3.43ms ± 4%    2.38ms ± 7%   -30.63%  (p=0.000 n=9+10)
MultiExpG1/4096_points-16               6.42ms ± 5%    4.20ms ± 4%   -34.55%  (p=0.000 n=10+10)
MultiExpG1/8192_points-16               11.9ms ± 4%     8.1ms ± 2%   -32.46%  (p=0.000 n=10+9)
MultiExpG1/16384_points-16              22.4ms ± 1%    15.9ms ± 3%   -29.16%  (p=0.000 n=10+10)
MultiExpG1/32768_points-16              42.3ms ± 2%    30.3ms ± 2%   -28.42%  (p=0.000 n=10+10)
MultiExpG1/65536_points-16              73.1ms ± 3%    53.1ms ± 3%   -27.39%  (p=0.000 n=9+10)
MultiExpG1/131072_points-16              126ms ± 2%      91ms ± 4%   -27.94%  (p=0.000 n=10+10)
MultiExpG1/262144_points-16              230ms ± 1%     166ms ±12%   -28.15%  (p=0.000 n=7+10)
MultiExpG1/524288_points-16              456ms ± 5%     332ms ± 7%   -27.21%  (p=0.000 n=10+10)
MultiExpG1/1048576_points-16             876ms ± 5%     606ms ± 8%   -30.82%  (p=0.000 n=10+10)
MultiExpG1/2097152_points-16             1.74s ± 3%     1.16s ± 4%   -33.59%  (p=0.000 n=10+9)
MultiExpG1/4194304_points-16             3.39s ± 2%     2.32s ± 1%   -31.40%  (p=0.000 n=10+10)
MultiExpG1/8388608_points-16             6.93s ± 4%     4.65s ± 1%   -32.80%  (p=0.000 n=10+10)
MultiExpG1/16777216_points-16            12.8s ± 2%      8.7s ± 0%   -32.30%  (p=0.000 n=9+9)
MultiExpG1Reference-16                   907ms ± 4%     589ms ± 2%   -35.12%  (p=0.000 n=10+9)
ManyMultiExpG1Reference-16               2.69s ± 2%     1.76s ± 1%   -34.56%  (p=0.000 n=9+9)
pkg:github.com/crate-crypto/go-ipa/bandersnatch/fr goos:linux goarch:amd64
ElementSetBytes-16                      50.5ns ± 2%    49.7ns ± 2%    -1.56%  (p=0.007 n=10+10)
ElementMulByConstants/mulBy3-16         5.15ns ± 3%    5.12ns ± 1%      ~     (p=0.280 n=10+10)
ElementMulByConstants/mulBy5-16         6.66ns ± 2%    6.66ns ± 1%      ~     (p=0.896 n=10+10)
ElementMulByConstants/mulBy13-16        10.0ns ± 2%     9.9ns ± 1%      ~     (p=0.155 n=10+9)
ElementInverse-16                       1.72µs ± 3%    1.67µs ± 5%    -2.45%  (p=0.038 n=10+10)
ElementButterfly-16                     4.64ns ± 2%    4.62ns ± 1%      ~     (p=0.807 n=10+8)
ElementExp-16                           6.41µs ± 6%    6.42µs ± 4%      ~     (p=0.853 n=10+10)
ElementDouble-16                        3.35ns ± 1%    3.31ns ± 1%    -1.01%  (p=0.001 n=8+8)
ElementAdd-16                           3.48ns ± 1%    3.40ns ± 2%    -2.17%  (p=0.000 n=9+10)
ElementSub-16                           3.46ns ± 2%    3.42ns ± 0%    -1.22%  (p=0.005 n=10+7)
ElementNeg-16                           2.35ns ± 4%    2.30ns ± 2%    -1.76%  (p=0.020 n=9+9)
ElementDiv-16                           1.73µs ± 4%    1.71µs ± 4%      ~     (p=0.280 n=10+10)
ElementFromMont-16                      11.4ns ± 1%    11.4ns ± 2%      ~     (p=0.499 n=8+10)
ElementToMont-16                        16.0ns ± 3%    15.5ns ± 2%    -3.05%  (p=0.000 n=10+9)
ElementSquare-16                        16.0ns ± 4%    15.5ns ± 2%    -2.83%  (p=0.000 n=10+10)
ElementSqrt-16                          6.37µs ± 2%    6.40µs ± 2%      ~     (p=0.796 n=10+10)
ElementMul-16                           16.8ns ± 1%    16.7ns ± 1%    -0.82%  (p=0.015 n=9+8)
ElementCmp-16                           24.1ns ± 0%    23.8ns ± 2%    -1.31%  (p=0.003 n=8+10)
pkg:github.com/crate-crypto/go-ipa/banderwagon goos:linux goarch:amd64
PrecompMSM/msm_length=1/precomp-16      5.52µs ± 2%    3.42µs ± 0%   -38.08%  (p=0.000 n=10+8)
PrecompMSM/msm_length=2/precomp-16      11.0µs ± 3%     6.7µs ± 0%   -39.28%  (p=0.000 n=10+8)
PrecompMSM/msm_length=4/precomp-16      22.2µs ± 5%    13.2µs ± 3%   -40.72%  (p=0.000 n=10+10)
PrecompMSM/msm_length=8/precomp-16      59.1µs ± 2%    35.5µs ± 3%   -39.97%  (p=0.000 n=9+10)
PrecompMSM/msm_length=16/precomp-16      149µs ± 3%      91µs ± 2%   -38.89%  (p=0.000 n=10+10)
PrecompMSM/msm_length=32/precomp-16      332µs ± 2%     209µs ± 1%   -37.05%  (p=0.000 n=10+9)
PrecompMSM/msm_length=64/precomp-16      712µs ± 1%     455µs ± 2%   -36.12%  (p=0.000 n=9+10)
PrecompMSM/msm_length=128/precomp-16    1.50ms ± 4%    0.97ms ± 2%   -35.38%  (p=0.000 n=10+10)
PrecompMSM/msm_length=256/precomp-16    2.94ms ± 2%    1.99ms ± 1%   -32.50%  (p=0.000 n=10+9)
PrecompInitialize-16                     1.34s ± 5%     1.24s ± 1%    -7.13%  (p=0.000 n=10+10)

name                                  old alloc/op   new alloc/op   delta
pkg:github.com/crate-crypto/go-ipa/bandersnatch goos:linux goarch:amd64
MultiExpG1/32_points-16                  400kB ± 0%      18kB ± 0%   -95.60%  (p=0.000 n=8+9)
MultiExpG1/64_points-16                  640kB ± 0%      21kB ± 0%   -96.78%  (p=0.000 n=10+10)
MultiExpG1/128_points-16                1.05MB ± 0%    0.02MB ± 0%   -97.84%  (p=0.000 n=10+10)
MultiExpG1/256_points-16                1.75MB ± 0%    0.02MB ± 0%   -98.64%  (p=0.000 n=10+10)
MultiExpG1/512_points-16                3.01MB ± 0%    0.03MB ± 0%   -99.01%  (p=0.000 n=10+10)
MultiExpG1/1024_points-16               5.27MB ± 0%    0.04MB ± 0%   -99.16%  (p=0.002 n=8+10)
MultiExpG1/2048_points-16               9.43MB ± 0%    0.08MB ± 0%   -99.19%  (p=0.000 n=9+10)
MultiExpG1/4096_points-16               17.0MB ± 0%     0.1MB ± 0%   -99.17%  (p=0.000 n=10+10)
MultiExpG1/8192_points-16               30.7MB ± 0%     0.3MB ± 0%   -99.11%  (p=0.000 n=10+10)
MultiExpG1/16384_points-16              55.7MB ± 0%     0.5MB ± 0%   -99.04%  (p=0.000 n=10+10)
MultiExpG1/32768_points-16               103MB ± 0%       1MB ± 0%   -98.98%  (p=0.000 n=10+10)
MultiExpG1/65536_points-16               190MB ± 0%       2MB ± 0%   -98.89%  (p=0.000 n=10+10)
MultiExpG1/131072_points-16              356MB ± 0%       4MB ± 0%   -98.82%  (p=0.000 n=10+10)
MultiExpG1/262144_points-16              650MB ± 0%       8MB ± 0%   -98.71%  (p=0.000 n=10+10)
MultiExpG1/524288_points-16             1.22GB ± 0%    0.02GB ± 0%   -98.63%  (p=0.000 n=9+10)
MultiExpG1/1048576_points-16            2.32GB ± 0%    0.03GB ± 0%   -98.55%  (p=0.000 n=10+8)
MultiExpG1/2097152_points-16            4.50GB ± 0%    0.07GB ± 0%   -98.51%  (p=0.000 n=9+10)
MultiExpG1/4194304_points-16            8.99GB ± 0%    0.13GB ± 0%   -98.51%  (p=0.000 n=10+10)
MultiExpG1/8388608_points-16            18.7GB ± 0%     1.5GB ± 0%   -92.09%  (p=0.000 n=10+6)
MultiExpG1/16777216_points-16           32.9GB ± 0%     1.7GB ± 0%   -94.70%  (p=0.000 n=10+10)
MultiExpG1Reference-16                  2.32GB ± 0%    0.03GB ± 0%   -98.55%  (p=0.000 n=10+9)
ManyMultiExpG1Reference-16              6.95GB ± 0%    0.10GB ± 0%   -98.55%  (p=0.000 n=10+10)
pkg:github.com/crate-crypto/go-ipa/bandersnatch/fr goos:linux goarch:amd64
ElementSetBytes-16                       0.00B          0.00B           ~     (all equal)
ElementMulByConstants/mulBy3-16          0.00B          0.00B           ~     (all equal)
ElementMulByConstants/mulBy5-16          0.00B          0.00B           ~     (all equal)
ElementMulByConstants/mulBy13-16         0.00B          0.00B           ~     (all equal)
ElementInverse-16                        0.00B          0.00B           ~     (all equal)
ElementButterfly-16                      0.00B          0.00B           ~     (all equal)
ElementExp-16                            0.00B          0.00B           ~     (all equal)
ElementDouble-16                         0.00B          0.00B           ~     (all equal)
ElementAdd-16                            0.00B          0.00B           ~     (all equal)
ElementSub-16                            0.00B          0.00B           ~     (all equal)
ElementNeg-16                            0.00B          0.00B           ~     (all equal)
ElementDiv-16                            0.00B          0.00B           ~     (all equal)
ElementFromMont-16                       0.00B          0.00B           ~     (all equal)
ElementToMont-16                         0.00B          0.00B           ~     (all equal)
ElementSquare-16                         0.00B          0.00B           ~     (all equal)
ElementSqrt-16                           0.00B          0.00B           ~     (all equal)
ElementMul-16                            0.00B          0.00B           ~     (all equal)
ElementCmp-16                            0.00B          0.00B           ~     (all equal)
pkg:github.com/crate-crypto/go-ipa/banderwagon goos:linux goarch:amd64
PrecompMSM/msm_length=1/precomp-16      2.05kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=2/precomp-16      4.10kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=4/precomp-16      8.19kB ± 0%    0.00kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=8/precomp-16      22.5kB ± 0%     0.0kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=16/precomp-16     54.9kB ± 0%     0.0kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=32/precomp-16      120kB ± 0%       0kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=64/precomp-16      250kB ± 0%       0kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=128/precomp-16     512kB ± 0%       0kB       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=256/precomp-16    1.03MB ± 0%    0.00MB       -100.00%  (p=0.000 n=10+10)
PrecompInitialize-16                    1.31GB ± 0%    0.83GB ± 0%   -36.55%  (p=0.000 n=8+9)

name                                  old allocs/op  new allocs/op  delta
pkg:github.com/crate-crypto/go-ipa/bandersnatch goos:linux goarch:amd64
MultiExpG1/32_points-16                  6.07k ± 0%     0.09k ± 0%   -98.53%  (p=0.000 n=10+10)
MultiExpG1/64_points-16                  9.81k ± 0%     0.13k ± 0%   -98.67%  (p=0.000 n=10+10)
MultiExpG1/128_points-16                 16.1k ± 0%      0.1k ± 0%   -99.19%  (p=0.000 n=10+10)
MultiExpG1/256_points-16                 27.1k ± 0%      0.1k ± 0%   -99.59%  (p=0.000 n=10+10)
MultiExpG1/512_points-16                 46.7k ± 0%      0.1k ± 0%   -99.79%  (p=0.000 n=10+10)
MultiExpG1/1024_points-16                81.8k ± 0%      0.1k ± 0%   -99.89%  (p=0.000 n=10+10)
MultiExpG1/2048_points-16                 146k ± 0%        0k ± 0%   -99.94%  (p=0.000 n=10+10)
MultiExpG1/4096_points-16                 264k ± 0%        0k ± 0%   -99.97%  (p=0.000 n=10+10)
MultiExpG1/8192_points-16                 476k ± 0%        0k ± 0%   -99.98%  (p=0.000 n=10+10)
MultiExpG1/16384_points-16                862k ± 0%        0k ± 0%   -99.99%  (p=0.000 n=10+10)
MultiExpG1/32768_points-16               1.60M ± 0%     0.00M ± 0%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/65536_points-16               2.93M ± 0%     0.00M ± 0%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/131072_points-16              5.50M ± 0%     0.00M ± 0%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/262144_points-16              10.0M ± 0%      0.0M ± 0%  -100.00%  (p=0.000 n=9+10)
MultiExpG1/524288_points-16              18.9M ± 0%      0.0M ± 0%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/1048576_points-16             35.7M ± 0%      0.0M ± 0%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/2097152_points-16             69.2M ± 0%      0.0M ± 1%  -100.00%  (p=0.000 n=9+10)
MultiExpG1/4194304_points-16              138M ± 0%        0M ± 1%  -100.00%  (p=0.000 n=10+10)
MultiExpG1/8388608_points-16              269M ± 0%        0M ± 0%  -100.00%  (p=0.000 n=10+6)
MultiExpG1/16777216_points-16             487M ± 0%        0M ± 1%  -100.00%  (p=0.000 n=10+9)
MultiExpG1Reference-16                   35.7M ± 0%      0.0M ± 0%  -100.00%  (p=0.000 n=10+10)
ManyMultiExpG1Reference-16                107M ± 0%        0M ± 1%  -100.00%  (p=0.000 n=10+10)
pkg:github.com/crate-crypto/go-ipa/bandersnatch/fr goos:linux goarch:amd64
ElementSetBytes-16                        0.00           0.00           ~     (all equal)
ElementMulByConstants/mulBy3-16           0.00           0.00           ~     (all equal)
ElementMulByConstants/mulBy5-16           0.00           0.00           ~     (all equal)
ElementMulByConstants/mulBy13-16          0.00           0.00           ~     (all equal)
ElementInverse-16                         0.00           0.00           ~     (all equal)
ElementButterfly-16                       0.00           0.00           ~     (all equal)
ElementExp-16                             0.00           0.00           ~     (all equal)
ElementDouble-16                          0.00           0.00           ~     (all equal)
ElementAdd-16                             0.00           0.00           ~     (all equal)
ElementSub-16                             0.00           0.00           ~     (all equal)
ElementNeg-16                             0.00           0.00           ~     (all equal)
ElementDiv-16                             0.00           0.00           ~     (all equal)
ElementFromMont-16                        0.00           0.00           ~     (all equal)
ElementToMont-16                          0.00           0.00           ~     (all equal)
ElementSquare-16                          0.00           0.00           ~     (all equal)
ElementSqrt-16                            0.00           0.00           ~     (all equal)
ElementMul-16                             0.00           0.00           ~     (all equal)
ElementCmp-16                             0.00           0.00           ~     (all equal)
pkg:github.com/crate-crypto/go-ipa/banderwagon goos:linux goarch:amd64
PrecompMSM/msm_length=1/precomp-16        32.0 ± 0%       0.0       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=2/precomp-16        64.0 ± 0%       0.0       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=4/precomp-16         128 ± 0%         0       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=8/precomp-16         352 ± 0%         0       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=16/precomp-16        858 ± 0%         0       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=32/precomp-16      1.88k ± 0%     0.00k       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=64/precomp-16      3.91k ± 0%     0.00k       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=128/precomp-16     8.00k ± 0%     0.00k       -100.00%  (p=0.000 n=10+10)
PrecompMSM/msm_length=256/precomp-16     16.1k ± 0%      0.0k       -100.00%  (p=0.000 n=10+10)
PrecompInitialize-16                     7.73M ± 0%     0.24M ± 0%   -96.94%  (p=0.000 n=10+9)

It looks quite impressive, but technically I'm just trying to return the performance we already had before this regression appeared.