Drzewo hash

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Przykład binarnego drzewa skrótów. Hasze 0-0 oraz 0-1 są wartościami skrótów bloków danych odpowiednio 1 oraz 2, a hasz 0 jest skrótem konkatenacji haszy 0-0 oraz 0-1.

Drzewo hash, drzewo skrótów, H-drzewo (ang. hash tree) – rodzaj struktury danych, która zawiera drzewo z informacjami zbiorczymi na temat większego fragmentu danych. Drzewa skrótów są uogólnieniem listy skrótów i łańcucha skrótów, które z kolei są przedłużeniem haszowania. Drzewa skrótów, w których podstawową funkcją skrótu jest Tiger, są często nazywane drzewami Tiger.

Zastosowanie[edytuj | edytuj kod]

Drzewa skrótów mogą być używane do weryfikacji wszelkiego rodzaju przechowywanych danych, przechowywane i przenoszone między komputerami. Obecnie głównym zastosowaniem drzew skrótów 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 skrótów w systemie plików ZFS. Drzewa skrótów są również używane w programie Google Wave, rozproszonych systemach kontroli wersji, w rozproszonym systemie plików Tahoe-LAFS oraz kryptowalucie Bitcoin.

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

Działanie drzewa skrótów[edytuj | edytuj kod]

Drzewa skrótów 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 na ilustracji hasz 0 jest wynikiem obliczenia skrótu z połączenia haszu 0-0 oraz 0-1. Oznacza to, że hasz 0 = H(hasz 0-0 | | hasz 0-1). Większość implementacji drzew skrótów jest binarnych (dwa węzły potomne pod każdym węzłem), ale mogą równie dobrze korzystać z wielu węzłów potomnych pod każdym węzłem.

Zwykle kryptograficzna funkcja skrótu taka jak SHA-1, Whirlpool czy Tiger jest stosowana do haszowania. Jeśli drzewo skrótów służy tylko do ochrony przed przypadkowym uszkodzeniem, zamiast niego mogą być użyte mniej bezpieczne sumy kontrolne takie jak CRC.

Na szczycie drzewa skrótów znajduje się korzeń (ang. top hash, root hash, master hash). Przed pobraniem pliku w sieci p2p, w większości przypadków korzeń uzyskuje się z zaufanego źródła lub ze strony internetowej, która jest znana z dobrych rekomendacji plików do pobrania. Kiedy korzeń jest dostępny, drzewo skrótów można pobrać z dowolnego niezaufanego źródła, jak użytkownik w sieci p2p. Potem otrzymane drzewo skrótów jest ponownie sprawdzane i jeśli jest uszkodzone lub fałszywe, inne drzewo z innego źródła będzie wypróbowane, dopóki program nie znajdzie tego, gdzie zgadza się korzeń. Główną różnicą od listy skrótów jest to, że pojedyncza gałąź drzewa skrótów może być pobrana osobno 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ż hasz 0-0 i hasz 1 w wyniku haszowania bloku danych. Ostatecznie można porównać wynik z korzeniem. Podobnie, integralność bloku danych 3 można sprawdzić, jeśli drzewo ma już kasz 1-1 i 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 lub lista skrótów stają się dość duże. Ale jeśli jest to drzewo to jedną małą gałąź można pobrać szybko, integralność gałęzi może być sprawdzona, a następnie pobieranie bloków danych może zostać rozpoczęte.

Drzewo Tiger[edytuj | edytuj kod]

Drzewo skrótów Tiger jest powszechnie stosowaną formą drzewa skrótów. Używa binarnych drzew skrótów (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. Drzewo Tiger jest wykorzystywane w Gnutella, Gnutella2, w protokołach udostępniania plików Direct Connect oraz w aplikacjach do wymiany plików, takich jak Phex, BearShare, LimeWire, Shareaza, DC++ i Valknut.

Linki zewnętrzne[edytuj | edytuj kod]