learn-blockchain-with-phoebe / Practitioner session 6 of 10
Learn Blockchain with Phoebe · Practitioner session 6 of 10

Merkle trees

Harbourgate's cold store has a handheld scanner on the loading bay. It has to answer one question about a consignment: is this record in the register, yes or no. It cannot hold the register, it cannot be sent the register, and it cannot phone somebody and take their word for it. Tonight is the structure that answers that question with a handful of hashes. Ten of them for a set of 1,024 records, and one of tonight's runs is a proof that fails, because a proof system you have never watched reject anything is not a proof system.

🟠 Working depth Engineers and data people Anyone designing a verifier 45 min
0-4 · Welcome 4-16 · The tree 16-28 · The proof 28-45 · Build-along and Q&A
Part 0

The question a scanner on a loading bay has to answer

There is a set of records and there is one record. You want to establish that the one is in the set. The obvious method is to send the whole set and let the checker look, and for four records that is fine. For a thousand it is absurd, and for a device with a small screen and a slow link it is impossible. The structure tonight removes almost all of that traffic and keeps the certainty, which is a rare combination and the reason this idea earns its place.

Live = presented in the 45 minutes Self-study = the full depth, after class 🔍 Every diagram zooms

★ What you walk out with tonight. The tree: hash every record, then hash pairs upward until one hash is left. The proof: the list of sibling hashes and nothing else, which is exactly log2 of the set size, so 1,024 records need 10. And a failing verification, run in front of you, so you have seen the structure say no.

Self-studyThe words that will keep coming back4 min▶
  • Leaf. The hash of one record. The bottom row of the tree, one leaf per record.
  • Parent. The hash of two children joined together. Every level halves the count.
  • Root. The single hash left at the top. One value standing for the whole set. CHAIN.merkleRoot(items).
  • Sibling. The hash next to yours at a given level. The thing you are missing and have to be told.
  • Proof. The ordered list of siblings from your leaf up to the root, each with the side it sits on. CHAIN.merkleProof(items, index).
  • Verification. Hash the record, fold in each sibling in order, compare the result with the root. CHAIN.verifyProof(item, path, root).
  • log2. How many times a number halves before it reaches 1. The proof length, exactly.
  • Inclusion. What a proof establishes: this record is in that set. Not that the set is right, and not that nothing is missing from it.
Part 1 · covers the tree

Hash the records, then hash the hashes

11 min live

Building the tree is two rules applied until they run out. Rule one: every record becomes its own hash. Rule two: take the hashes two at a time, join each pair and hash that, which halves the row. Repeat rule two until one hash is left. That last hash is the root, and changing any record anywhere below changes it.

Four records, two rules, one root Hash each record. Then hash pairs, halving the row, until one hash is left. RECORD 0 Consignment 41 signed over RECORD 1 Consignment 41 inspected RECORD 2 Consignment 41 released RECORD 3 Consignment 42 signed over H0 = hash(record 0) H1 = hash(record 1) H2 = hash(record 2) H3 = hash(record 3) H01 = hash(H0 + H1) H23 = hash(H2 + H3) ROOT = hash(H01 + H23) one hash standing for all four records Every level halves the row, so the height is log2 of the count. Four records give two levels, eight give three, 1,024 give ten. Change any record and every hash on the path above it changes, so the root changes, which is what makes one value stand for the whole set.
🔍 Click to zoom - the root is not a summary and not a compression. It is a value that is impossible to reproduce from a different set of records.
LiveWhy the root is worth one hash of storage4 min▶

A block can carry a root instead of carrying every record it covers. The block stays small and fixed in size no matter how many records are behind it, and the commitment is exactly as binding, because no different set of records produces that root. So a register of blocks can commit to a mountain of detail it never stores.

That is the everyday use, and it is the reason the structure turns up in places with no chain anywhere near them. Backup systems, package repositories and file synchronisers all use it for the same reason: one small value that cannot agree with the wrong data.

LiveWhat happens when the count is odd3 min▶

