Wat is een Merkle-boom? Beginnersgids voor deze Blockchain-component

Merkle Trees vormen een fundamenteel onderdeel van blockchains die hun functionaliteit ondersteunen. Ze maken efficiënte en veilige verificatie van grote datastructuren mogelijk, en in het geval van blockchains, potentieel grenzeloze datasets.

De implementatie van Merkle-bomen in blockchains heeft meerdere effecten. Het stelt hen in staat te schalen en biedt tegelijkertijd de op hash gebaseerde architectuur waarmee ze de gegevensintegriteit kunnen behouden en een triviale manier om de integriteit van gegevens te verifiëren.

Cryptografische hashfuncties zijn de onderliggende technologie waarmee Merkle-bomen kunnen werken, dus eerst is het belangrijk om te begrijpen wat cryptografische hashfuncties zijn.

Snelle uitspraak: Merkle-bomen zijn datastructuren die zijn samengesteld uit cryptografische hashes die een efficiënte integriteitsverificatie en het in kaart brengen van grote datasets mogelijk maken, waardoor ze een integraal onderdeel worden van systemen zoals blockchains en gedistribueerd versiebeheer.

Snelle feiten

Cryptografische hashfuncties

Simpel gezegd is een hashfunctie elke functie die wordt gebruikt om gegevens van een willekeurige grootte (invoer) toe te wijzen aan een uitvoer met een vaste grootte. Er wordt een hash-algoritme toegepast op de gegevensinvoer en de resulterende uitvoer met een vaste lengte wordt de hash genoemd.

Veel hash-algoritmen zijn algemeen beschikbaar en kunnen worden geselecteerd op basis van uw behoeften.

De resulterende hash van de willekeurige invoer heeft niet alleen een vaste lengte, maar is ook volledig uniek voor de invoer en de functie zelf is deterministisch. Dat wil zeggen: hoe vaak u de functie ook op dezelfde invoer uitvoert, de uitvoer zal altijd hetzelfde zijn.

Als u bijvoorbeeld de volgende gegevenssets hieronder als invoer heeft, zijn de resulterende uitvoer uniek voor elke invoer. Merk op hoe in het tweede en derde voorbeeld, ook al is het verschil tussen de invoer slechts één woord, de resulterende uitvoer totaal verschillend is.

Dit is erg belangrijk omdat het ‘vingerafdrukken’ van gegevens mogelijk maakt.

Een cryptografische hashfunctie, afbeelding van Wikipedia

Omdat de uitvoerlengte (hashsom in het voorbeeld) altijd hetzelfde is als bepaald door het gebruikte hash-algoritme, kunnen enorme hoeveelheden gegevens uitsluitend worden geïdentificeerd aan de hand van de resulterende hash.

Bij systemen die enorme hoeveelheden gegevens bevatten, kunnen de voordelen van het kunnen opslaan en identificeren van gegevens met een uitvoer met een vaste lengte enorme opslagbesparingen opleveren en de efficiëntie helpen verhogen.

Binnen blockchains worden hash-algoritmen gebruikt om de staat van de blockchain te bepalen.

Blockchains zijn gekoppelde lijsten die gegevens bevatten en een hash-pointer die naar het vorige blok verwijst, waardoor een keten van verbonden blokken ontstaat, vandaar de naam ‘blockchain’.

Elk blok is met elkaar verbonden via een hash-pointer, de hash van de gegevens in het vorige blok, samen met het adres van het vorige blok. Door gegevensblokken in dit formaat te koppelen, vertegenwoordigt elke resulterende hash van het vorige blok de volledige toestand van de blockchain, aangezien alle gehashte gegevens van de voorgaande blokken in één hash worden gehasht.

Dit wordt weergegeven (in het geval van het SHA-256-algoritme) door een uitvoer (hash) zoals deze:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

De bovenstaande hash is de vingerafdruk van de volledige staat van de blockchain ervoor. De toestand van de blockchain voorafgaand aan het nieuwe blok (als gehashte gegevens) is de invoer, en de resulterende hash is de uitvoer.

