Our choice of digital signature algorithm

alt

Transactions are the centerpiece of the Exonum design. They encode atomic changes of the blockchain as a distributed database. Transactions are authenticated with public-key digital signatures. Hence, the choice of digital signatures and cryptographic tools plays a crucial role in blockchain security. In this article we want to tell about the Ed25519 digital signature algorithm used in Exonum and explain why we have considered it as a good choice for solving blockchain challenges.

alt

secp256k1

There are different algorithms for public-key digital signatures. Algorithms based on elliptic curves have gained wide interest because the size of keys and signatures is significantly lower than in RSA alternatives. For blockchains, the most popular setup seems to be the ECDSA signing algorithm together with the secp256k1 elliptic curve. It is used in Bitcoin, Ethereum, Zcash, etc.

The secp256k1 curve is defined in SECG (Standards for Efficient Cryptography). Unlike many alternative curves, the parameters of secp256k1 are chosen in a predictable way (owing to it being a so called Koblitz curve). The choice of parameters makes computations on secp256k1 faster, and also provides a reasonable degree of assurance that it wasn’t backdoored. secp256k1 ows its popularity to Bitcoin; nowadays, it has multiple interoperable implementations, for example:

At the same time, secp256k1 has some issues:

Computational (in)efficiency. secp256k1 does not allow the Montgomery ladder implementation, a fast and simple algorithm to perform elliptic curve computations in constant time. This is because the curve does not have the necessary shape. Constant time computations help prevent leaking information about the secret key by measuring how long it takes to create the signature. secp256k1 works with other constant-time computations (for example, the Brier – Joye ladder), but they slow down computations too much.

Completeness of formulas and constructions. Classical arithmetic formulas for elliptic curves have exceptional cases; they do not work for all points and hence can lead to producing incorrect results if implemented without utmost attention to details. Completeness refers to a curve having no exceptional cases, and secp256k1 is unfortunately not complete.

Twist security. In a twist attack, an attacker uses a similar elliptic curve (a twist of the original curve) and pretends as if it was the original curve. The curve which is not twist-secure needs to check during the signature and verification procedure whether the points supplied to the algorithm are actually on the curve. These checks make the implementation less secure and efficient. The twist of secp256k1 is a safe curve, but there are additional twists, which lead to more possibilities for an attack. The twist attack complexity (that is, the expected number of computational operations in order for an attack to succeed), 2109.5, is sufficiently high for now, but lower than for comparable curves (Curve25519 and NIST P-256).

In Search of Alternatives

Besides secp256k1, there are other standardized curves which are researched and examined by scientists nowadays. For example, the NIST P-256 curve is commonly implemented in specialized hardware (HSMs), as well as software libraries, such as OpenSSL. At the same time, this curve is graded to be unsafe in almost the same categories as secp256k1, and its parameters were randomly handpicked, which raises concerns about a backdoor.

E-521 and Ed448-Goldilocks curves pass all SafeCurves security checks, but are less studied than the main contender to secp256k1 dominance, Curve25519. Curve25519 was proposed by D. J. Bernstein in 2006. It passes security tests with flying colors because of its construction. Curve25519 (or rather, its twist) is commonly used in combination with the Schnorr signature scheme, which is often discussed as an alternative to ECDSA. (Bitcoin is going to replace ECDSA with Schnorr algorithm too.) The resulting signature scheme is called Ed25519. This is the one we use in Exonum.

Schnorr signature scheme was proposed in 1988 being a modification of El-Gamal and Fiat-Shamir signature schemes. One of advantages of Schnorr’s algorithm is ability to compress signature data of multi-signature schemes. By some estimations, Schnorr signatures would reduce signature space in Bitcoin by at least 25%. Another advantage of this signature algorithm is that it would make signatures look indistinguishable from a conventional single public key, which benefits user privacy.

Ed25519

Ed25519 is a particular instantiation of the next-gen EdDSA signing algorithm. EdDSA uses twisted Edwards curves instead of Weierstrass ones. There are advantages of using Edwards curves: they are complete (that is, computations on Edwards curves have no exceptional cases) and fast (the average performance is ~1.5 times higher than performance on Weierstrass curves). Edwards curves are currently being studied to create post-quantum digital signature schemes.

Compared to secp256k1, Ed25519 has slightly smaller keys and signatures (see the table below); it is also ~30% faster and also allows especially fast batch verification. Ed25519 implementations do not have secret memory access or secret branch conditions (that is, access/conditions that depend on the secret key); the whole signing process flow is completely predictable. This means that Ed25519 is designed to be immune to side-channel attacks.

Criteria Secp256k1 ECDSA Ed25519
Key size 33 bytes 32 bytes
Signature size ~71 bytes 64 bytes
Security target 2128 2128
Security Tests 7 of 11 11 of 11

Ed25519 is not without challenges. For example, one of the challenging topics for this curve is HD key derivation used by most blockchains. As Ed25519 is non-linear, the key derivation is not obvious; there are no standards for HD key derivation yet, but there are proposals.

The interest in Ed25519 continuously grows! Currently, it is used in Tendermint, Stellar, Bigchain DB, Monero, Chain, and many other blockchains and blockchain frameworks.