Czym jest drzewo Merkle i jaka jest jego rola w Blockchain?

Drzewa Merkle są wykorzystywane w aplikacjach komputerowych jako struktura danych do weryfikacji i synchronizacji danych. Drzewa Merkle są również wykorzystywane do bezpieczniejszego i bardziej wydajnego szyfrowania danych blockchain w Bitcoin achi innych kryptowalutach. 

W przypadku kryptowalut baza danych Merkle jest wykorzystywana do bezpiecznego podziału danych bloku i zapewnienia, że nie zostaną one utracone, uszkodzone ani zmienione. Ta metoda zarządzania danymi umożliwia zatwierdzanie określonych transakcji bez pobierania całego łańcucha blokowego wielkości terabajta. Jest to niezawodna, bezpieczna i kryptograficzna metoda działania blockchain.

W wyniku upadku giganta Centralized Exchange (CEX), FTX, wiele CEX zbudowało i wdrożyło Merkle Tree jako formę dowodu rezerw (PoR), aby zapewnić użytkownikom bezpieczeństwo swoich środków. W tym artykule omówimy, czym są drzewa Merkle, ich rolę w blockchain i jak użytkownik może zweryfikować swoje fundusze za pomocą drzewa Merkle.

Kto jest założycielem Merkle Tree?

Ralph Merkle, informatyk znany ze swojej pracy nad kryptografii kluczy publicznych, zaproponował drzewa Merkle w artykule „Digital Signature Based a Conventional Encryption Function” z 1987 roku. Wynaleziono również haszowanie kryptograficzne przez Merkle.

Czym jest drzewo Merkle?

Drzewo Merkle to oparta na skrótach struktura danych matematycznych, która kompiluje podsumowania wszystkich transakcji w bloku. Jest to metoda szybkiego sprawdzania dokładności danych w sposób decentralizacyjny. Dzięki swoim funkcjonalnościom drzewa Merkle są skuteczniej i bezpieczniej wykorzystywane do szyfrowania danych blockchain. 

Drzewa Merkle są często używane w sieciach peer-to-peer (P2P) ze względu na konieczność udostępniania i niezależnej weryfikacji informacji. Dowiedzmy się więcej o drzewach Merkle i ich działaniu.

Struktura drzewa Merkle

Drzewo Merkle, znane również jako hasz drzewo, ma strukturę drzewa binarnego, a haszhe danych transakcyjnych w dolnym wierszu są określane jako „węzły liścia”, pośrednie hasztasy są określane jako „węzły nieliści”, a hash na górze są określane jako „korzenie”. Mimo że większość implementacji hash tree jest binarna (każdy węzeł ma dwa węzły podrzędne), mogą one również mieć znacznie więcej węzłów podrzędnych.

Patrząc na strukturę drzewa Merkle, wszystkie transakcje są grupowane w pary. Każda para ma obliczone haszowanie, które jest przechowywane bezpośrednio w węźle nadrzędnym. Węzły te są również pogrupowane w pary, po czym ich hasz jest przechowywany na następnym poziomie w górę. Proces ten trwa do osiągnięcia korzenia drzewa Merkle.

Przyjrzyjmy się każdemu z węzłów:

Węzły liści

Są to skróty każdej transakcji kryptowalutowej w bloku, określane również jako identyfikatory transakcji (TXID). Wyświetlasz hasz transakcji, gdy szukasz transakcji w eksploratorze bloków.

Węzły bez liści

Następnie, aby utworzyć warstwę węzłów innych niż węzły liściowe powyżej węzłów liści, te węzły liści są hartowane razem w parach. Są one znane jako węzły nieliściowe, ponieważ w przeciwieństwie do węzłów liści przechowują jedynie hasz dwóch reprezentowanych przez nie węzłów liści i nie zawierają identyfikatorów transakcji (lub haszów). W rezultacie w warstwie węzła nieliśćowego nad węzłami liści będzie o połowę więcej haszów (lub węzłów) niż w warstwie węzła liściowego. Gdy drzewo zwęża się wraz ze wzrostem, te warstwy węzłów bez węzła liściowego nadal są hartowane razem w parach, co skutkuje o połowę większą liczbą węzłów na warstwę. Dwa węzły będą obecne w końcowej warstwie węzła bez węzła. Tworzy to korzenie Merkle i jest lokalizacją ostatniego haszowania w drzewie Merkle.

