curves~behind.bitcoin

Bitcoin isn't "secured by passwords". It's secured by math.
And at the center of that math is one of the most elegant structures in cryptography:
an elliptic curve.

• What even is a field or a curve?
• How does 256-bit randomness become a public key that nobody can reverse?
• How are signatures used to verify transactions?

If you're more hands-on you can open this notebook which has code to follow along.

Why elliptic curves?

Cryptography needs mathematical structures where certain operations are easy in one direction but practically impossible to reverse. Before elliptic curves, systems like RSA used the difficulty of factoring large numbers. But there's a catch: as computers get faster, you need exponentially larger keys. A 256-bit RSA key is trivially breakable today.

Elliptic curves give us something special: a group where the discrete logarithm problem is much harder per bit of key size. A 256-bit elliptic curve key provides roughly the same security as a 3072-bit RSA key. This means:

• Smaller keys (32 bytes vs 384 bytes)
• Faster operations
• Smaller signatures
• Less bandwidth and storage

The "magic" is that while you can efficiently compute $P = dG$ (multiply a point by a scalar), there's no known shortcut to recover $d$ from $P$ and $G$. The group structure scrambles the point through billions of additions in a way that appears random, and unlike integer logarithms, there's no equivalent of a "slide rule" that lets you work backwards.

From continuous geometry to discrete arithmetic

Bitcoin uses an elliptic curve known as secp256k1.

On a continuous plane (real numbers), it looks like a smooth curve:

$y^2 = x^3 + 7$

We observe that in an elliptic curve, there are two y-values for a given x. This observation will come in handy later.

Bitcoin curves are modular and discrete

In Bitcoin, we don’t use real numbers at all.
Instead, all numbers live inside a finite field — integers modulo a large prime $p$.

A finite field $\mathbb{F}_p$ (where $p$ is prime) is the set:

$\{0, 1, 2, \ldots, p-1\}$

where addition, subtraction, multiplication, and division are all done modulo $p$.

Why must $p$ be prime?

Because when $p$ is prime, every non-zero element in $\mathbb{F}_p$ has a multiplicative inverse:

$\forall x \neq 0,\ \exists \space x^{-1} \pmod p$

That means division always works.
This is what makes $\mathbb{F}_p$ a proper field — and elliptic curve formulas rely heavily on division.

The curve equation modulo $p$

Bitcoin’s curve is not the real-number curve that we drew above $y^2 = x^3 + 7$.
It is the modular version:

$y^2 \equiv x^3 + 7 \pmod p$

That single change — doing everything mod $p$ — completely changes the geometry:

• you only get a finite set of valid integer points $(x, y)$
• there is no smooth curve anymore
• arithmetic wraps around at $p$
• there are no fractional coordinates

So what does the curve look like mod $p$?

Instead of a continuous curve, you get a cloud of discrete points:

At this point, the curve has boiled down into a finite set of points — and now we can define algebra on them. Even though it looks random, this set of points forms a group with a special addition rule. That group structure is what Bitcoin uses for public keys and signatures. Your public key is in fact, one of those points!

Terminologies: Curve, Point, and Scalar

To build Bitcoin signatures from scratch, we’ll use a few core objects and operations. All of this is discussed in the context of secp256k1.

1. Prime field modulus: $p$

All coordinate math is defined over finite field $\mathbb{F}_p$:

• valid coordinates are integers in the range $0 \le x,y < p$
• arithmetic “wraps around” mod $p$

$p = 2^{256} - 2^{32} - 977$
The same can be represented in:

Hex = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
Dec = 115792089237316195423570985008687907853269984665640564039457584007908834671663

2. Any point: $P = (x,y)$

A point is a pair $(x,y)$ that satisfies the curve equation mod $p$. Therefore, it's valid if and only if:

$y^2 \equiv x^3 + 7 \pmod p$

3. Point at infinity: $\mathcal{O}$

