Spis Treści
Drzewo Merkle jest strukturą służącą do skutecznego sprawdzania integralności danych w zestawie. Jest szczególnie interesujące w kontekście sieci
peer-to-peer, w których uczestnicy muszą udostępniać i niezależnie weryfikować informacje.
Funkcje hashujące są rdzeniem struktury drzewa Merkle, dlatego zalecamy sprawdzenie
Co to jest Hashowanie? przed kontynuowaniem.
Załóżmy, że chcesz pobrać duży plik. W
oprogramowaniu typu open source zazwyczaj chcesz sprawdzić, czy hash pobranego pliku jest zgodny z hashem opublikowanym przez programistów. Jeśli tak, wiesz, że plik na komputerze jest dokładnie taki sam jak ich.
Jeśli hashe się nie zgadzają, masz problem. Pobrałeś złośliwy plik podszywający się pod oprogramowanie lub nie został on pobrany poprawnie i dlatego nie działa. W tym drugim przypadku prawdopodobnie nie będziesz zbyt szczęśliwy, jeśli będziesz musiał ponownie poczekać na pobranie pliku. Teraz musisz ponownie uruchomić proces i mieć nadzieję, że nie zostanie on ponownie uszkodzony.
Gdyby tylko istniał łatwiejszy sposób na rozwiązanie tego problemu, pewnie pomyślałeś. Na szczęście właśnie w tym miejscu pojawiają się drzewa Merkle. Pozwalają one podzielić plik na mniejsze części. Jeśli był to plik 50 GB, możesz podzielić go na sto kawałków, tak aby każdy miał rozmiar 0.5 GB. Następnie plik będzie pobierany kawałek po kawałku. Zasadniczo to samo dzieje się, gdy torrentujesz pliki.
W takim przypadku twoje źródło dostarczy Ci hash znany jako korzeń (root) Merkle. Ten pojedynczy hash reprezentuje każdy fragment danych, z których składa się plik. Korzeń Merkle znacznie ułatwia weryfikację danych.
Upraszczając, weźmy przykład, w którym używamy pliku 8 GB podzielonego na osiem części. Nazwij różne fragmenty od A do H. Każdy fragment jest następnie przepuszczany przez funkcję hashującą, co daje nam osiem różnych hashy.
Przepuszczamy każdy z naszych ośmiu fragmentów przez funkcję hashującą, aby uzyskać ich hashe.
Ok, więc mamy coś, co ma trochę więcej sensu. Mamy hash wszystkich fragmentów, więc jeśli jeden jest wadliwy, dowiemy się, porównując go ze źródłem, prawda? Być może, ale jest to również niezwykle nieefektywne. Jeśli Twój plik zawiera tysiące fragmentów, czy naprawdę zamierzasz je wszystkie hashować i dokładnie porównać wyniki?
Nie. Zamiast tego weźmiemy każdą parę skrótów, połączymy je, a następnie zsumujemy. Mamy hashe: hA + hB, hC + hD, hE + hF i hG + hH. Skończyliśmy z czterema hashami. Następnie robimy kolejną rundę hashowania, aby otrzymać dwa. Na koniec hashujemy pozostałe dwa, aby dostać się do naszego głównego hasha - korzenia Merkle (lub hashu roota).
Struktura wygląda jak drzewo do góry nogami. W dolnym rzędzie mamy liście, które są połączone, aby wytworzyć gałęzie (węzły) i wreszcie korzeń.
Mamy teraz korzeń Merkle, który reprezentuje pobrany plik. Możemy porównać jego hash z tym dostarczonym przez źródło. Jeśli pasuje, idealnie! Ale jeśli skróty są różne, możemy być pewni, że dane zostały zmodyfikowane. Innymi słowy, jeden lub więcej fragmentów wytworzyło inny hash. Tak więc każda niewielka modyfikacja danych da nam zupełnie inny korzeń Merkle.
Na szczęście istnieje wygodny sposób sprawdzenia, który fragment jest wadliwy. W naszym przypadku powiedzmy, że to HE. Na początek zapytaj peera o dwa hashe, które wytworzyły korzeń Merkle (hABCD i hEFGH). Wartość hABCD powinna być poprawna, ponieważ w tym poddrzewie nie ma pomyłki. Natomiast hEFGH nie, więc musisz się zagłębić w to poddrzewo. Następnie prosisz o hEF i hGH i porównujesz je ze swoimi. hGH będzie dobrze wyglądać, więc wiesz, że winowajcą jest hEF. Na koniec porównujesz skróty hE i hF. Teraz wiesz, że hE jest niepoprawny, więc możesz ponownie pobrać ten fragment.
Podsumowując, drzewo Merkle powstaje poprzez dzielenie danych na wiele części, które są następnie wielokrotnie hashowane, aby utworzyć korzeń Merkle. Następnie możesz skutecznie sprawdzić, czy coś poszło nie tak z konkretnym fragmentem danych. Jak zobaczymy w następnej sekcji, są też inne ciekawe aplikacje.
Szukasz sposobu na rozpoczęcie swojej przygody z kryptowalutami? Kup Bitcoina na Binance!
Istnieje kilka przypadków użycia drzew Merkle, ale tutaj skupimy się na ich znaczeniu w
blockchainach. Drzewa Merkle są niezbędne w
Bitcoinie i wielu innych kryptowalutach. Są integralną częścią każdego
bloku, a znaleźć je można w
nagłówkach bloków. Aby uzyskać liście dla naszego drzewa, używamy hashu transakcji (
TXID) każdej transakcji zawartej w bloku.
Korzeń Merkle służy w tym przypadku kilku celom. Rzućmy okiem na jego aplikacje do kopania kryptowalut i weryfikacji transakcji.
Górnictwo
Blok Bitcoina składa się z dwóch części. Pierwsza część to nagłówek bloku, segment o stałej wielkości zawierający
metadane bloku. Druga część to lista transakcji, których rozmiar jest zmienny, ale zwykle jest znacznie większy niż nagłówek.
Górnicy muszą wielokrotnie hashować dane, aby uzyskać dane wyjściowe spełniające określone warunki, aby wydobyć prawidłowy blok. Mogą wykonać biliony prób przed ich znalezieniem. Przy każdej próbie zmieniają losową liczbę w nagłówku bloku (
nonce), aby uzyskać inny wynik, ale znaczna część bloku pozostaje taka sama. Możesz mieć tysiące transakcji i nadal będziesz musiał zaszyfrować je za każdym razem.
Korzeń Merkle znacznie usprawnia ten proces. Kiedy zaczynasz kopać, szeregujesz wszystkie transakcje, które chcesz uwzględnić, i budujesz drzewo Merkle. Wstawiasz hash korzenia (32 bajty) do nagłówka bloku. Następnie podczas wydobywania wystarczy szyfrować nagłówek bloku zamiast całego bloku.
Działa to, ponieważ jest odporne na manipulacje. Skutecznie podsumowujesz wszystkie transakcje bloku w kompaktowym formacie. Nie można znaleźć prawidłowego nagłówka bloku, a później zmienić listę transakcji, ponieważ zmieniłoby to korzeń Merkle. Kiedy blok jest wysyłany do innych węzłów, obliczają root z listy transakcji. Jeśli nie pasuje do tego w nagłówku, odrzucają blok.
Weryfikacja
Jest jeszcze jedna interesująca właściwość korzeni Merkle, którą możemy wykorzystać. Dotyczy ona "lekkich klientów" (light clients) (węzłów, które nie przechowują pełnej kopii blockchainu). Jeśli korzystasz z węzła na urządzeniu z ograniczonymi zasobami, nie chcesz pobierać i hashować wszystkich transakcji bloku. Zamiast tego możesz po prostu poprosić o dowód Merkle - dowód dostarczony przez pełny węzeł, który dowodzi, że twoja transakcja jest w określonym bloku. Jest to częściej określane jako uproszczona weryfikacja płatności lub SPV i zostało szczegółowo opisane przez
Satoshi Nakamoto w whitepaperze Bitcoina.
Aby sprawdzić hD, potrzebujemy tylko hashy zaznaczonych na czerwono.
Rozważmy scenariusz, w którym chcemy poznać informacje o transakcji, której TXID to hD. Jeśli znamy hC, możemy znaleźć hCD. Następnie potrzebujemy hAB do obliczenia hABCD. Wreszcie za pomocą hEFGH możemy sprawdzić, czy otrzymany korzeń Merkle odpowiada temu z nagłówka bloku. Jeśli tak, jest to dowód, że transakcja została uwzględniona w bloku - utworzenie takiego samego hashu przy użyciu różnych zestawów danych byłoby prawie niemożliwe.
W powyższym przykładzie musieliśmy hashować tylko trzy razy. Bez dowodu Merkle'a musielibyśmy to zrobić siedem razy. Ponieważ bloki zawierają obecnie tysiące transakcji, użycie dowodów Merkle pozwala nam zaoszczędzić dużo czasu i zasobów obliczeniowych.
Drzewa Merkle okazały się bardzo przydatne w wielu aplikacjach informatycznych - jak widzieliśmy, są niezwykle cenne w blockchainach. W systemach rozproszonych drzewa Merkle pozwalają na łatwą weryfikację informacji bez zalewania sieci niepotrzebnymi danymi.
Bez drzew Merkle (i korzeni Merkle) bloki
Bitcoina i innych
kryptowalut nie byłyby tak kompaktowe, jak są dzisiaj. Podczas gdy lekkim klientom brakuje frontów prywatności i bezpieczeństwa, dowody Merkle pozwalają użytkownikom sprawdzić, czy ich transakcje zostały uwzględnione w bloku przy minimalnym obciążeniu.
