Lecture 02 · Cryptographic Foundations

L02: Cryptographic Foundations

The Mathematical Bedrock of Blockchain Security

From hash functions to elliptic curves: how four mathematical properties replace institutional trust with computational guarantees, and why no blockchain transaction is possible without them.

Level: BSc Year 2 Prerequisites: Binary numbers, modular arithmetic Slides: 10 core · 35 extended Charts: 12

WHY

The Problem: Replacing Institutional Trust with Mathematics

When Alice sends Bob a digital file, Bob faces an immediate problem: how does he know the file has not been modified in transit? How does he know Alice actually sent it? And how does he know Alice has not sent the identical file to a hundred other recipients simultaneously? In the physical world, these questions are answered by institutions — banks, notaries, legal systems — that vouch for the authenticity and uniqueness of records. Blockchain’s radical proposition is that mathematics can replace these institutions entirely.

This is not a new idea. The cypherpunk movement of the 1980s and 1990s, which gave Bitcoin its intellectual DNA, argued that strong cryptography could shift the balance of power away from states and corporations and toward individuals. Whitfield Diffie, Martin Hellman, Ralph Merkle, and later Satoshi Nakamoto built the specific primitives that make a trustless ledger possible. Understanding those primitives is not optional background knowledge — it is the load-bearing foundation of everything that follows in this course.

Cryptography enables four properties that blockchain requires: (1) Integrity — detect any tampering with data; (2) Authentication — prove identity without a trusted third party; (3) Non-repudiation — a signer cannot later deny having signed; (4) Efficiency — verify large datasets in constant time.

Fig 2.1 — The cryptographic primitives stack: how hash functions, asymmetric keys, and Merkle trees compose into blockchain security

Without cryptographic hash functions, there is no way to detect if a historical block has been altered. Without digital signatures, there is no way to prove that a transaction was authorized by the holder of a private key rather than an impostor. Without Merkle trees, light clients would have to download the entire blockchain to verify a single payment. Each primitive solves a specific problem, and together they form a system with stronger security guarantees than any single institution could provide — not because any individual participant is trustworthy, but because deception is computationally infeasible.

WHAT

Hash Functions: Four Properties That Change Everything

A cryptographic hash function is a deterministic algorithm that maps an input of arbitrary length to a fixed-length output, called a digest or hash. Formally: H : {0,1}* → {0,1}ⁿ. Feed it a single character or a terabyte video file, and you always receive exactly n bits back. For SHA-256, used by Bitcoin, n = 256; for Keccak-256, used by Ethereum, n is the same. The fixed output size is what makes hashes useful as fingerprints.

Four properties distinguish a cryptographic hash function from a mundane one like a checksum or CRC:

⇋

Deterministic

Same input always produces the same output. Verification is reproducible by any party independently.

→

One-Way (Preimage Resistance)

Given H(x), finding x requires brute force. For SHA-256, that means 2²⁵⁶ attempts — comparable to the number of atoms in the observable universe.

≠

Collision Resistant

Hard to find distinct x and y where H(x) = H(y). The birthday paradox means collisions emerge after ~2¹²⁸ attempts for SHA-256.

⛡

Avalanche Effect

Flipping one input bit flips ~50% of output bits unpredictably. Even “Hello” vs “hello” produces completely different hashes.

Fig 2.2 — The four cryptographic hash function properties illustrated

The avalanche effect is particularly striking in practice. Consider SHA-256 applied to “Hello” versus “hello”:

# SHA-256 of "Hello" and "hello" differ completely
SHA256("Hello") = 185f8db32271fe25f561a6fc938b2e264306ec304eda518007d1764826381969
SHA256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
# Exactly one bit changed in input; ~128 of 256 output bits changed

Fig 2.3 — SHA-256 avalanche effect: a single input bit flip randomizes approximately half the output bits