Korzenie kostek

W Bitcoin hasz wszystkich transakcji są łączone w pojedynczy hasz i przechowywane w nagłówku bloku. Ten konkretny hasz jest korzeniem Merkle, znanym również jako hash root. Węzły liści (identyfikatory transakcji/piaski) u podstawy drzewa Merkle można zweryfikować za pomocą tego korzenia Merkle. W przypadku kryptowalut korzeń Merkle zapewnia, że bloki danych są niezmienione, nieuszkodzone i pełne.

Drzewo Merkle jest binarne, co oznacza, że całkowita liczba różnych węzłów liści musi być równa, aby drzewo było prawidłowo skonstruowane. Gdy istnieje nieparzysta liczba węzłów liści, poprzednie hash zostanie zduplikowane w celu zapewnienia parzystej liczby węzłów.

Jak działa drzewo Merkle?

Drzewo Merkle jest zasadniczo zaprojektowane tak, aby podzielić duże fragmenty danych na znacznie mniejsze fragmenty, co zapewnia szybką weryfikację wszystkich transakcji. Drzewo podsumowuje każdą transakcję, tworząc niewielki odcisk palca określonego zestawu transakcji, co ułatwia użytkownikom weryfikację dostępności transakcji w bloku. 

Drzewa Merkle są tworzone przez haszowanie różnych par węzłów do momentu, aż pozostanie tylko jedno hasz, co jest określane jako korzenie Merkle . Drzewa te budowane są od dołu do góry, przy czym każda transakcja składa się z haszów. Każdy węzeł liścia jest pojedynczym haszem danych. Jeśli chodzi o węzły nieliściowe, są to hasztaki poprzednich haszów.

Załóżmy, że drzewo Merkle składa się z czterech transakcji oznaczonych jako D0, D1, D2 i D3. Każda transakcja jest haszowana, zanim hash zostanie zapisany bezpośrednio na węźle liścia. W takim przypadku tworzone są skróty N0, N1, N2 i N3. Każda kolejna para węzłów liści zostanie następnie podsumowana w węźle nadrzędnym poprzez haszowanie hash N0 i hash N1, co skutkuje hash N4. Jeśli hash N2 i hash N3 są zmieszane razem, powstaje hash N5. Oba te hasztery, N4 i N5, są ponownie haszowane w celu utworzenia korzenia Merkle.

Proces ten może być stosowany z rozbudowanymi zbiorami danych. root Merkle jest odpowiedzialny za podsumowanie danych obecnych w określonych transakcjach, z których wszystkie są przechowywane bezpośrednio w nagłówku bloku. Technika ta skutkuje prawidłowym utrzymaniem integralności danych. W przypadku zmiany jednego szczegółu w transakcji, korzenie Merkle automatycznie się zmieni.

Korzyści z drzewa Merkle

Technologia blockchain i platformy kryptowalutowe zapewniają wiele korzyści podczas korzystania z drzewa Merkle do weryfikacji transakcji, które obejmują wszystko, od skutecznej weryfikacji po łatwe wykrywanie manipulacji.

Wydajny proces weryfikacji danych

Niezawodność transakcji można łatwo zweryfikować praktycznie w mgnieniu oka. Ze względu na strukturę danych, podczas procesu weryfikacji należy korzystać z bardzo małej ilości pamięci, a wymagana moc obliczeniowa jest znacznie zmniejszona. 

Łańcuchy blokowe zazwyczaj składają się z setek tysięcy bloków, z których każdy może zawierać do kilku tysięcy transakcji, a weryfikacja danych stanowi dwa główne wyzwania: pamięć i moc obliczeniowa. Każdy węzeł w sieci musiałby posiadać kompletną kopię każdej transakcji, która kiedykolwiek miała miejsce w blockchain, gdyby drzewa Merkle nie były koncepcją w blockchain. Węzeł musiałby porównać każdy wiersz wejścia po wierszu podczas weryfikacji transakcji, aby upewnić się, że jego rekordy dokładnie odpowiadają rekordom sieci. Zabezpieczenia sieci mogą być zagrożone w przypadku rozbieżności między rekordami. W rezultacie, aby porównać rekordy i upewnić się, że nie nastąpiły żadne zmiany, komputer użyty do weryfikacji danych wymagałby znacznie większej mocy obliczeniowej. 