Hoewel het mogelijk is om cryptografische hashes te gebruiken zonder Merkle-bomen, is dit uiterst inefficiënt en niet schaalbaar. Het gebruik van hashes om gegevens in een blok in serieformaat op te slaan is tijdrovend en omslachtig.

Zoals je zult zien, maken Merkle-bomen een triviale resolutie van de gegevensintegriteit mogelijk, evenals het in kaart brengen van die gegevens door de hele boom met behulp van Merkle-bewijzen.

Merkle-bomen en Merkle-bewijzen

Vernoemd naar Ralph Merkle, die het concept in 1979 patenteerde, zijn Merkle-bomen in wezen datastructuurbomen waarbij elk niet-bladknooppunt een hash is van zijn respectievelijke onderliggende knooppunten.

De bladknooppunten zijn de laagste reeks knooppunten in de boom. In eerste instantie klinkt het misschien moeilijk te begrijpen, maar als je naar de veelgebruikte figuur hieronder kijkt, wordt het veel gemakkelijker te begrijpen.

Een voorbeeld van een binaire hashboom, afbeelding van Wikipedia

Belangrijk is dat u ziet hoe de niet-bladknooppunten of “takken” (weergegeven door Hash 0-0 en Hash 0-1) aan de linkerkant hashes zijn van hun respectievelijke kinderen L1 en L2. Merk verder op hoe tak Hash 0 de hash is van zijn aaneengeschakelde kinderen, takken Hash 0-0 en Hash 0-1.

Het bovenstaande voorbeeld is de meest voorkomende en eenvoudige vorm van een Merkle-boom die bekend staat als een binaire Merkle-boom. Zoals je kunt zien, is er een top-hash die de hasj van de hele boom is, ook wel de root-hash genoemd. In wezen zijn Merkle-bomen een datastructuur die “n” aantal hashes kan aannemen en deze kan vertegenwoordigen met een enkele hash.

De structuur van de boom maakt het efficiënt in kaart brengen van willekeurig grote hoeveelheden gegevens mogelijk en maakt eenvoudige identificatie mogelijk van waar veranderingen in die gegevens optreden. Dit concept maakt Merkle-bewijzen mogelijk, waarmee iemand kan verifiëren dat de hashing van gegevens consistent is, helemaal bovenaan de boom en in de juiste positie, zonder daadwerkelijk naar de hele set hashes te hoeven kijken.

In plaats daarvan kunnen ze verifiëren dat een datafragment consistent is met de root-hash door slechts een kleine subset van de hashes te controleren in plaats van de hele dataset.

Zolang de root-hash publiekelijk bekend en vertrouwd is, is het voor iedereen die sleutel-waarde-opzoekingen wil doen in een database mogelijk om een ​​Merkle-bewijs te gebruiken om de positie en integriteit van een stukje data binnen een database te verifiëren. een bepaalde wortel.

Wanneer de root-hash beschikbaar is, kan de hash-boom worden ontvangen van elke niet-vertrouwde bron en kan één tak van de boom tegelijk worden gedownload met onmiddellijke verificatie van de gegevensintegriteit, zelfs als de hele boom nog niet beschikbaar is.

Een van de belangrijkste voordelen van de Merkle-boomstructuur is de mogelijkheid om willekeurig grote gegevenssets te authenticeren via een soortgelijk hashmechanisme dat wordt gebruikt om veel kleinere hoeveelheden gegevens te verifiëren.

De boom is voordelig voor het distribueren van grote gegevenssets in beheersbare kleinere delen, waarbij de barrière voor de verificatie van de integriteit aanzienlijk wordt verminderd ondanks de algehele grotere gegevensomvang.

De root-hash kan worden gebruikt als vingerafdruk voor een hele dataset, inclusief een hele database of die de hele staat van een blockchain vertegenwoordigt. In de volgende paragrafen zullen we bespreken hoe Bitcoin en andere systemen Merkle-bomen implementeren.

Merkle-bomen in Bitcoin

