Hash-boom

Een hash-boom of hash tree is een boom die kan worden gebruikt om gegevens veilig tussen twee computers te sturen. Ze worden op het moment vooral gebruikt om na te gaan of alle gegevens zijn aangekomen en of de gegevens onbeschadigd zijn. Een hash-boom kan als een graaf worden weergegeven. De hash-boom is in 1979 door Ralph Merkle uitgevonden en daarom worden hash-bomen ook wel merkle-bomen genoemd, in het Engels bijvoorbeeld een Merkle tree.

Een hash-boom is vaak een binaire boom. Dit houdt in dat iedere knoop twee knopen onder zich heeft. Het is wel mogelijk om een hash tree te maken met meer knopen onder iedere knoop. Om een hash tree te maken beginnen we onderaan, bij de bladeren van de boom. We hakken het bericht ${\displaystyle \ M}$ in stukken ${\displaystyle \ {m_{1},m_{2},...,m_{n}}}$ en elk stuk zetten we om in een hashwaarde met behulp van een hashfunctie ${\displaystyle H}$. Elk blaadje ${\displaystyle \ v_{1,j}}$ krijgt dus de hashwaarde ${\displaystyle H(m_{j})}$. De knopen ${\displaystyle \ v_{i,j}}$ kunnen we bepalen door de hashwaarde van de twee knopen ${\displaystyle \ v_{i-1,j*2-1}}$ en ${\displaystyle \ v_{i-1,j*2}}$ om te zetten in een nieuwe hashwaarde ${\displaystyle \ H(v_{i-1,j*2-1}||v_{i-1,j*2})}$ . Zo wordt de hele boom opgebouwd tot de topknoop ${\displaystyle \ v_{d,1}}$. Deze topknoop is de belangrijkste knoop van de boom en wordt opgestuurd door een betrouwbare bron. De ontvanger kan beginnen met downloaden van de gegevensblokken nadat hij de topknoop binnen heeft gekregen.

Zodra de hele boom is gedownload kan er onderzocht worden of de gegevens kloppen. De ingekomen gegevensblokken worden omgezet in hashwaarden en de hele boom wordt opgezet. Als een blok niet klopt krijgt deze een andere hashwaarden dan het moest zijn. Zo krijgen de knopen boven deze knoop ook andere hashwaarden, dus zal de topknoop van de boom niet overeenkomen met de topknoop die opgestuurd is. De boom is dus onjuist en moet opnieuw gedownload worden.

Hash-bomen zijn vooral toe te passen in peer-to-peer-netwerken. Een betrouwbare bron berekent de hele boom en stuurt de topknoop op. De rest van de blokken kan van elke bron vandaan komen. Met behulp van de hashfunctie kan er dan bepaald worden of alle gegevens zijn aangekomen, of er geen fouten in zitten of dat er iemand veranderingen heeft aangebracht.

Het originele doel van hash trees was om het mogelijk te maken om efficiënt om te gaan met Lamport-handtekeningen. Deze wachtwoorden zijn zeer moeilijk te kraken, maar elke Lamport Key kan maar voor één bericht gebruikt worden. In combinatie met hash trees kunnen ze ineens wel voor meer berichten gebruikt worden waardoor Lamport-handtekeningen veel efficiënter worden, omdat alleen de topknoop een handtekening nodig heeft.

Persoon A wil graag het bericht 'Dit is een hash boom' downloaden binnen een netwerk. Persoon B krijgt deze vraag binnen en begint de boom op te stellen. Hij begint met het in stukken hakken van het bericht. Dit levert hem 5 stukjes op. Hij gebruikt een 8-bit hashfunctie. Dit is alleen ter illustratie, want in het echt worden er veel langere hashfuncties gebruikt. Hij zet elk stukje van het bericht om in hashwaarden, dus heeft nu de bladeren van de boom gemaakt.

De volgende stap is de hashwaarden van iedere knoop te berekenen door de twee hashwaarden van de knopen onder die knoop samen te nemen en om te zetten in een nieuwe hashwaarde. Hiermee gaat hij door tot de topknoop is bereikt. Deze node stuurt hij op naar persoon A.

Persoon A krijgt dus de topknoop binnen van persoon B. Hij kan nu beginnen met downloaden van het bericht. Alle stukjes komen van verschillende personen vandaan. Zodra alles binnen is begint hij de boom op te bouwen zoals persoon B dat had gedaan. Dus eerste alle stukjes van het bericht omzetten in hashwaarden en daarmee de hogere knopen te bepalen. De topknoop die hij zo krijgt vergelijkt hij met de hashwaarde van de topknoop die hij van persoon B binnen heeft gekregen. Als alles goed is binnen gekomen moeten deze hashwaarden dus gelijk aan elkaar zijn. Is dit niet het geval dan is er iets mis met de binnengekomen stukjes.

• Merkle tree patent 4,309,569  USPTO Patent Full-Text and Image Database
• Tree Hash EXchange format (THEX). gearchiveerd
• RSA Laboratories. Recent Improvements in the Efficient Use of Merkle Trees: Additional Options for the Long Term, 10 maart 2004. gearchiveerd

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Hash tree op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.