Bitcoin uses SHA-256 applied twice (double-SHA-256, or SHA256d) for block hashing and transaction IDs. This double application provides extra protection against a class of vulnerabilities called length-extension attacks. Ethereum uses Keccak-256, a variant of SHA-3 that was finalized before the NIST standardization process introduced subtle modifications — a choice motivated by the same wariness of standardization-body influence that led Satoshi to favor secp256k1 over NIST’s elliptic curves.

Hash functions appear in five distinct roles in Bitcoin alone: linking blocks via previous-block-hash, summarizing transactions via Merkle root, deriving addresses from public keys, setting the proof-of-work target, and encoding P2SH and SegWit script hashes. Every transaction, every block, every address depends on hash security.

Fig 2.4 — Comparison of cryptographic hash algorithms by security level, output size, and blockchain adoption

HOW

Digital Signatures: Proving Ownership Without Revealing Secrets

A digital signature answers the question: how can Alice prove she authorized a transaction without sharing her private key? The answer is asymmetric cryptography, also called public-key cryptography. Alice generates a mathematically linked key pair: a private key she keeps secret and a public key she shares freely. A signature created with the private key can be verified by anyone holding the corresponding public key, but cannot be forged without knowing the private key.

Fig 2.5 — Digital signature lifecycle: signing with private key, verification with public key

The ECDSA (Elliptic Curve Digital Signature Algorithm) signing process works in five steps. Crucially, the message itself is never encrypted — blockchain transactions are public by design. The signature proves only that the sender authorized the transaction, not that the transaction content is confidential.

1
Hash the message: Compute z = SHA256d(transaction_data). Working on the hash rather than the raw message prevents length-extension attacks and ensures the signature commits to a fixed-size value.
2
Choose ephemeral key k: Pick a fresh random integer k from [1, n-1]. This must be cryptographically secure and never reused — reusing k across two signatures reveals the private key algebraically.
3
Compute point R = k · G: Multiply the generator point G by k using elliptic curve scalar multiplication. Set r = R_x mod n (the x-coordinate of R).
4
Compute s = k^-1(z + r · d) mod n: Where d is the private key. The signature is the pair (r, s).
5
Broadcast (r, s) with the transaction. Any node can verify: compute R′ = s^-1(z · G + r · Q) and confirm that R′_x = r, where Q is the public key.

Critical implementation detail: The ephemeral key k must be freshly random for every signature. The PlayStation 3 was hacked in 2010 when Sony reused a constant k in all their ECDSA signatures — this allowed hackers to solve for the private key algebraically from just two signatures. Modern implementations use deterministic k generation (RFC 6979) to eliminate this class of failure entirely.

Fig 2.6 — ECDSA signing and verification steps with mathematical detail

It is important to distinguish signing from encryption. Blockchain transactions are signed but not encrypted — the entire world can read what Alice sent to Bob and how much she paid. Signing provides authentication (this transaction came from Alice) and non-repudiation (Alice cannot later deny it). Encryption would provide confidentiality (only Bob can read the content). For public ledgers, authentication is what matters; confidentiality is a separate concern handled by privacy-focused protocols like Zcash or Tornado Cash.

Fig 2.7 — Encryption vs digital signatures: different goals, different key usage direction

CASE

Elliptic Curve Cryptography: Why secp256k1?

Both Bitcoin and Ethereum use ECDSA over secp256k1, a specific elliptic curve defined by the equation y² = x³ + 7 over a prime finite field. The choice of elliptic curves over older alternatives like RSA is primarily about efficiency: a 256-bit elliptic curve key provides approximately the same security as a 3072-bit RSA key, meaning signatures and public keys are dramatically smaller and computationally faster to verify at scale.

The mathematics of elliptic curves over finite fields is elegant. Points on the curve form a mathematical group under a special addition rule: draw a line through two points P and Q, find the third intersection with the curve, and reflect it over the x-axis. This “chord and tangent” operation is the foundational operation. Scalar multiplication — computing k · G where G is a distinguished generator point — is easy to compute forward but hard to invert.

The discrete logarithm problem: Given public key Q = k · G, finding the private key k is the elliptic curve discrete logarithm problem (ECDLP). No efficient classical algorithm is known. The best known attacks (baby-step giant-step, Pollard’s rho) require O(n^1/2) operations — approximately 2¹²⁸ for secp256k1.