There’s a special point called the point at infinity, written $\mathcal{O}$. It behaves like the identity element of addition:

$P + \mathcal{O} = P$

4. Point addition: $P + Q$

Elliptic curve points can be “added” using a special algebraic rule. This addition has important properties:

• it stays on the curve (closure)
• it is associative
• there is an identity element $\mathcal{O}$

This is what makes elliptic curve points form a group. The algebraic process graphically is shown below:

P + Q

2P

5. Point negation / inverse: $-P$

Every point $P=(x,y)$ has an inverse:

$-P = (x, -y \bmod p)$, such that $P + (-P) = \mathcal{O}$

6. A scalar: $k$

A scalar is just an integer used to repeatedly add a point.

We use scalars in two places:

• mod $p$ for field arithmetic (coordinates and slopes)
• mod $n$ for group scalars (private keys and signatures)

7. Scalar multiplication: $kP$

Scalar multiplication means:

$kP = P + P + \cdots + P \quad (k \text{ times})$

This is the core operation behind Bitcoin keys:

• easy to compute forward
• hard to undo (discrete log problem)

8. Generator point: $G$

The generator point $G$ is a fixed point on the curve chosen by the standard. It generates the subgroup used in Bitcoin.

Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240
Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424

In practice, private key is a scalar $d$ while public key is the point $P = dG$.

9. Group order: $n$

If you add $G$ to itself $n$ times, you get the identity point.

$nG = \mathcal{O}$

The number $n$ is called the order of the subgroup generated by $G$.

Hex = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
Dec = 115792089237316195423570985008687907852837564279074904382605163141518161494337

Bitcoin requires scalars to be in this range, $1 \le d \le n-1$ and most signature math happens modulo $n$.

Generating a Public/Private Keypair

Private Key: Any scalar $1 \le d \le n-1$
Corresponding public key: $P = dG$, a point on the secp256k1 curve.

d = secrets.randbelow(n)
P = d * G

This operation is easy to compute, but hard to reverse. Mathematically, given $P$ and $G$, it's infeasible to compute $d$, where $P = dG$.

SEC1 Public Key Serialization (used in ECDSA)

The points are generated modulo $p$ which is in 256 bits or 32 bytes. Therefore, x or y coordinate values will be of 32 bytes.

Uncompressed Serialization (65 bytes)

04 || x(32 bytes) || y(32 bytes)

Compressed Serialization (33 bytes)

For a given x, there can be ONLY two values of y, because $y = \pm\sqrt{x^3+7}$

(03|02) || x(32 bytes)
 
03 = odd y
02 = even y

BIP340 X-Only Public Key Serialization (used in Schnorr/Taproot)

BIP340 enforces a canonical rule:

The public key point is always interpreted as the point with even $y$

Thereby, if public key $P = dG$ has an odd y value ($P.y$ is odd), then the private key is negated to $d' = n - d$, giving $P' = d'G = -P$ which has even $y$.

The serialization here will only be the x value, so 32 bytes.

x(32 bytes)

Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA is the signature scheme Bitcoin used from day one (and it’s still widely used today). It lets you prove:

I know the private key $d$ corresponding to public key $P=dG$,
without revealing $d$.

ECDSA Signing Algorithm

The signer has:

• Private Key $d$
• Public Key $P = dG$
• Message Hash $z$ (For Bitcoin, this is the transaction sighash)

The signature is the pair $(r, s)$

Step 1: Generate a secret nonce $k$

$k \in [1, n-1]$ - $k$ must be unpredictable - $k$ must never repeat - $k$ must remain secret

In production Bitcoin, this is done deterministically using RFC6979 $k = f(d, z)$

Step 2: Compute the nonce point $R$

$R = kG$

Take its x-coordinate: $r = R_x \bmod n$

Step 3: Compute the signature scalar $s$

The signing formula is:

$s = k^{-1}(z + rd) \bmod n$

The final ECDSA signature is: $(r, s)$

