Drzewo hash

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Drzewo hash, H-drzewo (ang. Hash Trees) – w kryptografii i informatyce drzewo hash lub drzewo merkle – rodzaj struktury danych, która zawiera drzewo z informacjami zbiorczymi na temat większego fragmentu danych. Hash drzewa są kombinacją hash list i hash łańcuchów, które z kolei są przedłużeniem haszowania. Hash drzewa, w których podstawową funkcją skrótu jest Tiger, są często nazywane drzewami Tiger.

Zastosowanie[edytuj | edytuj kod]

Hash drzewa mogą być używane do weryfikacji wszelkiego rodzaju przechowywanych danych, przechowywane i przenoszone między komputerami. Obecnie głównym zastosowaniem hash drzew jest upewnienie się, że bloki danych otrzymanych od innych użytkowników za pośrednictwem sieci peer-to-peer są odbierane w stanie nieuszkodzonym i niezmienionym. Mogą być użyte do weryfikacji poprawności bloków danych otrzymywanych od innych użytkowników. Firma Sun Microsystems wykorzystuje drzewa Hash w systemie plików ZFS. Hash drzewa są również używane w programie Google Wave, rozproszonych systemiach kontroli wersji, w rozproszonym sytemie plików Tahoe-LAFS, kryptowalucie Bitcoin.

Hash drzewa zostały wynalezione w 1979 przez Ralpha Merkle. Pierwotnym celem ich istnienia było umożliwienie efektywnej obsługi wielu jednorazowych podpisów elektronicznych (Lamport). Uważa się, że podpisy Lamport są odporne na atak za pomocą komputerów kwantowych. Każdy klucz Lamport może być używany tylko do podpisania pojedynczej wiadomości, ale w połączeniu z drzewami hash mogą one być wykorzystywane do podpisywaniua wielu wiadomości, a następnie stać się dość wydajnym schematem podpisu cyfrowego.

Działanie hash drzewa[edytuj | edytuj kod]

Hash drzewo to drzewo, w którym liście są blokami danych. Danymi tymi może być plik lub zestaw plików. Wierzchołki położone wyżej (rodzice) są skrótami wierzchołków które są jego dziećmi. Na przykład, w hash obrazie 0, który jest wynikiem mieszania hash 0-0, a następnie mieszania 0-1. Oznacza to, że hash 0 = hash (hash 0-0 | | hash 0-1). Większość hash implementacji jest binarnych (dwa węzły potomne pod każdym węzłem), ale mogą równie dobrze korzystać z innych węzłów potomnych pod każdym węzłem.Kryptograficzna funkcja skrótu taka jak SHA-1, Whirlpool czy Tiger jest stosowana do hashowania.

Jeśli hash drzewo potrzebuje skrótu tylko do ochrony przed przypadkowym uszkodzeniem, to mogą być użyte bardziej bezpieczne takie jak CRC. W górnej części drzewa Hash jest top hash (lub hash master). Przed pobraniem pliku w sieci p2p, w większości przypadków górę Hash uzyskuje się z zaufanego źródła lub ze strony internetowej, która jest znana z dobrych rekomendacji plików do pobrania. Kiedy góra hash jest dostępna, hash drzewo można odebrać z dowolnego niezaufanego źródła, jak użytkownik w sieci p2p. Potem otrzymane drzewo Hash jest ponownie sprawdzane i jeśli hash drzewo jest uszkodzone lub fałszywe, inne hash drzewo z innego źródła będzie wypróbowane, dopóki program nie znajdzie tego, które przypasuje z górą Hash. Główną różnicą od Hash listy jest to, że jedna gałąź hash drzewa może być pobrana w czasie i integralność każdej gałęzi można sprawdzić od razu, nawet jeśli całe drzewo nie jest jeszcze dostępne.

Na przykład obraz integralności bloku danych 2 można sprawdzić natychmiast, jeśli drzewo zawiera już hash 0-0 i hash 1 w wyniku wymieszania bloku danych. Ostatecznie można porównać wynik z górnym hash. Podobnie, integralność bloku danych 3 można sprawdzić, jeśli drzewo ma już 1-1 i hash 0. Zaletą może być to, że można skutecznie dzielić pliki w bardzo małych blokach danych tak, że tylko małe bloki muszą być ponownie pobrane, jeśli ulegną uszkodzeniu. Jeśli haszowany plik jest bardzo duży to drzewo hash lub hash lista stają się dość duże. Ale jeśli jest to drzewo to jedną mała gałąź można pobrać szybko, integralność gałęzi może być sprawdzona, a następnie pobieranie bloków danych może zostać rozpoczęte.

Hash drzewo Tiger[edytuj | edytuj kod]

Hash drzewo Tiger jest powszechnie stosowaną formą skrótu drzewa. Używa binarnych hash drzew (dwa węzły potomne pod każdym węzłem), zazwyczaj ma rozmiar bloku danych 1024 – bajtów i używa kryptograficznego skrótu Tiger. Tiger drzewa hash jest wykorzystywany w Gnutella, Gnutella2 i Direct Connect P2P protokołach udostępniania plików i wymiany plików takich aplikacji, jak Phex , BearShare, LimeWire, Shareaza, DC++ i Valknut .

Linki zewnętrzne[edytuj | edytuj kod]