In the previous lessons we learned about finite fields, elliptic curves, point multiplication, the elliptic curve discrete logarithm problem (ECDLP), private keys and public keys. We will now combine all of these tools into the Elliptic Curve Digital Signature Algorithm, which is at the heart of Bitcoin transactions.
Elliptic Curve Digital Signature Algorithm (ECDSA)
In Bitcoin, ECDSA is used for legacy and SegWit v0 signatures. Taproot uses Schnorr signatures instead.
In Bitcoin, spending means satisfying the conditions attached to unspent transaction outputs (UTXOs). For a simple single-key output, this involves a signature made with the corresponding private key. Other outputs can require multiple signatures or additional conditions such as timelocks. The network checks these conditions, including that each required signature is valid for the public key and the transaction data being signed.
But how does this actually work? And how do you prove that you signed a transaction with your private key without ever revealing that private key?
This is where ECDSA comes in. ECDSA can be broken down into three steps:
-
Key generation
-
Signing
-
Verification
We will first look at all these from a mathematical perspective and explain the formulas that underpin each step and then we will walk through a simplified example using Python code for a more intutive understanding.
Key generation
As discussed in the previous lesson, a private key is simply a random integer, d, in the range [1, …, n−1] that is securely and randomly generated. The public key, Q, is the point on the elliptic curve that is the result of point multiplying the generator point, G, with the private key:
Q = dG
This multiplication is a one-way operation, making it computationally infeasible to derive the private key from the public key.
The parameters that define the elliptic curve that Bitcoin uses (secp256k1) are publicly known, constant, and are the following:
Curve equation: y2 = x3 + 7
Prime order of the finite field: 2256- 232- 977
Generator point, G, with x- and y-coordinates:
x = 0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
y= 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
Order of generator point, G:
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
Signing
For Bitcoin’s ECDSA signatures, the message, m, is a signature-hash preimage: a serialisation of selected transaction data determined by the spending type, input and signature-hash flags. It is not simply the serialised transaction or an already-computed hash. Hashing this preimage gives z; the short text message used in our Python examples is only a demonstration.
The steps for creating the signature for a message are the following:
- Hash the message, m:
Compute z = hash256(m).
By hashing the message we create a fixed-size representation of the message. This also ensures that even the smallest change in the message creates a completely different hash, thereby adding to security.
- Generate a random integer k
Select a cryptographically secure random integer k such that 1 <= k <= n−1.
This integer has to be kept secret by the signer, similar to how the private key has to be kept secret!
k is crucial for ensuring randomness and security of the signature. Why having this random integer as part fo the signature is important will become clear shortly.
- Compute the elliptic curve point R
Compute the point R = kG, where G is the generator point.
This point corresponds to k on the elliptic curve. The signer computes it from k; the verifier can reconstruct it from the signature, message hash and public key without learning k.
- Calculate the first part of the signature, r
Compute r = Rₓ mod n, where Rₓ is the x-coordinate of the point R.
If r = 0, go back to step 2 and select a new random k.
r is the part of the signature that ties the signature to the random integer k.
- Calculate the second part of the signature, s
Compute s = k−1(z+r⋅d) mod n.
If s = 0, go back to step 2 and select a new random k.
s combines the private key with the message hash and the random integer k. It ensures that only the holder of the private key could have produced the signature.
- Output the signature
The signature is the pair (r, s).
These two values, along with the public key, the publicly known parameters of the elliptic curve and the message are enough to verify the authenticity of the mesage and the signature without revealing the private key.
Signature Verification
In order to verify a signature on the Bitcoin blockchain we need the following parameters and variables:
Signature: (r, s).
Public Key: Q.
Curve parameters: G, n, p.
Message Hash: z.
Given all of these parameters and variables, the steps to verify a signature are the following:
- Check Signature Validity
Verify that 1 <= r <= n−1 and 1 <= s <=n−1.
r and s must be valid integers within the order of the generator point.
- Compute the inverse of s
Compute w = s−1 mod n.
w allows us to “unwind” the signature equation.
- Calculate u1 and u2
Compute u1 = z ⋅ w mod n and u2 = r ⋅ w mod n.
These values are used to combine the public key and the generator point in a way that allows the verifier to reconstruct the elliptic curve point corresponding to r.
- Compute the Elliptic Curve Point R′
Compute the point R′ = u1G + u2Q, where G is the generator point and Q is the public key. Reject the signature if R′ is the point at infinity. Q must also be a valid non-identity point in the subgroup.
This equation reconstructs R, which was previously computed using k and G, without knowing k through the values u1 and u2.
- Calculate v
Compute v = Rₓ′ mod n, where Rₓ′ is the x-coordinate or R′.
v should equal r if the signature is valid.
- Verify the Signature
If v = r, the signature is valid.
This proves that the signature was indeed created using the private key corresponding to the public key Q and that the message has not been tampered with.
Proof that the verification works
To see why the verification functions correctly we will show how the formulas come together. We start with the formula for R′ from step 4 of the verification process:
R′ = u1G + u2Q
Substituting in the definition of the public key (Q = dG):
R′ = u1G + u2⋅ d⋅ G
Elliptic curve point multiplication distributes over addition so we can collect terms:
R′ = (u1+ u2⋅ d)⋅ G
Expanding the definition of u1 and u2:
R′ = (z ⋅ w + r ⋅ d ⋅ w) ⋅ G
Collecting common term w:
R′ = (z + r ⋅ d) ⋅ w ⋅ G
Because w = s−1, we get:
R′ = (z + r ⋅ d) ⋅ (z + r ⋅ d)−1 ⋅ (k−1)−1⋅ G
The product of an element and its inverse is the identity and the inverse of an inverse is just the orignal element, so we get:
R′ = k ⋅ G
Why k is such as crucial part of the signing process
The nonce k must stay secret and be generated securely. Here is why:
-
Random or deterministic signatures: a secure random nonce normally produces different signatures for the same message, but uniqueness is not guaranteed or required. Secure deterministic ECDSA, such as RFC 6979, derives k from the private key and message hash and can safely repeat the same signature for the same message.
-
Protection against key exposure: reusing the same k with the same private key for different message hashes can expose that private key through a system of linear equations.
-
Cryptographic security: k must be unpredictable to an attacker. Use a cryptographically secure generator or an established deterministic signing method, not Python’s random module.
Example Signature Creation and Verification
Example private key and public key
After covering the algorithms and mathematics behind ECDSA, let’s look at an example of this on a really small elliptic curve over a finite field. We will use the elliptic curve y2 = x3- x + 1 over the finite field F29 and the generator point G = (5, 18). This is the Python code that sets up all the parameters and plots the points on the curve as well as the generator point:
p = 29
a = FiniteFieldElement(-1 % p, p)
b = FiniteFieldElement(1, p)
curve = EllipticCurve(a, b)
G_x = FiniteFieldElement(5, p)
G_y = FiniteFieldElement(18, p)
G = ECPoint(G_x, G_y, curve)
n = 37
curve.plot_curve_over_field(point=G)
TapClick to enlarge ↗The first step is to create a private and a public key. We will use a byte string of our choosing, hash it using double SHA256 and then convert it into an integer modulo n as our private key and then point multiply the generator point by it to get the public key, Q. The private key is generated this way purely for demonstration purposes and something like this should never be done in practice! Here is the code and resulting public key point:
secret = int.from_bytes(hash256(b'Satoshi Nakamoto'), 'big')
d = secret % n
Q = d * G
curve.plot_curve_over_field(point=Q, p_label='Q')
# print(f'The public key corresponding to the private key {d} is: {(Q.x.num, Q.y.num )}')
TapClick to enlarge ↗As we learned previosuly, the public key is just a point on the elliptic curve. In case of our private key, which corresponds to the integer 28, the resulting public key has the coordinates (17, 24).
Example Signature
The following code walks through the signing process step by step:
These examples are for learning, not for signing real Bitcoin transactions. The printed nonces below are fixed only to make the examples reproducible; never reuse them for real signatures. For fresh demonstration signatures, use secrets.randbelow(n - 1) + 1 and retry if r or s is zero. Production software should use a vetted signing library.
m = b'Send 0.1 Bitcoin to Satoshi Nakamoto'
z = int.from_bytes(hash256(m), 'big') % n
print(f'Message Hash (z): {z}')
k = 15 # Fixed, public demonstration nonce; never use for real signatures
print(f"Demonstration k: {k}")
R = k * G
print(f"R: {(R.x.num, R.y.num)}")
r = R.x.num % n
if r == 0:
raise ValueError("Choose a new nonce: r is zero")
print(f'r: {r}')
k_inv = FiniteFieldElement(k, n) ** -1
s = (k_inv.num * (z + r * d)) % n
if s == 0:
raise ValueError("Choose a new nonce: s is zero")
print(f's = {s}')
sig = (r, s)
print(f'Signature: {sig}')The resulting output is the following:
Message Hash (z): 16
Demonstration k: 15
R: (1, 28)
r: 1
s = 35
Signature: (1, 35)These are all just integer values or (x, y) coordinates.
Example Signature Verification
Now let’s go through the Python code for the verification process step by step:
r = sig[0]
s = sig[1]
if not (0 < r < n and 0 < s < n):
raise ValueError("Invalid signature: r or s out of range")
if Q.x is None or (n * Q).x is not None:
raise ValueError("Invalid public key")
print(f'r is valid: {0 < r < n}')
print(f's is valid: {0 < s < n}')
w = (FiniteFieldElement(s, n) ** -1).num % n
print(f'w: {w}')
u_1 = (z * w) % n
u_2 = (r * w) % n
print(f'u1: {u_1}, u2: {u_2}')
R_ = u_1 * G + u_2 * Q
if R_.x is None:
raise ValueError("Invalid signature: point at infinity")
print(f'R\': {(R_.x.num, R_.y.num)}')
v = R_.x.num % n
print(f'v is equal to r: {v == r}')The output of this is:
r is valid: True
s is valid: True
w: 18
u1: 29, u2: 18
R': (1, 28)
v is equal to r: TrueWe have successfully verified the signature and proven that the signer had to have had knowledge of the private key, d, to sign the transaction.
Creating concrete examples like the one above often makes these very theoretical mathematical processes more easily understandable and allows us to follow along by printing intermediate results. We can do the same for Bitcoin’s elliptic curve.
Signing and Verifying on Bitcoin’s Elliptic Curve
Signature Creation
The mechanism is exactly the same for ECDSA on Bitcoin’s elliptic curve, the value of the integers that the variables can take is is just vastly larger. The below code signs the same message we used above using the same the private key over Bitcoin’s elliptic curve:
# Define parameters of secp256k1
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2 ** 256 - 2 ** 32 - 977
# Define the Bitcoin curve
a = FiniteFieldElement(0, p)
b = FiniteFieldElement(7, p)
btc_curve = EllipticCurve(a, b)
# Create the generator
G_x = FiniteFieldElement(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798, p)
G_y = FiniteFieldElement(0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8, p)
G = ECPoint(G_x, G_y, btc_curve)
# Create private and public key
secret = int.from_bytes(hash256(b'Satoshi Nakamoto'), 'big')
d = secret % n
Q = d * G
print(f'Private key (d): {d}\n')
print(f'The public key (Q):\n({Q.x.num},\n {Q.y.num})\n')
# 1. Hash the message
m = b'Send 0.1 Bitcoin to Satoshi Nakamoto'
z = int.from_bytes(hash256(m), 'big') % n
print(f'Message Hash (z): {z}\n')
# 2. Use the fixed demonstration nonce k
# Public demonstration nonce; never use for real signatures
k = 25310935698184543314689296824436401890082733445991940098448795401926645293558
print(f"Demonstration k: {k}\n")
# 3. Compute the elliptic curve point R
R = k * G
print(f'R: ({R.x.num},\n {R.y.num})\n')
# 4. Calculate the first part of the signature, r
r = R.x.num % n
if r == 0:
raise ValueError("Choose a new nonce: r is zero")
print(f'r: {r}')
# 5. Calculate the second part of the signature, s
k_inv = FiniteFieldElement(k, n) ** -1
s = (k_inv.num * (z + r * d)) % n
if s == 0:
raise ValueError("Choose a new nonce: s is zero")
print(f's = {s}\n')
# 6. Output the signature
sig = (r, s)
print(f'Signature: ({sig[0]},\n {sig[1]})\n')The resulting variables are the following:
Private key (d): 15347435467633910075102098082213037117011454378824675510569767404987889485607
The public key (Q):
(21811169802197051269054468546803067869118132299621442904016337768954148287522,
56608919366188758187152936660368979637141300997575071110010417636273132022178)
Message Hash (z): 37164022153960300488979650053899892666954836167732657308788256862398775396684
Demonstration k: 25310935698184543314689296824436401890082733445991940098448795401926645293558
R: (103595376066964697387497908009654511008128923861086556524923908338068713883437,
96698267710076854563886033158128698035167250026253690534165778360078149636358)
r: 103595376066964697387497908009654511008128923861086556524923908338068713883437
s = 90255741919487968844233130295106450824870401067709267232120698047218746884836
Signature: (103595376066964697387497908009654511008128923861086556524923908338068713883437,
90255741919487968844233130295106450824870401067709267232120698047218746884836)We can see that the privae key is a way larger integer than in the previous example. The same applies to the message hash. This, in combination with really large integer values as the x- and y-coordinates of the generator point results in way bigger integer values for everything in the entire process compared to the small example we saw before. This is exactly where the security of Bitcoin comes from. In the prior example one could’ve easily solved for the private key using brute force but it would be computationally infeasible with known classical methods for the example using Bitcoin’s elliptic curve.
Signature Verification
The code for the signature verification is the following:
# 1. Check Signature Validity
r = sig[0]
s = sig[1]
if not (0 < r < n and 0 < s < n):
raise ValueError("Invalid signature: r or s out of range")
if Q.x is None or (n * Q).x is not None:
raise ValueError("Invalid public key")
print(f'r is valid: {0 < r < n}')
print(f's is valid: {0 < s < n}\n')
# 2. Compute the inverse of s, w
w = (FiniteFieldElement(s, n) ** -1).num % n
print(f'w: {w}\n')
# 3. Calculate u_1 and u_2
u_1 = (z * w) % n
u_2 = (r * w) % n
print(f'u1: {u_1} \nu2: {u_2}\n')
# 4. Compute the Elliptic Curve Point R'
R_ = u_1 * G + u_2 * Q
if R_.x is None:
raise ValueError("Invalid signature: point at infinity")
print(f'R\': ({R_.x.num},\n {R_.y.num})\n')
# 5. Calculate v
v = R_.x.num % n
# 6. Verify the Signature
print(f'v is equal to r: {v == r}')
if v == r:
print('Valid signature')
else:
print('Invalid signature')Which prints the following outputs:
r is valid: True
s is valid: True
w: 73271073375020845113111613846550106210459438407704517811015528088419167376159
u1: 26857717933636912051627834771215355476103463403260176018963872334814676814603
u2: 29518055668275830459357127014331969154451206180352345454113335571960030845716
R': (103595376066964697387497908009654511008128923861086556524923908338068713883437,
96698267710076854563886033158128698035167250026253690534165778360078149636358)
v is equal to r: True
Valid signatureWalking through the signature creation and verification process step by step and looking at the results hopefully makes the ECDSA algorithm more tangible and intuitive. The essence of ECDSA is in the way it securely mixes a secret nonce with the private key to create a signature that proves the signer knows the private key. The process is designed so that the private key remains secret, even as others can verify that the signature is valid using the public key.
This combination of secure nonce generation, cryptographic math, and the hidden secret (the private key) is what makes ECDSA both secure and verifiable.
If you’ve made it until here, congratulations, you now understand how the cryptography behind Bitcoin works and have seen an example using real numbers to walk through the process step-by-step.