Elliptic Curve Signatures

Site: Saylor Academy
Course: CS120: Bitcoin for Developers I
Book: Elliptic Curve Signatures
Printed by: Guest user
Date: Friday, March 29, 2024, 9:37 AM

Description

Let's dig into when, where, and how Bitcoin uses Elliptic curve signatures in transactions. This chapter covers the importance of signatures to transactions, the three purposes these signatures serve, and how they are applied.

Digital Signatures (ECDSA)

So far, we have not delved into any detail about "digital signatures". In this section we look at how digital signatures work and how they can present proof of ownership of a private key without revealing that private key.

The digital signature algorithm used in bitcoin is the Elliptic Curve Digital Signature Algorithm, or ECDSA. ECDSA is the algorithm used for digital signatures based on elliptic curve private/public key pairs, as described in [elliptic_curve]. ECDSA is used by the script functions OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKMULTISIG, and OP_CHECKMULTISIGVERIFY. Any time you see those in a locking script, the unlocking script must contain an ECDSA signature.

A digital signature serves three purposes in bitcoin. First, the signature proves that the owner of the private key, who is by implication the owner of the funds, has authorized the spending of those funds. Secondly, the proof of authorization is undeniable (nonrepudiation). Thirdly, the signature proves that the transaction (or specific parts of the transaction) have not and cannot be modified by anyone after it has been signed.

Note that each transaction input is signed independently. This is critical, as neither the signatures nor the inputs have to belong to or be applied by the same "owners". In fact, a specific transaction scheme called "CoinJoin" uses this fact to create multi-party transactions for privacy.

Note: Each transaction input and any signature it may contain is completely independent of any other input or signature. Multiple parties can collaborate to construct transactions and sign only one input each. 

Wikipedia's Definition of a "Digital Signature": A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or documents. A valid digital signature gives a recipient reason to believe that the message was created by a known sender (authentication), that the sender cannot deny having sent the message (nonrepudiation), and that the message was not altered in transit (integrity).


Source: Andreas M. Antonopoulos, https://github.com/bitcoinbook/bitcoinbook/blob/develop/ch06.asciidoc
Creative Commons License This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 License.

How Digital Signatures Work

A digital signature is a mathematical scheme that consists of two parts. The first part is an algorithm for creating a signature, using a private key (the signing key), from a message (the transaction). The second part is an algorithm that allows anyone to verify the signature, given also the message and a public key.

 

Creating a digital signature 

In bitcoin's implementation of the ECDSA algorithm, the "message" being signed is the transaction, or more accurately a hash of a specific subset of the data in the transaction. The signing key is the user's private key. The result is the signature:

 Sig = F_{sig}(F_{hash}(m), dA)

where:

  • dA is the signing private key
  • m is the transaction (or parts of it)
  • Fhash is the hashing function
  • Fsig is the signing algorithm
  • Sig is the resulting signature

More details on the mathematics of ECDSA can be found in ECDSA Math.

The function Fsig produces a signature Sig that is composed of two values, commonly referred to as R and S:

Sig = (R, S)

Now that the two values R and S have been calculated, they are serialized into a byte-stream using an international standard encoding scheme called the Distinguished Encoding Rules, or DER.

 

Serialization of signatures (DER)

Let's look at the transaction Alice created again. In the transaction input there is an unlocking script that contains the following DER-encoded signature from Alice's wallet:

3045022100884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb02204
b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e381301

That signature is a serialized byte-stream of the R and S values produced by Alice's wallet to prove she owns the private key authorized to spend that output. The serialization format consists of nine elements as follows:

  • 0x30 – indicating the start of a DER sequence
  • 0x45 – the length of the sequence (69 bytes)
  • 0x02 – an integer value follows
  • 0x21 – the length of the integer (33 bytes)
  • R – 00884d142d86652a3f47ba4746ec719bbfbd040a570b1deccbb6498c75c4ae24cb
  • 0x02 – another integer follows
  • 0x20 – the length of the integer (32 bytes)
  • S – 4b9f039ff08df09cbe9f6addac960298cad530a863ea8f53982c09db8f6e3813
  • A suffix (0x01) indicating the type of hash used (SIGHASH_ALL)

See if you can decode Alice's serialized (DER-encoded) signature using this list. The important numbers are R and S; the rest of the data is part of the DER encoding scheme.

