Cryptographic primitives for decentralization

Every transaction gets hashed. Every pair of hashes gets combined into a new hash, one level up. Do that until only one hash is left — the root. Nothing here is fixed in place; if any transaction below changes, the specific hash sitting above it changes too, and so does everything above that.

This Part shares one concrete, deterministic hash function everywhere it's needed: toyHash(input), which returns a number in $[0, 1000)$, and toyHashPair(left, right), which combines two child hashes into a parent's. Real hash functions (SHA-256) return 256-bit numbers instead of one in $[0,1000)$, but behave the same way qualitatively — deterministic, and a one-character change in the input scrambles the output unpredictably (the avalanche effect).

1. Hash every transaction

   Leaf $i$'s hash is $h_i = \text{toyHash}(\text{tx}_i)$ — one hash per transaction, independent of every other transaction.

2. Combine pairs going up

   Each parent combines two children: $p_{i} = \text{toyHashPair}(h_{2i}, h_{2i+1})$. With 4 transactions that gives 2 parents.

3. Repeat until one hash remains — the root

   The root is the parents' parent: $\text{root} = \text{toyHashPair}(p_0, p_1)$. A block's entire set of transactions is now represented by exactly one number.

4. A digital signature binds one signer to one message

   A signature is a value only the holder of a private key can produce for a given message, and anyone who knows the corresponding public key can check. This chapter's toy version, $\text{toySign}(m, k)$, is symmetric rather than truly asymmetric — but it demonstrates the operational property that matters: change the key, or the message, and verification fails.

• $\text{tx}_i$ — the $i$-th transaction, as raw text.
• $h_i$ — that transaction's leaf hash, $\text{toyHash}(\text{tx}_i)$.
• $p_i$ — a parent hash, combining two children with $\text{toyHashPair}$.
• root — the single hash at the top, standing in for every transaction below it at once.

root = 577 — Alice's signature over the original message still verifies ✓

Tamper with transaction 0 and watch two things break at once: the Merkle root changes (anyone recomputing it from the transactions sees a mismatch instantly), and Alice's signature — computed over the original wording — no longer verifies against the tampered one. Two independent tripwires over the same data.

Four fixed transactions: alice pays bob 3, bob pays carol 1, carol pays dave 2, dave pays alice 1.

1. Hash each leaf

   • $h_0=\text{toyHash}(\texttt{"alice pays bob 3"})=459$
   • $h_1=\text{toyHash}(\texttt{"bob pays carol 1"})=416$
   • $h_2=\text{toyHash}(\texttt{"carol pays dave 2"})=636$
   • $h_3=\text{toyHash}(\texttt{"dave pays alice 1"})=976$
2. Combine into parents

   • $p_0=\text{toyHashPair}(459,416)=741$
   • $p_1=\text{toyHashPair}(636,976)=229$
3. Combine into the root

   $\text{root}=\text{toyHashPair}(741,229)=577$.

4. Now tamper with transaction 0

   Change it to alice pays bob 9:

   1. Its leaf hash becomes $465$ instead of $459$ — a one-character change, an unrelated-looking output
   2. Parent 0 becomes $\text{toyHashPair}(465,416)=808$ instead of $741$
   3. Parent 1 is untouched, still $229$, since it doesn't depend on $h_0$
   4. The root becomes $\text{toyHashPair}(808,229)=301$ — nowhere near the original $577$, even though only one transaction out of four changed