Acceleration of ECDSA Verification with Endomorphism Mapping of secp256k1

longcpp

longcpp9@gmail.com

January 2, 2020

Due to the fact that the ECDSA signature mechanism has been adopted by Bit- coin, the ECDSA signature mechanism based on the secp256k1 elliptic curve is widely used in the blockchain industry. At the very beginning, Bitcoin adopted the ECDSA signature mechanism based on secp256k1 implemented in OpenSSL, where there is no targeted optimization for the secp256k1 curve leading to the low efficiency of the ECDSA based on the secp256k1 curve in OpenSSL. It is worth noting that the ESDSA signature mechanism based on the secp256r1 curve is deeply optimized in the OpenSSL project. The performance of these two ECDSAs in OpenSSL in running speed tests is given in Listing 1.

The result of compiling and linking OpenSSL version 1.1 on the Intel(R) Core(TM) i7–6700HQ CPU shows that the running speed of the secp256k1-based ECDSA provided by OpenSSL is approximately 2000 sign/s and 2300 verify/s, while the running speed of ECDSA based on secp256r1 is about 33000 sign/s and 12000 veriy/s. It can be said that the implementation speed of ECDSA based on the secp256k1 curve in OpenSSL is slower than that of the ECDSA based on the secp256r1 curve, by one order of magnitude. When it comes to security, according to the conclusion in [1], the implementation of the secp256k1-based ECDSA in OpenSSL 1.1 is not secure.

The efficiency and security issues of OpenSSL implementation and the inconsistencies that may be introduced by OpenSSL version variations (See DER Encoding Rules and BIP 66) mean that it cannot meet the speed, security, and stability requirements of blockchain use cases. Bitcoin core developers of Bitcoin reimplemented the ECDSA based on secp256k1 in the libsep256k1 project, where the secp256k1 curve was deeply optimized and the constant implementation was guaranteed. Most blockchain projects adopting the ECDSA mechanism based on secp256k1 are currently using the implementation in libsec256k1 by default.

A great number of techniques are used in the libsep256k1 project to improve the efficiency of signature verification. We here only focus on the utilization of the endomorphism feature of secp256k1 to improve the efficiency of the verification. Prior to any technical discussions, we firstly show the speed improvements brought by the endomorphism feature of secp256k1 in the libsecp256k1 project. It should be noted that in order to use the endomorphism feature to speed up the verification process, the −−enable−endomorphism option should be specified at the time of ./configure; in order to use the built-in speed test cases of libsec256k1, −enable−benchmark should also be specified. When compiling without the −−enable−endomorphism option, the results that come from the built-in test tool of libsecp256k1 are as follows:

Compiling with the −−enable−endomorphism option specified, the results that come from the built-in test tool of libsecp256k1 are as follows:

As can be seen, whether the option of −−enable−endomorphism option is speficied has no effect on the ECDSA signature speed. Each sign operation takes about 46 us, which is 22000 sign/s. Specifiying the −−enable−endomorphism option brings about a significantly increased speed of signature verification, from 66.5 us to 47.6 us, which is an increase from 15000 verify/s to 21000 verify/s (a speed improvement around 40%). It is worth noting that the speed test tool of libsecp256k1 also tested the speed of secp256k1-based ECDSA in OpenSSL. The speed was around 475 us per verification, which was equivalent to 2100 verify/s. It is basically the same as the result of our previous test. The results of all the above tests are given in Table 1. We will focus on the internals of the endomorphism feature in the next section.

As early as 2011, Bitcoin developer Hal Finney pointed out on Bitcointalk that the endomorphism feature of secp256k1 could be used to accelerate the signature verification of the ECDSA [2], Finney also gave the PoC code backing up the statement. It can be seen by browsing the code implementation of libsecp256k1 that, the implementation in libsecp256k1 is based on the sample code given by Hal Finney, and the Hal Finney example is based on the content in Section 3.5 of [3], which is basically a reproduce of contents from [6].

Assume E is an elliptic curve defined over field K, we also use E to denote the set of all points on this curve, then the endomorphism mapping in E is a rational mapping φ : E → E satisfying

The 4̃0% improvement in libsecp256k1 is achieved by utilizing more techniques, such as avoiding division operation when decomposing k by precomputation, we will further investigate this in the future.

References

1. Genkin, Daniel, Lev Pachmanov, Itamar Pipman, Eran Tromer, and Yuval Yarom. ”ECDSA key extraction from mobile devices via nonintrusive physical side channels.” In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1626–1638. ACM, 2016.
2. Hal Finney. bitcointalk — Speeding up signature verification. 2011. https:// bitcointalk.org/index.php?topic=3238.0
3. Hankerson, Darrel, Alfred J. Menezes, and Scott Vanstone. ”Guide to elliptic curve cryptography.” Computing Reviews 46, no. 1 (2005): 13.
4. Blahut, Richard E. Cryptography and secure communication. Cambridge University Press, 2014.
5. Stallings, William. Cryptography and network security: principles and practice. Up- per Saddle River: Pearson, 2017.
6. Gallant, Robert P., Robert J. Lambert, and Scott A. Vanstone. ”Faster point multiplication on elliptic curves with efficient endomorphisms.” In Annual International Cryptology Conference, pp. 190–200. Springer, Berlin, Heidelberg, 2001.

This article was written by the CoinEx Chain Team.