Drzewo skrótów

Drzewo skrótów, drzewo hasz, drzewo Merkle, H-drzewo (ang. hash tree) – rodzaj struktury danych w postaci drzewa zawierającego haszowane skróty informacji na temat danych (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.

Przykład binarnego drzewa skrótów. Skróty S1 oraz S2 są wartościami skrótów bloków danych odpowiednio 1 oraz 2, a skrót S12 – konkatenacji skrótów S1 oraz S2.

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.

Zastosowanie

Drzewa skrótów mogą być używane do weryfikacji integralności 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 wykorzystywała drzewa skrótów w systemie plików ZFS. Drzewa skrótów były również używane w programie Google Wave, rozproszonych systemach kontroli wersji, w rozproszonym systemie plików Tahoe-LAFS oraz w technologii blockchain i kryptowalutach (np. Bitcoin).

Działanie drzewa skrótów

Drzewo 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 skrót S12 jest wynikiem obliczenia skrótu z połączenia skrótu S1 oraz S2. Oznacza to, że skrót S12 = H (skrót S1 || skrót S2). 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ż skrót S1 i skrót S12 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ż skrót S4 i S34. 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 również 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

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

• Tiger Tree Hash (TTH) source code in C#. codeproject.com. [zarchiwizowane z tego adresu (2007-03-17)]. – by Gil Schmidt
• Tiger Tree Hash (TTH) implementations in C and Java
• RHash, an open source command-line tool, which can calculate TTH and magnet links with TTH.
• Systemy zarządzania bazami danych