Merkle Trees en Merkle Roots uitgelegd
StartpaginaArtikelen

Merkle Trees en Merkle Roots uitgelegd

Geavanceerd
1w ago
7m

Wat is een Merkle Tree?

Het concept van Merkle Trees werd in de vroege jaren tachtig voorgesteld door Ralph Merkle, een computerwetenschapper die bekend staat om zijn werk aan public-key cryptografie.
Een Merkle Tree is een structuur die wordt gebruikt om de integriteit van de gegevens in een set op een efficiënte manier te verifiëren. Zeker in de context van peer-to-peer-netwerken is dit interessant, omdat deelnemers constant informatie met elkaar delen en die onafhankelijk moeten kunnen valideren.
Hashfuncties vormen de kern van Merkle Tree-structuren. Lees daarom ook vooral ons artikel Wat is hashing? als je hier meer over wilt weten.


Hoe werken Merkle Trees?

Stel je voor dat je een groot bestand wilt downloaden. Met behulp van open-source software kun je controleren of de hash van het bestand dat je hebt gedownload, overeenkomt met de hash die de ontwikkelaars hebben gepubliceerd. Is dit het geval, dan weet je dat het bestand dat op je computer staat identiek is aan dat van hun.

Als de hashes niet hetzelfde zijn, dan heb je een probleem. Je hebt in dat geval misschien een kwaadaardig bestand gedownload dat zich voordoet als legitieme software of misschien is je download corrupt geraakt, waardoor de software niet naar behoren werkt. In dat geval zul je waarschijnlijk best geïrriteerd zijn, zeker als je lang hebt moeten wachten tot de download klaar was. Nu moet je het bestand opnieuw downloaden en hopen dat het dit keer wel goed gaat.

Was er maar een makkelijkere manier om dit te doen, denk je bij jezelf. Hier komen Merkle Trees van pas. Met een Merkle Tree zou je bestand opgebroken zijn in stukjes. Stel dat je bestand 50 GB groot was, dan kun je het bijvoorbeeld in 100 stukjes opdelen van elk 0,5 GB groot. Daarna zou je die één voor één hebben gedownload. In feite is dit precies hoe torrents werken. 
In dit geval zou de bron waaruit je download je een hash hebben gegeven, de zogenaamde Merkle Root. Deze hash vertegenwoordigt ieder stukje data waaruit je bestand bestaat. Dankzij de Merkle Root is het veel eenvoudiger om de integriteit van de gegevens te controleren. 
Om het simpel te houden gebruiken we een voorbeeld waarin we een bestand van 8 GB opbreken in acht stukken, die we aanduiden met A tot en met H. Elk fragment wordt vervolgens door een hash gehaald, waardoor we uiteindelijk acht verschillende hashes hebben.


We halen elk van onze acht fragmenten door een hashfunctie om hun hashes te verkrijgen.


Oké, nu hebben we iets waarmee we kunnen werken: de hash van alle fragmenten. Als er met één van deze fragmenten iets aan de hand is, dan kunnen we dat te weten komen door de hashes van de fragmenten te vergelijken. Toch? Ja, dat kan. Dit is echter ongelooflijk inefficiënt. Als je bestand is opgedeeld in duizenden fragmenten, ga je elk van deze fragmenten dan hashen en de resultaten ervan zorgvuldig met elkaar vergelijken?

Nee. In plaats daarvan nemen we een aantal hashes en hashen we deze combinatie nog een keer. In onderstaande afbeelding hashen we hA + hB, hC + hD, hE + hF en hG + hH. We eindigen dan met vier hashes, waarna we dit proces nog eens herhalen om op twee hashes uit te komen. Tot slot hashen we deze twee hashes nog een keer om onze master hash te krijgen: de Merkle Root of de root hash.


De structuur ziet eruit als een boom, maar dan ondersteboven. Op de onderste rij hebben we de bladeren, die we met elkaar combineren in takken tot we uiteindelijk bij de wortel uitkomen.


We hebben nu de Merkle Root die het bestand vertegenwoordigt dat we downloaden. We kunnen deze root hash vergelijken met de hash die we van de bron hebben gekregen. Zijn die hetzelfde? Perfect! Als de hashes van elkaar verschillen, dan weten we dat er iets met de data is gebeurd. Met andere woorden, er zijn één of meer fragmenten die een andere hash hebben geproduceerd. Een kleine aanpassing van de gegevens leidt namelijk tot een volledig andere Merkle Root.

Gelukkig kunnen we eenvoudig controleren waar het is misgegaan. Stel dat dat in ons geval bij fragment hE was. Eerst vraag je een peer om de twee hashes die de Merkle Root hebben geproduceerd (hABCD en hEFGH). De waarde die jij hebt voor hABCD moet hetzelfde zijn als die van de peer, omdat er geen fouten in de onderliggende hashes zitten. Als de hashes van hEFGH echter niet hetzelfde zijn, dan weet je dat er hier een fout in is geslopen. Vervolgens vraag je de hashes van hEF en hGH op en vergelijk je die met je eigen hashes. hGH klopt, dus nu weet je dat de fout in hEF zit. Ten slotte vergelijk je de hashes van hE en hF, waarna je erachter komt dat hE onjuist is en je dit fragment opnieuw downloadt.

