Spis treści

• Co to jest drzewo Merkle?

• Jak działa drzewo Merkle?

• Dlaczego w Bitcoinie używany jest korzeń Merkel?

  • Górnictwo

  • zweryfikować

• Podsumować

Co to jest drzewo Merkle?

Na początku lat 80. Ralph Merkle, znany informatyk zajmujący się kryptografią klucza publicznego, zaproponował koncepcję drzewa Merkle.

Struktura drzewa Merkle może skutecznie weryfikować integralność zbioru danych i jest bardziej skuteczna w sieciach peer-to-peer, które wymagają od uczestników dzielenia się i niezależnej weryfikacji informacji.

Funkcje skrótu stanowią serce struktury drzewa Merkle. Dlatego zalecamy zrozumienie, czym jest hashowanie przed kontynuowaniem tego artykułu.

Jak działa drzewo Merkle?

Załóżmy, że chcesz pobrać duży plik. W przypadku pobierania oprogramowania typu open source często konieczne jest sprawdzenie, czy skrót pobranego pliku odpowiada hashowi udostępnionemu publicznie przez programistę. Jeśli są zgodne, oba dokumenty są spójne.

Jeśli skróty nie pasują, masz kłopoty. Albo pobrałeś złośliwy plik podszywający się pod oprogramowanie, albo pobrałeś go niepoprawnie, w wyniku czego plik stał się bezużyteczny. Jeśli pobieranie jest nieprawidłowe, na pewno poczujesz się zirytowany, ponieważ długo czekałeś na pobranie pliku. Jeśli teraz zaczniesz od nowa, musisz mieć nadzieję, że ten sam problem się nie powtórzy.

Czy zastanawiałeś się kiedyś, czy istnieje łatwiejszy sposób rozwiązania tego problemu? Tutaj właśnie pojawia się drzewo Merkle. Drzewa Merkle mogą dzielić pliki na wiele bloków danych. Na przykład plik o wielkości 50 GB można podzielić na 100 kopii, z których każda ma rozmiar 0,5 GB. Następnie możesz pobrać je jeden po drugim. Tak działają torrenty.

Źródłem pliku w tym momencie jest wartość skrótu, zwana korzeniem Merkle. Ta pojedyncza wartość skrótu reprezentuje wszystkie bloki danych tworzące plik. Co więcej, korzenie Merkle ułatwiają walidację danych.

Aby ułatwić zrozumienie, podajemy przykład. Poniżej plik o wielkości 8 GB jest podzielony na osiem części, a każdy fragment ma odpowiednio nazwy od A do H. Każdy fragment jest następnie podłączany do funkcji skrótu, co daje osiem różnych wartości skrótu.

Za pomocą funkcji skrótu obliczane są wartości skrótu ośmiu fragmentów.

Mamy nadzieję, że powyższy przykładowy opis jest łatwy do zrozumienia. Mamy wartości skrótu wszystkich fragmentów. Jeśli jeden z nich jest błędny, czy możemy znaleźć problem, porównując go z plikiem źródłowym? Być może, ale nadal jest wyjątkowo nieefektywny. Jeśli plik zawiera dziesiątki tysięcy fragmentów, czy musimy zahaszować wszystkie fragmenty i szczegółowo porównać wyniki?

niepotrzebny. Musimy tylko połączyć parę wartości skrótu i ​​wykonać połączoną operację mieszania. Oznacza to, że mieszamy z hA + hB, hC + hD, hE + hF i hG + hH. Wynikiem będą cztery wartości skrótu. Następnie przechodzimy do następnej rundy łączenia skrótów, aż otrzymamy dwie wartości skrótu. Te dwie wartości skrótu są następnie łączone i ostatecznie uzyskuje się główną wartość skrótu, którą jest pierwiastek Merkle (zwany także główną wartością skrótu).

Konstrukcja przypomina odwrócone drzewo. Dolny rząd liści łączy się ze sobą, tworząc węzły, a na końcu korzenie.

Teraz mamy katalog główny Merkle reprezentujący pobrany plik. Porównaj skrót główny z wartością pliku źródłowego, a jeśli pasuje, wszyscy są szczęśliwi! Gdy wartości skrótu są różne, oznacza to, że dane zostały naruszone. Innymi słowy, jeden lub więcej fragmentów wygenerowało inną wartość skrótu. Dlatego nawet niewielkie modyfikacje danych mogą całkowicie zmienić pierwiastek Merkel.

Na szczęście łatwo jest też sprawdzić, czy nie występują w nich błędne segmenty. Załóżmy, że błąd wynosi hE. Najpierw prosimy innych o dwa skróty (hABCD i hEFGH), aby wygenerować pierwiastek Merkle. Nasza wartość hABCD powinna odpowiadać wartościom innych, co dowodzi, że poddrzewo jest wolne od błędów. Jeśli hEFGH nie pasuje, możemy poprawić błąd w tym miejscu. Następnie poproś innych o ich skróty hEF i hGH i porównaj je z własnymi. Jeśli hGH jest w porządku, przyczyną jest hEF. Na koniec porównujemy wartości skrótu hE i hF. Gdy stwierdzimy, że źródłem błędu jest hE, możemy ponownie pobrać blok danych.

