Et Merkle tree er en datastruktur, der bruges inden for datalogi og kryptografi. På kryptomarkedet betegner et Merkle tree en datastruktur, som indeholder et sammendrag af de transaktioner, der er gennemført på blockchainen ved hjælp af en hashfunktion. Merkle tree gør det nemt og effektivt at verificere transaktionsblokke på blockchainen. I denne artikel får du svar på, hvad et Merkle tree egentlig er.
Merkle tree blev opfundet af Ralph Merkle. Han patenterede konceptet i 1979 og omtalte det i artiklen "En digital signatur baseret på en konventionel krypteringsfunktion", der udkom i 1987. Et Merkle tree er en diagramformet datastruktur, der består af hashværdier. Hashkoderne for de enkelte data står opstillet i diagrammet nedefra og op, og værdien af en hash længere oppe bestemmes ved at lægge hashværdierne under den sammen.
Dataintegriteten i systemet sikres netop af denne opbygning: hashværdierne står ordnet i et diagram og lægges trin for trin sammen nedefra og op. Strukturen bruges ved dataoverførsler fra person til person, i peer-to-peer-netværk og til at verificere de overførte data. Med et Merkle tree kan man se, om de overførte data eller datablokke er beskadigede eller forfalskede – og netop derfor kan blokkenes rigtighed bekræftes med det.
Hvordan fungerer et Merkle tree?
Et Merkle tree består af de hashværdier, der ligger i blokkene. Nederst i træet finder man selve transaktionsdataene. Hashværdien (hashkoden) for disse data fremkommer ved at køre hashfunktionen. Derefter lægges værdierne nederst i diagrammet sammen to og to, og resultatet skrives ind i rækken ovenover. Ved at gentage processen bygges hele Merkle tree op. Til sidst kaldes hashværdien øverst i diagrammet for root hash eller Merkle root. Den beregnede root hash afslører, om der er fejl i blokkene. Er der uoverensstemmelser i de værdier, som root hash er bygget af, arbejder systemets algoritme videre med hashfunktioner, indtil den danner en fejlfri Merkle root.
Hvorfor bruges Merkle tree i Bitcoin?
Fordi det gør arbejdet lettere for de minere, der skal verificere blokke på Bitcoins blockchain. Minere på Bitcoin-blockchainen verificerer blokke ved at køre hashfunktionen. På Bitcoin-blockchainen sorteres dataene og placeres i et Merkle tree, hvorefter algoritmens hashfunktioner beregner root hash. Den resulterende root hash kan også bruges i det videre mining-arbejde. På den måde kan minerne fortsætte deres arbejde ved kun at hashe root hash i stedet for at hashe alle blokke. Merkle tree leverer også løsninger på blockchains for andre kryptovalutaer end Bitcoin.