Signature determinism for blockchain developers
During my work in the blockchain space, the topic deterministic signatures comes up from time to time, along with misconceptions and sometimes even severe security flaws. But what exactly are deterministic signatures and why would you want them?
The rough non-academic interpretation of a deterministic signature is: if the same key signs the same message multiple times, the same signature is generated. If life was as simple as that, you could do fun things like ensuring that only one signed transaction exists for a given unsigned transaction. Or you could construct an on-chain random number generator where one party submits a message to be signed, a predefined signer signs it and the signature bytes serve as randomness.
At first glance this seems promising as we observe that both Ed25519 claims to generate signatures deterministically and Secp256k1 signing produces the same signature every time. But how is that possible, when I was taught in university that one of the great drawbacks of the Elliptic Curve Digital Signature Algorithm (ECDSA) signing algorithm is that good randomness is required for every single signature and that a single leaked random value allows the calculation of the private key, which was famously used to hack the PlayStation 3.
ECDSA applied to the curve Secp256k1 is used in Bitcoin, Ethereum, Cosmos SDK among others for signing transactions. As shown in step 3 of the signing algorithm definition, a random integer k is used. Not only is this element random, it is also secret, since you could use the triple (message, k, signature) to calculate the private key. As the signature depends on k, it is intuitive to expect random signatures for every invocation of the signing algorithm. How can this match the observation of stable results?
The requirement on good randomness for every single signature is a burden, especially in old school web browsers or low end hardware without a lot of entropy collecting sensors. At some point people came up with a more practical way to fulfil the algorithm’s requirements for k: a pseudorandom number generator plus a secret seed will generate a secret and cryptographically secure random k, sourced from a deterministic calculation. One example implementation of this can be found in the elliptic library. It uses HMAC-DRBG with an configurable hash function as a pseudorandom number generator, which is seeded by the private key and the message.
To achieve deterministic signature generation, the secp256k1 implementation in Tendermint (and go-ethereum) uses RFC-6979 by default. Unfortunately, the RFC does not come with test vectors for Secp256k1. Otherwise it would be easy to see if different implementations apply the same algorithm. In any case, the principle is the same: by mixing private key and message you can securely fake randomness.
But chosing a deterministic algorithm to obtain k is completely up to the signer. You can easily replace it with a real random number generator that does not depend on the private key or the message. Since k is secret (otherwise 💥), an observer cannot tell which algorithm the signer used. As a consequence, a signer can generate an arbitrary number of valid signatures using the same keypair and message. This is demonstrated in the following code for a few different choices of k:
What about Ed25519?
ECDSA from the 1980s is curve agnostic and used for sigining over a wide range of curves. In 2011 the more integrated solution Ed25519 came up, specifying a signing algorithm over the Curve25519, which does not support ECDSA. This time, deterministic signature generation was built into the protocol from the beginning. It works very differently from ECDSA, but here a signer can change the right half of SHA-512(seed)used as an ingredient for signing without affecting the public key, which comes from the left half of SHA-512(seed).
As a consequence, you can generate an arbitrary amount of nonces (RH) for a single public key (LH), allowing you to generate an arbitrary number of valid signatures for the same message. A demo how to implement that with ed25519-dalek in Rust is available here.
This caused a bug in the Lisk multisig verification where different valid signatures were interpreted as different signers, such that a single signer could reach any n/m multisig threshold alone.
Takeaways
In all ECDSA schemes and Ed25519 a signer can generate an arbitrary number of valid signatures for the same message, using the same key. The term “deterministic signing” means that at least one deterministic way to generate signatures exist. It does not imply that a signer can only generate one valid signature. Due to the nature of the signing algorithms, an observer cannot detect if a standard algorithm or a customization was used.
In the context of blockchain an arbitrary number of signed transactions and transaction IDs for a given unsigned transaction may exist. Usually signers have no reason to generate them, but if they want to spam a network with valid transactions, they can. Which of those transactions is processed in a block is a different question.
Avoiding common pitfalls
If you forget all of the above soon, no worries. Just try to avoid the most common mistakes:
- Using a signature as a fair random value — the signer can use it to its advantage.
- Assuming that different signatures on a given message are from different signers — a single signer can generate as many as they want.
- Assuming there is a single signed transaction and transaction ID for a given unsigned transaction — every signer can generate as many different signed transactions as they want by generating different signatures.
