Wat is een Merkle tree?

Korte samenvatting

✔️ Een Merkle tree deelt gegevens op, maakt hashwaarden van deze gegevens en voegt ze samen in een boomstructuur, wat efficiënte verificatie en overdracht mogelijk maakt.

✔️ De Merkle tree is uitgevonden door Ralph Merkle en is een boomdiagram dat wordt gebruikt voor gegevensintegriteit.

✔️ Merkle trees worden veel gebruikt in blockchain-technologieën zoals Bitcoin en Ethereum, waar ze helpen bij het valideren van transacties en het verminderen van de gegevensbelasting.

Wat is een Merkle tree?

Het concept van de Merkle tree is uitgevonden door Amerikaans wiskundige Ralph Merkle en gepatenteerd in 1979. De Duitse ex-bondskanselier heeft er dus niks mee te maken. Het werd omschreven in de paper “A certified digital signature”.

In de naam Merkle tree staat het laatste gedeelte voor boom. Dat is niet zomaar, het betreft hier namelijk een boomdiagram, oftewel een vertakkingsmodel, waarbij steeds meer takken leiden tot één hoofdtak. Het is vergelijkbaar met een stamboomvertakkingsmodel.

Een andere benaming voor de Merkle tree is de hash-boom. Een hash is een algoritmisch derivaat van een input, dat wil zeggen dat je uit bijvoorbeeld een woord (input) een hash kunt trekken (derivaat) door middel van een bepaald systeem van algoritmes.

Een heel bekend systeem is SHA (Secure Hash Algorithm) 256. Hierbij wordt uit een bepaalde input een hash getrokken van 256 bits. De uitkomst (output) wordt dan een reeks van 64 cijfers en letters.

Een typisch SHA 256 hash derivaat:

”Anycoindirect” heeft als output als je er SHA 256 op los laat:

98948d20dc70322d424ea5bbf37970e20b6aafa90c498116779ea964042c2c64

“anycoindirect” heeft als output:

a730a577d61512581afdd9c74e68abb2c43b0f7db3c70a92583464277b7abc81

Je ziet dat een enkele hoofdletter al alles verandert. Uit dit soort hashes wordt een boom opgemaakt. Net kerstmis, nietwaar?

Hoe werkt een Merkle tree?

Stel je wilt een boodschap of file sturen naar iemand anders, maar je wilt niet dat anderen mee kunnen kijken. Het kan dan gaan om geheime informatie, zoals een wachtwoord, maar ook om een file delen met belangrijke informatie. Dan kun je gebruik maken van een SHA 256 om de boodschap te encrypten.

Een boodschap wordt opgedeeld in stukjes en in een hash veranderd. Elke hash komt in de tree te staan, waarbij bovenaan de tree de root staat. Dit is de volledige boodschap of file. Een groot voordeel hierbij is, dat de boodschap opgedeeld kan worden in kleine stukjes, waardoor enorme files niet volledig door een enkele computer geleverd hoeven te worden en het veel sneller kan.

De boom wordt dus van onderop opgebouwd, ongeveer zoals je met Bittorrent doet. Iedereen heeft dan een klein stukje van de file (peer to peer netwerken) en bij de eindgebruiker worden alle kleine stukjes weer in elkaar gezet, waarna de boom weer compleet is. Vervolgens kan de eindgebruiker berekenen met zijn Merkle tree of alle stukjes origineel zijn (de hashes die berekend kunnen worden moeten dan overeenkomen met zijn tabel).

De root heeft een specifieke uitkomst, dus als je die weet, weet je ook of het bericht of de file origineel zijn. Zodra dat niet zo is zal er een hernieuwde poging worden gedaan om het origineel te ontvangen. Zodra de root tree en de output bij jou overeenkomen heb je de juiste informatie ontvangen.

Hierboven hebben we uitgelegd hoe je één hash maakt. In het boomdiagram worden een aantal van deze outputs samengevoegd en in een nieuwe hash gezet met dezelfde methode. Er komt dus, als je boven in de boom komt, steeds meer informatie te staan in een hogere hash. Totdat je bovenaan komt en alle hashes uit de boom samenvoegt tot 1 hash, waarna je klaar bent om de informatie te versturen.

De ontvanger van de boodschap krijgt de root tree medegedeeld en begint met het downloaden van de takken, de hashes. Deze takken kunnen van meerdere bronnen komen. Hierna gaat hij alle hashes in de boom reconstrueren. Elk onderdeel van de boom moet kloppen, zodra dat niet zo is klopt de root tree niet, maar via reconstructie kan hij bepalen welke gedeelte niet klopt. Meestal probeert hij dan nog eens de hele boom te downloaden.

Aangezien deze Merkle trees werken met binaire gegevens noemt men het ook wel binaire bomen.

Waar worden Merkle trees voor gebruikt in crypto?

Nu je weet dat je voor het checken van de juistheid van een hash eigenlijk alleen maar de root tree hoeft te weten, kun je je misschien voorstellen dat er systemen kunnen zijn die hier gebruik van maken.

Een belangrijke blockchain die hier gebruik van maakt is Bitcoin. Op deze blockchain moet veel informatie worden verwerkt in een block. Hoe minder informatie je hoeft te checken en in zo’n block hoeft te zetten, hoe beter.

Aangezien een Merkle tree een flink aantal gegevens kan samenvoegen tot een enkel getal is dat zeer handig bij het samenstellen van een block.

Stel je hebt in de afgelopen tien minuten (elke tien minuten ongeveer komt er een nieuw block bij op het Bitcoin netwerk) 200 transacties te verwerken gekregen als miner. De Merkle tree gaat dan aan de slag om al deze transacties te reduceren tot een enkele root tree.

Validatoren op het Bitcoin netwerk moeten de staat van de blockchain bijhouden, transacties valideren en nieuwe munten toevoegen. Als zij slechts 1 reeks hoeven te checken op juistheid zijn ze niet alleen veel sneller, maar is een block ook veel kleiner. Als 51% van deze miners het eens zijn dat de root tree klopt, kan het block toegevoegd worden.

Deze root tree hash wordt in het begin van het volgende block gezet, zodat alle miners weten wat de waarde is van de hash van het vorige block. Als ze een nieuw block maken zetten ze dus met een enkele cijferreeks de hele staat van het netwerk neer. Vervolgens komen er weer nieuwe transacties bij die hetzelfde proces doorlopen enzovoorts. Klopt de root tree niet, bijvoorbeeld omdat er malafide records tussen zitten, dan kunnen miners het ook niet eens worden en gaan ze op zoek naar een Merkle tree met de juiste root tree. Ook Ethereum maakt gebruik van een Merkle tree, maar die hebben natuurlijk weer iets speciaals uitgevonden: de Merkle Patricia tree.

Zouden netwerken geen gebruik maken van Merkle trees, dan moeten alle gegevens verzonden worden en je kunt je wel voorstellen wat dat voor de snelheid zou betekenen, laat staan de veiligheid.