[go: nahoru, domu]
Przejdź do zawartości

Drzewo skrótów

Z Wikipedii, wolnej encyklopedii
To jest stara wersja tej strony, edytowana przez Ented (dyskusja | edycje) o 00:00, 1 cze 2012. Może się ona znacząco różnić od aktualnej wersji.

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 kawałka danych (na przykład plik służy do sprawdzenia jej zawartości). 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

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 osób w użytkowaniu peer-to-peer są odbierane nieuszkodzone i niezmienione. Można nawet sprawdzić, czy inni nie kłamią i nie wysyłają fałszywych bloków. Sun Microsystems wykorzystuje drzewa Hash w systemie plików ZFS. Hash drzewa są używane w programie Google Wave, rozproszonym systemie kontroli wersji, w Tahoe-LAFS kopii zapasowej, systemie Bitcoin peer-to-peer.

Hash drzewa zostały wynalezione w 1979 przez Ralpha Merkle. Pierwotnym celem było pozwolenie na efektywne obsługiwanie wielu jednorazowych podpisów (Lamport). Uważa się, że podpisy Lamport nadal będą bezpieczne nawet w przypadku, gdy komputery kwantowe staną się rzeczywistością. Niestety każdy klawisz Lamport może być używany tylko do podpisania pojedynczej wiadomości. Ale w połączeniu z drzewami hash mogą one być wykorzystywane do wielu wiadomości, a następnie stać się dość wydajnym schematem podpisu cyfrowego.

Działanie hash drzewa

Hash drzewo to drzewo, w którym liście są blokami danych, na przykład plik lub zestaw plików. Dalsze węzły do drzewa są skrótami do ich potomnych. Na przykład, w hash obrazu 0 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. Zazwyczaj kryptograficzna funkcja skrótu taka jak SHA-1, Whirlpool czy Tiger jest stosowana do mieszania.

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, na przykład znajomego 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 jeden oddział hash drzewa może być pobrany 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 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 jeden mały oddział można pobrać szybko, integralność oddziału może być sprawdzona, a następnie pobieranie bloków danych może zostać rozpoczęte.

Hash drzewo Tiger

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 hash drzewa są wykorzystywane 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

Źródło: „https://pl.wikipedia.org/w/index.php?title=Drzewo_skrótów&oldid=31489517”