Hash-boom (Merkle tree)

Wat is een Hash-boom?

Een Hash-boom, ook wel Merkle tree genoemd, is een datastructuur die gebruikt wordt in de cryptografie, blockchains en sommige cryptocurrencies om de integriteit van data-elementen binnen een grotere dataset te verifiëren.

Een Hash-boom bestaat uit blokken met gegevens die elk worden omgezet in een unieke hash. De individuele hashes worden dan gekoppeld en opnieuw gehasht, een proces dat bekend staat als ‘concatenation’. Dit proces gaat door tot er slechts één hash overblijft, de zogenaamde Merkle root.

De root biedt een enkel referentiepunt voor de hele dataset.

Techopedia legt uit

Boomstructuren zijn hiërarchische gegevensstructuren met een ouder-kind relatie tussen knooppunten. Na verloop van tijd is het plaatsen van de wortels van een boom aan de bovenkant van een diagram een standaard manier geworden om boomstructuren in de informatica weer te geven.

De reden voor de omgekeerde oriëntatie kan worden toegeschreven aan historische conventies in diagrammen. Bijvoorbeeld, veel hiërarchische representaties, zoals organogrammen, worden van nature van boven naar beneden gelezen.

Hoe Hash-bomen worden gemaakt

Hash-bomen worden gemaakt met cryptografische hashfuncties die invoergegevens omzetten in tekenreeksen met een vaste grootte, genaamd hashes. Elke hash in de boom vertegenwoordigt een specifiek data-element of een blok data-elementen.

Terwijl de boom vanaf de basis (het bladniveau van de boom) naar boven wordt opgebouwd, vertegenwoordigt elke volgende hash een combinatie van de hashes van de kinderen van de ouder, totdat de bovenste hash, de Merkle root, effectief alle invoergegevens vertegenwoordigt.

Om een Hash-boom te construeren, wordt de volledige dataset eerst verdeeld in kleinere segmenten die blokken worden genoemd. Als er geen even aantal blokken is, wordt het laatste blok gedupliceerd om pariteit te verkrijgen. Elk blok krijgt dan een hash toegewezen, die een bladknoop wordt in de boom.

Om de hiërarchie van de boom te bepalen, worden twee naburige hashes gecombineerd (concatenated). Het samengevoegde paar wordt dan gehasht om een ‘parent knooppunt’ te produceren dat zich boven de twee originele bladknooppunten bevindt.

Het proces van koppelen en hashen gaat laag per laag verder, waarbij de boom omhoog gaat totdat er nog maar één hash overblijft aan de top. De uiteindelijke hash, bekend als de “Merkle root” of “root hash”, vat de hele dataset samen.

Hoe Hash-bomen worden gebruikt voor gegevensverificatie

Met Merkle trees kunnen specifieke gegevensitems die deel uitmaken van een grote dataset snel en efficiënt worden geverifieerd door een subset van de hashes van de boom te inspecteren. In wezen bestaat het proces uit het controleren van het pad van het gegevensblok in kwestie naar de Merkle root.

Hier volgt een vereenvoudigd overzicht van het verificatieproces:

  • Begin het verificatieproces met het lokaliseren van de hash van het specifieke gegevensblok dat moet worden geverifieerd.
  • Ga omhoog in de boom. Lokaliseer op elk niveau van de boom de aangrenzende (zuster) hash van de huidige hash, concateneer (combineer) deze met zijn zuster en hash de resulterende combinatie.
  • Vergelijk de nieuw berekende hash met de hash van de parent node in de boom. Als er een overeenkomst is, ga dan verder met het proces tot de Merkle root is bereikt.

Zolang de nieuw berekende hashes overeenkomen met de parent node hashes in de originele boom, kan de integriteit van het specifieke gegevensblok in kwestie worden geverifieerd.

(Elke wijziging in de gegevens zou discrepanties veroorzaken in de hashes van de paden of de Merkle root).

De rol van Hash-bomen in Blockchains en Bitcoin

Hash-bomen zijn handig voor het controleren op inconsistenties en het valideren van blockchains.

Door transactiehashes te organiseren in een Hash-boom, kan elk blockchainknooppunt snel en efficiënt controleren of een bepaalde transactie bestaat in een blok. Deze structuur helpt ook om de integriteit van de gegevens in een specifiek blok te garanderen, want als zelfs maar één enkele transactie verandert, zal de Merkle root (de bovenste hash van de boom) ook veranderen en inconsistenties detecteerbaar maken.

In het Bitcoin-protocol, wanneer een nieuw blok wordt toegevoegd aan de blockchain, bevat elk blok de Merkle root van een Hash-boom in de header. Dit creëert automatisch een “proof-of-inclusion” voor elke Bitcoin-transactie.

Proof-of-inclusion is een manier om aan te tonen dat een specifieke transactie deel uitmaakt van een blok zonder alle transacties in dat blok te hoeven onthullen of controleren. Dit bewijs is vooral cruciaal voor lichtgewicht SPV (Simplified Payment Verification) wallets die niet de volledige blockchain downloaden om transacties te verifiëren.

Hash-bomen spelen ook een rol in “proof-of-reserves”. Proof of Reserves is een methode die wordt gebruikt door cryptocurrency exchanges en walletproviders om te bewijzen dat ze voldoende geld hebben om de tegoeden van hun klanten te dekken.

Gerelateerde begrippen

Margaret Rouse

Margaret Rouse is een bekroond technisch schrijver en docent die bekend staat om haar vermogen om complexe technische onderwerpen uit te leggen aan een niet-technisch, zakelijk publiek. In de afgelopen twintig jaar is haar uitleg verschenen op vele websites en is ze als autoriteit aangehaald in artikelen van de New York Times, Time Magazine, USA Today, ZDNet, PC Magazine en Discovery Magazine. Margaret geniet ervan om IT- en business professionals te helpen om elkaars zeer gespecialiseerde talen te begrijpen. Als je een suggestie hebt voor een nieuwe definitie of hoe je een technische uitleg kunt verbeteren, stuur Margaret dan een…