Merkle Tree uitgelegd

Invalid Date | 4 min leestijd

Wat is een Merkle-tree?

Een Merkle-tree is een gegevensversleutelingsstructuur die wordt gebruikt in gegevensbeheertoepassingen waarbij gegevens op verschillende manieren via een hash-algoritme worden verzonden om een hash te creëren die alle gegevens in een bestand vertegenwoordigt.

De Bitcoin blockchain en andere blockchains gebruiken Merkle-tree's om blockchain-gegevens efficiënter en veiliger te coderen door individuele transacties en de resulterende hashes te hashen tot een hash die een Merkle-root wordt genoemd. De Merkle-root wordt gebruikt om de blokhash te creëren, de unieke identificatiecode van een blok. Merkle-bomen worden ook wel “binaire hashbomen” genoemd.

Korte samenvatting

Merkle-bomen zijn een gestructureerde manier om gegevens te coderen voor eenvoudige verificatie en betere beveiliging.
Blockchains gebruiken Merkle-tree's om hashes te genereren die worden gebruikt om transacties te verifiëren en de blokken te beveiligen.
Visuele weergaven van Merkle-tree's lijken op omgekeerde bomen met de wortel bovenaan.
De herhaalde hashing-techniek die wordt gebruikt in blockchain Merkle-tree's is een van de mechanismen die bijdragen aan hun onveranderlijkheid.

Merkle tree voorbeeld

Een Merkle-tree (of Merkle-boom) klinkt ingewikkeld, maar het is eigenlijk gewoon een slimme manier om grote hoeveelheden gegevens (zoals transacties) samen te vatten in een unieke code (hash).

Stel je voor: je hebt een boodschappenlijst van 1000 items. In plaats van die hele lijst te sturen naar iemand, maak je er een korte, unieke samenvatting van. En als ook maar één letter op die lijst verandert, verandert die samenvatting volledig. Dat is wat een hash doet.

Een Merkle-tree doet dit niet met één lijst, maar met duizenden stukjes informatie. Eerst worden alle stukjes apart gehashed (versleuteld tot een code), dan telkens twee aan twee gecombineerd en opnieuw gehashed, en dat gaat door tot er nog één hash overblijft: de Merkle-root.

In de Bitcoin-blockchain werkt dit zo:

Elke transactie wordt gehashed.
Die hashes worden weer gehashed tot er één Merkle-root is.
Die Merkle-root vormt samen met andere info de hash van het hele blok, zeg maar de ‘vingerafdruk’ van het blok.

Zo weet je zeker dat de inhoud van dat blok klopt. Als iemand ook maar één transactie verandert, klopt de hele boom niet meer en wordt het blok ongeldig.

Dus kort gezegd:

Een Merkle-tree is een soort digitale boom die helpt om te checken of alle data in een blok klopt – snel, veilig en zonder dat je alles hoeft te bekijken

Merkle-tree begrijpen

Merkle trees zijn vernoemd naar computerwetenschapper Ralph Merkle, die het concept introduceerde in 1979. In een Merkle tree wordt informatie gecodeerd met behulp van een cryptografische hashfunctie. Die functie zet data om in een reeks cijfers en letters van vaste lengte, ook wel een hash genoemd.

Een belangrijk kenmerk van een hashfunctie is dat dezelfde invoer altijd dezelfde hash oplevert, terwijl het vrijwel onmogelijk is om de oorspronkelijke data terug te halen uit de hash. Dit maakt het mogelijk om bestanden met elkaar te vergelijken zonder hun volledige inhoud te hoeven bekijken.

In een Merkle tree worden individuele stukken data (zoals transacties) eerst afzonderlijk gehasht. Vervolgens worden deze hashes paarsgewijs gecombineerd en opnieuw gehasht. Dit proces herhaalt zich totdat er één hash overblijft: de Merkle root. Deze root vertegenwoordigt alle onderliggende data in één enkele hashwaarde.

Als iemand de juistheid van een specifieke transactie wil controleren, hoeft hij niet het hele blok te bekijken. Met een paar tussenliggende hashes en de Merkle root kan snel worden vastgesteld of de transactie inderdaad deel uitmaakt van het blok. Dit zorgt voor snelle en efficiënte gegevensverificatie, zonder dat je de volledige dataset hoeft te downloaden of verwerken.

Merkle trees vormen een essentieel onderdeel van veel blockchains, zoals Bitcoin, omdat ze bijdragen aan de integriteit, veiligheid en efficiëntie van het systeem.