Z drugiej strony drzewa Merkle oferują rozwiązanie tego problemu, drastycznie zmniejszając ilość danych, które muszą być pod ręką w celu weryfikacji. Zapisują każdy wpis w księdze, skutecznie oddzielając dane od dowodów, które je potwierdzają. Nie znając każdego TXID w bloku, możesz sprawdzić TXID za pomocą korzenia Merkle z drzewem Merkle. Drzewo Merkle to świetny sposób na zademonstrowanie, że coś jest obecne w zestawie danych bez konieczności pobierania całego zestawu. W związku z tym do walidacji transakcji potrzebna jest mniejsza moc obliczeniowa.

Szybsze przetwarzanie

W wyniku dystrybucji transakcji w bloku między weryfikatorami, każdy weryfikator pracuje nad inną transakcją w tym samym czasie. W porównaniu z metodą, w której każda transakcja jest sekwencyjnie sprawdzana po drugiej, jest to znacznie bardziej skuteczne.

Korzystanie z portfela kryptowalutowego

Prosta weryfikacja płatności (SPV), która umożliwia potwierdzenie transakcji bez pobierania całego bloku lub łańcucha blokowego, jest możliwa dzięki drzewu Merkle. Umożliwia to wysyłanie i odbieranie transakcji za pomocą węzła lekkiego klienta, znanego bardziej formalnie jako portfel kryptowalutowy.

Wykrywanie wszelkich manipulacji

Struktura haszowania ułatwia górnikom określenie, czy w transakcjach doszło do manipulacji. 

Dla każdego bloku przy użyciu korzenia Merkle generowana jest odrębna wartość hash. Blok łączy jeden blok z drugim w łańcuchu blokowym, dodając hasz poprzedzającego bloku. Haszowanie każdej transakcji zmienia się za każdym razem, gdy transakcja jest modyfikowana. Blok staje się nieważny w wyniku tej zmiany, ponieważ kaskaduje się do korzenia Merkle i zmienia jego wartość. Powoduje to zmianę w hash następującego bloku, co powoduje, że pozostała część Blockchain jest nieprawidłowa. W rezultacie drzewo Merkle tworzy niemożliwy do zatrzymania rejestr transakcji bloku.

W rezultacie można również zapobiec wydatkom podwójnym. Jeśli dana osoba spróbuje dwukrotnie wydać swoją walutę cyfrową, dla tej transakcji zostanie wygenerowany hasz. Jeśli to hasz pasuje do istniejących rekordów obecnych w Blockchain, transakcja zostanie odrzucona.

Dlaczego drzewa Merkle są ważne w Blockchain?

Drzewa Merkle okazały się niezbędne dla technologii blockchain, ponieważ ułatwiają szybką i łatwą weryfikację w sposób, który nie jest możliwy przy użyciu innych technik. Drzewa Merkle zapewniają programistom możliwość kompresji bardzo dużych zestawów danych poprzez pozbycie się wszystkich niepotrzebnych danych i przekształcanie danych, które pozostają w hasztery. Różne funkcje drzew Merkle obejmują:

• Bardzo lekka konstrukcja
• Efektywna skalowalność
• Oszczędność paliwa
• Weryfikacja, czy transakcje są zawarte w określonym bloku
• Podstawowe uwierzytelnianie płatności

Dowód rezerwacji (PoR) drzewa Merkle

Jak wspomniano na początku, po spadku FTX, użytkownicy obawiali się, czy ich fundusze są faktycznie bezpieczne w CEX. W rezultacie pojawiło się wiele CEX, aby opracować mechanizm weryfikacji rezerwacji Merkle Tree. W tej sekcji przyjrzymy się sprawdzeniom Merkle i temu, w jaki sposób nasi użytkownicy mogą weryfikować swoje środki.

