Merkle tree

Een Merkle tree is een datastructuur die een grote verzameling items samenvat in één enkele hash door herhaaldelijk te paren en te hashen: elke transactie wordt gehasht, de hashes worden in paren samen gehasht, die resultaten worden opnieuw in paren gehasht, enzovoort totdat er één waarde overblijft — de Merkle root. Blockchains slaan deze root op in elke blokheader, waarmee met slechts 32 bytes elke transactie in het blok wordt vastgelegd.

De kracht van de structuur is efficiënt bewijs. Om aan te tonen dat één specifieke transactie in een blok zit, heb je niet het hele blok nodig — alleen de transactie en de handvol aangrenzende hashes langs het pad naar de root, een Merkle proof genoemd. Een verifier berekent het pad opnieuw en controleert of dat de bekende root oplevert; bij een blok met duizenden transacties gaat het bewijs om slechts een twaalftal hashes. Zo bevestigt bijvoorbeeld een lichte Bitcoin-wallet op een telefoon dat er is betaald: die bewaart alleen blokheaders, vraagt een full node om de Merkle proof van zijn transactie en controleert de wiskunde zelf — de node kan de opname in het blok niet vervalsen, omdat daarvoor de hashfunctie gebroken zou moeten worden.

Een veelvoorkomende misvatting is dat Merkle trees de transactiedata zelf opslaan of beschermen; ze leggen die alleen vast — de data staat elders, en de boom maakt knoeien detecteerbaar, niet onmogelijk om te proberen. Varianten breiden het idee uit: Ethereum gebruikt Merkle-Patricia-tries om zijn hele accountstatus vast te leggen, en nieuwere ontwerpen zoals Verkle trees willen bewijzen nog kleiner maken, wat ertoe doet om ketenverificatie lichter te maken.