Poor performance of ECC implementation of secp256k1

[Megaloblastt]

Hi,

I had to benchmark my own application that uses OpenSSL, and I noticed a important difference in execution time between at least the two following elliptic curves: secp256r1 and secp256k1.

I saw nothing wrong with my code (doesn't mean it's right though), but I started looking at the OpenSSL code itself, and wanted to run OpenSSL benchmarks. Unfortunately, secp256k1 was not in the list of curves for the openssl speed tool, so I had to add it myself (as shown in the patch below).

diff --git a/apps/speed.c b/apps/speed.c
index b978323f56..73f1e809f5 100644
--- a/apps/speed.c
+++ b/apps/speed.c
@@ -1829,7 +1829,8 @@ int speed_main(int argc, char **argv)
         {"nistp192", NID_X9_62_prime192v1, 192},
         {"nistp224", NID_secp224r1, 224},
         {"nistp256", NID_X9_62_prime256v1, 256},
-        {"nistp384", NID_secp384r1, 384},
+        {"nistp256k1", NID_secp256k1, 256},
+        // {"nistp384", NID_secp384r1, 384},
         {"nistp521", NID_secp521r1, 521},
 #ifndef OPENSSL_NO_EC2M
         /* Binary Curves */

Once run, the benchmarks confirmed what I saw previously

$ ./apps/openssl speed ecdsa
[...]
Doing 256 bits sign ecdsa ops for 10s: 674930 256 bits ECDSA sign ops in 9.99s
Doing 256 bits verify ecdsa ops for 10s: 216809 256 bits ECDSA verify ops in 10.00s
Doing 256 bits sign ecdsa ops for 10s: 47745 256 bits ECDSA sign ops in 9.98s
Doing 256 bits verify ecdsa ops for 10s: 50692 256 bits ECDSA verify ops in 9.99s
[...]
version: 3.3.0-dev
built on: Thu Feb  8 13:50:08 2024 UTC
options: bn(64,64)
compiler: gcc -fPIC -pthread -m64 -Wa,--noexecstack -Wall -O3 -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_BUILDING_OPENSSL -DNDEBUG
CPUINFO: OPENSSL_ia32cap=0x7ffaf3ffffebffff:0x98c027bc239c27eb
                              sign    verify    sign/s verify/s
 160 bits ecdsa (secp160r1)   0.0001s   0.0001s  11511.8  10702.0
 192 bits ecdsa (nistp192)   0.0001s   0.0001s   8858.3   8774.4
 224 bits ecdsa (nistp224)   0.0002s   0.0002s   5907.2   6237.3
 256 bits ecdsa (nistp256)   0.0000s   0.0000s  67560.6  21680.9
 256 bits ecdsa (nistp256k1)   0.0002s   0.0002s   4784.1   5074.3

There is a ~14x factor in execution time between ecdsa signatures times on these two curves! Few articles I found over the internet state that secp256k1 is in average 30% faster than secp256r1 (e.g. see here). Also secp256r1 is 11x faster than secp224r1 which should not be. So my guess is that point multiplication on secp256r1 has been highly optimized, maybe by using precomputation (e.g. store multiples of the base, then simply combine them once needed).

If my guess is true, adding precomputations on the secp256k1 curve could be a smart move since this curve gained more and more traction because of bitcoin. If my guess is wrong, please explain.

Thanks

[t8m]

Yes, the secp256r1 code is heavily optimized in comparison to the secp256k1 curve code. If a similar optimization is implemented for secp256k1 and submitted as a PR we would consider it for inclusion.

[jamuir]

@Megaloblastt : have you tried out https://github.com/bitcoin-core/secp256k1 ?

[Megaloblastt]

@jamuir unfortunately, my module already uses OpenSSL for various other cryptographic operations, and I don't want to multiply the number of dependencies yet. But that's definitely something I want to try, thanks for sharing.