decred / dcrd

Decred daemon in Go (golang).
https://decred.org
ISC License
738 stars 291 forks source link

secp256k1: Optimize field inverse calc. #3421

Closed davecgh closed 2 months ago

davecgh commented 2 months ago

This optimizes the field multiplicative inverse calculation to use a more optimal addition chain which reduces the number of field squarings from 258 to 255 and the number field multiplications from 33 to 15.

This calculation is primarily involved when converting back to affine space which is done for various things such as:

The following benchmarks show a before and after comparison of field inversion as well as how it that translates to public key calculation, Schnorr signature verification, and recovery from compact signatures:

name               old time/op   new time/op   delta
------------------------------------------------------------------------
FieldInverse       12.0µs ± 0%   10.9µs ± 1%   -8.96%  (p=0.008 n=10+10)
PrivateKeyPubKey   35.0µs ± 1%   33.9µs ± 2%   -3.18%  (p=0.008 n=10+10)
SchnorrSigVerify    122µs ± 1%    121µs ± 1%   -0.82%  (p=0.015 n=10+10)
RecoverCompact      137µs ± 1%    135µs ± 1%   -1.35%  (p=0.002 n=10+10)
davecgh commented 2 months ago

Rebased to latest master.