Algorithm	Key Size	Security	Used By
RSA-2048	2048 bits	112 bits	TLS, PGP
RSA-3072	3072 bits	128 bits	High-sec TLS
secp256k1	256 bits	128 bits	Bitcoin, ETH
Ed25519	256 bits	128 bits	Solana, SSH
BLS12-381	381 bits	128 bits	ETH 2.0 PoS

Fig 2.8 — The secp256k1 elliptic curve y² = x³ + 7, with point addition illustrated

The secp256k1 curve has specific parameters chosen for favorable computational properties. The prime p = 2²⁵⁶ − 2³² − 977 is a Mersenne-like prime that makes modular reduction extremely efficient in hardware. The generator point G is a public constant specified in the standard. Critically, secp256k1 was not one of the NIST-recommended curves — a deliberate choice, since the NIST curves have parameters whose selection justification is opaque, raising concerns (still unproven) that the NSA may have introduced backdoors. The secp256k1 parameters were chosen by a verifiable algorithm, leaving no room for hidden weaknesses.

Fig 2.9 — The elliptic curve discrete logarithm problem: scalar multiplication is a one-way trapdoor function

Ethereum’s transition to Proof-of-Stake introduced a second signature scheme alongside ECDSA: BLS signatures (Boneh-Lynn-Shacham) over the BLS12-381 curve. BLS signatures have a critical property ECDSA lacks: aggregation. Instead of storing one 96-byte signature per validator per attestation, the network can aggregate thousands of signatures into a single constant-size proof. With 500,000 active validators, this aggregation reduces signature data by orders of magnitude and is essential for Ethereum’s consensus layer scalability.

Fig 2.10 — Schnorr vs ECDSA signature schemes: Bitcoin Taproot added Schnorr for batch verification and key aggregation

WHERE

Merkle Trees: Logarithmic Verification at Scale

Invented by Ralph Merkle in 1979 and first described in a paper on digital signatures, the Merkle tree is a binary hash tree in which each leaf node contains the hash of a data block, and each interior node contains the hash of its two children. The single root hash at the top of the tree — the Merkle root — summarizes the entire dataset. Any change to any leaf propagates upward and changes the root, making tampering detectable in O(1) time once the root is known.

Every Bitcoin block header contains the Merkle root of all transactions in that block. A block with 3,000 transactions has a Merkle tree of depth log²(3000) ≈ 12. The header is only 80 bytes, yet it commits cryptographically to the exact set of transactions below.

The killer application is the Merkle proof: a compact certificate that a specific transaction is included in a block, without requiring the verifier to download the entire block. The proof consists of the sibling hashes along the path from the transaction’s leaf to the root — O(log n) hashes total.

Transactions	Full Block	Merkle Proof
1,000	250 KB	320 bytes (10 hashes)
10,000	2.5 MB	416 bytes (13 hashes)
100,000	25 MB	544 bytes (17 hashes)

Fig 2.11 — Merkle tree structure: leaves are transaction hashes, interior nodes hash their children, root commits to all data

SPV — Simplified Payment Verification: Bitcoin’s whitepaper (Section 8) describes SPV clients that can verify payments without running a full node. An SPV client downloads only block headers (80 bytes each × ~880,000 blocks = ~70 MB total) and requests Merkle proofs for transactions of interest. This enables lightweight mobile wallets to verify payments with cryptographic certainty rather than trusting a third-party API.

Fig 2.12 — Merkle proof for a single transaction: only the highlighted sibling hashes are needed, not the entire tree

Merkle trees appear far beyond blockchain. Git uses a Merkle DAG (directed acyclic graph) to commit entire repository states; ZFS uses Merkle trees for filesystem integrity; BitTorrent uses them for peer verification of downloaded chunks; and certificate transparency logs (used by HTTPS) use Merkle trees to make certificate issuance auditable. The data structure is genuinely general-purpose. Ethereum extends the concept with Patricia Merkle Tries — a combination of Merkle trees with Patricia trie path compression — to store the entire world state (all account balances and contract storage) in a single authenticated data structure whose root appears in every block header.