Verifying the Signature

To verify the signature, one must have the signature (R and S), the serialized transaction, and the public key (that corresponds to the private key used to create the signature). Essentially, verification of a signature means "Only the owner of the private key that generated this public key could have produced this signature on this transaction".

The signature verification algorithm takes the message (a hash of the transaction or parts of it), the signer's public key and the signature (R and S values), and returns TRUE if the signature is valid for this message and public key.

Signature Hash Types (SIGHASH)

Digital signatures are applied to messages, which in the case of bitcoin, are the transactions themselves. The signature implies a commitment by the signer to specific transaction data. In the simplest form, the signature applies to the entire transaction, thereby committing all the inputs, outputs, and other transaction fields. However, a signature can commit to only a subset of the data in a transaction, which is useful for a number of scenarios as we will see in this section.

Bitcoin signatures have a way of indicating which part of a transaction's data is included in the hash signed by the private key using a SIGHASH flag. The SIGHASH flag is a single byte that is appended to the signature. Every signature has a SIGHASH flag and the flag can be different from input to input. A transaction with three signed inputs may have three signatures with different SIGHASH flags, each signature signing (committing) different parts of the transaction.

Remember, each input may contain a signature in its unlocking script. As a result, a transaction that contains several inputs may have signatures with different SIGHASH flags that commit different parts of the transaction in each of the inputs. Note also that bitcoin transactions may contain inputs from different "owners," who may sign only one input in a partially constructed (and invalid) transaction, collaborating with others to gather all the necessary signatures to make a valid transaction. Many of the SIGHASH flag types only make sense if you think of multiple participants collaborating outside the bitcoin network and updating a partially signed transaction.

There are three SIGHASH flags: ALL, NONE, and SINGLE, as shown in SIGHASH types and their meanings.

 

Table 4. SIGHASH types and their meanings 

SIGHASH flag Value Description

ALL

0x01

Signature applies to all inputs and outputs

NONE

0x02

Signature applies to all inputs, none of the outputs

SINGLE

0x03

Signature applies to all inputs but only the one output with the same index number as the signed input

 

In addition, there is a modifier flag SIGHASH_ANYONECANPAY, which can be combined with each of the preceding flags. When ANYONECANPAY is set, only one input is signed, leaving the rest (and their sequence numbers) open for modification. The ANYONECANPAY has the value 0x80 and is applied by bitwise OR, resulting in the combined flags as shown in SIGHASH types with modifiers and their meanings.

 

Table 5. SIGHASH types with modifiers and their meanings

SIGHASH flag Value Description

ALL|ANYONECANPAY

0x81

Signature applies to one input and all outputs

NONE|ANYONECANPAY

0x82

Signature applies to one input, none of the outputs

SINGLE|ANYONECANPAY

0x83

Signature applies to one input and the output with the same index number

 

These flag combinations are summarized in Summary of different sighash combinations.

Figure 8. Summary of different sighash combinations

The way SIGHASH flags are applied during signing and verification is that a copy of the transaction is made and certain fields within are truncated (set to zero length and emptied). The resulting transaction is serialized. The SIGHASH flag is added to the end of the serialized transaction and the result is hashed. The hash itself is the "message" that is signed. Depending on which SIGHASH flag is used, different parts of the transaction are truncated. The resulting hash depends on different subsets of the data in the transaction. By including the SIGHASH as the last step before hashing, the signature commits the SIGHASH type as well, so it can't be changed (e.g., by a miner).

Note: All SIGHASH types sign the transaction nLocktime field. In addition, the SIGHASH type itself is appended to the transaction before it is signed, so that it can't be modified once signed.

In the example of Alice's transaction, we saw that the last part of the DER-encoded signature was 01, which is the SIGHASH_ALL flag. This locks the transaction data, so Alice's signature is committing the state of all inputs and outputs. This is the most common signature form.

Let's look at some of the other SIGHASH types and how they can be used in practice:

ALL|ANYONECANPAY

This construction can be used to make a "crowdfunding"- style transaction. Someone attempting to raise funds can construct a transaction with a single output. The single output pays the "goal" amount to the fundraiser. Such a transaction is obviously not valid, as it has no inputs. However, others can now amend it by adding an input of their own, as a donation. They sign their own input with ALL|ANYONECANPAY. Unless enough inputs are gathered to reach the value of the output, the transaction is invalid. Each donation is a "pledge," which cannot be collected by the fundraiser until the entire goal amount is raised.

 