Podsumowując, funkcją drzewa Merkle'a jest podzielenie danych na wiele części, a następnie wielokrotne wykonanie operacji haszujących, aby ostatecznie utworzyć korzeń Merkle'a, dzięki któremu będzie można skutecznie zweryfikować, gdzie występują błędne dane. W następnej sekcji przedstawimy inne ciekawe aplikacje.

Chcesz rozpocząć swoją przygodę z kryptowalutami? Wejdź na Binance i kup Bitcoin już teraz!

Dlaczego w Bitcoinie używany jest korzeń Merkel?

Istnieje wiele przypadków użycia drzew Merkle, ale w tym artykule skupiono się na ich ważnej roli w blockchainie. Bitcoin i wiele kryptowalut są nierozerwalnie związane z drzewami Merkle. Drzewo Merkle jest integralną częścią każdego bloku i zwykle znajduje się w nagłówku bloku. Poprzez wartość skrótu transakcji (TXID) każdej transakcji w bloku możemy uzyskać liście.​

W tym kontekście korzeń Merkel służy kilku celom. Przyjrzyjmy się zastosowaniu Merkle Root w wydobywaniu kryptowalut i weryfikacji transakcji.

Górnictwo

Bloki Bitcoin składają się z dwóch części. Pierwsza część to nagłówek bloku, który ma stały rozmiar i zawiera metadane bloku. Druga część to treść bloku, która ma różny rozmiar, ale zwykle jest znacznie większa niż nagłówek bloku i zawiera listę transakcji.

Górnicy muszą wielokrotnie hashować dane, aż uzyskany zostanie wynik spełniający określone warunki, zanim będą mogli wykopać prawidłowy blok. Aby uzyskać poprawny wynik, muszą próbować tryliony razy. Przy każdej próbie górnik zmienia losową liczbę w nagłówku bloku, wartość Nonce, aby wygenerować różne wyniki. Jednak reszta bloku pozostaje taka sama, a tysiące zawartych w nim transakcji nadal wymaga każdorazowego mieszania.

Merkel znacznie uprościła ten proces. Kiedy rozpoczyna się wydobycie, wszystkie kolejki transakcji są pakowane i konstruowane w drzewie Merkle, a wygenerowana 32-bitowa wartość skrótu głównego jest umieszczana w nagłówku bloku. Wtedy nie ma potrzeby mieszania całego bloku, wystarczy nagłówek bloku.

Metoda ta zapobiega manipulacji danymi i dlatego jest skuteczna, umożliwiając efektywne podsumowanie wszystkich transakcji w bloku w zwartej formie. Nie można modyfikować listy transakcji ważnych nagłówków bloków, w przeciwnym razie zostanie zmieniony korzeń Merkle. Po wysłaniu bloku do innych węzłów, z listy transakcji obliczany jest skrót główny. Jeśli nie odpowiada wartości w nagłówku bloku, blok może zostać odrzucony.

zweryfikować

Możemy także skorzystać z innej ciekawej właściwości korzeni Merkle, która wiąże się z zastosowaniem lekkich klientów (węzłów, które nie przechowują pełnej kopii blockchainu). Jeśli uruchamiasz węzeł na urządzeniu z ograniczonymi zasobami, nie chcesz pobierać i szyfrować wszystkich transakcji w bloku. Zamiast tego po prostu prosisz o dowód Merkle, który jest dowodem dostarczonym przez pełny węzeł, że transakcja została uwzględniona w określonym bloku. Dowód ten jest lepiej znany jako prosta weryfikacja płatności lub SPV i został szczegółowo opisany w białej księdze Bitcoin autorstwa Satoshi Nakamoto.

Aby sprawdzić HD, po prostu zweryfikuj czerwony skrót.

Załóżmy, że chcemy uzyskać informacje o transakcji na temat dysku TXID. Jeśli znane jest hC, można obliczyć hCD. Następnie za pomocą hAB można obliczyć hABCD. Na koniec, odwołując się do hEFGH, możesz sprawdzić, czy obliczony pierwiastek Merkle'a jest zgodny z hashem korzenia w nagłówku bloku. Pomyślne dopasowanie świadczy o tym, że transakcja została uwzględniona w bloku, ponieważ wygenerowanie tego samego skrótu przy użyciu różnych danych jest prawie niemożliwe.

W powyższym przykładzie hashowaliśmy tylko trzy razy. Bez certyfikatu Merkel zajęłoby to siedem. Dzisiejsze bloki zawierają tysiące transakcji, a dowody Merkle oszczędzają nam mnóstwo czasu i mocy obliczeniowej.

Podsumować

Drzewa Merkle okazały się ważne w zastosowaniach informatycznych i, jak widzieliśmy, są również cenne w blockchain. Drzewa Merkle sprawiają, że weryfikacja informacji w systemach rozproszonych jest wygodniejsza i pozwala uniknąć przeciążenia nadmiarowych danych w sieci.

Bez drzew Merkle i korzeni Merkle Bitcoin i inne bloki kryptowalut nie byłyby tak zwarte jak dzisiaj. Chociaż lekkim klientom brakuje korzyści w zakresie prywatności i bezpieczeństwa, dzięki dowodom Merkle użytkownicy mogą sprawdzić, czy transakcje są zawarte w blokach przy minimalnych opłatach.