Dowody na kostkę

Dowód na drzewo Merkle to cięcie z drzewa Merkle, a nie z prawdziwego drzewa. I być reprezentowane jako tablica lub sekwencja (pokazana przez pomarańczową część na poniższym schemacie).

Wszystkie węzły liści i informacje o saldzie dla konkretnego pojedynczego użytkownika naszej firmy są reprezentowane przez węzły ostatniego poziomu figury. Zakładając, że różowi ludzie na rysunku reprezentują zamierzonych odbiorców dowodów, wyodrębniamy pomarańczowe części poziomu figury według poziomu i przedstawiamy dokumenty dowodów użytkownikom w kolejności wzrostu. Należy pamiętać, że produkt Merkle proof składa się z dwóch głównych elementów

1. Bezpośrednie węzły nadrzędne (tj. B i D) tego użytkownika nie są wyodrębniane.
2. Podaj węzeł główny, tj. root Merkle.

Na przykładzie objętości 10 milionów użytkowników wysokość drzewa można obliczyć jako Log2(10 000 000) = 23,2534966642 na podstawie wzoru matematycznego, który daje wysokość drzewa jako 24 poziomy. Dlatego węzły na wykresie, które celowo nie są dostarczane użytkownikom, będą miały wartość 24 - 2 = 22.

Drzewo Merkle to kompletne drzewo binarne, które pozwala nam obliczyć wszystkie informacje o węźle macierzystym, po prostu znając lewy i prawy węzeł. Te pełne informacje składają się na dwie części: dane bilansu i dane hash.

1. Dane salda: Dane węzła nadrzędnego można i można je dzielić tylko na węzły dolne lewe i prawe.
2. Dane skrótu: Dla każdego węzła będą obecne tylko dane salda, dane hierarchii drzewa i dane hash węzła podrzędnego (każdy węzeł przechowuje dane podsumowania lewego i prawego węzła poniżej).

Walidacja drzewa Merkle jest obliczana poprzez wyprowadzenie B i D i sprawdzenie, czy

1. saldo jest zgodne z zasadą podziału; oraz
2. hasz jest legalny.

Korzystając z funkcji skrótu, drzewo Merkle umożliwia użytkownikom określenie, czy są częścią całego drzewa bez konieczności znajdowania każdego fioletowego węzła na wykresie. Produkt Merkle proof jest dostępny wyłącznie dla tego użytkownika. Na przykład 24-poziomowe drzewo Merkle wymaga matrycy 23 elementów do weryfikacji informacji o saldzie użytkownika, a ta matryca może tylko potwierdzić, że bilans użytkownika jest dokładny.

Użytkownik nie może zrekonstruować całego drzewa na podstawie fragmentarycznych informacji, o ile nie uzyska więcej niż połowy całkowitej liczby użytkowników. W rezultacie drzewo Merkle chroni zarówno prywatność użytkowników, jak i zdolność firmy do zapobiegania wyciekom informacji o ogólnych aktywach firmy.

Walidacja konta Bybit

Dostępne są 2 metody weryfikacji konta Bybit i sprawdzania ważności środków.

Narzędzie do walidacji platformy

Ta metoda jest pierwszą i jedyną metodą w całej sieci, która będzie pokazywać proces wyprowadzania Merkle Tree w intuicyjny graficzny sposób na platformie firmy.

Narzędzie do samodzielnej walidacji

Firmowy kod źródłowy generowania drzew Merkle i kod weryfikacyjny są otwarcie dostępne w github, aby pomóc użytkownikom w programowaniu ich własnej walidacji. Proces obliczania drzewa Merkle obejmuje ogromną liczbę obliczeń użytkownika, które są zwykle wdrażane przez big data i Java. 

*Otwarty kod Java oznacza, że jest otwarty dla użytkowników bez zatrzymywania żadnych informacji.

Bybit otworzył poniższy kod dla profesjonalnych użytkowników, aby zweryfikować własny plik próbny Merkle Tree, kopiując go ze strony potwierdzenia rezerw na własną „lepką” wersję systemu za pomocą przycisku Kopiuj dane i przechowując go jako plik o nazwie myProof.json na dysku lokalnym.