Hoe een Merkle-tree wordt gebruikt in een blockchain

Merkle-bomen hoeven niet te worden gebruikt in blockchains, maar veel blockchains maken wel gebruik van deze structuur. Bovendien kunnen ze verschillende technieken binnen de bomen implementeren. Bitcoin is het bekendst, dus wordt het hier als voorbeeld gebruikt.

De software van Bitcoin voert niet het hele blok met transactiegegevens in één keer door de hashfunctie. In plaats daarvan wordt elke transactie gehasht, waarna een paar transacties aan elkaar worden gekoppeld en samen worden gehasht, enzovoort, totdat er één hash is voor het hele blok. Als er een oneven aantal transacties is, wordt één transactie verdubbeld en wordt de hash ervan aan zichzelf gekoppeld. Wanneer dit gestructureerde proces wordt gevisualiseerd, lijkt het op een omgekeerde boom.

Voordelen van de Merkle-tree

Merkle trees zijn superhandig voor blockchains zoals Bitcoin, en dat heeft een paar goede redenen:

Snelle controle van transacties
Je hoeft niet een heel blok of de hele blockchain te downloaden om te checken of een transactie klopt. Met een paar tussenliggende hashes en de Merkle root kun je supersnel verifiëren of een transactie echt is. Dit bespaart enorm veel tijd en opslagruimte.
Efficiënt omgaan met grote hoeveelheden data
Blockchains bevatten duizenden transacties per blok. Dankzij Merkle trees worden die netjes en efficiënt in laagjes gehashed, waardoor het hele blok overzichtelijk en makkelijk te verwerken blijft.
Data integriteit
Als er iets aan één transactie verandert, verandert de root hash, en dus ook de hele Merkle tree. Hierdoor valt fraude of geknoei meteen op. De structuur zorgt er dus voor dat alles goed gecontroleerd kan worden.
Makkelijk werken met light nodes
Light clients hoeven niet de hele blockchain op te slaan. Ze kunnen via Merkle proofs toch controleren of een transactie klopt, zonder al die data te downloaden.

Kortom: Merkle trees maken blockchains sneller, lichter en veiliger. Best slim gevonden dus.

Waar wordt een Merkle tree voor gebruikt?

Merkle trees worden gebruikt in systemen waar je op een efficiënte en veilige manier wilt controleren of data klopt. In blockchains wordt een Merkle tree gebruikt om alle transacties in een blok samen te vatten in één hash: de Merkle root. Deze Merkle root komt in de header van het blok terecht en wordt uiteindelijk gebruikt bij het maken van de unieke blokhash.

Met deze structuur kun je later makkelijk bewijzen of een specifieke transactie wel of niet in een blok zit, zónder het hele blok te hoeven downloaden. Dat maakt Merkle trees ideaal voor bijvoorbeeld light clients, digitale handtekeningen en datastructuren waar betrouwbaarheid en controle belangrijk zijn.

Hoe groot kan een Merkle-tree worden?

De grootte van een Merkle-tree hangt af van de hoeveelheid gegevens die wordt gehasht voor opname en hoe de blockchain is geprogrammeerd. De Merkle-tree van een blok neemt echter niet veel opslagruimte in beslag op een blockchain. Bitcoin-blok 854.473 had bijvoorbeeld 2.530 transacties en de hash van elke transactie is 64 bytes. De Merkle-tree van het blok nam dus 161,92 Kb van de totale 1,54 Mb van het blok in beslag.

Waarom gebruikt Bitcoin Merkle-bomen?

Bitcoin gebruikt Merkle-bomen omdat ze een efficiënte manier zijn om transacties te verifiëren en helpen bij het creëren van de informatieketen die de blokken met elkaar verbindt.

Conclusie

Een Merkle-tree is een gegevensstructuur waarin gehashte gegevens worden gebruikt om een andere hash te creëren die de gegevens in een bestand vertegenwoordigt. Deze structuur maakt het voor computers gemakkelijk om informatie te vergelijken, omdat het slechts enkele milliseconden duurt om hashes te genereren op basis van de informatie en te verifiëren of de resultaten identiek zijn.

Merkle-bomen zijn ook een van de mechanismen waarmee blokken in een blockchain aan elkaar kunnen worden gekoppeld. Als er gegevens worden gewijzigd, zal de resulterende hash anders zijn, waardoor het voorgestelde blok door het consensusmechanisme van de blockchain wordt afgewezen.