ECDSA

ECDSA, the Elliptic Curve Digital Signature Algorithm, is the signature scheme Bitcoin used from its first transactions. It takes a message hash and a private key, and it produces two numbers, r and s. Anyone who has the public key can check the pair without learning the private key. Most older locking scripts still expect ECDSA signatures, so you will meet it in many transactions.

What does ECDSA need?

Signing needs three inputs. Verifying needs three different ones.

Input	Used for signing	Used for verifying
z	The hash of the data being signed	The same hash, rebuilt by the verifier
d	Your private key	Not used
k	A fresh random number, the nonce	Not used
Q	Not needed	The public key, which is Q = d·G
(r, s)	Created by the signer	Checked by the verifier

In Bitcoin, z is a sighash. It is a HASH256 of the transaction data prepared for signing. Read more about what a signature covers on the signature page. The private key d is a number from 1 to n − 1, and the public key is the point Q = d·G on the elliptic curve.

How do you sign a message?

The signer follows four steps. All arithmetic on the scalars is modulo n, the order of the curve.

R = k·G
r = R.x mod n
s = k⁻¹ (z + r·d) mod n
signature = (r, s)

First, the signer multiplies the generator point G by the random nonce k. That gives a random point R. Only the x coordinate of R is kept, as r. Then s combines the message hash z with r and the private key d, using the inverse of k. The signature is the pair (r, s). If r or s comes out as zero, the signer must choose a different k.

Here is a worked example with exact numbers. The fixed k makes the output repeatable, which is why this is for learning only. In real signing, k must be random.

message = "ECDSA is the most fun I have ever experienced"
z = 103318048148376957923607078689899464500752411597387986125144636642406244063093
d = 112757557418114203588093402336452206775565751179231977388358956335153294300646
k = 12345
r = 108607064596551879580190606910245687803607295064141551927605737287325610911759
s = 73791001770378044883749956175832052998232581925633570497458784569540878807131

Here z is the SHA-256 hash of the message text. The public key Q = d·G has x = 33886286099813419182054595252042348742146950914608322024530631065951421850289.

The signing formula in Python is one line once you have the inverse:

s = pow(k, -1, n) * (z + r * d) % n

How do you verify a signature?

A verifier needs z, the signature (r, s) and the public key Q. The verifier computes:

w  = s⁻¹ mod n
u1 = z·w mod n
u2 = r·w mod n
X  = u1·G + u2·Q
valid if X.x mod n = r

Why does this work? The signing equation gives k = s⁻¹(z + r·d). Multiply out the verifying side and you get u1·G + u2·Q = s⁻¹·z·G + s⁻¹·r·d·G. That equals s⁻¹(z + r·d)·G, which is k·G. The verifier arrives at the same point R that the signer started from. Only someone who knows d can build a valid s for this R.

For the example above, the verifier gets X.x equal to r, so the signature passes.

What is low-s?

ECDSA has a flaw called malleability. If (r, s) is valid, then (r, n − s) is also valid for the same message and key. A third party could swap one form for the other and change the transaction's TXID without changing what it does. The rule in BIP 146 requires the low-s form, where s ≤ n/2. Wallets publish that form.

In the worked example, s is above n/2, so a wallet would publish n − s, not s. Both forms verify, so the rule only fixes which one counts as standard.

Why must you never reuse k?

If two signatures from the same key use the same nonce k, they share r, because r depends only on R = k·G. Each signature gives one equation, and the two equations can be solved together. The result is k, and from k you get the private key d.

k = (z1 − z2) / (s1 − s2)  mod n
d = (k·s1 − z1) / r        mod n

In Python:

def recover_d(z1, z2, s1, s2, r, n):
    k = (z1 - z2) * pow(s1 - s2, -1, n) % n
    return (k * s1 - z1) * pow(r, -1, n) % n

This is not a theory. In December 2010, the hacker group fail0verflow showed how to recover the signing key of the PlayStation 3. Sony had used the same nonce for its signatures. Many wallets now derive k deterministically from the private key and the message, as RFC 6979 describes. That lowers the risk, but the lesson still holds: a repeated nonce gives away the key.

Where does ECDSA appear in Bitcoin?

ECDSA signs the inputs of legacy P2PKH transactions and of SegWit P2WPKH transactions. The signature is encoded in DER form, usually 70 to 72 bytes long. A one-byte sighash type follows it, so a signature in a transaction is usually 71 to 73 bytes. Read the script pages to see where the signature sits in each locking type.

Since 2021, Bitcoin also accepts Schnorr signatures for Taproot outputs. Those use a simpler scheme, covered on the Schnorr signatures page. ECDSA and Schnorr work on the same curve, so the keys you already have can serve either one.

What is the standard for ECDSA?

The core definition is in NIST's FIPS 186-4 standard. The curve parameters come from SEC 2. Read the elliptic curve page first if the point maths is new. The signature page shows what a signature covers in a spend, and the Schnorr page is the next step.