def ecdsa_sign(z: int, d: int, G: Point) -> Tuple[int, int]:
    """
    Sign a message hash interpreted as integer z.
    Returns (r, s) as integers in [1, n-1].
    """
    n = G.curve.n
 
    if n is None:
        raise ValueError("Curve must have order n")
    if not (1 <= d < n):
        raise ValueError("Invalid private key d")
 
    z = z % n # message should also be mod n
 
    while True:
        # Random Nonce is fine for learning but not production
        # because what if nonce reused because of randomness?
        # k = secrets.randbelow(n)
 
        # RFC6979 Deterministic Nonce
        k = rfc6979_generate_nonce(d, z, n)
 
        R = k * G
        if R.is_infinity(): continue
 
        r = R.x % n
        if r == 0: continue
 
        k_inv = Scalar(k, n).inv().value
        s = (k_inv * (z + r * d)) % n
        if s == 0: continue
 
        # The signature is NOT a point, just a pair of values
        return (r, s)

ECDSA Verification Algorithm

The verifier has:

• signature $(r,s)$
• message hash $z$
• public key $P$

They want to verify the signature without knowing $d$.

Step 1: Range checks

• $r \in [1, n-1]$
• $s \in [1, n-1]$

Otherwise reject

Step 2: Compute inverse of $s$

$w = s^{-1} \bmod n$

Step 3: Compute two scalars

$u_1 = zw \bmod n$ $u_2 = rw \bmod n$

Step 4: Reconstruct the point $X$

$X = u_1G + u_2P$

Reject if $X = \mathcal{O}$.

Step 5: Compare x-coordinate

$v = X_x \bmod n$

The signature is valid iff $v = r$

def ecdsa_verify(z: int, sig: Tuple[int, int], P: Point, G: Point) -> bool:
    """
    Verify ECDSA signature (r,s) for message hash integer z against public key P.
    """
    r, s = sig
    n = G.curve.n
    if n is None:
        raise ValueError("Curve must have order n")
 
    if P.is_infinity() or (P.curve != G.curve):
        return False
    if not (1 <= r < n and 1 <= s < n):
        return False
 
    z = z % n # message should be mod n
 
    s_inv = Scalar(s, n).inv().value
 
    u1 = (z * s_inv) % n
    u2 = (r * s_inv) % n
 
    X = (u1 * G) + (u2 * P)
    if X.is_infinity():
        return False
 
    return (X.x % n) == r

ECDSA Problems

Bitcoin, historically, had to deal with two classes of problems.

1. Nonce reuse leaks the private key

$s=k^{-1}(z+rd) \bmod n$
$\Rightarrow sk = z+rd \bmod n$

Now, suppose you sign $s_1$ and $s_2$ with the same nonce $k$.

$s_1k = z_1 + rd \bmod n$
$s_2k = z_2 + rd \bmod n$

Subtract:

$(s_1-s_2)k = (z_1-z_2) \bmod n$
$\implies k = (z_1-z_2)(s_1-s_2)^{-1} \bmod n$

And once $k$ is known,

Private Key $d = (sk - z)r^{-1} \bmod n$

Why Deterministic Nonces?

If $k$ is generated randomly, even a tiny flaw in the RNG (biased bits, predictable state, or VM snapshot reuse) can leak the private key. RFC6979 removes this risk entirely by deriving $k$ deterministically from the private key and message: $k = f(d, z)$.

This means:

• Same $(d, z)$ always produces the same $k$ — no randomness needed
• Different messages produce different $k$ values — no reuse
• The nonce is unpredictable to attackers who don't know $d$

2. Signature Malleability

If $(r,s)$ is a valid ECDSA signature, then $(r, n-s)$ is also valid.

r, s = sig = ecdsa_sign(z, d, G)
 
assert ecdsa_verify(z, (r, s), P, G) # expected to pass
assert ecdsa_verify(z, (r, n - s), P, G) # NO ERROR!