A row with an odd number of hashes cannot be paired off cleanly, and the engine here pairs the last hash with itself. That is one common convention and it keeps the arithmetic simple, which is why the sizes in tonight's table are all powers of two: the clean cases make the log2 relationship visible without a footnote on every row.

Conventions differ between implementations, and two verifiers that disagree about the odd case will disagree about the root of the same records. Same lesson as field order in session 2. The structure is standard; the details around its edges are decisions somebody has to write down.

Self-studyOrdering is part of what the root commits to3 min▶

Pairs are joined in a fixed order, left then right, so the same records in a different order give a different root. That is usually what you want, because the order of a custody register is part of what it says, and a root that ignored order would let two entries be swapped invisibly.

It also means a root cannot answer the question people most often want to ask next: is this record absent from the set. Inclusion is cheap and absence is not, and any system that needs to prove absence has to be designed for it from the start rather than have it bolted on.

Part 2 · covers the proof

The siblings you are missing, and nothing else

11 min live

To rebuild the root from one record you need that record and, at every level, the hash sitting next to yours. You can compute your own side. You cannot compute theirs, so theirs is what gets sent. That list is the proof, and it has one entry per level.

Proving record 2 is in the set, without the set Dark blue is computed by the holder. Amber is sent to them. Pale blue is rebuilt on the way up. H0 not sent, never seen H1 not sent, never seen H2 the holder hashes their own record H3 proof step 1 · sits on the right H01 proof step 2 · sits on the left H23 recomputed, not received ROOT the value the holder already trusts What travels: the record, then two hashes, in order. Step 1 is H3 and sits on the right. Step 2 is H01 and sits on the left. The side matters, because joining two hashes the wrong way round produces a different parent and the rebuilt root will not match. What does not travel: records 0, 1 and 3. The holder never sees them, so the rest of the register stays private and the traffic stays small.
🔍 Click to zoom - the proof is a list of things the verifier cannot work out for themselves. Everything they can work out, they do.
Live merkleRoot, merkleProof and verifyProof, running in this page. Switch the record to an altered one and watch it fail.

...

...
LiveWatch it say no4 min▶

Switch to the altered record. One word of the consignment line changes, the leaf hash it produces is unrecognisable, every parent computed from it is unrecognisable, and the root the verifier rebuilds does not match the root they hold. verifyProof returns false, with no partial credit and no near miss.

It is worth pressing that button before you trust anything the other button says. A verifier that only ever returns true is indistinguishable from a function that returns true, and that mistake has shipped in real systems more than once.

LiveWhat a passing proof establishes, exactly3 min▶

It establishes that this record was one of the records that produced that root. That is all, and it is a lot. It does not say the record is accurate, it does not say the set is complete, and it does not say the record is the most recent version of anything.

It also rests entirely on the root being the right root. The proof is a statement relative to a value the verifier already holds, and where that value came from is a separate question with a separate answer, which is the argument in the card two below.

Self-studyThe side of each sibling is part of the proof3 min▶

Each step in the path carries a hash and a side. Hashing your value joined to the sibling gives one result; hashing the sibling joined to your value gives a completely different one. A proof with the right hashes and the wrong sides fails exactly as hard as a proof with the wrong hashes.

Read the path in the live box and notice the sides changing as the index moves. An even index sits on the left and takes its sibling on the right; an odd index is the other way round. That alternation is the whole of the bookkeeping, and getting it wrong is the commonest bug in a first implementation.

Part 3 · covers the length

Ten hashes for a thousand records

8 min live

The proof has one entry per level, and the number of levels is the number of times the set halves before it reaches one. Double the records and the proof grows by exactly one hash. Every row below was measured against a real root, and every one of those proofs verified.

