Faster Signatures on secp256k1

In my last post I mentioned that both the Schnorr and ECDSA signature schemes on secp256k1 could be made faster via the so-called wNAF method for elliptic curve point multiplication (short for the cumbersome “w-ary non-adjacent form”). I implemented wNAF for ppad-secp256k1 afterwards, adding a bunch of functions that use it internally.

The only “downside” to the use of wNAF is that one needs to supply a context argument that consists of a bunch of precomputed multiples of the secp256k1 base point (this is at least one of the reasons why libsecp256k1, as well as any bindings to it, generally require you to pass a context argument everywhere). It’s not much of a downside, but it does complicate the API to some degree, so I added these functions on top of the existing ones – the original functions are preserved for when terse code, rather than raw speed, is desired.

The wNAF method really shines when it comes to ECDSA. Here are some benchmarks that illustrate the improvement – the wNAF-powered functions are differentiated by a trailing apostrophe:

benchmarking ecdsa/sign_ecdsa
time                 1.795 ms   (1.767 ms .. 1.822 ms)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 1.806 ms   (1.785 ms .. 1.849 ms)
std dev              93.43 μs   (58.86 μs .. 163.7 μs)

benchmarking ecdsa/sign_ecdsa'
time                 243.1 μs   (237.6 μs .. 249.6 μs)
                     0.996 R²   (0.993 R² .. 0.999 R²)
mean                 241.4 μs   (238.1 μs .. 245.3 μs)
std dev              12.06 μs   (9.492 μs .. 16.17 μs)

benchmarking ecdsa/verify_ecdsa
time                 2.473 ms   (2.409 ms .. 2.541 ms)
                     0.995 R²   (0.991 R² .. 0.997 R²)
mean                 2.432 ms   (2.396 ms .. 2.480 ms)
std dev              140.2 μs   (110.4 μs .. 187.0 μs)

benchmarking ecdsa/verify_ecdsa'
time                 1.460 ms   (1.418 ms .. 1.497 ms)
                     0.994 R²   (0.989 R² .. 0.997 R²)
mean                 1.419 ms   (1.398 ms .. 1.446 ms)
std dev              80.76 μs   (66.73 μs .. 104.9 μs)

So, a 7.5x improvement on ECDSA signature creation, and almost a 2x improvement on signature verification. Not bad.

For Schnorr signatures the improvements are less pronounced, but still substantial:

benchmarking schnorr/sign_schnorr
time                 5.368 ms   (5.327 ms .. 5.423 ms)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 5.436 ms   (5.410 ms .. 5.464 ms)
std dev              84.83 μs   (72.17 μs .. 101.4 μs)

benchmarking schnorr/sign_schnorr'
time                 2.557 ms   (2.534 ms .. 2.596 ms)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 2.579 ms   (2.556 ms .. 2.605 ms)
std dev              83.75 μs   (69.50 μs .. 100.5 μs)

benchmarking schnorr/verify_schnorr
time                 2.338 ms   (2.309 ms .. 2.382 ms)
                     0.998 R²   (0.995 R² .. 0.999 R²)
mean                 2.339 ms   (2.316 ms .. 2.366 ms)
std dev              82.73 μs   (65.83 μs .. 105.9 μs)

benchmarking schnorr/verify_schnorr'
time                 1.429 ms   (1.381 ms .. 1.482 ms)
                     0.993 R²   (0.987 R² .. 0.998 R²)
mean                 1.372 ms   (1.355 ms .. 1.396 ms)
std dev              67.72 μs   (50.44 μs .. 110.5 μs)

So here about a 2x improvement, plus or minus change, across the board. I hope to hammer these down a good bit further in the future if at all possible!