Et Merkle-tre er en datastruktur som brukes i datavitenskapelige applikasjoner. I bitcoin og andre cryptocurrencies tjener Merkle-trær til å kode blockchain-data mer effektivt og sikkert.
De blir også referert til som "binære hasjtrær."
Breaking Down Merkle Tree
I bitcoin's blockchain kjøres en blokk med transaksjoner gjennom en algoritme for å generere en hash, som er en streng med tall og bokstaver som kan brukes til å bekrefte at et gitt datasett er det samme som det opprinnelige settet med transaksjoner, men ikke for å oppnå det opprinnelige settet med transaksjoner. Bitcoin-programvaren kjører ikke hele blokken med transaksjonsdata - som i gjennomsnitt representerer 10 minutters transaksjoner - gjennom hasjfunksjonen på en gang, imidlertid. Snarere er hver transaksjon hashet, så blir hvert par av transaksjoner sammenkjørt og hashet sammen, og så videre til det er en hasj for hele blokken. (Hvis det er et ulikt antall transaksjoner, blir en transaksjon doblet og hashens side er sammenkoblet med seg selv.)
Visualisert, denne strukturen ligner et tre. I diagrammet nedenfor betegner "T" en transaksjon, "H" en hasj. Legg merke til at bildet er svært forenklet; en gjennomsnittlig blokk inneholder over 500 transaksjoner, ikke åtte.
Hasjene på den nederste raden blir referert til som "blader", mellomliggende hasjene som "grener", og hasjen øverst som "roten." Merkle-roten til en gitt blokk blir lagret i overskriften: for eksempel er Merkle-roten til blokk # 482819 e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Roten er kombinert med annen informasjon (programvareversjonen, den forrige blokkens hasj, tidsstemplet, vanskelighetsmålet og feilen) og kjøres deretter gjennom en hasjfunksjon for å produsere blokkens unike hash: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 i tilfelle av block # 48. Denne hasjen er faktisk ikke inkludert i den aktuelle blokken, men den neste; den er forskjellig fra Merkle-roten.
Merkle-treet er nyttig fordi det lar brukere bekrefte en spesifikk transaksjon uten å laste ned hele blockchain (over 130 gigabyte i slutten av august 2017). Si for eksempel at du ønsket å bekrefte at transaksjon T D er inkludert i blokken i diagrammet over. Hvis du har roten-hasj (H ABCDEFGH), er prosessen som et spill med sudoku: du spør i nettverket om H D, og det returnerer H C, H AB og H EFGH. Merkle-treet lar deg bekrefte at alt blir gjort rede for med tre hasjer: gitt H AB, H C, H EFGH, og roten H ABCDEFGH, H D (den eneste manglende hasj) må være til stede i dataene.
Merkle-trær er oppkalt etter Ralph Merkle, som foreslo dem i et papir fra 1987 med tittelen "En digital signatur basert på en konvensjonell krypteringsfunksjon." Merkle oppfant også kryptografisk hashing.
