Skip to content
LumenaryAcademy
Foundations 75 min

Hash functions, commitments and Merkle trees

The fingerprints every blockchain is built from — what a cryptographic hash promises, how to commit to a secret, and how one 32-byte root vouches for a million records.

Code tested · 6AI-draftedAwaiting review by a computer scientist

Your guides: Chloe · The Computer Scientist, Margaret · The Experimenter, Gideon · The Verifier

MotivationH

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.

DefinitionsH

What a hash function promises

A hash function HH maps inputs of any length to an nn-bit output (the digest); n=256n = 256 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 yy (of a random, unknown input), it is infeasible to find any xx with H(x)=yH(x) = y.
  • Second-preimage resistance: given an input xx, it is infeasible to find x′≠xx' \ne x with H(x′)=H(x)H(x') = H(x).
  • Collision resistance: it is infeasible to find any pair x≠x′x \ne x' with H(x)=H(x′)H(x) = H(x').

For an ideal nn-bit hash, the best generic attacks cost about 2n2^n evaluations for a preimage or a second preimage (try inputs until one hits the target) but only about 2n/22^{n/2} 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 AA finds second preimages for HH, then there is an algorithm, about as fast, that finds collisions for HH.

Proof

Pick any input xx and run AA on it. It returns x′≠xx' \ne x with H(x′)=H(x)H(x') = H(x), and the pair (x,x′)(x, x') 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.

ExplanationH

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 H(m)H(m) and the length of mm, anyone can compute H(m ∥ pad ∥ m′)H(m \,\|\, \text{pad} \,\|\, m') for a suffix m′m' of their choice without knowing mm. This length-extension property is why H(key ∥ message)H(\text{key} \,\|\, \text{message}) 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:

python
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])
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

DefinitionsH

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 mm, choose a random rr and publish c=Commit(m,r)c = \mathrm{Commit}(m, r). Open: reveal (m,r)(m, r); anyone checks that Commit(m,r)=c\mathrm{Commit}(m, r) = c. It must be

  • hiding: cc reveals nothing useful about mm;
  • binding: the committer cannot find a different (m′,r′)(m', r') that opens the same cc.

The hash commitment is c=H(r ∥ m)c = H(r \,\|\, m), with rr 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 H(m)H(m) can be opened by anyone in three tries. The random rr is what makes guessing hopeless: the attacker must now guess mm and 256 random bits together. (Strictly, hiding for hash commitments is proved by modelling HH 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.)

ComputationC

Birthdays and guesses, measured

How many random nn-bit digests must we draw before two coincide? With kk digests there are (k2)≈k2/2\binom{k}{2} \approx k^2/2 pairs, each colliding with probability 2−n2^{-n}, so the expected number of colliding pairs reaches about one when k≈2n/2k \approx 2^{n/2}. More precisely, the probability of no collision among kk digests is about e−k(k−1)/2n+1e^{-k(k-1)/2^{n+1}}, and the expected number of draws until the first collision is about π2⋅2n\sqrt{\tfrac{\pi}{2} \cdot 2^n}. Let us test that with SHA-256 cut down to 12, 16, 20 and 24 bits, and then try to open commitments by guessing:

python
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)
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The measured means sit close to π/2⋅2n\sqrt{\pi/2 \cdot 2^n} — 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 2\sqrt 2. The unsalted vote commitment falls to three guesses; the salted one does not, and it still opens correctly.

ComputationC

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.

root012345670123456701234567
A Merkle tree over eight records. To prove that record 5 is included, the prover sends its three siblings on the path to the root: leaf 4, node 67 and node 0123 (dashed). The verifier hashes record 5, combines it with each sibling in turn (the shaded path) and compares the result with the root it already trusts.

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 nn records the proof has at most ⌈log⁡2n⌉\lceil \log_2 n \rceil 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 H(0x00 ∥ record)H(\texttt{0x00} \,\|\, \text{record}) and an inner node as H(0x01 ∥ left ∥ right)H(\texttt{0x01} \,\|\, \text{left} \,\|\, \text{right}), 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.

python
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}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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 HH is collision-resistant and the verifier holds the correct root of a tree built from records d0,…,dn−1d_0, \ldots, d_{n-1}. If an attacker produces a proof that makes the verifier accept a record d′≠did' \ne d_i at position ii, then from that proof and the honest tree one can read off a collision in HH.

Proof

The verifier's computation walks from position ii 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 H(0x00 ∥ d′)H(\texttt{0x00} \,\|\, d') and the honest one is H(0x00 ∥ di)H(\texttt{0x00} \,\|\, d_i). At the top both equal the root. Take the lowest level at which the two values are equal. If it is the leaf level, d′≠did' \ne d_i 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.

∎

Worked examplesH

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:

python
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))
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

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.

ExplanationH

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 mm is a prefix of the tree of size nn, 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 misconceptionsH

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

Exercises

1. Hash functions, commitments and Merkle trees

Warm-upHuman

SHA-1 has a 160-bit output. For an ideal 160-bit hash, a generic collision search needs about 2k2^k evaluations. What is kk?

2. Hash functions, commitments and Merkle trees

Warm-upHuman

A 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?

Choose one

3. Hash functions, commitments and Merkle trees

CoreHuman

In 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.)

Choose all that apply

4. Hash functions, commitments and Merkle trees

CoreHuman

A 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

CoreComputational

Write 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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

6. Hash functions, commitments and Merkle trees

StretchComputational

naive_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.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Hash functions, commitments and Merkle trees

StretchHuman

A 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?

Choose one

Further reading and resources