Reasons Bitcoin moved away from ECDSA (towards Schnorr / Taproot)

1. Transaction ID Malleability: (pre- SegWit)

Before SegWit, the transaction ID was computed as: $txid = sha256d(\text{serialized-transaction})$

and the serialization included scriptSig, which contains the signature bytes. So any mutation to signature bytes could change the txid even though the spend remained valid.

a) DER encoding malleability (non-canonical encodings)

• The same mathematical ECDSA signature (r, s) could be encoded in multiple valid (but non-canonical) ways in DER
• This allowed third parties to mutate signature bytes, and therby mutate txid

It was fixed by BIP66 (Strict DER encoding) (consensus rule).

b) s-value malleability (high-s / low-s)

For any valid signature (r,s), this is also valid: (r, n - s)

This produces a different signature that still verifies, again allowing txid mutation pre-SegWit.

Mitigated by enforcing low-S signatures as policy/standardness (often discussed in context of BIP62), and later enforced more strictly for SegWit spends.

c) SegWit solved it structurally

SegWit moved signatures into the witness, so:

• txid no longer commits to signatures
• malleability no longer breaks txid-based chaining

Fixed by SegWit (BIP141) at the protocol level.

2. Nonce Fragility / Leaking Private Key (discussed above)

3. No clean key aggregation

ECDSA's multiplicative structure ($s = k^{-1}(z + rd)$) doesn't compose nicely. If Alice and Bob want to create a joint signature, they can't simply add their individual signatures together.

Schnorr's linear structure ($s = k + ed$) is fundamentally different. If Alice signs with $s_1 = k_1 + e \cdot d_1$ and Bob signs with $s_2 = k_2 + e \cdot d_2$, then $s_1 + s_2 = (k_1 + k_2) + e(d_1 + d_2)$ is a valid signature for the aggregated key $(d_1 + d_2)G = P_1 + P_2$.

This linearity enables protocols like MuSig2, where multiple parties can create a single signature that's indistinguishable from a regular signature — enabling efficient multisig, atomic swaps, and more.

4. Additional malleability vectors

Beyond the $(r, n-s)$ malleability discussed above, ECDSA has other subtle malleability issues:

• The same $(r, s)$ values can sometimes be valid for different messages if $r$ values collide after mod $n$ reduction (extremely rare but theoretically possible)
• Implementation bugs around DER encoding created additional attack surface

Schnorr's design eliminates these by construction: the even-$y$ requirement and the way the challenge hash commits to the full message remove ambiguity.

5. No efficient batch verification

When a Bitcoin node receives a block with hundreds of transactions, it must verify hundreds of signatures. With ECDSA, each verification requires separate elliptic curve operations.

Schnorr verification is a linear equation: check that $sG = R + eP$, or equivalently, $sG - eP - R = \mathcal{O}$.

For multiple signatures, you can combine these checks: $\sum_i (s_i G - e_i P_i - R_i) = \mathcal{O}$

With random coefficients (to prevent cancellation attacks), this becomes a single multi-scalar multiplication — which is much faster than $n$ separate verifications. Batch verification can speed up block validation by 2-3x.

Schnorr Signatures (BIP340)

Schnorr signatures are what Bitcoin uses for Taproot outputs. They are cleaner, more structured, and more composable.

Schnorr signatures look like: $(r_x, s)$

where:

• $r_x$ is the x-coordinate of nonce point $R$
• $s$ is a scalar modulo $n$

Schnorr Signing Algorithm

The signer has:

• Private Key $d$
• Public Key $P = dG$
• Message $m$ (32 bytes)

Step 1: Compute public key and enforce even-y

$P = dG$

If $P_y$ is odd, replace $d \leftarrow n-d$ and $P \leftarrow -P$ so that $P_y$ is always even.

Step 2: Generate nonce $k$ deterministically

BIP340 uses tagged hashes with optional aux randomness: $k = f(d, m, aux)$

