Merkle Tree

Wat is een Merkle Tree?

Een Merkle-boom is een datastructuur die wordt gebruikt in computerwetenschappelijke toepassingen. In bitcoin en andere cryptocurrencies dienen Merkle-bomen om blockchain-gegevens efficiënter en veiliger te coderen.

Ze worden ook wel “binaire hash-bomen” genoemd.

Merkle Tree afbreken

In de blockchain van bitcoin wordt een transactieblok door een algoritme geleid om een hash te genereren, een reeks cijfers en letters die kan worden gebruikt om te verifiëren dat een bepaalde set gegevens hetzelfde is als de oorspronkelijke set transacties, maar niet om de oorspronkelijke set transacties te verkrijgen. De software van Bitcoin voert echter niet het hele blok transactiegegevens – gemiddeld 10 minuten aan transacties uit – in één keer door de hash-functie. In plaats daarvan wordt elke transactie gehasht, dan wordt elk paar transacties aaneengeschakeld en samen gehasht, enzovoort totdat er één hash is voor het hele blok. (Als er een oneven aantal transacties is, wordt één transactie verdubbeld en wordt de hash met zichzelf samengevoegd.)

Gevisualiseerd, lijkt deze structuur op een boom. In het onderstaande diagram duidt “T” een transactie aan, “H” een hash. Merk op dat de afbeelding sterk vereenvoudigd is; een gemiddeld blok bevat meer dan 500 transacties, geen acht.

De hashes op de onderste rij worden “bladeren” genoemd, de tussenliggende hashes als “takken” en de hasj bovenaan als de “wortel”. De Merkle-root van een bepaald blok wordt opgeslagen in de header: de Merkle-root van blok # 482819 is bijvoorbeeld e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. De root wordt gecombineerd met andere informatie (de softwareversie, de hash van het vorige blok, de tijdstempel, het moeilijkheidsdoel en de nonce) en vervolgens doorlopen via een hashfunctie om de unieke hash van het blok te produceren: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b089594 in het geval van blok # 482819. Deze hash zit niet echt in het relevante blok, maar in de volgende; het verschilt van de Merkle-wortel.

De Merkle-boom is handig omdat het gebruikers in staat stelt een specifieke transactie te verifiëren zonder de hele blockchain te downloaden (meer dan 130 gigabyte eind augustus 2017). Stel bijvoorbeeld dat u wilt verifiëren dat transactie T D  is opgenomen in het blok in het bovenstaande diagram. Als je de root-hash (H ABCDEFGH ) hebt, is het proces als een spelletje sudoku: je vraagt ​​het netwerk naar H D en het retourneert H C, H AB en H EFGH. Met de Merkle-structuur kunt u verifiëren dat alles wordt verantwoord met drie hashes: gegeven H AB, H C, H EFGH en de wortel H ABCDEFGH, moet H D  (de enige ontbrekende hash) aanwezig zijn in de gegevens.

Merkle-bomen zijn vernoemd naar Ralph Merkle, die ze voorstelde in een paper uit 1987 met de titel ” Een digitale handtekening op basis van een conventionele coderingsfunctie “. Merkle vond ook cryptografisch hashen uit.