Samengevat wordt een Merkle Tree gecreëerd door gegevens in verschillende stukjes op te delen, die vervolgens meerdere keren worden gehashed om de Merkle Root te vormen. Vervolgens kun je op een efficiënte manier controleren of alle gegevens correct zijn. In het volgende hoofdstuk bespreken we een aantal andere interessante toepassingen van Merkle Trees.



Wil je aan de slag met cryptocurrency? Koop Bitcoin op Binance!



Waarom maakt Bitcoin gebruik van Merkle Roots?

Er zijn diverse use cases voor Merkle Trees, maar in dit artikel richten we ons op de toepassing ervan in blockchains. Merkle Trees zijn een essentieel onderdeel van Bitcoin en veel andere cryptocurrencies en vormen een integraal onderdeel van ieder block, waar ze zijn opgenomen in de block header. Om tot de bladeren van onze boom te komen, gebruiken we de transactiehash (het TXID) van elke transactie die het block bevat. 

De Merkle Root dient in dit geval een aantal doeleinden. We gaan hier dieper in op hun toepassing bij het minen van cryptocurrency en het verifiëren van transacties.


Mining

Een Bitcoin-block bestaat uit twee delen. Het eerste deel is de block header, een vast segment dat de metadata van het block bevat. Het tweede segment is een variabel overzicht van alle transacties in het block. Vaak is dit segment een stuk groter dan de block header.
Miners moeten gegevens herhaaldelijk hashen om een output te genereren die voldoet aan bepaalde voorwaarden, waarna ze een geldig block produceren. Er kunnen echter miljoenen pogingen overheen gaan voordat de juiste hash wordt gevonden. Bij iedere nieuwe poging wordt er een willekeurig nummer in de block header aangepast (de nonce) om tot een andere output te komen. De rest van het block blijft grotendeels hetzelfde. Het kan duizenden transacties bevatten, die iedere keer opnieuw gehashed moeten worden.

Een Merkle Root maakt dit proces een stuk eenvoudiger. Voor het minen maak je een overzicht van alle transacties die je in de hash wilt opnemen en stel je op basis daarvan een Merkle Tree op. De resulterende hash (van 32 bytes) neem je op in de block header. Vervolgens hoef je alleen de block header te hashen om tot de juiste output te komen in plaats van het hele block.

Dit werkt omdat er niet met het resultaat geknoeid kan worden: in feite maak je een compacte samenvatting van alle transacties in het block. Het is onmogelijk om na het vinden van een geldige block header de transacties aan te passen, omdat de Merkle Root hierdoor zal veranderen. Als het block vervolgens naar de andere nodes wordt verstuurd, kunnen zij de Merkle Root berekenen op basis van de transacties in het block. Komt die niet overeen met de hash van de block header, dan wordt het block geweigerd.


Verificatie

Merkle Roots hebben ook een andere interessante eigenschap waarvan we kunnen profiteren. Deze heeft betrekking op de light nodes (nodes die geen volledige kopie van de blockchain synchroniseren). Als je een node draait op een apparaat met weinig rekenkracht, dan wil je niet constant alle transacties downloaden en hashen. Wat je in plaats daarvan kunt doen is om een Merkle Proof vragen: bewijs, geleverd door een full node, dat je transactie is opgenomen in een bepaald block. Vaak wordt dit aangeduid als Simplified Payment Verification of SPV. In het Bitcoin-whitepaper beschreef Satoshi Nakamoto dit in uitgebreid detail.


Om hD te controleren, hebben we alleen de rode hashes nodig.


Stel je een scenario voor waarin we meer willen weten over de transactie met TXID hD. Als we hC weten, dan kunnen we daarmee hCD afleiden. Vervolgens hebben we hAB nodig om hABCD te berekenen. Ten slotte kunnen we met hEFGH controleren of de resulterende Merkle Root gelijk is aan die van de block header. Als dit zo is, dan bewijst dit dat de transactie was opgenomen in het block: met andere data zou het namelijk zo goed als onmogelijk zijn om dezelfde hash te produceren.

In het bovenstaande voorbeeld hebben we maar drie keer hoeven hashen. Zonder de Merkle Proof hadden we dit zeven keer moeten doen. Omdat blocks tegenwoordig duizenden transacties bevatten, zorgen Merkle Proofs voor een grote besparing van tijd en middelen.


Tot slot

Merkle Trees hebben bewezen erg nuttig te zijn in diverse toepassingen binnen de computerwetenschap en, zoals we hebben gezien, bij blockchains in het bijzonder. In gedistribueerde systemen maken Merkle Trees het mogelijk om eenvoudig informatie te valideren zonder het netwerk te overspoelen met onnodige data.

Zonder Merkle Trees (en Merkle Roots) zouden de blocks van Bitcoin en andere cryptocurrencies veel minder compact zijn dan nu het geval is. En hoewel zogenaamde light clients minder privé en veilig zijn, maken ze het gebruikers met minder middelen mogelijk om te controleren of hun transacties in een block zijn opgenomen.