IMPACT

Address Derivation: From Entropy to Identity

A blockchain address is not a username or an email — it is a mathematical derivative of a public key, which is itself a mathematical derivative of a private key, which is a random 256-bit number. The derivation chain is one-way at every step: knowing an address does not reveal the public key (until first spend), and knowing the public key does not reveal the private key. This hierarchy provides layered protection.

Fig 2.13 — Key generation pipeline: entropy source → private key → public key → address

Bitcoin’s address derivation applies two hash functions for additional security. Starting from a 256-bit private key d:

1
Public key: Q = d · G (elliptic curve scalar multiplication with secp256k1 generator G). Result is a 512-bit uncompressed point, or 257-bit compressed point using sign of y-coordinate.
2
First hash: SHA-256(public key). SHA-256 provides quantum resistance compared to exposing raw ECC output.
3
Second hash: RIPEMD-160(SHA-256(public key)). RIPEMD-160 shortens the result to 160 bits (20 bytes), making addresses shorter and providing a second layer of hash security.
4
Checksum + Base58Check encoding: Prepend version byte, append first 4 bytes of SHA256d(payload), encode in Base58 (omitting ambiguous characters like 0, O, I, l). Produces a human-readable address starting with “1”.

Fig 2.14 — Bitcoin and Ethereum address derivation: parallel pipelines using different hash functions and encoding schemes

Ethereum takes a simpler approach: Keccak-256(public key) retaining only the last 20 bytes (160 bits), prefixed with “0x”. The EIP-55 checksum standard uses mixed-case encoding — each hex character is uppercased if the corresponding nibble of the hash is ≥ 8 — providing error detection without changing the address’s byte representation. A related but distinct innovation is Hierarchical Deterministic (HD) wallets (BIP-32/39/44): a single 12-word or 24-word mnemonic phrase generates a master key from which an unlimited tree of child keys can be derived deterministically. This means backing up one seed phrase backs up every address the wallet will ever generate.

Fig 2.15 — HD wallet key derivation tree (BIP-32/44): one seed phrase generates all child keys deterministically

RISK

Pitfalls: When Cryptography Fails in Practice

Cryptographic algorithms are rarely broken directly — their mathematical foundations remain sound. What fails is implementation: weak randomness, incorrect usage patterns, deprecated algorithm choices, and the ever-present threat of quantum computing. Each failure mode has caused real-world losses measured in millions of dollars.

Real-world cryptographic failures:
• Android Bitcoin wallet (2013): Java’s SecureRandom implementation on Android had a weak entropy pool on some devices. Attackers who recognized the pattern could narrow the private key space and brute-force wallets. Estimated losses: several hundred BTC.
• PlayStation 3 (2010): Sony used a constant k = 1 in all ECDSA signatures for their firmware. Two signatures with the same k and different messages algebraically reveal the private key. Fail Overflow published this at 27C3.
• Blockchain.info (2014): A random number generator failure in the browser produced insufficiently random signatures. Some private keys were recoverable.

Deprecated algorithms still in use:
• MD5: Practical collisions found in 1996, fully broken by 2004. Still found in legacy systems.
• SHA-1: Theoretical weaknesses since 2005; Google’s SHAttered attack produced the first known SHA-1 collision in 2017 (cost ~$110K). Deprecated by NIST.
• Both are unsuitable for any new blockchain application. SHA-256 and Keccak-256 remain secure against classical computers.
• Quantum threat: Grover’s algorithm halves effective key length (128-bit hash → 64-bit security). Shor’s algorithm breaks ECC entirely — NIST is standardizing post-quantum replacements.

Fig 2.16 — Timeline of cryptographic algorithm breaks: from MD5 to SHA-1 collisions and the quantum computing horizon