Zastosowania drzew Merkle w Blockchain

Struktury korzeniowe Merkle i Merkle zostały już szeroko przyjęte w wielu różnych łańcuchach blokowych i platformach kryptowalutowych. Poniżej wyszczególniono trzy takie aplikacje.

Bitcoin

Bitcoin wykorzystuje drzewa Merkle na kilka sposobów, co czyni je integralną częścią całej platformy Bitcoin. Drzewa te są obecne w każdym nagłówku bloku bitcoinów. Hasz dla każdej transakcji dostępnej w bloku jest umieszczany w nagłówku. Jeśli chodzi o Bitcoina, korzeń Merkle jest ważny zarówno dla górnictwa, jak i weryfikacji.

Górnictwo

Bloki bitcoin składają się z nagłówków zawierających metadane, a także z obszernej listy transakcji. Lista ta jest zazwyczaj większa niż nagłówek bloku. Górnicy mieszają dane, aby utworzyć wyjście, które jest zgodne z określonymi warunkami, co jest konieczne podczas walidacji bloku. Górnicy mogą wykonać bilion oddzielnych prób, zanim znajdą prawidłowy blok. Każda próba wymaga zmiany numeru w nagłówku bloku. Mimo że w bloku mogą istnieć tysiące oddzielnych transakcji, każda z nich musi zostać zaszyfrowana.

Korzenie Merkle pozwalają górnikom znacznie zwiększyć wydajność tego procesu. Po rozpoczęciu procesu wydobycia wystarczy, że transakcje zostaną przekształcone w drzewo Merkle, po czym w nagłówku bloku można umieścić hasz korzenia. W tym momencie wydobywca jest zobowiązany tylko do haszowania nagłówka bloku, a nie całego bloku.

Weryfikacja

Innym aspektem korzenia Merkle, który jest używany z Bitcoinem, jest dźwignia, która koncentruje się na lekkich klientach. Gdy węzeł jest obsługiwany na stosunkowo słabym urządzeniu, które ma ograniczone zasoby, użytkownicy nie będą mogli pobrać i wyszyfrować każdej transakcji w jednym bloku. Zamiast tego można poprosić o dowód Merkle, który jest potwierdzeniem, że transakcja jest obecna w bloku. Zmniejszając liczbę haszów, które należy wykonać podczas procesu weryfikacji, weryfikacja może nastąpić bez użycia jak największej liczby zasobów komputerowych.

Ethereum

Ethereum opiera się na nieco zmodyfikowanej wersji drzewa Merkle, dlatego nazywa się ono drzewem Merkle Patricia . Każdy blok w blockchain Ethereum składa się z trzech drzew Merkle, w przeciwieństwie do jednego drzewa binarnego – co dzieje się w blokach bitcoinów. Każdy z trzech korzeni ma swój własny cel.

Pierwotny korzeń jest uważany za podstawę każdej transakcji. Jeśli chodzi o drugie źródło, pokazuje ono stan transakcji. Ostatecznym korzeniem jest otrzymanie transakcji. Użytkownik może przyjrzeć się korzeniu Merkle, aby określić, czy transakcja znajduje się w określonym bloku, a także określić, jakie jest saldo jego konta.

Tkanina Hyperledger

Patrząc konkretnie na Hyperledger Fabric, ta platforma blockchain wykorzystuje drzewo Merkle do obliczenia danych blokowych jako hasz. Wartość hash określa szerokość drzewa Merkle. Drzewa Merkle na platformie Hyperledger Fabric działają tak samo jak te na platformie Bitcoin.

Konkluzja

Drzewa Merkle okazały się bardzo przydatne dla platform kryptowalutowych, które chcą mieć pewność, że ich proces weryfikacji transakcji jest tak łatwy i wydajny, jak to tylko możliwe. Bez tej struktury weryfikacja byłaby czasochłonnym procesem, ponieważ dane musiałyby zostać przesłane do całej sieci w celu weryfikacji. Platformy wykorzystujące drzewa Merkle czerpią korzyści z mniejszej przepustowości i wymagań w zakresie mocy obliczeniowej.