Proof length against set size, measured Every proof below was checked against its root with verifyProof. None was assumed. RECORDS IN THE SET PROOF STEPS HASHES IF YOU SENT EVERYTHING WHAT YOU SEND, OF WHAT EXISTS 4 2 4 2 of 4 8 3 8 3 of 8 16 4 16 4 of 16 64 6 64 6 of 64 256 8 256 8 of 256 1,024 10 1,024 10 of 1,024 Proof length is exactly log2 of the set size. Double the records and the proof grows by one hash. At 1,024 records the proof is 10 hashes, which is why a device that cannot hold the register can still check that its own consignment is in it.
🔍 Click to zoom - the right hand column is the one to remember. The set grows by doubling and the proof grows by one.
Live the table above, rebuilt in this browser. Each size builds a real root, takes a real proof and verifies it.

...

...
LiveThe scanner on the loading bay4 min▶

Give the handheld the root and nothing else. When a consignment arrives it receives that consignment's record and ten hashes, does eleven hash operations, and either matches the root or does not. It never holds the register, never asks anybody's opinion, and cannot be talked round.

That is the practical consequence worth carrying out of tonight. A device too small for the data can still verify its own slice of it, which is what makes the structure useful far outside this subject. Anywhere a small client needs certainty about a large set, this is the shape of the answer.

LiveWhy log2 and not something worse3 min▶

At each level your value has exactly one sibling, whatever the level and whatever the set size. So the proof needs one hash per level, and the levels are the halvings. Nothing about the set's content changes that, which is why the numbers in the table are exact rather than approximate.

It also means the cost of proving membership barely notices the set growing. Going from 256 records to 1,024 quadruples the register and adds two hashes to the proof, which is the sort of curve that makes an idea worth its complexity.

Self-studyWhere the disagreement really is4 min▶

One camp holds that this delivers genuine independence to a small client. The device checks membership for itself, with arithmetic it performs and can repeat, and never has to trust the party that sent the proof. Ten hashes buys a verification that used to require the whole register, and that is a real transfer of power to the edge of the system.

The other camp holds that the independence is partly staged. The proof is only ever a statement relative to a root, and the device did not derive that root, it was handed it. The hard question was never whether the record is under the root; it was which root is the current and correct one, and answering that still means trusting somebody or watching the whole register. On this reading the structure moved the trust rather than removing it.

Both are describing the same ten hashes. The disagreement is about whether a verifier that cannot choose its own root counts as independent, and it is worth deciding where you stand before you design one, because it changes what the device has to be told and how often.

Part 4 · covers verification

Recompute upward, then compare once

5 min live

Verification has no clever step in it. Hash the record. Fold in each proof hash on the side it says. Compare what you end up with against the root you already hold. One comparison, at the very end, and it is true or it is false.

The same four steps, twice. One record is as filed, one is not. THE RECORD AS FILED the record exactly as written hash it the leaf the tree used fold in each sibling on the side the step names root rebuilt matches the one held true THE SAME RECORD, ONE WORD CHANGED the record, edited one word different hash it a leaf no tree ever had fold in each sibling the same two hashes root rebuilt does not match false Nothing inspected the edit. The proof simply failed to reproduce the root. There is no partial match and no near miss, because the leaf of an edited record has no relationship to the leaf of the original, and every hash above it inherits that. One comparison at the top settles it. A verifier you have never watched return false is not yet evidence of anything when it returns true.
🔍 Click to zoom - the two pipelines are the same four operations. Only the first input differs, and the last comparison is where that shows up.
Part 5 · build-along

Prove it, then break it

14 min hands on

Console open on this page. Build a root, take a proof, verify it, then make it fail on purpose. The last step is the one that matters.

Consolevar ITEMS = []; for (var i = 0; i < 1024; i++) ITEMS.push("Cold store manifest line " + i); var root = CHAIN.merkleRoot(ITEMS); var path = CHAIN.merkleProof(ITEMS, 700); path.length path.map(function (s) { return s.side; }) CHAIN.verifyProof(ITEMS[700], path, root) CHAIN.verifyProof(ITEMS[700] + " amended", path, root) CHAIN.verifyProof(ITEMS[701], path, root)

Check the hash before you trust a root

Run CHAIN.selfTest().ok. A root is only worth as much as the hash under it, and this takes four seconds.

Count the proof, then predict the next one