De cryptografische hashfunctie die door Bitcoin wordt gebruikt, is het SHA-256-algoritme. Dit staat voor “Secure Hashing Algorithm”, waarvan de uitvoer een vaste lengte van 256 bits heeft. De basisfunctie van Merkle-bomen in Bitcoin is het opslaan en uiteindelijk snoeien van transacties in elk blok.

Zoals eerder vermeld zijn blokken in een blockchain met elkaar verbonden via hashes van het vorige blok. In Bitcoin bevat elk blok alle transacties binnen dat blok, evenals de blokkop die bestaat uit:

• Blokversienummer
• Vorige Block Hash
• Tijdstempel
• Moeilijkheidsdoel voor mijnbouw
• nonce
• Merkle Root-hash

De onderstaande afbeelding komt uit de Bitcoin-whitepaper en illustreert hoe de Merkle-boom in elk blok past.

De transacties worden door mijnwerkers in blokken opgenomen en gehasht als onderdeel van een Merkle-boom, wat leidt tot de Merkle-root die wordt opgeslagen in de blokheader. Dit ontwerp heeft een aantal duidelijke voordelen.

Het meest opvallende is dat dit, zoals uiteengezet in de whitepaper, het bestaan ​​mogelijk maakt van Simple Payment Verification (SPV)-knooppunten, ook wel bekend als ‘lichtgewicht clients’. Deze knooppunten hoeven niet de volledige Bitcoin-blockchain te downloaden, alleen de blokheaders van de langste keten.

SPV-knooppunten kunnen dit bereiken door hun peer-knooppunten te ondervragen totdat ze ervan overtuigd zijn dat de opgeslagen blokheaders waarmee ze werken deel uitmaken van de langste keten. Een SPV-knooppunt kan vervolgens de status van een transactie bepalen door het Merkle-bewijs te gebruiken om de transactie toe te wijzen aan een specifieke Merkle-boom met de root-hash van die respectieve Merkle-boom in een blokkop die deel uitmaakt van de langste keten.

Bovendien maakt Bitcoin's implementatie van Merkle-bomen het mogelijk om de blockchain te snoeien om ruimte te besparen. Dit is het resultaat van het feit dat alleen de root-hash wordt opgeslagen in de blokheader. Daarom kunnen oude blokken worden gesnoeid door onnodige takken van de Merkle-boom te verwijderen, terwijl alleen de takken behouden blijven die nodig zijn voor het Merkle-bewijs.

Implementatie van Merkle Trees in andere blockchains en systemen

Hoewel Bitcoin de eerste blockchain was die Merkle-bomen implementeerde, implementeren veel andere blockchains vergelijkbare Merkle-boomstructuren of zelfs complexere versies.

Verder is de implementatie van de Merkle-boom niet alleen beperkt tot blockchains, maar wordt deze ook toegepast op een verscheidenheid aan andere systemen.

Ethereum, de andere meest herkenbare cryptocurrency, is ook een goed voorbeeld van een andere Merkle-boomimplementatie. Omdat Ethereum compleet is als platform voor het bouwen van veel complexere applicaties, gebruikt het een complexere versie van de Merkle-boom, een Merkle Patricia Tree genaamd, die eigenlijk uit drie afzonderlijke Merkle-bomen bestaat die voor drie soorten objecten worden gebruikt. Meer over deze bomen kunt u hier te weten komen.

Ten slotte zijn Merkle-bomen een belangrijk onderdeel van gedistribueerde versiebeheersystemen zoals Git en IPFS. Hun vermogen om eenvoudig de integriteit van gegevens die tussen computers worden gedeeld in een P2P-formaat te garanderen en te verifiëren, maakt ze van onschatbare waarde voor deze systemen.

Conclusie

Merkle-bomen zijn een integraal onderdeel van blockchains en zorgen ervoor dat ze effectief kunnen functioneren met aantoonbare onveranderlijkheid en transactie-integriteit.

Het begrijpen van de rol die ze spelen in gedistribueerde netwerken en hun onderliggende technologie van cryptografische hashfuncties is cruciaal voor het begrijpen van de basisconcepten binnen cryptocurrencies terwijl ze zich blijven ontwikkelen tot grotere en complexere systemen.