The quantum computing threat deserves nuanced treatment. A sufficiently powerful quantum computer running Shor’s algorithm could solve the elliptic curve discrete logarithm problem in polynomial time, breaking ECDSA entirely. Current quantum computers (2025) have at most a few thousand noisy physical qubits; estimates suggest millions of error-corrected logical qubits are needed to threaten secp256k1. NIST finalized its first post-quantum cryptography standards in 2024 (CRYSTALS-Kyber for key encapsulation, CRYSTALS-Dilithium and FALCON for signatures). Blockchain protocols will need migration paths, but the timeline is measured in years to decades, not months.

Fig 2.17 — Post-quantum cryptography timeline: NIST standardization and estimated threat horizon for current elliptic curve schemes

The cardinal rule of applied cryptography: Never implement cryptographic primitives yourself. Use well-audited, widely-deployed libraries — libsecp256k1 (used by Bitcoin Core), OpenSSL, or NaCl/libsodium. Even experienced cryptographers make subtle implementation errors. Rolling your own hash function or signature scheme guarantees vulnerabilities that attackers will find.

SO WHAT

Synthesis: How the Primitives Compose Into Blockchain Security

The four primitives — hash functions, digital signatures, elliptic curve keys, and Merkle trees — do not operate independently. They form a layered security system where each depends on the others’ properties. Understanding how they compose explains why blockchain security is qualitatively different from traditional database security.

Fig 2.18 — Hash collision probability vs output size: why 256-bit hashes provide astronomical collision resistance

Consider a Bitcoin transaction from end to end. Alice generates a 256-bit random private key using her wallet software. The wallet multiplies the secp256k1 generator G by that private key to produce a 512-bit public key. The public key is double-hashed (SHA-256 then RIPEMD-160) to produce a 20-byte address. Alice publishes this address as her receiving address. When she spends from it, she constructs a transaction, hashes the transaction data, and signs the hash with her private key using ECDSA. Every full node verifies the signature against her public key, confirms the transaction is valid, and adds it to their mempool. When a miner includes the transaction in a block, they construct a Merkle tree over all block transactions and place the root in the block header. The block header is then hashed in the proof-of-work loop until the result satisfies the network difficulty target. Every subsequent block’s header includes this block’s hash, chaining the entire history together.

The security argument in one sentence: Altering any past transaction requires forging a digital signature (computationally infeasible without the private key), then recalculating the block’s Merkle root (O(log n) hashes), then re-solving that block’s proof-of-work (currently ~500 exahashes/second on Bitcoin), then doing the same for every subsequent block, all while the honest network is extending the chain. The combination of these independently hard problems makes revision of history practically impossible.

Fig 2.19 — Multisignature schemes: m-of-n threshold signing for institutional custody and smart contract authorization

Advanced applications build on these foundations in sophisticated ways. Multisignature (multisig) schemes require k-of-n private keys to authorize a transaction, enabling shared custody without any single point of failure. Schnorr signatures (introduced to Bitcoin in Taproot, 2021) allow multiple signers to aggregate their signatures into a single, indistinguishable signature, enhancing privacy and reducing verification cost. Zero-knowledge proofs use hash functions and algebraic structures to allow one party to prove knowledge of a secret without revealing it — the foundation of Zcash, zk-rollups, and privacy-preserving smart contracts.

Fig 2.20 — Zero-knowledge proofs: proving knowledge of a secret without revealing the secret itself

The trajectory is clear: cryptography in blockchain is moving from single-party signing toward multi-party and threshold schemes, from privacy-transparent to privacy-preserving, and from classical security toward post-quantum hardness assumptions. The primitives you have studied in this lecture are the stable foundation; the frontier is how they are composed. In Lecture 03, we apply these tools directly to the Bitcoin protocol — the UTXO model, transaction scripts, and the mining puzzle that uses SHA-256 as its work function.

Download Slides & Resources

📄 5-Slide Teaser Executive summary 📄 10-Slide Standalone Self-contained overview 📄 Full Lecture (35 slides) Complete lecture deck 📄 Core Slides 10-slide summary 📄 Extended Slides Full detail version

Take the Quiz → View Slide Gallery Back to Course Overview