Een Merkle-boom, ook wel hashboom genoemd, is een hiërarchische datastructuur waarin elk bladknooppunt de cryptografische hash van een datablok bevat, en elk niet-bladknooppunt (ouderknooppunt) de cryptografische hash bevat van de concatenatie van de hashes van zijn kindknooppunten. Deze binaire boomstructuur maakt het mogelijk om grote datasets met buitengewone efficiëntie te verifiëren op integriteit en consistentie – in plaats van elk afzonderlijk stukje data te controleren, hoeft een verificator slechts een klein aantal hashes langs een enkele tak van een blad naar de wortel te onderzoeken. De enkele hash bovenaan de boom, de Merkle-wortel genoemd, dient als een unieke vingerafdruk voor de gehele dataset eronder. Als zelfs maar één bit data ergens in de boom wordt gewijzigd, gaat de wijziging door naar boven via elke ouderhash totdat de Merkle-wortel zelf verandert, wat direct aangeeft dat er met de data is geknoeid.
In blockchaintechnologie vormen Merkle-bomen de basis voor de manier waarop blokken transacties opslaan en valideren. Elke blokheader in Bitcoin, Ethereum en vrijwel alle andere blockchainprotocollen bevat een Merkle-root die alle transacties in dat blok samenvat. Dit ontwerp stelt lichtgewicht clients – vaak Simplified Payment Verification (SPV)-nodes genoemd – in staat om te bevestigen dat een specifieke transactie in een blok is opgenomen zonder de volledige inhoud van het blok te downloaden. De client heeft alleen de blokheader (die de Merkle-root bevat) en een korte reeks sibling-hashes nodig, een zogenaamd Merkle-bewijs of Merkle-pad. Voor een blok met 4,096 transacties vereist dit bewijs slechts 12 hashes in plaats van alle 4,096 transactiehashes – een logaritmische reductie die mobiele wallets en apparaten met beperkte resources geschikt maakt voor deelname aan het netwerk.
Merkle-bomen vormen niet alleen de basis voor eenvoudige transactieverwerking, maar ook voor enkele van de meest geavanceerde constructies in het cryptocurrency-ecosysteem. Ethereum gebruikt een aangepaste versie, de Merkle Patricia Trie, om de volledige wereldstatus op te slaan – elk accountsaldo, elke opslaglocatie voor smart contracts en elk stukje code. Zero-knowledge rollups gebruiken Merkle-bomen om batches van off-chain transacties samen te voegen tot één on-chain root. Airdrop-distributiecontracten gebruiken Merkle-bomen om duizenden adressen tokens te laten claimen met minimale on-chain data. De elegantie van de structuur schuilt in de eenvoud: een recursieve toepassing van hashing die een willekeurig grote dataset omzet in één enkele, vaste commit, die in logaritmische tijd verifieerbaar is.
Oorsprong en geschiedenis
1979: Ralph Merkle beschreef hashbomen voor het eerst in zijn proefschrift aan Stanford en patenteerde het concept vervolgens (Amerikaans patent 4,309,569, ingediend op 5 september 1979 en verleend op 5 januari 1982). Merkle ontwikkelde de structuur als onderdeel van zijn baanbrekende werk op het gebied van publieke-sleutelcryptografie en digitale handtekeningen, op zoek naar een efficiënte methode voor het authenticeren van grote datastructuren.
1987-1988: Merkle combineerde zijn hashboomstructuur met eenmalige handtekeningschema's, voortbouwend op de eerdere Lamport-Diffie-constructie voor eenmalige handtekeningen, in een paper gepresenteerd op CRYPTO '87 en gepubliceerd in de congresbundel in 1988. Deze combinatie, nu algemeen bekend als het Merkle-handtekeningschema, toonde aan dat een enkele hashboom veel eenmalige sleutelparen kon authenticeren onder één publieke sleutel, waardoor grote aantallen cryptografische sleutels efficiënt beheerd konden worden.
Eind jaren negentig: Met de opkomst van peer-to-peer-bestandsuitwisselingssystemen werden hashboomstructuren gebruikt om knooppunten in staat te stellen de integriteit van gedownloade bestandssegmenten onafhankelijk van elkaar te verifiëren, waardoor beschadigde of kwaadaardige gegevens konden worden gedetecteerd zonder dat hele bestanden opnieuw gedownload hoefden te worden. Dit patroon werd later geformaliseerd in specificaties zoals het Tree Hash Exchange (THEX)-formaat.
2008: Satoshi Nakamoto integreerde Merkle-bomen in het Bitcoin-protocolontwerp. Sectie 7 van de Bitcoin-whitepaper, "Reclaiming Disk Space", beschrijft hoe Merkle-bomen het mogelijk maken om oude transactiegegevens te verwijderen terwijl een compacte root-hash behouden blijft. Sectie 8, "Simplified Payment Verification", legt afzonderlijk uit hoe dezelfde structuur het mogelijk maakt voor lichte clients om te bevestigen dat een transactie in een blok is opgenomen, met behulp van alleen de blokheader en een Merkle-bewijs.
2009: Het Bitcoin-netwerk werd gelanceerd met Merkle-roots ingebed in elke blokheader. Het genesisblok (blok 0) bevatte één transactie met een Merkle-root gelijk aan de hash van die transactie, waarmee het patroon voor alle volgende blokken werd vastgesteld.
2015: Ethereum werd gelanceerd met drie verschillende Merkle-boomvarianten in elke blokheader – een transactietrie, een ontvangstbewijstrie en een statustrie – die allemaal waren geïmplementeerd als Merkle Patricia Tries. Dit ontwerp breidde de functionaliteit van de Merkle-boom uit van eenvoudige transactieverificatie naar volledige authenticatie van de wereldwijde status.
2017-2019: Merkle-bomen werden essentieel voor het ontwerp van layer-2 schaaloplossingen. Plasma-ketens gebruikten Merkle-commitments om de status van child-ketens te verankeren aan het Ethereum-mainnet, terwijl vroege rollup-ontwerpen Merkle-roots gebruikten om honderden transacties te bundelen tot één on-chain proof.
2020–2024: Zero-knowledge proof-systemen zoals zkSync en StarkNet namen gespecialiseerde Merkle-boomvarianten in gebruik – waaronder op Poseidon-hash gebaseerde sparse Merkle-bomen – geoptimaliseerd voor efficiënte berekeningen binnen ZK-circuits. Merkle airdrop-contracten werden het standaardpatroon voor tokendistributies op Ethereum.
"Een hashboom maakt het mogelijk om elke tak van de hashboom onafhankelijk te controleren, zonder dat de knooppunten de volledige dataset hoeven op te slaan."
In eenvoudige bewoordingen
Stel je een toernooischema voor. Elke wedstrijd in de eerste ronde levert een winnaar op. Die winnaars worden gekoppeld voor de tweede ronde, enzovoort, totdat er één kampioen overblijft aan de top. Een Merkle-boom werkt op dezelfde manier – alleen begin je in plaats van sportteams met datablokken, en in plaats van wedstrijden te spelen, combineer je paren van data met behulp van cryptografische hashing totdat je één enkele "kampioen-hash" aan de top krijgt, de zogenaamde Merkle-root.
Zie het als een omgekeerde stamboom. Onderaan staan honderden individuele familieleden (datablokken). Elk paar broers en zussen wordt gecombineerd om hun ouders te vertegenwoordigen. Die ouders worden gecombineerd om de grootouders te vormen, enzovoort, tot je een enkele voorouder bovenaan bereikt. Als een familielid verandert, verandert elke generatie daarboven ook, helemaal tot aan de voorouder bovenaan.
Stel je een bibliotheekcatalogus voor. In plaats van elk boek op elke plank te controleren om te bevestigen dat er niets ontbreekt, houdt de bibliothecaris een overzicht bij van elke plank, combineert deze overzichten tot overzichten per gangpad, combineert deze overzichten tot overzichten per verdieping en houdt één overkoepelend overzicht bij voor de hele bibliotheek. Om te controleren of een bepaald boek bestaat, hoef je alleen de overzichten langs het traject van de plank naar het overkoepelende overzicht te raadplegen – niet elk ander boek.
Stel je voor dat je bewijsmateriaal in een rechtszaak verzegelt. Elk bewijsstuk krijgt een eigen, fraudebestendige envelop. Twee enveloppen gaan in grotere enveloppen, die weer in nóg grotere enveloppen gaan, totdat alles in één grote envelop met één enkele verzegeling zit. Als iemand met een bewijsstuk knoeit, vertonen alle enveloppen erboven sporen van manipulatie en breekt de verzegeling van de grote envelop.
Belangrijk: Merkle-bomen bieden bewijs van de aanwezigheid en integriteit van gegevens, maar ze versleutelen geen gegevens en bieden geen vertrouwelijkheid. Iedereen met toegang tot de boom kan de gegevens inzien – de boom garandeert alleen dat de gegevens niet zijn gewijzigd. Bovendien hangt de veiligheid van een Merkle-boom volledig af van de sterkte van de onderliggende hashfunctie; als de hashfunctie wordt gekraakt, stort de integriteit van de boom gegarandeerd in.
Belangrijkste technische kenmerken
Binaire hashboomstructuur
Bladknooppunten bevatten de hash van individuele datablokken (bijvoorbeeld transacties).
Interne knooppunten bevatten de hash van de samenvoeging van hun twee onderliggende hashes: H(parent) = Hash(H(left) || H(right))
De boom is altijd in evenwicht; als het aantal bladeren oneven is, wordt het laatste blad verdubbeld om een paar te vormen.
Boomdiepte is log2(n) met de meeste n is het aantal bladknoppen
De root-hash (Merkle root) is een vingerafdruk van vaste grootte van de gehele dataset, ongeacht de grootte van de dataset.
Hoe werkt Merkle-bewijsverificatie?
Een verificator wil bevestigen dat een specifieke transactie correct is verlopen. Tx_k is opgenomen in een blok
De verificator verkrijgt de blokheader, die de Merkle-root bevat.
De bewijzer levert de hash van Tx_k samen met het Merkle-bewijs – de reeks hashes van broers en zussen langs het pad van het blad naar de wortel
De verificator hasht Tx_ken combineert het vervolgens met de hash van het eerste broertje of zusje met behulp van dezelfde hashfunctie.
Het resultaat wordt gecombineerd met de hash van het volgende broerelement, enzovoort, waarbij de boomstructuur niveau voor niveau wordt doorlopen.
Als de uiteindelijke berekende hash overeenkomt met de Merkle-root in de blokheader, wordt de transactie als opgenomen geverifieerd.
Voor een boom met n bladeren, alleen log2(n) Er zijn hashes nodig – bijvoorbeeld 20 hashes om 1 transactie te verifiëren van de 1,048,576 transacties.
Merkle Patricia Trie (Ethereum)
Ethereum breidt de basis Merkle-boom uit tot een Patricia-trie (radixboom) die sleutels aan waarden koppelt.
De state trie koppelt accountadressen aan accountstatussen (saldo, nonce, opslagroot, code hash).
De opslagtrie koppelt 256-bits opslagslots aan hun waarden voor elk smart contract.
Padcompressie vermindert de opslagoverhead door ketens met één kindknooppunt samen te voegen tot uitbreidingsknooppunten.
Drie typen knooppunten: vertakkingsknooppunten (16 kinderen + waarde), uitbreidingsknooppunten (gedeeld voorvoegsel + volgend knooppunt), bladknooppunten (resterend pad + waarde)
Dunne Merkle-bomen voor nulkennisbewijzen
Sparse Merkle-bomen (SMT's) zijn Merkle-bomen waarvan de meeste bladeren leeg zijn (standaard hashwaarde).
Wordt gebruikt in ZK-rollups om accountstatussen weer te geven met efficiënte bewijzen van lidmaatschap en niet-lidmaatschap.
Geoptimaliseerde hashfuncties zoals Poseidon en Pedersen worden gebruikt voor ZK-circuitvriendelijke berekeningen.
Een SMT met een diepte van 256 kan alle mogelijke 256-bits sleutels weergeven en blijft daarbij computationeel beheersbaar.
Het bewijs van niet-inclusie is net zo eenvoudig als bewijzen dat het blad op een bepaalde positie de standaardwaarde bevat.
Voordelen nadelen
Voordelen
Nadelen
Logaritmische verificatie: schaal van bewijsgrootte en verificatietijd als O(log n)waardoor zelfs miljoenen transacties efficiënt geverifieerd kunnen worden.
Opslagoverhead: Het opslaan van alle tussentijdse hashes vereist ongeveer 2n - 1 knooppunten voor n bladknooppunten, waardoor de benodigde opslagruimte voor ruwe data ruwweg verdubbelt.
Manipulatiedetectie: Elke wijziging aan een bladknooppunt plant zich naar boven voort, waardoor de Merkle-root verandert en gegevenscorruptie of -manipulatie onmiddellijk aan het licht komt.
Herberekeningskosten: Het bijwerken van een enkel blad vereist het opnieuw berekenen van alle hashes langs het pad naar de root. O(log n) hash-bewerkingen per update
Lichtgewicht clientondersteuning: SPV-nodes kunnen de opname van transacties verifiëren met alleen blokheaders en Merkle-bewijzen, waardoor mobiele en ingebouwde wallets mogelijk worden.
Afhankelijkheid van de hashfunctie: Het gehele beveiligingsmodel is afhankelijk van de botsingsbestendigheid van de gekozen hashfunctie; een defecte hashfunctie verstoort de boomstructuur.
Bandbreedte-efficiëntie: Merkle-bewijzen verzenden alleen log2(n) hashes in plaats van de volledige dataset, waardoor de netwerkbandbreedte voor verificatie drastisch wordt verminderd.
Balanceringseis: Standaard binaire Merkle-bomen vereisen een even aantal bladeren; datasets met een oneven aantal bladeren vereisen duplicatie, wat subtiele implementatiefouten kan introduceren.
Composeerbaarheid: Merkle-bomen kunnen genest worden – een Merkle-wortel kan een blad zijn in een boom op een hoger niveau – waardoor meerlaagse datacommit-schema's mogelijk worden die gebruikt worden in rollups en sharding.
Complexiteit van Tries: Merkle Patricia Tries (zoals in Ethereum) zijn aanzienlijk complexer om te implementeren dan eenvoudige binaire Merkle-bomen, met meerdere knooppunttypen en padcodering.
Parallelle constructie: Bladhashes kunnen onafhankelijk en parallel worden berekend, waardoor de constructie van Merkle-bomen zeer goed paralleliseerbaar is op moderne hardware.
State Bload: In stateful blockchains groeit de Merkle-trie met elk nieuw account en opslagslot, wat bijdraagt aan state bload op de lange termijn en langere synchronisatietijden.
Gestandaardiseerd en beproefd: decennia van academisch onderzoek en implementatie in de praktijk (Bitcoin sinds 2009) bieden een groot vertrouwen in de beveiligingseigenschappen van de structuur.
Schaalvergroting van bewijsgrootte: Hoewel logaritmisch, neemt de omvang van bewijzen nog steeds toe met de grootte van de dataset; voor zeer grote bomen (miljarden bladeren) kunnen bewijzen een aanzienlijke omvang bereiken.
RISICO BEHEER
Kwetsbaarheidsrisico van hashfuncties
Merkle-bomen erven de beveiligingseigenschappen van hun onderliggende hashfunctie (doorgaans SHA-256 voor Bitcoin, Keccak-256 voor Ethereum).
Als botsingsaanvallen op de hashfunctie uitvoerbaar worden, zou een aanvaller twee verschillende datasets met dezelfde Merkle-root kunnen construeren.
Mitigatie: Houd cryptografisch onderzoek in de gaten voor verbeteringen ten opzichte van SHA-256 en Keccak-256; blockchain-gemeenschappen kunnen een hard fork uitvoeren om de hashfuncties indien nodig te upgraden.
Kwantumcomputers vormen een bedreiging op de lange termijn voor de veiligheid van hashfuncties, hoewel huidige schattingen suggereren dat SHA-256 nog tientallen jaren veilig zal blijven.
Implementatiefoutrisico
Subtiele fouten in Merkle-boomimplementaties – zoals onjuiste behandeling van oneven genummerde bladeren, off-by-one-fouten in bewijspaden of endianness-mismatches – kunnen exploiteerbare kwetsbaarheden creëren.
De Bitcoin Cash-splitsing in 2018 bracht uitzonderlijke gevallen aan het licht in de Merkle-boomvalidatie tijdens de blokverificatie.
Maatregelen ter beperking van de risico's: Gebruik goed gecontroleerde open-sourcebibliotheken (bijvoorbeeld MerkleProof.sol van OpenZeppelin voor Solidity); voer formele verificatie uit van kritieke implementaties.
Test met vijandige invoer, waaronder lege bomen, bomen met één blad en bomen met maximale diepte.
Type-ambiguïteitsaanvalrisico
In een naïeve Merkle-boom zou een aanvaller mogelijk een frauduleus intern knooppunt kunnen creëren dat botst met een legitiem bladknooppunt.
Dit wordt nauwkeuriger een type-ambiguïteitsaanval of cross-node-aanval genoemd en kan worden tegengegaan door een domeinscheider (0x00 voor bladeren, 0x01 voor interne knooppunten) voor de hash te plaatsen.
De Merkle-boomimplementatie van Bitcoin maakt gebruik van dubbele SHA-256-hashing, wat extra weerstand biedt.
Oplossing: Maak altijd onderscheid tussen hashing van bladknooppunten en interne knooppunten; volg vastgestelde standaarden zoals RFC 6962 (Certificate Transparency).
Groei- en prestatierisico van de staat
In Ethereum groeit de state trie met elke nieuwe account- en contractopslagplaats, waardoor de kosten voor het genereren en verifiëren van bewijzen in de loop der tijd toenemen.
De synchronisatietijden van volledige knooppunten worden sterk beïnvloed door de grootte van de statustabel (honderden gigabytes).
Mitigatie: Voorstellen voor het vervallen van de status (EIP-4444, Verkle-bomen) zijn erop gericht de historische status te snoeien; onderzoek naar stateless clients richt zich op het leveren van statusbewijzen bij elk blok.
Culturele relevantie
Merkle-bomen nemen een unieke positie in binnen de cryptovalutacultuur als een van de weinige datastructuren die buiten de informaticakringen naamsbekendheid hebben verworven. De term "Merkle proof" wordt veelvuldig gebruikt op Discord-servers, Twitter-threads en in discussies op governanceforums, vaak door deelnemers die de onderliggende wiskunde misschien niet volledig begrijpen, maar wel de betekenis van de term inzien.
“Merkle-bomen zijn de onbezongen helden van de blockchain. Bedank Ralph Merkle elke keer dat je een transactie verifieert.”
Het concept verwierf grote bekendheid binnen de cryptocultuur tijdens de ineenstorting van FTX in 2022, toen de term "bewijs van reserves" in het publieke debat opdook. Beurzen zoals Binance en Kraken implementeerden op Merkle-bomen gebaseerde systemen voor bewijs van reserves, waardoor gebruikers onafhankelijk konden controleren of hun tegoeden daadwerkelijk tot de door de beurs aangegeven reserves behoorden. De term "Merkle-boom bewijs van reserves" werd een vertrouwenssignaal in de periode na FTX, en liet zien hoe een computerwetenschappelijke uitvinding uit 1979 een cultureel ijkpunt voor financiële verantwoording kon worden.
Binnen de NFT- en airdrop-gemeenschappen is "Merkle airdrop" een gangbare term geworden. Projecten zoals Uniswap, ENS en Optimism gebruikten op Merkle-bomen gebaseerde distributiecontracten waarmee in aanmerking komende adressen tokens konden claimen door een Merkle-bewijs te leveren van hun opname in de distributielijst. Dit patroon, populair gemaakt door de OpenZeppelin-bibliotheek, is door honderden projecten overgenomen en is nu de de facto standaard voor on-chain tokendistributie.
Binnen de ontwikkelaarsgemeenschap wordt regelmatig gedebatteerd over de voor- en nadelen van Merkle-bomen ten opzichte van nieuwere alternatieven zoals Verkle-bomen (voorgesteld voor Ethereums roadmap voor statelessness), wat aantoont hoe diep deze structuur verankerd is in discussies over blockchainarchitectuur.
Voorbeelden uit de echte wereld
Bitcoin SPV-walletverificatie
Scenario: Een gebruiker met een mobiele Bitcoin-wallet op een smartphone met beperkte opslagruimte wil controleren of een ontvangen betaling van 0.5 BTC legitiem is, zonder de volledige blockchain van meer dan 500 GB te hoeven downloaden.
Implementatie: De SPV-wallet downloadt alleen de blokheaders (80 bytes per stuk, in totaal ongeveer 60 MB voor de volledige blockchaingeschiedenis). Wanneer de gebruiker een betaling ontvangt, vraagt de wallet een Merkle-bewijs aan bij een full node – een set van 10-12 sibling hashes die een pad traceren van de transactie naar de Merkle-root in de blokheader.
Resultaat: De wallet verifieert de opname van de transactie in het blok door de hashes opnieuw te berekenen tot aan de Merkle-root, waarmee de legitimiteit van de betaling wordt bevestigd. Dit duurt milliseconden en gebruikt kilobytes aan data, waardoor Bitcoin bruikbaar is op mobiele apparaten met beperkte resources. Dit is precies het gebruiksscenario dat Satoshi beschreef in sectie 8 van de Bitcoin-whitepaper.
Uniswap UNI Token Airdrop (2020)
Scenario: Uniswap moest 150 miljoen UNI-tokens distribueren aan ongeveer 250,000 historische gebruikers. Het opslaan van al deze 250,000 adressen op de blockchain zou miljoenen dollars aan transactiekosten (gas fees) kosten.
Implementatie: Uniswap-engineers construeerden een Merkle-boom met elk in aanmerking komend adres en het bijbehorende claimbare bedrag als bladknooppunten. Alleen de Merkle-root (32 bytes) werd on-chain opgeslagen in het distributiecontract. Elke gebruiker kon zijn tokens claimen door een Merkle-bewijs (ongeveer 18 hashes voor 250,000 adressen) in te dienen dat aantoonde dat hij in de boom was opgenomen.
Resultaat: Het airdrop-contract verbruikte minimale on-chain opslag en stelde elke in aanmerking komende gebruiker in staat om tokens zonder toestemming te claimen. De gaskosten per claim bedroegen ongeveer 80,000-100,000 gas, vergeleken met de miljoenen dollars die het zou hebben gekost om alle adressen vooraf on-chain te laden. Dit patroon is sindsdien de industriestandaard geworden voor tokendistributies.
Binance bewijs van reserves (na FTX, 2022)
Scenario: Na de ineenstorting van FTX stond Binance onder grote druk om aan te tonen dat de klanttegoeden volledig gedekt waren. De beurs beheerde activa voor een zeer groot aantal gebruikersaccounts, waardoor openbaarmaking op individueel accountniveau onpraktisch en een schending van de privacy was.
Implementatie: Binance implementeerde een op Merkle-bomen gebaseerd proof-of-reserves-systeem, waarbij het accountsaldo van elke gebruiker als een leaf-node werd gehasht. Gebruikers konden de aanwezigheid van hun eigen account verifiëren door in te loggen en hun persoonlijke Merkle-bewijs op te vragen, dat ze vervolgens onafhankelijk konden vergelijken met de gepubliceerde Merkle-root. Externe auditors controleerden of de totale reserves overeenkwamen met de Merkle-root-verplichting.
Resultaat: Gebruikers konden de aanwezigheid van hun account in de reservesstructuur verifiëren, waardoor het vertrouwen in gecentraliseerde beurzen gedeeltelijk werd hersteld. De aanpak, hoewel niet perfect (het bewijst niet de afwezigheid van verplichtingen), heeft transparantie op basis van de Merkle-structuur gevestigd als een breed geaccepteerde standaard voor verantwoording binnen beurzen.
Ethereum-statusverificatie voor DeFi-protocollen
Scenario: Een DeFi-leenprotocol op Ethereum moet het huidige onderpandsaldo van een gebruikersaccount op een layer-2 rollup verifiëren voordat een liquidatie kan worden verwerkt.
Implementatie: De rollup plaatst zijn state root (een Merkle root van alle accountsaldi) op het Ethereum mainnet. Het liquidatiecontract op Ethereum accepteert een Merkle proof die het onderpandsaldo van de gebruiker binnen de state tree van de rollup aantoont. Het proof bevat ongeveer 20-30 hashes voor een dunne Merkle tree die een zeer grote ruimte van mogelijke accounts vertegenwoordigt.
Resultaat: De cross-layer liquidatie wordt uitgevoerd zonder dat er een vertrouwensrelatie nodig is – er hoeft geen orakel of bridge relayer te worden vertrouwd. Het Merkle-bewijs koppelt de status van de rollup cryptografisch aan het mainnet-contract, waardoor composability tussen L1 en L2 mogelijk is zonder dat de beveiliging in gevaar komt. Dit algemene patroon wordt gebruikt in een aantal rollup- en cross-chain lending-ontwerpen.
Vergelijkingstabel
Kenmerk
Merkle-boom (binair)
Merkle Patricia Trie (Ethereum)
Verkle-boom (voorgesteld)
Structuur
Binaire boom van hashes
Radix-trie met hash-commitments
Boom met vectorverplichtingen
Bewijs grootte
O(log n) hashes (~32 bytes per stuk)
O(log n) maar groter vanwege vertakkingsfactor 16
O(log n) maar kleiner dan Merkle-proeven
Primair gebruik
Transactie-inclusie (Bitcoin)
Volledige opslag van de wereldstatus (Ethereum)
Stateloze clientverificatie (toekomstig Ethereum)
Sleutelmapping
Positioneel (indexgebaseerd)
Sleutel-waarde (adres-naar-staat)
Sleutel-waarde (adres-naar-staat)
Update kosten
O(log n) herkauwen
O(log n) maar met de overheadkosten van de herstructurering van de proef
O(log n) met goedkopere verplichtingen
Bewijsverificatie
Eenvoudige hash-herberekening
Complexer (meerdere knooppunttypen)
Vereist bewerkingen op elliptische krommen.
Staatsopzwellen
Minimaal (transactielijsten zijn begrensd)
Ernstig (de toestand neemt onbeperkt toe)
Verzacht door kleinere proefafdrukken.
Kwantumweerstand
Op hash gebaseerd (relatief kwantumveilig)
Op hash gebaseerd (relatief kwantumveilig)
Maakt gebruik van elliptische krommen (kwetsbaar voor kwantummechanische effecten).
Volwassenheid
In gebruik sinds 2009 (Bitcoin)
In gebruik sinds 2015 (Ethereum)
Onderzoeks-/implementatiefase (EIP-6800)
Gerelateerde termen
Hash-functie – Een wiskundige functie die invoergegevens omzet in een uitvoer van vaste grootte, en die dient als de fundamentele bouwsteen van elk knooppunt in een Merkle-boom.
Vereenvoudigde betalingsverificatie (SPV) – Een methode voor het verifiëren van Bitcoin-transacties met behulp van alleen blokheaders en Merkle-bewijzen, waardoor lichtgewicht clients mogelijk worden die volledig vertrouwen op de efficiëntie van Merkle-bomen.
Merkle Root – De enkele hash bovenaan een Merkle-boom die dient als cryptografische garantie voor alle gegevens die in de boom zijn opgeslagen, en die in de header van elk blockchainblok is opgenomen.
Koptekst blokkeren – Het metadata-gedeelte van een blockchainblok dat de Merkle-root, de hash van het vorige blok, de tijdstempel en andere protocolspecifieke velden bevat.
Patricia Trie – Een ruimtegeoptimaliseerde trie (prefixboom) die door Ethereum in combinatie met Merkle-hashing wordt gebruikt om de Merkle Patricia Trie te creëren voor het opslaan van de status.
Merkle Tree – Een voorgestelde opvolger van Merkle-bomen in Ethereum die gebruikmaakt van vectorcommitments in plaats van hash-gebaseerde commitments, waardoor de bewijsgrootte wordt verkleind.
Nul-Kennisbewijs – Een cryptografische methode waarmee een partij kennis van een feit kan bewijzen zonder het feit zelf te onthullen, vaak met behulp van Merkle-bomen voor staatsverbintenissen in ZK-rollups.
Bewijs van reserves – Een auditmethode waarbij cryptobeursen Merkle-bomen gebruiken om aan te tonen dat klantstortingen volledig gedekt zijn door on-chain activa.
Airdrop – Een evenement voor de distributie van tokens waarbij doorgaans gebruik wordt gemaakt van op Merkle-bomen gebaseerde smart contracts, waarmee in aanmerking komende ontvangers tokens kunnen claimen door Merkle-bewijzen in te dienen.
State Trie – Ethereum's Merkle Patricia Trie die elk accountadres koppelt aan de huidige status ervan en de ruggengraat vormt van Ethereum's dataopslagarchitectuur.
Binaire boom – Een fundamentele datastructuur in de informatica waarbij elk knooppunt maximaal twee kinderen heeft, en die dient als structurele basis voor standaard Merkle-bomen.
Transactiebewijs – Een datastructuur die wordt gegenereerd na de uitvoering van een Ethereum-transactie en die in een aparte Merkle-trie binnen elk blok wordt opgeslagen voor efficiënte verificatie van het ontvangstbewijs.
FAQ
V: Wat is een Merkle-boom en waarom is deze belangrijk voor blockchain? Een Merkle-boom is een datastructuur die gegevens organiseert in een binaire boom van cryptografische hashes, waarbij één enkele root-hash wordt geproduceerd die de gehele dataset vertegenwoordigt. Het is cruciaal voor blockchain omdat het efficiënte transactieverificatie mogelijk maakt – een lichtgewicht client kan bevestigen dat een transactie in een blok is opgenomen door slechts een klein Merkle-bewijs (logaritmisch van grootte) te controleren in plaats van elke transactie te downloaden.
V: Hoe werkt een Merkle-bewijs? Een Merkle-bewijs bestaat uit de hashes van de sibling-elementen langs het pad van een specifiek bladknooppunt naar de Merkle-wortel. Om te verifiëren, hash je de doelgegevens, combineer je deze met de hash van het eerste sibling-element, hash je het resultaat, combineer je dit met de hash van het volgende sibling-element en herhaal je dit totdat je de wortel bereikt. Als je berekende wortel overeenkomt met de bekende Merkle-wortel, zijn de gegevens geverifieerd als onderdeel van de boom. Voor een boom met 1 miljoen bladeren zijn hiervoor slechts ongeveer 20 hashes nodig.
V: Wat is het verschil tussen een Merkle-boom en een Merkle Patricia Trie? Een standaard Merkle-boom is een eenvoudige binaire hashboom die wordt gebruikt voor geordende lijsten met gegevens (zoals transacties in een Bitcoin-blok). Een Merkle Patricia Trie, gebruikt door Ethereum, is een complexere structuur die een radix-trie (prefixboom) combineert met Merkle-hashing om een sleutel-waardesysteem met aantoonbare integriteit te creëren.
V: Wat zijn Verkle-bomen en zullen ze Merkle-bomen vervangen? Verkle-bomen zijn een voorgestelde upgrade voor Ethereum (EIP-6800) die op hashes gebaseerde toezeggingen vervangen door polynomiale (vector) toezeggingen, waardoor kleinere bewijzen ontstaan die van belang zijn voor de roadmap van Ethereum voor stateless clients. Verkle-bomen zijn echter gebaseerd op elliptische-curve-cryptografie, die potentieel kwetsbaar is voor kwantumcomputers, terwijl op hashes gebaseerde Merkle-bomen als kwantumbestendiger worden beschouwd.
V: Hoe worden Merkle-bomen gebruikt bij NFT- en token-airdrops? Projecten bouwen een Merkle-boom met in aanmerking komende walletadressen (en de bedragen die ze kunnen claimen) als bladeren. Alleen de Merkle-root wordt on-chain opgeslagen, wat gaskosten bespaart. Elke in aanmerking komende gebruiker kan tokens claimen door zijn Merkle-bewijs in te dienen – een kleine set hashes die bewijzen dat zijn adres in de boom voorkomt. Dit patroon, populair gemaakt door de MerkleProof-bibliotheek van OpenZeppelin, is gebruikt door Uniswap, ENS, Optimism en honderden andere projecten.
V: Kunnen Merkle-bomen worden gebruikt voor privacydoeleinden? Standaard Merkle-bomen bieden geen privacy – alle gegevens zijn zichtbaar. Er bestaan echter gespecialiseerde varianten die worden gebruikt in privacybeschermende systemen. Zero-knowledge Merkle-bewijzen maken het mogelijk om inclusie te bewijzen zonder de bladgegevens te onthullen, waardoor privétransacties en vertrouwelijke statusverificatie mogelijk zijn.
V: Wat gebeurt er als twee verschillende datasets dezelfde Merkle-root opleveren? Dit zou een hash-botsing zijn – twee verschillende invoerwaarden die dezelfde uitvoer van de hashfunctie produceren. Met SHA-256 (gebruikt in Bitcoin) zou het vinden van zo'n botsing ongeveer 2^128 bewerkingen vereisen, wat computationeel onhaalbaar is met de huidige en toekomstige technologie.
Bronnen
Merkle, RC “Een digitale handtekening gebaseerd op een conventionele encryptiefunctie”
