Merkle Tree
Een merkle tree, ook wel een hash tree (vertaling: hash-boom) genoemd, is een binaire hashboom waarin elke node (knooppunt) gelabeld is met de hash is van twee samengevoegde onderliggende nodes. De hoogste liggende node- de merkle root of ‘top-node’- bevat informatie over alle data in de boom. Dit heeft als gevolg dat een kleine verandering in data een andere merkle root geeft.
Merkle trees zijn genoemd naar zijn uitvinder, Ralph Merkle.
In Bitcoin worden o.a. txid’s op deze manier gebundeld. De merkle root van deze boom is onderdeel van de block header, hetgeen wat door miners gehashed wordt.
Het voordeel van het toepassen van een boomstructuur is dat voor verificatie van de inhoud van de tree erg efficiënt is voor grote datasets. Een merkle tree schaalt namelijk logaritmisch. Dit betekent dat voor N txid’s maar log2(N) hashes nodig zijn. In Bitcoin zitten er al gauw 2000+ transacties in een blok. In plaats van 2000 hashes zijn er nu dus maar 11 nodig.
Dankzij merkle trees zijn lightweight-clients mogelijk, die transacties verifiëren zonder de gehele blockchain te downloaden en op te slaan. Een block header is immers maar ~80 bytes waar een blok vaak 1-2Mb is.
Het verificatieproces van data in een merkle tree heet ook wel een merkle proof.
Stel je wilt verifiëren dat txid 7 onderdeel van dit blok is. Een merkle proof gaat dan als volgt:
- Een full-node geeft de de block header (met daarin de merkle root), de merkle proof en txid 7 aan de light-client. De merkle proof bevat alle gekleurde nodes (txid 8, h56 en h1,4).
- De light-client hasht txid 7 en txid 8 en voegt deze samen waarna deze samen nogmaals gehashed wordt tot h78.
- De light-client voegt h78 en h56 samen en hasht dit tot h5,8.
- De light-client voegt h5,8 en h1,4 samen en hasht dit tot h1,8. h1,8 de merkle root.
- Als de berekende merkle root hetzelfde is als de door de full-node gegeven merkle root, is geverifieerd dat txid 7 in dit blok zit.