Print path.length for 1,024 records and confirm it is 10. Before you run it, write down what you expect for 2,048 and for 512. Then check.

Read the sides

Print the side of each step for index 700, then for index 701. Two neighbouring records, two different patterns. Say why the first step flips while the later steps mostly do not.

Make it fail three different ways

Verify with an amended record, then with a different record from the same set, then with a proof for the wrong index. All three return false. A structure that rejects three different wrong things is worth more than one that accepts the right thing.

Change the set and keep the old proof

Add one record to the end, rebuild the root, and verify the old proof against it. It fails, because the root committed to a set that no longer exists. Write one sentence about what that means for any system where the set grows.

Compare the traffic honestly

For 1,024 records, count what a proof costs: one record and 10 hashes. Then count what sending the set costs. Write the ratio down and keep it for session 10, where the whole engine runs at once.

The habit to keep. When somebody shows you a verifier, ask them to make it fail in front of you. If they cannot produce a case that returns false, you have not been shown a verifier, you have been shown a function that agrees with you.

Check yourself

Three questions

A set holds 1,024 records. How many hashes does a proof of membership contain, and why?

Each level supplies exactly one sibling, whatever the size of the set, and the number of levels is the number of halvings. 1,024 halves to 512, 256, 128, 64, 32, 16, 8, 4, 2 and finally 1, which is ten steps. Proof length is exactly log2 of the set size, and every proof in tonight's table was verified against its root.

Somebody alters a record and then presents its original proof. What happens, and how?

Nothing inspects the edit and nothing holds a copy to compare against. The failure comes from arithmetic: an altered record gives a leaf with no relationship to the original, that difference propagates up every level, and the single comparison at the top does not match. No partial match and no near miss.

A handheld scanner verifies a proof successfully. What has it established, and what has it not?

Inclusion is the claim and it is narrow. The proof is a statement relative to the root the device already holds, and where that root came from is a separate question the proof cannot touch. Absence is not provable this way either, and accuracy was never in scope for any hash.

Before session 7

Homework

Twenty five minutes, on a set of records you already have.

Build a root over your own data

Take a few hundred rows from a table you work with, build a root, and take a proof for one row. Confirm the proof length is what log2 says it should be, and confirm an edited row fails.

Write down who hands out the root

For any system you would actually build this into, name the party that tells a verifier which root is current, and how often. Bring that name to session 7, because it turns out to be a question about identity rather than about hashing.

Covered tonight

What this session covers

✓Building the treeHash every record, hash pairs upward until one hash is left. merkleRoot driven live.
✓The proof as a list of siblingsOne hash per level, each with the side it sits on, and nothing else travels. merkleProof driven live.
✓Verification, including a failing caseverifyProof returns true on the record as filed and false on an altered one, both run in the page.
✓Proof length is log2 of the set size4 needs 2, 8 needs 3, 16 needs 4, 64 needs 6, 256 needs 8, and 1,024 records need 10.
◐Who tells a verifier which root is currentNamed tonight as the limit of an inclusion proof. Identity is session 7.
◐Proving a record is absent from a setNamed as a different and harder problem that has to be designed for from the start.
○Key management, rotation and certificate hygieneA discipline of its own, covered in the security and access control courses.
○Named commercial chains and their tree variantsThey move faster than a course can, and the structure tonight does not depend on which one.
Take this with you

Cheat sheet

The build. Hash every record, then hash pairs upward until one hash is left. That is the root.
The proof. One sibling hash per level, each with the side it sits on. Nothing else.
The length. Exactly log2 of the set size. 4 needs 2, 64 needs 6, 1,024 needs 10.
The calls. merkleRoot(items), merkleProof(items, i), verifyProof(item, path, root).
Verification. Hash, fold in each sibling on its side, compare once at the top.
The failure. An edited record gives an unrelated leaf, so the rebuilt root misses. No near miss.
The claim. This record is under that root. Not that it is accurate, complete, or current.
The use. A device too small to hold the register can still check its own consignment is in it.