One number that vouches for a million
Your phone runs a lightweight wallet. A shop in Nairobi says it has paid you, and points to a transaction in a block of a few thousand transactions. Your phone cannot download every block, so how can it check that the payment really is in that block? The answer is that the block's 80-byte header contains a single 32-byte number, the Merkle root, and the shop can send a short proof — a dozen hashes — that links your transaction to that root. If the proof checks out, the transaction is in the block, unless someone has broken SHA-256.
The same trick lets your browser check that a website's certificate was publicly logged (Certificate Transparency), lets Git name a whole project history with one hash, and lets Ethereum summarise the balance and code of every account in one root in each block header.
All of it rests on cryptographic hash functions. Applied cryptography introduced them; this lesson studies them as a blockchain engineer must: precisely what they promise, how the two families used in blockchains are built, how to use them to commit to a secret, and how to build, prove and break Merkle trees.
What a hash function promises
A hash function maps inputs of any length to an -bit output (the digest); for SHA-256, SHA3-256 and Keccak-256. Three properties matter, each defined by what an attacker cannot do in a feasible amount of computation.
Definition— Preimage, second-preimage and collision resistance
- Preimage resistance: given a digest (of a random, unknown input), it is infeasible to find any with .
- Second-preimage resistance: given an input , it is infeasible to find with .
- Collision resistance: it is infeasible to find any pair with .
For an ideal -bit hash, the best generic attacks cost about evaluations for a preimage or a second preimage (try inputs until one hits the target) but only about for a collision, because of the birthday effect measured below. So a 256-bit hash gives about 128 bits of collision resistance, and output lengths are chosen with that halving in mind.
Theorem— Collision resistance implies second-preimage resistance
If an algorithm finds second preimages for , then there is an algorithm, about as fast, that finds collisions for .
Proof
Pick any input and run on it. It returns with , and the pair is a collision. So a hash that resists collisions must also resist second preimages.
∎
The converse fails: a function can resist second preimages yet have collisions that are easy to find, and MD5 and SHA-1 are real examples. Practical MD5 collisions have been known since 2004, and the first SHA-1 collision, SHAttered, was published in 2017; second preimages for both remain out of reach. That is why "broken" needs qualifying: both are broken for any use where an attacker could choose both inputs, such as certificates, signatures and content addressing.
Two families: SHA-256 and Keccak
SHA-256 (in the SHA-2 family, standardised by NIST in 2002) processes its input in 512-bit blocks with a compression function, carrying a 256-bit state from block to block; the final state is the digest. This chaining design, the Merkle–Damgård construction, has a known quirk: given and the length of , anyone can compute for a suffix of their choice without knowing . This length-extension property is why is not a safe MAC (HMAC exists to fix it) and is one reason Bitcoin hashes block headers and transactions with SHA-256 applied twice, often written SHA-256d.
Keccak, designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche, won NIST's SHA-3 competition in 2012. It is a sponge: a 1600-bit state is split into a rate part, into which input blocks are XORed, and a hidden capacity part, with a fixed permutation, Keccak-f[1600], applied between blocks. Because the capacity is never output, length extension does not apply.
Here is the catch for blockchain engineers. Ethereum adopted Keccak in 2014, before NIST finished the standard. When NIST published SHA-3 as FIPS 202 in 2015, it changed one detail: the padding appended to the message, which in byte terms became 0x06 instead of the original 0x01, to separate SHA-3 from the related SHAKE functions. So Ethereum's Keccak-256 and NIST's SHA3-256 are the same permutation with different padding, and they give completely different outputs. Python's hashlib.sha3_256 is the NIST version. The program below implements the permutation from the specification, checks it against hashlib, and then changes only the padding byte:
import hashlib
def rol(v, n):
return ((v << n) | (v >> (64 - n))) & 0xFFFFFFFFFFFFFFFF
# Round constants and rotation offsets, generated as the Keccak specification describes.
RC, R = [], 1
for _ in range(24):
rc = 0
for j in range(7):
R = ((R << 1) ^ ((R >> 7) * 0x71)) % 256 # an 8-bit LFSR
if R & 2:
rc |= 1 << ((1 << j) - 1)
RC.append(rc)
ROT = [[0] * 5 for _ in range(5)]
x, y = 1, 0
for t in range(24):
ROT[x][y] = (t + 1) * (t + 2) // 2 % 64
x, y = y, (2 * x + 3 * y) % 5
def keccak_f(A):
"""The Keccak-f[1600] permutation on 25 lanes of 64 bits (A[x + 5*y])."""
for rnd in range(24):
C = [A[x] ^ A[x + 5] ^ A[x + 10] ^ A[x + 15] ^ A[x + 20] for x in range(5)]
D = [C[(x - 1) % 5] ^ rol(C[(x + 1) % 5], 1) for x in range(5)]
A = [A[i] ^ D[i % 5] for i in range(25)] # theta
B = [0] * 25
for x in range(5):
for y in range(5):
B[y + 5 * ((2 * x + 3 * y) % 5)] = rol(A[x + 5 * y], ROT[x][y]) # rho, pi
A = [B[i] ^ (~B[(i + 1) % 5 + 5 * (i // 5)] & B[(i + 2) % 5 + 5 * (i // 5)])
for i in range(25)] # chi
A[0] ^= RC[rnd] # iota
return A
def sponge_256(data, pad_byte):
"""A sponge with a 1088-bit rate and 256-bit output; only the padding byte varies."""
rate = 136
msg = bytearray(data) + bytes([pad_byte])
msg += bytes(-len(msg) % rate)
msg[-1] |= 0x80
A = [0] * 25
for off in range(0, len(msg), rate):
for i in range(rate // 8):
A[i] ^= int.from_bytes(msg[off + 8 * i: off + 8 * i + 8], "little")
A = keccak_f(A)
return b"".join(A[i].to_bytes(8, "little") for i in range(4)).hex()
def sha3_256(data): return sponge_256(data, 0x06) # NIST FIPS 202 (2015)
def keccak_256(data): return sponge_256(data, 0x01) # the 2011 Keccak submission, used by Ethereum
for msg in [b"", b"abc", b"Lumenary" * 40]:
print(f"{len(msg):3}-byte input SHA3-256 matches hashlib: {sha3_256(msg) == hashlib.sha3_256(msg).hexdigest()}")
print("SHA3-256(\"\") =", sha3_256(b""))
print("Keccak-256(\"\") =", keccak_256(b""))
print("SHA-256(\"\") =", hashlib.sha256(b"").hexdigest())
sig = b"transfer(address,uint256)"
print("first 4 bytes of Keccak-256(transfer(address,uint256)):", keccak_256(sig)[:8])
print("first 4 bytes of SHA3-256 of the same string: ", sha3_256(sig)[:8])Our SHA3-256 agrees with hashlib on all three inputs, so the permutation is right; Keccak-256 of the empty string comes out as c5d24601…5d85a470, a constant that appears throughout Ethereum's code as the hash of empty contract code. The last two lines show why the difference matters in practice: Ethereum identifies a contract function by the first four bytes of the Keccak-256 hash of its signature, and a9059cbb is the well-known selector of the token-transfer function. A library that silently used SHA3-256 would compute 4b40e901 and call nothing.
Commitments: sealed envelopes made of hashes
A commitment scheme is the digital version of writing a choice on paper, sealing it in an envelope and handing it over: later you open the envelope and everyone can see you did not change your mind. Blockchains use commitments for sealed-bid auctions, for fair random-number generation (each party commits to a random value, then all reveal), and inside the proof systems of the last level of this course.
Definition— Commitment scheme
A commitment scheme has two steps. Commit: to commit to a message , choose a random and publish . Open: reveal ; anyone checks that . It must be
- hiding: reveals nothing useful about ;
- binding: the committer cannot find a different that opens the same .
The hash commitment is , with a fresh random string of at least 256 bits.
Binding follows from collision resistance: two different openings of one commitment are a collision. Hiding is subtler, and it is where people go wrong. A hash hides nothing about an input that can be guessed. If the message is a vote — yes, no or abstain — then can be opened by anyone in three tries. The random is what makes guessing hopeless: the attacker must now guess and 256 random bits together. (Strictly, hiding for hash commitments is proved by modelling as a random function, the random-oracle model; commitments built on algebra, such as the Pedersen commitments of the Verifiable level, can be hiding unconditionally.)
Birthdays and guesses, measured
How many random -bit digests must we draw before two coincide? With digests there are pairs, each colliding with probability , so the expected number of colliding pairs reaches about one when . More precisely, the probability of no collision among digests is about , and the expected number of draws until the first collision is about . Let us test that with SHA-256 cut down to 12, 16, 20 and 24 bits, and then try to open commitments by guessing:
import hashlib, math, random
def truncated(data, bits):
"""The first `bits` bits of SHA-256: a deliberately weak hash for experiments."""
return int.from_bytes(hashlib.sha256(data).digest(), "big") >> (256 - bits)
def hashes_until_collision(bits, trial):
seen = set()
for i in range(1, 1 << bits):
h = truncated(f"trial {trial} message {i}".encode(), bits)
if h in seen:
return i
seen.add(h)
print("bits trials mean hashes to first collision sqrt(pi/2 * 2^bits) 2^bits (preimage)")
for bits, trials in [(12, 400), (16, 200), (20, 60), (24, 200)]:
mean = sum(hashes_until_collision(bits, t) for t in range(trials)) / trials
print(f"{bits:4} {trials:7} {mean:31.0f} {math.sqrt(math.pi / 2 * 2**bits):20.0f} {2**bits:18,}")
# Commitments: an unsalted hash of a vote can be "opened" by anyone, by guessing.
votes = ["yes", "no", "abstain"]
c = hashlib.sha256(b"no").hexdigest()
print("\ncommitment to a secret vote:", c[:24] + "...")
print("an observer tries all three votes:", [v for v in votes if hashlib.sha256(v.encode()).hexdigest() == c])
rng = random.Random(2026) # demo only: real code uses secrets.token_bytes(32)
r = rng.randbytes(32)
c = hashlib.sha256(r + b"no").hexdigest()
print("with a 256-bit random r: ", c[:24] + "... (guessing now means guessing r)")
print("opening (r, 'no') checks out: ", hashlib.sha256(r + b"no").hexdigest() == c)The measured means sit close to — about 80 for 12 bits and about 5,000 for 24 bits — while a preimage for a 24-bit hash would take on the order of 16.8 million tries. Each extra bit of output doubles the preimage cost but multiplies the collision cost by only . The unsalted vote commitment falls to three guesses; the salted one does not, and it still opens correctly.
Merkle trees and inclusion proofs
A Merkle tree, invented by Ralph Merkle in 1979, hashes a list of records pairwise, then hashes the results pairwise, and so on, until one hash, the root, remains. The root commits to the entire list in order: change any record and the root changes.
An inclusion proof (or Merkle path) for one record is the list of sibling hashes along the path from its leaf to the root. The verifier, who knows only the root, the record, its position and the tree size, recomputes the path and compares. For records the proof has at most hashes.
Two design choices make the tree safe, and we will see in the next section what goes wrong without them. First, domain separation: a leaf is hashed as and an inner node as , so a leaf can never be confused with an inner node. Second, when a level has an odd number of nodes, the last one is promoted unchanged to the next level rather than paired with a copy of itself. This is the tree of Certificate Transparency (RFC 6962), and the program checks that the level-by-level construction gives the same root as the RFC's recursive definition.
import hashlib
def leaf_hash(data):
return hashlib.sha256(b"\x00" + data).digest() # 0x00: "this is a leaf"
def node_hash(left, right):
return hashlib.sha256(b"\x01" + left + right).digest() # 0x01: "this is an inner node"
def levels(leaves):
"""All levels of the tree, leaves first. A lone last node is promoted unchanged."""
level = [leaf_hash(d) for d in leaves]
out = [level]
while len(level) > 1:
nxt = [node_hash(level[i], level[i + 1]) for i in range(0, len(level) - 1, 2)]
if len(level) % 2:
nxt.append(level[-1])
out.append(nxt)
level = nxt
return out
def root(leaves):
return levels(leaves)[-1][0]
def prove(leaves, index):
"""The sibling hashes on the path from leaf `index` to the root, bottom first."""
proof = []
for level in levels(leaves)[:-1]:
sibling = index ^ 1
if sibling < len(level):
proof.append(level[sibling])
index //= 2
return proof
def verify(data, index, size, proof, expected_root):
h, proof = leaf_hash(data), list(proof)
while size > 1:
if index % 2 == 1:
h = node_hash(proof.pop(0), h)
elif index + 1 < size:
h = node_hash(h, proof.pop(0))
# else: a promoted node, nothing to combine with at this level
index, size = index // 2, (size + 1) // 2
return not proof and h == expected_root
txs = [f"tx{i}: {a} pays {b} {n}".encode() for i, (a, b, n) in enumerate([
("Aiko", "Bola", 5), ("Bola", "Carmen", 2), ("Dmitri", "Aiko", 7), ("Esra", "Femi", 1),
("Femi", "Gita", 3), ("Gita", "Hamid", 4), ("Hamid", "Ines", 9)])]
r = root(txs)
print("root of 7 transactions:", r.hex()[:32] + "...")
for i in [0, 4, 6]:
p = prove(txs, i)
print(f"proof for tx{i}: {len(p)} hashes, verifies: {verify(txs[i], i, len(txs), p, r)}")
p = prove(txs, 3)
print("tx3 with a changed amount: ", verify(b"tx3: Esra pays Femi 100", 3, len(txs), p, r))
print("tx3's proof used for index 2:", verify(txs[3], 2, len(txs), p, r))
# The same construction matches RFC 6962's recursive definition, which splits at the largest power of two.
def mth(d):
if len(d) == 1:
return leaf_hash(d[0])
k = 1 << ((len(d) - 1).bit_length() - 1)
return node_hash(mth(d[:k]), mth(d[k:]))
many = [f"leaf {i}".encode() for i in range(100)]
same = all(root(many[:n]) == mth(many[:n]) for n in range(1, 101))
print("same root as RFC 6962's recursive definition, for 1 to 100 leaves:", same)
for n in [1_000, 100_000]:
leaves = [f"leaf {i}".encode() for i in range(n)]
p = prove(leaves, n // 3)
ok = verify(leaves[n // 3], n // 3, n, p, root(leaves))
print(f"{n:>7,} leaves: a proof has {len(p)} hashes ({32 * len(p)} bytes), verifies: {ok}")Every honest proof verifies; the proof for transaction 6, a promoted leaf in a tree of seven, needs only two hashes. A changed record fails, and so does a correct record presented at the wrong position, because left and right are hashed in order. A proof for one of 100,000 records is 17 hashes, 544 bytes.
Theorem— Soundness of inclusion proofs
Suppose is collision-resistant and the verifier holds the correct root of a tree built from records . If an attacker produces a proof that makes the verifier accept a record at position , then from that proof and the honest tree one can read off a collision in .
Proof
The verifier's computation walks from position to the root, computing one hash per level; the honest tree has a value at each of those positions. At the leaf, the verifier's value is and the honest one is . At the top both equal the root. Take the lowest level at which the two values are equal. If it is the leaf level, hash to the same value: a collision. Otherwise, one level below, the two computations had different values, and at this level each is the hash of a prefix byte, a left child and a right child. The hashed inputs differ (they contain different child values in the same position), yet the outputs are equal: a collision. Domain separation guarantees that the inputs being compared are of the same kind, so a leaf can never be passed off as a node.
∎
Odd leaves and second preimages: how naive trees break
Bitcoin's Merkle tree, designed in 2008, does neither of the two things above. It hashes leaves and inner nodes the same way, and when a level has an odd number of nodes it duplicates the last one. Both choices have caused real problems. The program below builds a tree the naive way (with single SHA-256 for brevity; Bitcoin uses SHA-256d) and attacks it:
import hashlib
def H(b):
return hashlib.sha256(b).digest()
def naive_root(leaves):
"""No domain separation, and an odd level duplicates its last node (Bitcoin's rule, with one SHA-256)."""
level = [H(d) for d in leaves]
while len(level) > 1:
if len(level) % 2:
level = level + [level[-1]]
level = [H(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
return level[0]
block = [b"coinbase: 3.125 to Lerato", b"Wanjiru pays Tomas 1", b"Tomas pays Yuki 2"]
# Problem 1: duplication. A list with its last element repeated has the same root.
print("3 leaves vs the same with the last repeated, same root:",
naive_root(block) == naive_root(block + block[-1:]))
# Problem 2: an inner node is just 64 bytes, and a leaf can be any bytes.
four = [b"Ama pays Kwame 1", b"Kwame pays Esi 2", b"Esi pays Yaw 3", b"Yaw pays Ama 4"]
fake = [H(four[0]) + H(four[1]), H(four[2]) + H(four[3])] # two 64-byte "transactions"
print("4 real leaves vs 2 forged 64-byte leaves, same root: ", naive_root(four) == naive_root(fake))
print("the forged leaves look like:", fake[0].hex()[:32] + "...", len(fake[0]), "bytes")
def safe_root(leaves):
"""The fix: prefix leaves with 0x00 and inner nodes with 0x01, and promote a lone node."""
level = [H(b"\x00" + d) for d in leaves]
while len(level) > 1:
nxt = [H(b"\x01" + level[i] + level[i + 1]) for i in range(0, len(level) - 1, 2)]
level = nxt + level[-1:] if len(level) % 2 else nxt
return level[0]
print("with domain separation:", safe_root(block) == safe_root(block + block[-1:]),
safe_root(four) == safe_root(fake))Duplication. A list of three transactions and the same list with the third repeated have the same root. In 2012 this was found to let an attacker take a valid block, duplicate its last transactions to make an invalid block with the same header hash, and send it to nodes that would then mark that header as invalid and refuse the real block when it arrived (CVE-2012-2459). Bitcoin Core fixed it by detecting such duplications, because changing the tree itself would have required changing the consensus rules.
Second preimages of the tree. An inner node is the hash of 64 bytes, and nothing stops a 64-byte string from being presented as a leaf. Concatenating the hashes of leaves 0 and 1, and of leaves 2 and 3, gives two forged "records" whose tree has exactly the root of the original four. In Bitcoin, a transaction that happens to be 64 bytes long is therefore ambiguous to a light client that sees only a Merkle path. Today such transactions are non-standard (nodes do not relay them), and a "consensus cleanup" soft fork under discussion as of 2026 would make them invalid.
The domain-separated tree defeats both attacks, as the last line shows. The general lesson, which you will meet again in signatures and proof systems: whenever a hash is used for more than one kind of object, tag each kind so that one can never be reinterpreted as another.
Merkle structures in practice
- Block headers. A Bitcoin header is 80 bytes: version, the previous header's hash, the Merkle root of the block's transactions, a timestamp, the difficulty target and a nonce. Light clients use simplified payment verification, described in section 8 of Nakamoto's paper: download headers only and check Merkle paths. How a light client finds its transactions without revealing them to the server is its own problem; the compact block filters of BIP 157 and BIP 158 replaced an earlier design that leaked users' addresses.
- Git. Every file, directory and commit is stored under the hash of its contents, and a directory lists its children's hashes, so a commit hash commits to the whole project history: a Merkle DAG (a directed acyclic graph rather than a tree). Git used SHA-1, now with collision detection after SHAttered; since version 2.29 (2020) it can also use SHA-256 for new repositories.
- Certificate Transparency. Certificate authorities must log every certificate in public, append-only Merkle-tree logs before browsers will accept it. Besides inclusion proofs, CT logs serve consistency proofs, which show that the tree of size is a prefix of the tree of size , so a log cannot quietly rewrite its past. The same idea protects Go's module checksum database and Sigstore's software-signing log: verifiable logs without any blockchain.
- Ethereum's state. Ethereum's state — every account's balance, nonce, code and storage — lives in a Merkle–Patricia trie: a radix trie, keyed by the Keccak-256 hash of the address, whose nodes are hashed so that one state root in each block header commits to all of it. Each header also has roots for the block's transactions and receipts. Every node of the trie can have 16 children, so a proof for one account must include up to 15 sibling hashes per level, typically a few kilobytes.
- Verkle and binary trees. Proof size matters for stateless clients, which would verify blocks using proofs (witnesses) of just the state they touch, instead of storing the whole state. Verkle trees (proposed by John Kuszmaul in 2018) replace hashes with vector commitments from elliptic-curve cryptography, shrinking witnesses greatly; they were Ethereum's plan for several years. In 2025 developers also proposed a binary Merkle tree with a hash function chosen to be cheap inside zero-knowledge proofs (EIP-7864), partly because Verkle trees' elliptic-curve commitments would not survive quantum computers. As of 2026 the choice is still under discussion; ethereum.org's roadmap tracks it.
Common misconceptions
Misconception
"Hashing data hides it." A hash hides an input only if the input is hard to guess. Hashes of phone numbers, votes, dates of birth or small amounts can be reversed by trying every possibility, as the unsalted commitment showed. To hide, add a long random value and keep it secret until you open.
Misconception
"SHA3-256 and Keccak-256 are the same thing." They share the permutation but not the padding, so every output differs. Use Keccak-256 for Ethereum addresses, function selectors and storage slots, and SHA3-256 where a standard asks for SHA-3.
Misconception
"A Merkle proof shows that a record is valid." It shows only that the record is in the committed list, at that position. Whether the list itself is legitimate — whether the block followed the rules, whether the log is honest — must be established some other way: consensus, signatures on the root, or consistency proofs.
Misconception
"A 256-bit hash gives 256 bits of security." Against preimages, yes; against collisions, only 128, because of the birthday bound. When collisions matter, the output must be twice as long as the security level wanted.
Exercises
1. Hash functions, commitments and Merkle trees
Warm-upHumanSHA-1 has a 160-bit output. For an ideal 160-bit hash, a generic collision search needs about evaluations. What is ?
2. Hash functions, commitments and Merkle trees
Warm-upHumanA developer writes a tool that computes Ethereum function selectors (the first 4 bytes of the hash of a signature such as transfer(address,uint256)) using Python's hashlib.sha3_256. What happens?
3. Hash functions, commitments and Merkle trees
CoreHumanIn a sealed-bid auction, each bidder publishes a commitment to a bid, a whole number of euros between 1 and 1,000,000, and opens it after bidding closes. Which commitments hide the bid from other bidders? Select all that apply. (r denotes fresh random bytes from secrets.token_bytes.)
4. Hash functions, commitments and Merkle trees
CoreHumanA domain-separated Merkle tree like the lesson's is built over 1,000,000 records. What is the largest number of hashes an inclusion proof for one record can contain?
5. Hash functions, commitments and Merkle trees
CoreComputationalWrite verify(data, index, size, proof, root) for the lesson's Merkle tree: leaves are leaf_hash(data), inner nodes node_hash(left, right) (both provided, with domain separation), and a lone last node on a level is promoted to the next level unchanged. proof lists the sibling hashes from the bottom up, with no entry for a level where the node was promoted.
Return True only if the proof shows that data is record number index (counting from 0) of a tree of size records with this root. Reject an index out of range, and reject a proof with too few or too many hashes.
6. Hash functions, commitments and Merkle trees
StretchComputationalnaive_root (provided) builds a Merkle tree the naive way: no domain separation, and an odd level duplicates its last node. Write forge(leaves) that, for any list of at least two leaves, returns a different list of byte strings, none of them equal to an original leaf, with the same naive_root. This is the second-preimage weakness the lesson demonstrated for four leaves; make it work for any length.
7. Hash functions, commitments and Merkle trees
StretchHumanA service authenticates API requests with tag = SHA-256(secret_key + request). An attacker sees one request and its tag but not the key. Which statement is correct?
Further reading and resources
- FIPS 180-4: Secure Hash Standard (SHA-1 and SHA-2) · NIST · 2015
- FIPS 202: SHA-3 Standard · NIST · 2015
- The Keccak team's websiteSpecifications, reference code and design notes from Keccak's designers.
- RFC 6962: Certificate Transparency · 2013Section 2.1 defines the domain-separated Merkle tree used in this lesson, with inclusion and consistency proofs.
- RFC 9162: Certificate Transparency Version 2.0 · 2021
- Certificate TransparencyHow the logs, monitors and browsers fit together.
- Ethereum: Merkle Patricia Trie
- Ethereum: Verkle trees
- EIP-7864: Ethereum state using a unified binary treeA 2025 proposal to replace the hexary trie with a binary Merkle tree instead of a Verkle tree.
- Git: hash function transition
- SHAttered: the first SHA-1 collision · 2017
- A Certified Digital Signature · Ralph C. Merkle · 1989Merkle's tree of hashes, first described in his 1979 thesis and patent (Advances in Cryptology, CRYPTO '89).