Hash-boom

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een hash-boom (Engels: hash tree) is een boom die kan worden gebruikt om gegevens (data) 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. De hash-boom is uitgevonden door Ralph Merkle in 1979 en daarom worden hash-bomen ook wel Merkle-bomen genoemd.

Opbouw[bewerken]

De hash tree

Een hash-boom is vaak een binaire boom. Dit houdt in dat elke parent node twee child nodes heeft. Het is wel mogelijk om een hash tree te maken met meerdere child nodes. Om een hash tree te maken beginnen we onderaan, bij de bladeren van de boom. We hakken het bericht \ M in stukken \ {m_1, m_2, ..., m_n} en elk stuk zetten we om in een hashwaarde met behulp van een Hashfunctie \ H. Elk blaadje \ v_{1, j} krijgt dus de hash waarde \ H(m_j). De parent nodes \ v_{i, j} kunnen we bepalen door de hashwaarde van de twee childs \ v_{i-1, j*2-1} en \ v_{i-1, j*2} om te zetten in een nieuwe hashwaarde \ H( v_{i-1, j*2-1} || v_{i-1, j*2}) . Zo wordt de hele boom opgebouwd tot de top \ v_{d,1}. Deze top node is de belangrijkste node van de boom en wordt opgestuurd door een betrouwbare bron. De ontvanger kan beginnen met downloaden van de datablocks nadat hij deze top binnen heeft gekregen.

Zodra de hele boom is gedownload kan er onderzocht worden of de gegevens kloppen. De ingekomen datablokken worden omgezet in hashwaarden en de hele boom wordt opgezet. Als een datablok niet klopt krijgt deze een andere hashwaarden dan de juiste datablock. Zo krijgen de parents van deze child ook andere hashwaarden en zal dus de top van de boom niet overeenkomen met de top die opgestuurd is. De boom is dus onjuist en moet opnieuw gedownload worden.

Toepassingen[bewerken]

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

De originele doel van hash-trees was om het mogelijk te maken om efficiënt om te gaan met Lamport one-time signatures. Lamport Signiture 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 meerdere berichten gebruikt worden waardoor Lamport Signitures veel efficiënter worden. Alleen de top heeft namelijk een handtekening nodig.

Voorbeeld[bewerken]

Gezien een voorbeeld vaak duidelijker is dan een lap tekst volgt hier een voorbeeld van de hash-boom. 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 enkel ter illustratie, want in het echt worden er veel langere hashfuncties gebruikt. Hij zet elk stukje van het bericht om een hashwaarden en heeft dus nu de bladeren van de boom gemaakt.

Stap 1: De bladeren

De volgende stap is de hashwaarden van elke parent node te berekenen door de twee hashwaarden de van childnodes samen te nemen en om te zetten in een nieuwe hashwaarde. Hiermee gaat hij door tot hij de top node heeft bereikt. Deze node stuurd hij op naar persoon A.

Stap 2: De parents

Stap 3: De top

Persoon A krijgt dus de top node binnen van persoon B. Hij kun 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 parentnodes te bepalen. De top node die hij zo krijgt vergelijkt hij met de hashwaarde van de top node dat 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.

Referenties[bewerken]