Now that you know how to derive a public key from a private key, you can already receive bitcoins by using this pair of keys as a spending condition. But how to spend them? To spend bitcoins, you will need to unlock the scriptPubKey attached to your UTXO to prove that you are indeed its legitimate owner. To do this, you must produce a signature that matches the public key present in the scriptPubKey using the private key that was initially used to calculate . The digital signature is thus irrefutable proof that you are in possession of the private key associated with the public key you claim.

To perform a digital signature, all participants must first agree on the parameters of the elliptic curve used. In the case of Bitcoin, the parameters of secp256k1 are as follows:

The finite field defined by:

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

is a very large prime number slightly less than .

The elliptic curve over defined by:

The generator point or origin point :

G = 0x0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

This number is the compressed form that only gives the abscissa of point . The prefix 02 at the beginning determines which of the two values having this abscissa is to be used as the generating point. The order of (the number of existing points) and the cofactor :

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

is a very large number slightly less than .

is the cofactor or the number of subgroups. I will not elaborate on what this represents here, as it’s quite complex, and in the case of Bitcoin, we do not need to take it into account since it is equal to .

All this information is public and known to all participants. Thanks to them, users are able to make a digital signature and verify it.

The ECDSA algorithm allows a user to sign a message using their private key, in such a way that anyone knowing the corresponding public key can verify the validity of the signature, without the private key ever being revealed. In the context of Bitcoin, the message to be signed depends on the sighash chosen by the user. It is this sighash that will determine which parts of the transaction are covered by the signature. I will talk more about this in the next chapter.

Here are the steps to generate an ECDSA signature:

First, we calculate the hash () of the message that needs to be signed. The message is thus passed through a cryptographic hash function, generally SHA256 or double SHA256 in the case of Bitcoin:

Next, we calculate a nonce. In cryptography, a nonce is simply a number generated in a random or pseudo-random manner that is used only once. That is to say, each time a new digital signature is made with this pair of keys, it will be very important to use a different nonce, otherwise, it will compromise the security of the private key. It is therefore sufficient to determine a random and unique integer such that , where is the order of the generating point of the elliptic curve.

Then, we will calculate the point on the elliptic curve with the coordinates such that:

We extract the value of the abscissa of the point (). This value represents the first part of the signature. And finally, we calculate the second part of the signature in this manner:

where:

The signature is then simply the concatenation of and :

To verify a signature , anyone knowing the public key and the parameters of the elliptic curve can proceed in this way:

First, verify that and are within the interval . This ensures that the signature respects the mathematical constraints of the elliptic group. If this is not the case, the verifier immediately rejects the signature as invalid.

Then, calculate the hash of the message:

Calculate the modular inverse of modulo :

Calculate two scalar values and in this way:

And finally, calculate the point on the elliptic curve such that:

The signature is valid only if , where is the coordinate of the point . Indeed, by combining and , one obtains a point which, if the signature is valid, must correspond to the point used during the signature (modulo ).

The Schnorr signature scheme is an alternative to ECDSA that offers many advantages. It has been possible to use it in Bitcoin since 2021 and the introduction of Taproot, with the P2TR script patterns. Like ECDSA, the Schnorr scheme allows signing a message using a private key, in such a way that the signature can be verified by anyone knowing the corresponding public key. In the case of Schnorr, the exact same curve as ECDSA is used with the same parameters. However, public keys are represented slightly differently compared to ECDSA. Indeed, they are designated only by the coordinate of the point on the elliptic curve. Unlike ECDSA, where compressed public keys are represented by 33 bytes (with the prefix byte indicating the parity of ), Schnorr uses 32-byte public keys, corresponding only to the coordinate of the point , and it is assumed that is even by default. This simplified representation reduces the size of the signatures and facilitates certain optimizations in the verification algorithms. The public key is then the coordinate of the point :

The first step to generate a signature is to hash the message. But unlike ECDSA, it is done with other values and a labeled hash function is used to avoid collisions in different contexts. A labeled hash function simply involves adding an arbitrary label to the hash function's inputs alongside the message data.

In addition to the message, the coordinate of the public key , as well as the point , calculated from the nonce (which is itself a unique integer for each signature, calculated deterministically from the private key and the message to avoid vulnerabilities related to nonce reuse), are also passed into the labeled function. Just like for the public key, only the coordinate of the nonce point is retained to describe the point.

The result of this hashing noted is called the "challenge":

Here, is the SHA256 hash function, and is the specific tag for the hashing.

Finally, the parameter is calculated from the private key , the nonce , and the challenge as follows:

The signature is then simply the pair and .

The verification of a Schnorr signature is simpler than that of an ECDSA signature. Here are the steps to verify the signature with the public key and the message . First, we verify that is a valid integer less than . If this is the case, we retrieve the corresponding point on the curve with being even. We also extract and by splitting the signature . Then, we check that and (the order of the curve). Next, we calculate the challenge in the same way as the issuer of the signature:

Then, we calculate a reference point on the curve in this way:

Finally, we verify that . If the two x-coordinates match, then the signature is indeed valid with the public key .

The signer has calculated , so should be equal to the original point , because:

Since , we have . Thus:

Therefore, we have:

The Schnorr signature scheme offers several advantages for Bitcoin over the original ECDSA algorithm. First, Schnorr allows for the aggregation of keys and signatures. This means that multiple public keys can be combined into a single key.

And similarly, multiple signatures can be aggregated into a single valid signature. Thus, in the case of a multisignature transaction, a set of participants can sign with a single signature and a single aggregated public key. This significantly reduces storage and computation costs for the network, as each node only needs to verify a single signature.

Moreover, signature aggregation improves privacy. With Schnorr, it becomes impossible to distinguish a multisignature transaction from a standard single-signature transaction. This homogeneity makes chain analysis more difficult, as it limits the ability to identify wallet fingerprints.

Finally, Schnorr also offers the possibility of batch verification. By verifying multiple signatures simultaneously, nodes can gain efficiency, especially for blocks containing many transactions. This optimization reduces the time and resources needed to validate a block. Also, Schnorr signatures are not malleable, unlike signatures produced with ECDSA. This means that an attacker cannot modify a valid signature to create another valid signature for the same message and the same public key. This vulnerability was previously present in Bitcoin and notably prevented the secure implementation of the Lightning Network. It was resolved for ECDSA with the SegWit softfork in 2017, which involves moving the signatures to a separate database from the transactions to prevent their malleability.

As we have seen, Satoshi initially chose to implement ECDSA for digital signatures in Bitcoin. Yet, we have also seen that Schnorr is superior to ECDSA in many aspects, and this protocol was created by Claus-Peter Schnorr in 1989, 20 years before the invention of Bitcoin.

Well, we don't really know why Satoshi didn't choose it, but a likely hypothesis is that this protocol was under patent until 2008. Although Bitcoin was created a year later, in January 2009, no open-source standardization for Schnorr signatures was available at that time. Perhaps Satoshi deemed it safer to use ECDSA, which was already widely used and tested in open-source software and had several recognized implementations (notably the OpenSSL library used until 2015 in Bitcoin Core, then replaced by libsecp256k1 in version 0.10.0). Or maybe he simply wasn't aware that this patent was going to expire in 2008. In any case, the most probable hypothesis seems related to this patent and the fact that ECDSA had a proven history and was easier to implement.