Wat is Merkle Tree?

Merkle Tree is een datastructuur die een grote verzameling records samendrukt tot één korte vingerafdruk. Daarmee kun je aantonen dat een item in een enorme lijst staat door slechts een paar kleine stukken te controleren, niet het hele geheel. Stel je een stamboom voor waarin elke ouder een samenvatting is van zijn kinderen, die allemaal samenkomen in één uiteindelijke voorouder.

Mythe

Merkle Tree "slaat" alle transacties zelf op. Niet helemaal. Het bewaart alleen compacte vingerafdrukken ervan, en de boom kan steeds opnieuw worden opgebouwd uit de ruwe records wanneer dat nodig is.

Hoe Merkle Tree werkt

Stel je een blok betalingen voor dat een snelle, verifieerbare samenvatting nodig heeft. Zo werkt Merkle Tree in eenvoudige bewoordingen:

Stap 1: Begin met een lijst items zoals transacties; elk item is een blad in de boom.
Stap 2: Zet elk item om in een korte vingerafdruk met behulp van een hashfunctie.
Stap 3: Koppel aangrenzende vingerafdrukken, voeg elk paar samen en bereken daar weer een hash van om hun ouder te maken.
Stap 4: Herhaal het koppelen en hashen tot er één bovenste vingerafdruk overblijft. Dat is de Merkle root van deze set.
Stap 5: Om te bewijzen dat een item in de set zit, heb je alleen dat item nodig plus een kort pad met de vingerafdrukken van broertjes of zusjes. Snel en compact.

Dat is het idee: kleine bewijzen, grote zekerheid.

Waarom Merkle Tree van belang is

Door enorme hopen transactiegegevens samen te vatten tot één compacte vingerafdruk, maakt Merkle Tree verificatie snel en goedkoop.

Voordeel: Je kunt inclusie controleren zonder het hele blok te downloaden, wat tijd en bandbreedte bespaart.
Perspectief: Het past bij de huidige internetmentaliteit: vertrouw maar verifieer, Rolex ontmoet Reddit-draadjes.
Relevantie: Je komt het tegen in Bitcoin-blokken, Ethereum-receipts, NFT-allowlists, airdrops en rollups.

Tip

Als het aantal bladeren oneven is, dupliceren veel ontwerpen het laatste blad voordat ze omhoog hashen in de boom. Controleer ook goed het exacte hashproces dat jouw keten of bibliotheek gebruikt, omdat kleine regelverschillen bewijzen kunnen veranderen.

Belangrijkste kenmerken van Merkle Tree

Dit maakt het bijzonder en praktisch:

Efficiëntie: Bewijzen blijven klein, ook als de dataset enorm groeit, zodat lichte clients licht blijven.
Integriteit: Verander één byte in een blad en de wijziging loopt door naar de top, waardoor manipulatie duidelijk wordt.
Root: Alles valt samen in een enkele Merkle root die kan worden opgeslagen of ondertekend voor latere controles.

Varianten

Merkle Tree heeft een paar populaire varianten die je vaak tegenkomt:

Binair: De klassieke op paren gebaseerde boom, gebruikt in Bitcoin-blokken.
Merkle Patricia: Een op trie gebaseerde versie voor key-value data, gebruikt voor de Ethereum-state en receipts.
Sparse: Een enorm geïndexeerde boom waar de meeste bladeren leeg zijn, geschikt voor beknopte bewijzen van aanwezigheid en afwezigheid.
Verkle: Een nieuwere verwant met kortere bewijzen bij hoge vertakkingsgraad, onderzocht voor mogelijke toekomstige upgrades.

Herinnering

Bewijzen van Merkle Tree zijn alleen zo betrouwbaar als de header of checkpoint die je accepteert. Als je de verkeerde root vertrouwt, zegt het meest zuivere bewijs nog niets.

Voorbeeld

Een Bitcoin-stijl lichte wallet kan je betaling verifiëren door een kort pad met hashes te controleren van je transactie tot aan de blockheader, zonder de volledige transactiegeschiedenis te downloaden.

Leuk weetje

Ralph Merkle schetste dit idee eind jaren zeventig als studentenproject, en het bleef jaren in academische kringen voordat Satoshi het in Bitcoin gebruikte. Het bewijst dat goede ideeën de tand des tijds doorstaan.

Samenvatting

Kort gezegd? Merkle Tree geeft je snelle, compacte bewijzen dat iets bij een grote verzameling hoort, zonder zware downloads.

Merkle Tree