evmone icon indicating copy to clipboard operation
evmone copied to clipboard

Optimize `ecmul` and `ecrecovery` implementation with field endomorphism

Open rodiazet opened this issue 2 years ago • 1 comments

  • ecmul in ecc lib for bn254 is optimized using curve endomorphism and "Shamir's trick" multiplication.
  • https://www.iacr.org/archive/crypto2001/21390189.pdf
  • v1 and v2 vectors taken from cloudflare implementation

Prev version bench:

--------------------------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------------------------------------
identity<evmone::state::identity_execute>                 56.9 ns         56.9 ns     11887577 gas_rate=7.01801G/s gas_used=399
ecrecover<evmone::state::ecrecover_execute>             315018 ns       314858 ns         2246 gas_rate=9.52812M/s gas_used=3k
ecrecover<evmone::state::silkpre_ecrecover_execute>      37609 ns        37590 ns        18163 gas_rate=79.8074M/s gas_used=3k
ecadd<evmone::state::ecadd_execute>                       7643 ns         7628 ns        94194 gas_rate=19.665M/s gas_used=150
ecadd<evmone::state::silkpre_ecadd_execute>               2842 ns         2841 ns       243360 gas_rate=52.8011M/s gas_used=150
ecmul<evmone::state::ecmul_execute>                     146770 ns       146614 ns         4772 gas_rate=40.9238M/s gas_used=6k
ecmul<evmone::state::silkpre_ecmul_execute>             197282 ns       197215 ns         3608 gas_rate=30.4236M/s gas_used=6k

vs. new version:

--------------------------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations UserCounters...
--------------------------------------------------------------------------------------------------------------
identity<evmone::state::identity_execute>                 56.1 ns         56.1 ns     12784221 gas_rate=7.11174G/s gas_used=399
ecrecover<evmone::state::ecrecover_execute>             131971 ns       131685 ns         5299 gas_rate=22.7816M/s gas_used=3k
ecrecover<evmone::state::silkpre_ecrecover_execute>      37476 ns        37447 ns        18732 gas_rate=80.1135M/s gas_used=3k
ecadd<evmone::state::ecadd_execute>                       7480 ns         7476 ns        93637 gas_rate=20.0635M/s gas_used=150
ecadd<evmone::state::silkpre_ecadd_execute>               2822 ns         2818 ns       248081 gas_rate=53.2334M/s gas_used=150
ecmul<evmone::state::ecmul_execute>                      62607 ns        62566 ns        11059 gas_rate=95.8992M/s gas_used=6k
ecmul<evmone::state::silkpre_ecmul_execute>             199830 ns       199335 ns         3680 gas_rate=30.1001M/s gas_used=6k
(vvenv) rodia@MacBook-Air-3 evmone % cmake --build build                 

rodiazet avatar Jan 30 '24 14:01 rodiazet

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (17e1dcb) 97.94% compared to head (0d11857) 32.89%.

Additional details and impacted files
@@             Coverage Diff             @@
##           master     #800       +/-   ##
===========================================
- Coverage   97.94%   32.89%   -65.05%     
===========================================
  Files         110      109        -1     
  Lines       10797     9590     -1207     
===========================================
- Hits        10575     3155     -7420     
- Misses        222     6435     +6213     
Flag Coverage Δ
blockchaintests 59.88% <ø> (ø)
statetests 61.31% <0.00%> (-0.93%) :arrow_down:
statetests-silkpre 25.80% <100.00%> (+0.24%) :arrow_up:
unittests ?

Flags with carried forward coverage won't be shown. Click here to find out more.

Files Coverage Δ
lib/evmone_precompiles/bn254.cpp 100.00% <100.00%> (ø)
lib/evmone_precompiles/ecc.hpp 91.17% <100.00%> (-8.83%) :arrow_down:
lib/evmone_precompiles/secp256k1.cpp 94.85% <100.00%> (-5.15%) :arrow_down:

... and 95 files with indirect coverage changes

codecov[bot] avatar Jan 30 '24 14:01 codecov[bot]