Wat is een Merkle tree?
Een Merkle tree is een boomdiagram dat van onder op wordt opgebouwd. Onderaan staan afzonderlijke data (zoals een transactie ID) waar een hash van wordt gemaakt via een algoritme. Elk blad aan de boom wordt gehasht met zijn buurman, en samen vormen zij een nieuwe hash. Zo wordt de Merkle tree of hash-boom van onderop opgebouwd, totdat 1 hash de hele boom vertegenwoordigt.
Een Merkle tree is een cryptografische verzameling data die wordt gebruikt om grote hoeveelheden data in gedistribueerde databases veilig te verifiëren. De beste voorstelling hiervan voor de meeste mensen is het stamboomdiagram. Je kunt er lang over bomen, maar we houden het kort vandaag.
Hoe werkt een Merkle tree?
Een boomdiagram is een structuur die onderaan veel data heeft en hogerop steeds minder, totdat hij de top of piek bereikt. Bij een Merkle tree staan onderaan alle afzonderlijke data. Van de onderste laag worden paren gevormd, waarmee een nieuwe hash wordt gevormd. Hashing leggen we uit in een ander artikel. In het kort kun je een hash verkrijgen door van een bepaalde input of invoer via een algoritme een output te genereren. Om een idee te krijgen van een hash, kun je zelf wat invoeren op GitHub.
Bij blockchain heb je, zoals je wellicht weet, een gedistribueerde database, waar alle informatie over wat gebeurd is opgeslagen is. Ook moeten er nieuwe blokken gemaakt worden. De Merkle tree speelt hierin een belangrijke rol.
In het verleden van een blockchain zijn er allemaal blokken gemaakt die een hash hebben gekregen. Dit is het identificatienummer van het blok. Zodoende wordt de volgorde ook bepaald, want er zit ook een tijdstempel in deze hash verwerkt.
Root tree per blok
In een enkel blok van een blockchain zitten alle transacties van de afgelopen blokperiode, bijvoorbeeld tien minuten bij Bitcoin. Als we ons alleen focussen op de transacties om het simpeler te houden kunnen we de boom van onder op op gaan bouwen. Onderaan staan alle transacties van deze periode. Deze transacties met alle informatie die daarbij hoort worden per stuk gehasht.
De buurman in de boom (ook een transactie dus waar een hash van is gemaakt) levert zijn hash en wordt in een paar gehasht, zodat van twee hashes 1 hash wordt gemaakt. Dit proces gaat door, totdat er nog maar 1 of 2 hashes in de boom over zijn. Als er nog twee over zijn, zal dit een enkele hash opleveren en dat heet de root (wortel) tree of Merkle root oftewel de top hash in de Merkle tree. Als er maar 1 overblijft, zal deze gedupliceerd worden en wordt daarvan de root tree gemaakt via hashing.
Scan de QR-code of klik de link om lid te worden bij Whitebit en je exclusieve korting te claimen op de toch al goedkope transactiekosten van 0,1% bij deze exchange. Maak zelf ook referrals en krijg 40-50% commissie over hun transactiekosten.
Waarom gebruiken we een Merkle tree?
Als we alle transacties (en andere informatie) in een blok op een blockchain kunnen reduceren tot een enkel getal, de hash, dan is het veel eenvoudiger en goedkoper om te bepalen of de data wel klopt. De hash van de hele boom geeft dus een representatie van de totale inhoud van de boom via een lang alfanumeriek getal.
Het is door deze techniek veel gemakkelijker om grote datasets als blockchains te onderhouden en te beveiligen tegen vervalsing, zoals dubbele uitgaven of corrupte data.
Wie heeft de Merkle tree bedacht?
Het concept van de Merkle tree is uitgevonden door Amerikaans wiskundige Ralph Merkle en gepatenteerd in 1979. De Duitse ex-bondskanselierarin heeft er dus niks mee te maken. Het werd omschreven in de paper “A certified digital signature”.
Merkle tree in de praktijk
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 het SHA-256 (Secure Hash Algorithm 256 bit) dat onder anderen door Bitcoin wordt gebruikt om de boodschap te encrypten of coderen.
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 opbouwen
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 root tree).
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, want elke hash is uniek.
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.
Bitcoin voorbeeld Merkle tree
Stel er waren in de afgelopen tien minuten 200 transacties op de Bitcoin blockchain. De Merkle tree gaat dan aan de slag om al deze transacties te reduceren tot een enkele root tree. Alle Bitcoin blokken hebben dus een root tree, die je kunt gebruiken om te controleren of alle records nog kloppen. Dit vereenvoudigt het beheer van de blockchain in hoge mate.
Miners en nodes 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 blok ook veel kleiner. Als 51% van deze miners het eens zijn dat de root tree klopt, kan het blok toegevoegd worden.
Deze root tree hash wordt aan het begin van het volgende blok gezet, zodat alle miners weten wat de waarde is van de hash van het vorige blok. 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 voor de veiligheid.
Voordelen van de Merkle tree
- Je reduceert alle informatie in een blok op een blockchain of in een database tot een enkel alfanumeriek getal of waarde
- De kosten van het bijhouden van een database zijn veel lager en het gaat sneller, nodes kunnen zelfs puur op de root tree checken of informatie klopt
- Het is heel simpel om fraude te detecteren, aangezien een hash uniek is, dit zorgt voor hoge veiligheid en heet Merkle proof
Conclusie
Een Merkle tree wordt zowel in blockchain als in andere databases gebruikt en is een onmisbaar onderdeel van efficiënt en veilig databeheer.
