Paul Hammant's Blog: Merkle Trees In Pictures (assuming you know what a SHA1 hash is)

Earlier today I posted Old School Merkle Trees Rock. Not so much about ‘rocking’ this time, more about depictions of plain Merkle trees that are are not what you usually encounter online.

I regularly see a balanced representation of Merkle trees. This one is from wikipedia (today):

^ one node from two nodes, each from two more nodes, and each of those having some notion of content (‘block’ in this case).

Lack of symmetry (irregularity) and change over time

One trouble with that representation is that a lack of symmetry is normal in a Merkle tree, and that is not shown in this style of diagram.

Secondly, there’s no representation of change over time, and how Merkle hashes work in respect of that.

I’ll try for that (SVG inline):

Produced by OmniGraffle 7.4.2 2017-09-17 12:55:10 +0000 Canvas 2 Layer 1 A Merkle tree at rest A node changed, so its SHA1 should change After that its parent’s SHA1 should change too And finally then the root SHA1 should change X A node is deleted: its SHA1 should be deleted too And another added, meaning a new SHA1 is created for it Their parent’s SHA1 should change too And finally then the root SHA1 should change

Content as well as SHA1

Classic diagrams of Merkle trees don’t show content as something tangible. Often content isn’t represented at all.

I’ll recycle the picture from the other blog entry today:

Produced by OmniGraffle 7.4.2 2017-09-17 13:19:49 +0000 Canvas 3 Layer 1 a-document.xml another - document.doc SHA1 for that SHA1 for that yet-another - document.txt SHA1 for that something.txt SHA1 for that something- else.json SHA1 for that top-level.xls SHA1 for that SHA1 for that abc/ directory def/ directory SHA1 for that SHA1 for that interm- ediate directory SHA1 for the root ‘root’ directory

^ content can appear anywhere in a Merkle tree, and directories can be empty, too.

Merkle trees typically change below root at a fixed location.

Produced by OmniGraffle 7.4.2 2017-09-17 13:49:51 +0000 Canvas 4 Layer 1 Typical operations on a centralized Merkle tree is moving added, in to the move added (will look like a delete) address remains the same even if the hash changes

Note: Err, it appears that OmniGraffle is slightly messing of the <TEXT/> nodes of SVG. At least in Chrome, Firefox and Safari that’s true today. When that’s fixed, I’ll update the SVGs, but I think you can follow, and we have to put the knife in the PNG era sooner or later (where we can).

Firefox:

Chrome:

Safari:

And then, I couldn’t leave it as was … I went ahead and fixed it by hand

Published

September 17th, 2017
Reads:

Categories