This is the second cryptographic primitive, along with hash functions, that we need as building blocks for the cryptocurrency discussion later on. A digital signature is supposed to be the digital analog to a handwritten signature on paper. We desire two properties from digital signatures that correspond well to the handwritten signature analogy. Firstly, only you can make your signature, but anyone who sees it can verify that it’s valid. Secondly, we want the signature to be tied to a particular document so that the signature cannot be used to indicate your agreement or endorsement of a different document. For handwritten signatures, this latter property is analogous to assuring that somebody can’t take your signature and snip it off one document and glue it onto the bottom of another one.
How can we build this in a digital form using cryptography? First, let’s make the previous intuitive discussion slightly more concrete. This will allow us to reason better about digital signature schemes and discuss their security properties.
Digital signature scheme. A digital signature scheme consists of the following three algorithms:
- (sk, pk) := generateKeys(keysize) The generateKeys method takes a key size and generates a key The secret key sk is kept privately and used to sign messages. pk is the public verification key that you give to everybody. Anyone with this key can verify your signature.
- sig := sign(sk, message) The sign method takes a message and a secret key, sk, as input and outputs a signature for message under sk
- isValid := verify(pk, message, sig) The verify method takes a message, a signature, and a public key as It returns a boolean value, isValid, that will be true if sig is a valid signature for message under public key pk, and false otherwise.
We require that the following two properties hold:
- Valid signatures must verify
verify(pk, message, sign(sk, message)) == true
- Signatures are existentially unforgeable
We note that generateKeys and sign can be randomized algorithms. Indeed, generateKeys had better be randomized because it ought to be generating different keys for different people. verify, on the other hand, will always be deterministic.
Let us now examine the two properties that we require of a digital signature scheme in more detail. The first property is straightforward — that valid signatures must verify. If I sign a message with sk, my secret key, and someone later tries to validate that signature over that same message using my public key, pk, the signature must validate correctly. This property is a basic requirement for signatures to be useful at all.
Unforgeability. The second requirement is that it’s computationally infeasible to forge signatures. That is, an adversary who knows your public key and gets to see your signatures on some other messages can’t forge your signature on some message for which he has not seen your signature. This unforgeability property is generally formalized in terms of a game that we play with an adversary. The use of games is quite common in cryptographic security proofs.
In the unforgeability game, there is an adversary who claims that he can forge signatures and a challenger that will test this claim. The first thing we do is we use generateKeys to generate a secret signing key and a corresponding public verification key. We give the secret key to the challenger, and we give the public key to both the challenger and to the adversary. So the adversary only knows information that’s public, and his mission is to try to forge a message. The challenger knows the secret key. So he can make signatures.
Intuitively, the setup of this game matches real world conditions. A real‐life attacker would likely be able to see valid signatures from their would‐be victim on a number of different documents. And maybe the attacker could even manipulate the victim into signing innocuous‐looking documents if that’s useful to the attacker.
To model this in our game, we’re going to allow the attacker to get signatures on some documents of his choice, for as long as he wants, as long as the number of guesses is plausible. To give an intuitive idea of what we mean by a plausible number of guesses, we would allow the attacker to try 1 million guesses, but not 280 guesses2.
Once the attacker is satisfied that he’s seen enough signatures, then the attacker picks some message, M, that they will attempt to forge a signature on. The only restriction on M is that it must be a message for which the attacker has not previously seen a signature (because the attacker can obviously send back a signature that he was given!). The challenger runs the verify algorithm to determine if the signature produced by the attacker is a valid signature on M under the public verification key. If it successfully verifies, the attacker wins the game.
We say that the signature scheme is unforgeable if and only if, no matter what algorithm the adversary is using, his chance of successfully forging a message is extremely small — so small that we can assume it will never happen in practice.
Practical Concerns. There are a number of practical things that we need to do to turn the algorithmic idea into a digital signature mechanism that can be implemented in practice. For example, many signature algorithms are randomized (in particular the one used in Bitcoin) and we therefore need a good source of randomness. The importance of this really can’t be underestimated as bad randomness will make your otherwise‐secure algorithm insecure.
Another practical concern is the message size. In practice, there’s a limit on the message size that you’re able to sign because real schemes are going to operate on bit strings of limited length. There’s an easy way around this limitation: sign the hash of the message, rather than the message itself. If we use a cryptographic hash function with a 256‐bit output, then we can effectively sign a message of any length as long as our signature scheme can sign 256‐bit messages. As we discussed before, it’s safe to use the hash of the message as a message digest in this manner since the hash function is collision resistant.
Another trick that we will use later is that you can sign a hash pointer. If you sign a hash pointer, then the signature covers, or protects, the whole structure — not just the hash pointer itself, but everything the chain of hash pointers points to. For example, if you were to sign the hash pointer that was at the end of a block chain, the result is that you would effectively be digitally signing the that entire block chain.
ECDSA. Now let’s get into the nuts and bolts. Bitcoin uses a particular digital signature scheme that’s called the Elliptic Curve Digital Signature Algorithm (ECDSA). ECDSA is a U.S. government standard, an update of the earlier DSA algorithm adapted to use elliptic curves. These algorithms have received considerable cryptographic analysis over the years and are generally believed to be secure.
More specifically, Bitcoin uses ECDSA over the standard elliptic curve “secp256k1” which is estimated to provide 128 bits of security (that is, it is as difficult to break this algorithm as performing 2128 symmetric‐key cryptographic operations such as invoking a hash function). While this curve is a published standard, it is rarely used outside of Bitcoin, with other applications using ECDSA (such as key exchange in TLS for secure web browsing) typically using the more common “secp256r1” curve. This is just a quirk of Bitcoin, as this was chosen by Satoshi in the early specification of the system and is now difficult to change.
We won’t go into all the details of how ECDSA works as there’s some complicated math involved, and understanding it is not necessary for any other content in this book. If you’re interested in the details, refer to our further reading section at the end of this chapter. It might be useful to have an idea of the sizes of various quantities, however:
Private key: 256 bits Public key, uncompressed: 512 bits Public key, compressed: 257 bits Message to be signed: 256 bits
Signature: 512 bits
Note that while ECDSA can technically only sign messages 256 bits long, this is not a problem: messages are always hashed before being signed, so effectively any size message can be efficiently signed.
With ECDSA, a good source of randomness is essential because a bad source of randomness will likely leak your key. It makes intuitive sense that if you use bad randomness in generating a key, then the key you generate will likely not be secure. But it’s a quirk of ECDSA3 that, even if you use bad
randomness just in making a signature, using your perfectly good key, that also will leak your private key. And then it’s game over; if you leak your private key, an adversary can forge your signature. We thus need to be especially careful about using good randomness in practice, and using a bad source of randomness is a common pitfall of otherwise secure systems.
This completes our discussion of digital signatures as a cryptographic primitive. In the next section, we’ll discuss some applications of digital signatures that will turn out to be useful for building cryptocurrencies.
Sidebar: cryptocurrencies and encryption. If you’ve been waiting to find out which encryption algorithm is used in Bitcoin, we’re sorry to disappoint you. There is no encryption in Bitcoin, because nothing needs to be encrypted, as we’ll see. Encryption is only one of a rich suite of techniques made possible by modern cryptography. Many of them, such as commitment schemes, involve hiding information in some way, but they are distinct from encryption.