NONE

This construction can be used to create a "bearer check" or "blank check" of a specific amount. It commits to the input, but allows the output locking script to be changed. Anyone can write their own bitcoin address into the output locking script and redeem the transaction. However, the output value itself is locked by the signature.

 

NONE|ANYONECANPAY

This construction can be used to build a "dust collector". Users who have tiny UTXO in their wallets can't spend these because the cost in fees exceeds the value of the dust. With this type of signature, the dust UTXO can be donated for anyone to aggregate and spend whenever they want.

There are some proposals to modify or expand the SIGHASH system. One such proposal is Bitmask Sighash Modes by Blockstream's Glenn Willen, as part of the Elements project. This aims to create a flexible replacement for SIGHASH types that allows "arbitrary, miner-rewritable bitmasks of inputs and outputs" that can express "more complex contractual precommitment schemes, such as signed offers with change in a distributed asset exchange".

Note: You will not see SIGHASH flags presented as an option in a user's wallet application. With few exceptions, wallets construct P2PKH scripts and sign with SIGHASH_ALL flags. To use a different SIGHASH flag, you would have to write software to construct and sign transactions. More importantly, SIGHASH flags can be used by special-purpose bitcoin applications that enable novel uses.

ECDSA Math

As mentioned previously, signatures are created by a mathematical function Fsig that produces a signature composed of two values R and S. In this section we look at the function Fsig in more detail.

The signature algorithm first generates an ephemeral (temporary) private public key pair. This temporary key pair is used in the calculation of the R and S values, after a transformation involving the signing private key and the transaction hash.

The temporary key pair is based on a random number k, which is used as the temporary private key. From k, we generate the corresponding temporary public key P (calculated as P = k*G, in the same way bitcoin public keys are derived. The R value of the digital signature is then the x coordinate of the ephemeral public key P.

From there, the algorithm calculates the S value of the signature, such that:

S = k-1 (Hash(m) + dA*R)mod n

where:

  • k is the ephemeral private key
  • R is the x coordinate of the ephemeral public key
  • dA is the signing private key
  • m is the transaction data
  • n is the prime order of the elliptic curve

Verification is the inverse of the signature generation function, using the R, S values and the public key to calculate a value P, which is a point on the elliptic curve (the ephemeral public key used in signature creation):

P = S-1*Hash(m) *G+S-1*R*Qa

where:

  • R and S are the signature values
  • Qa is Alice's public key
  • m is the transaction data that was signed
  • G is the elliptic curve generator point

If the x coordinate of the calculated point P is equal to R, then the verifier can conclude that the signature is valid.

Note that in verifying the signature, the private key is neither known nor revealed.

Tip: ECDSA is necessarily a fairly complicated piece of math; a full explanation is beyond the scope of this book. A number of great guides online take you through it step by step: search for "ECDSA explained" or try this one: https://bit.ly/2r0HhGB.

The Importance of Randomness in Signatures

As we saw in ECDSA Math, the signature generation algorithm uses a random key k, as the basis for an ephemeral private/public key pair. The value of k is not important, as long as it is random. If the same value k is used to produce two signatures on different messages (transactions), then the signing private key can be calculated by anyone. Reuse of the same value for k in a signature algorithm leads to exposure of the private key!

Warning: If the same value k is used in the signing algorithm on two different transactions, the private key can be calculated and exposed to the world!

This is not just a theoretical possibility. We have seen this issue lead to exposure of private keys in a few different implementations of transaction-signing algorithms in bitcoin. People have had funds stolen because of inadvertent reuse of a k value. The most common reason for reuse of a k value is an improperly initialized random-number generator.

To avoid this vulnerability, the industry best practice is to not generate k with a random-number generator seeded with entropy, but instead to use a deterministic-random process seeded with the transaction data itself. This ensures that each transaction produces a different k. The industry-standard algorithm for deterministic initialization of k is defined in RFC 6979, published by the Internet Engineering Task Force.

If you are implementing an algorithm to sign transactions in bitcoin, you must use RFC 6979 or a similarly deterministic-random algorithm to ensure you generate a different k for each transaction.