Merkle Tree Hashing: Hoe Blockchainverificatie werkt

Met een Merkle tree kunnen computers in een netwerk afzonderlijke records verifiëren zonder versies van de gehele database te hoeven bekijken en te vergelijken. Ze doen dit door cryptografie te gebruiken die een individueel record laat zien, terwijl ze ook garanderen dat alle andere records in de database niet zijn gewijzigd. De Merkle trees werden in 1979 voor het eerst gepatenteerd door Ralph Merkle en vormen een belangrijke sleutel tot databaseverificatie in de geschiedenis van computers.

Merkle trees zijn vooral handig voor gedistribueerde netwerken waar meerdere computers kopieën van dezelfde database bewaren. Toen Satoshi Bitcoin creëerde, was het gebruiken van een Merkle tree voor verificatie van transacties een no-brainer. Vanwege de gedistribueerde aard van de blockchain hebben we een veilige en snelle manier nodig om ervoor te zorgen dat iedereen op het netwerk dezelfde database heeft.

Als je blockchain hebt bestudeerd heb je waarschijnlijk wel gehoord van Merkle trees en Merkle roots. Veel traders en blockchainenthousiastelingen weten alleen niet hoe ze werken. Aangezien ze een belangrijk onderdeel zijn van de beveiliging en het vertrouwen in blockchain, is het de moeite waard om de basisprincipes te begrijpen. Dit ingenieuze mechanisme maakt de opslag en het achterhalen van miljoenen blockchaintransacties mogelijk.

De noodzaak van een efficiënte verificatie

Laten we beginnen met de basis. Waarom hebben we Merkle trees nodig en wat maakt ze bruikbaar in de context van blockchain?

Om die vraag te beantwoorden stellen we ons voor dat er geen Merkle trees voor verificatie zouden bestaan. Als Bitcoin geen Merkle trees had, zou elke node op het netwerk een volledige kopie van de database moeten bewaren, met daarin elke transactie die ooit met Bitcoin heeft plaatsgevonden. Bij het bevestigen van een transactie uit het verleden moet de node vervolgens contact opnemen met het netwerk en kopieën van de database van zijn peers ophalen. De node moet regel voor regel elk item met zijn eigen records vergelijken om ervoor te zorgen dat de data precies overeenkomt. Als er wijzigingen zouden zijn doorgevoerd, zou dit de veiligheid van het netwerk in gevaar brengen.

Omdat het valideren van de gegevens vereist dat de gegevens zelf aanwezig zijn, zou elk verificatieverzoek op Bitcoin vereisen dat enorme pakketten informatie via het netwerk worden verzonden. De validerende computer zou dan alle rekenkracht moeten gebruiken om de databases te vergelijken om er zeker van te zijn dat er niks gewijzigd is.

Merkle trees lossen dit probleem op door de records in een database te hashen. Dit ontkoppelt effectief het bewijs dat de gegevens correct zijn van de gegevens zelf. Deze hashes zijn vele malen kleiner dan de database zelf. Dus om te bewijzen dat een transactie geldig is hoeven alleen kleine pakketjes over het netwerk verzonden te worden. Hiermee wordt met minimale rekenkracht en bandbreedte bewezen dat twee versies van een database consistent zijn.

Dit klinkt goed en dat is het ook! Merkle trees zijn echt een geweldige cryptografische uitvinding. Dus nu is de vraag hoe werken ze?

Een snelle opfriscursus in hash

Voordat ik inga op de details van Merkle trees dien je de cryptografische fundamenten van hashing te begrijpen. Blockchains gebruiken hashing overal, van proof-of-work algoritmen tot bestandsverificatie. Hashing is de hoeksteen van moderne cryptografie.

Zonder er al te diep op in te gaan, een hash is een type algoritme dat elke invoer kan bevatten, ongeacht de lengte, en een standaard lengte als uitvoer heeft. Met andere woorden, in Bitcoin bijvoorbeeld, ziet de transactie ‘Alice stuurt Bob 1 BTC’ eruit als een reeks willekeurige tekens:

“3cbcf3e1075b0b3357140de438336733bd6927cd1e78d36cc278324fcce932ad”

Deze reeks tekens is de hash en het is deterministisch. Dat betekent dat “A -> B 1BTC” altijd hashes dezelfde output heeft.

Hashes hebben echter nog een andere goede eigenschap. Zelfs de kleinste verandering bij de input betekend een drastische verandering in de output. Als we de transactie wijzigen in “A-> B 1.1BTC”, wordt de hash compleet anders. Daarom is het meteen heel duidelijk wanneer een record ook maar door één karakter is veranderd.

Hoe maak je een Merkle Tree?

In dit voorbeeld gaan we een Merkle tree bouwen. We nemen de Allice/Bob transactie hierboven als voorbeeld en noemen we “Transactie A”. Als deze transactie aan de blockchain wordt toegevoegd vormt het samen met andere transacties een blok. Om het makkelijk te houden noemen we dit transacties B, C en D.

Elk van deze transacties wordt gehasht, dus we hoeven niet vast te houden aan precies wie en hoeveel de transactie was. We kunnen nog steeds bewijzen dat er niet met de transactie is geknoeid, omdat we alle hashes hebben. Nu hebben we H(A), H(B), H(C) en H(D).

Vasthouden aan vier hashes is niet zo’n probleem. Elk Bitcoinblok bevat echter ongeveer 2000 transacties, dus om al deze hashes bij elkaar te houden en te transporteren en is te veel opslagruimte en bandbreedte nodig. Een Merkle tree structuur lost dat probleem op door al deze transacties koppelen en in een hash samen te voegen.

Nu, H(A) + H(B) = H(AB) en H(C) + H(D) = H(CD). Door de transacties te combineren en te hashen hebben we het aantal hashes dat we moeten opslaan met de helft verminderd. We kunnen hetzelfde opnieuw doen, dus H(AB) + H(CD) = H(ABCD). Door dit te doen hebben we nu slechts één hash om op te slaan die deterministisch is, gebaseerd op de hashes van alle onderliggende transacties. Deze enkele hash wordt de Merkle root genoemd.

Verifiëren van transacties met behulp van de Merkle Root

Elk Bitcoinblok heeft de Merkle root in de block header. Zo controleren we de inhoud van het blok en de consistentie van meerdere databases. Als mijn exemplaar van de blockchain dezelfde Merkle root heeft voor een blok als jouw kopie van de blockchain, dan weten we dat alle transacties in dat blok hetzelfde zijn en gaan we akkoord met dit record. Zelfs een kleine inconsistentie zou leiden tot enorm verschillende Merkle roots vanwege de eigenschappen van een hash.

Als er een discrepantie is in de Merkle root kunnen we de twee sub-hashes bij een vertrouwde instantie aanvragen. Van daaruit kunnen we nagaan welk record we niet goedkeuren door verdere sub-hashes op te vragen. Als gevolg hiervan kunnen we verschillen vaststellen zonder regel voor regel door de hele database te hoeven gaan.

Conclusie

Blockchains, databases en netwerken over de hele wereld gebruiken Merkle trees voor het snel en efficiënt coördineren en transporteren van records op meerdere computers. Nu je deze basisbegrijpt, is het makkelijker om in te zien waarom deze manier van structureren van gegevens blockchain veilig en efficiënt maakt.

Dit artikel van Fabian Leferink verscheen eerst op Coincentral.com