02 - Elliptic Curve Signatures in Bitcoin

Bitcoin signatures use a well known and widely used cryptographic technique known as Elliptic Curve Digital Signature algorithm (ECDSA). ECDSA was developed over many years and was accepted in 1998 as an ISO standard, in 1999 as an ANSI standard, and in 2000 as IEEE and NIST standards. ECDSA is closely linked to Elliptic Curve Encryption (ECE) and key pairs that are used to encrypt data with ECE can also be used to generate digital signatures with ECDSA.

An elliptic curve signature is generated by applying an elliptic curve function to a message. For the purposes of this exercise there is no direct need to understand the mathematics. Students who wish to gain further expertise in this area are urged to take the Bitcoin Primitives course, Introduction to Digital Signatures in Bitcoin.

For Bitcoin to work, the nodes that validate transactions must have a way of reconstructing the message signed by the user without the user having to provide anything but the Bitcoin transaction they are sending to the network.

This is achieved by making the message from a rigidly defined transaction pre-image that is comprised of a set of information that the node can extract directly from the transaction in order to reconstruct the message. That information is made up of the following set of 11 parameters:

Item	Name	Description, Length and format
1	nVersion	The version of the protocol being used to define this transaction - 4 Bytes little-endian integer
2	hashPrevouts	either a SHA256 hash of the transaction's concatenated input source / sources or a 32 byte null string if SIGHASH_ANYONECANPAY is used - 32 Byte hash string
3	hashSequence	the concatenation of the input nSequence value / values or a null string if SIGHASH_ANYONECANPAY is used - 32 Byte hash string
4	outpoint	Outpoint for input being signed - concatenation of input TXID + Vout - 32 Byte transaction hash + 4 Byte little-endian integer
5	lockScriptLength	Locking script length - a VarInt - 1, 3, 5 or 9 bytes depending on script length
6	lockScript	Locking script for output being spent - scriptLen byte string
7	value	Value of input - An integer representing the input's satoshi value - 8 Byte little-endian integer
8	nSequence	Then nSequence value for input being signed - 4 byte little-endian integer
9	hashOutputs	If SIGHASH_ALL is used, this value is the SHA256 hash of the concatenation of all transaction outputs in Transaction output format. If SIGHASH_SINGLE is used, this value is the SHA256 hash of only the output corresponding to the input's Vin index. If SIGHASH_NONE is used, this is a null string - 32 Byte hash string
10	nLocktime	The nLocktime value for the transaction - 4 byte little-endian integer
11	sighash	The SIGHASH flags being applied to this signature - 4 bytes, XX000000 where XX is Sighash Flag

To calculate a signature the following mathematical data points are used:

1. A keypair In the sect256k1 calculated with: P = S · G where: P is the public key, calculated using: S, the Private key, an integer value in the range 0 - n where n = FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 G, the Generator Point, a point on the elliptic curve with the following co-ordinate: x - 79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798 y - 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8\

2. Message m where: m is the transaction pre-image as defined on page 2

Using these datapoints the following method is applied:

1. Calculate R = k · G where k is typically a randomly generated number (called an ephemeral key) generated on demand. When using R-Puzzles, k is pre-known and is used as part of the evaluation process

2. Define r = x-coordinate of R

3. Calculate s = k^-1(H(m) + S * r)mod n Unpacking this:

   1. H(m) is the double SHA256 hash of message m

   2. Treating the SHA256 hash as an integer, we add S x r which is the private key multipled by the ephemeral key's x co-ordinate

   3. We multiply the sum from step 2 by k^-1

   4. We perform a modulo function with n as the denominator and the result of step 3 as numerator to get the signature

The full signature is a concatenation of r and s in DER format as outlined below:

Data Structure	Length	Data (hex)
Sequence Identifier	1	30
Length of Sequence	1	46
Integer Identifier	1	02
Byte-length of r	1	20 or 21 (decimal 32 or 33)
r (must be positive)	32 if positive or if negative, append 0x00 in MS byte to generate absolute value giving length 33 bytes	e.g. e9d34347e597e8b335745c6f8353580f4cbdb4bcde2794ef7aab915d996642
Integer identifier	1	02
Byte-length of s	1	20 or 21 (decimal 32 or 33)
s (must be positive)	32 if positive or if negative, append 0x00 in MS byte to generate absolute value giving length 33 bytes	e.g. df2ccb52c7243c55bde34934bd55efbdac21c74a20bb7b438d1b6de3311f
Sighash type	1	e.g 41 (SIGHASH_ALL)