Step 3: Compute nonce point $R$

$R = kG$

If $R_y$ is odd, replace $k \leftarrow n-k$ and $R \leftarrow -R$ so that $R_y$ is always even.

Step 4: Compute challenge $e$

$e = H(r_x, p_x, m) \bmod n$

Step 5: Compute signature scalar $s$

$s = k + ed \bmod n$

The Schnorr signature is $(r_x, s)$, serialized as

rx(32 bytes) || s(32 bytes)

Schnorr Verification Algorithm

The verifier has:

• x-only public key $p_x$
• signature $(r_x, s)$
• message $m$

Step 1: Range checks

• $r_x \in [0, p-1]$
• $s \in [0, n-1]$

Step 2: Lift x-only public key

Compute $P = lift\_x(p_x)$: solve $y^2 \equiv x^3 + 7 \pmod p$ and choose the even $y$.

Step 3: Compute challenge

$e = H(r_x, p_x, m) \bmod n$

Step 4: Reconstruct nonce point

$R' = sG - eP$

Reject if $R' = \mathcal{O}$.

Step 5: Final checks

Signature is valid iff $R'_y$ is even and $R'_x = r_x$.

You can take a look at the implementation of Schnorr Signatures in the notebook.

Tagged Hashes in BIP340

BIP340 uses tagged hashes for domain separation:

• BIP0340/aux
• BIP0340/nonce
• BIP0340/challenge

$H_{tag}(x) = sha256(sha256(tag) \| sha256(tag) \| x)$

Schnorr vs ECDSA: No Malleability

In ECDSA, $(r, s)$ and $(r, n-s)$ both verify.

In BIP340 Schnorr, signatures are canonicalized using the even-$y$ requirement on $R$, so the "flip $s$" trick does not produce a second valid signature.

A Note on Quantum Computing

Everything in this post assumes classical computers. A sufficiently powerful quantum computer running Shor's algorithm could solve the discrete log problem in polynomial time, breaking ECDSA and Schnorr alike.

How worried should we be?

• Current state: As of 2026, the largest quantum computers have a few thousand qubits. Breaking secp256k1 would require millions of stable, error-corrected qubits.
• Timeline estimates: Experts disagree wildly — some say 10 years, others say 30+, some say never at scale.
• Bitcoin's exposure: Only public keys that have been revealed (by spending) are vulnerable. Addresses that have never spent are protected by the hash function layer (RIPEMD160 + SHA256), which quantum computers don't break as efficiently.
• Mitigation: Post-quantum signature schemes exist (lattice-based, hash-based) and could be added to Bitcoin via soft fork if quantum computers become a real threat.

The cryptographic community is actively researching post-quantum alternatives, but for now, elliptic curves remain secure against all known attacks.

Takeaways

The security of Bitcoin rests on a beautiful mathematical foundation: the difficulty of reversing scalar multiplication on elliptic curves. From a 256-bit random number (your private key), we derive a public key that's trivial to compute but impossible to reverse. Signatures prove you know the private key without revealing it, using the clever trick of committing to randomness before being challenged.

ECDSA served Bitcoin well for over a decade, but its multiplicative structure created subtle problems: fragile nonces, signature malleability, and no path to aggregation. Schnorr's linear design ($s = k + ed$) elegantly solves these issues while enabling new capabilities like efficient multisig and batch verification.

Key concepts:

• $\mathbb{F}_p$ for coordinates/slopes, $\mathbb{Z}_n$ for private keys/signature scalars
• Modular inverse exists for all non-zero values in both fields
• A point has a group inverse $-P$, not a modular inverse
• Recovering $d$ from $P=dG$ is the Elliptic Curve Discrete Log Problem (infeasible)
• ECDSA nonce failure is catastrophic (leaks private key)
• Schnorr signatures are smaller, canonical, and better for aggregation
• Tagged hashes provide domain separation
• aux is signer-only randomness to harden nonce generation