Drzewo Merkle to koncepcja, używana do sprawdzania prawdziwości i integralności danych. To ono stoi u podstawy wiarygodności kryptowalut i uniemożliwia np. kreowanie BTC z powietrza. Rzućmy okiem, jak działa.
Zacznijmy od haszowania
Drzewo Merkle (Merkle Tree) opiera się na zastosowaniu funkcji haszującej. Haszowanie (tworzenie skrótu, ang. hash) to generowanie niewielkiej porcji danych jako wyniku przetworzenia ich dużej ilości.
Funkcje haszujące są deterministyczne, co oznacza, iż dopóki dane wejściowe się nie zmienią, algorytm zawsze będzie generował ten sam hasz. Wystarczy jednak zmienić jeden bit w danych wejściowych, a wygenerowany hasz będzie zupełnie inny.
Długość wynikowego hasza zależy od użytego algorytmu. Wykorzystywany przez Bitcoina SHA-256 wygeneruje hasz o długości 256 bitów, zaś SHA-1 -160 bitów, niezależnie od wielkości danych wejściowych.
Trzeba pamiętać, że haszowanie nie jest szyfrowaniem. Hasz nie zawiera danych które mogłyby zostać odzyskane, jest on tylko skrótem poświadczającym wiarygodność. Jeśli wygenerujemy hasz np. dla dzieła Wojna i pokój, nie jesteśmy w stanie odzyskać treści książki żadnym algorytmem. 😉 Jesteśmy raczej w sytuacji człowieka, który potrafi udowodnić że ją czytał, wynotowując pierwszą literę każdego zdania.
Droga dane->hasz jest jednokierunkowa, nawet wprowadzenie komputerów kwantowych nie zmieni tej sytuacji, choć mogą one zagrozić tradycyjnej kryptografii, a przez to niektórym kryptowalutom. Algorytmy haszujące w połączeniu z kryptografią stoją bowiem u podstawy prawie wszystkich istniejących blockchainów.
Co to jest drzewo Merkle?
Drzewo Merkle to struktura danych, zaproponowana w latach ’80 przez badacza kryptografii Ralpha Merkle. Opiera się on na zastosowaniu funkcji haszującej, pozwalającej na sprawdzenie poprawności danych, koniecznych dla właściwego działania blockchain. Drzewo Merkle jest reprezentacją wszystkich danych, zawieranych przez konkretny zbiór.
Niektórzy uważają, że Drzewo Merkle reprezentuje główny pień, gałęzie i liście, inni porównują je z rozgałęzionym systemem korzeniowym, gdzie malutkie korzonki poszczególnych transakcji są poniżej większych korzeni i głównego korzenia, przechodzącego w pień. W sumie to bez znaczenia, liczy się tylko hierarchia i powiązanie poszczególnych bloków.
Struktura danych wykorzystuje hasze, zawierające informacje o zbiorach danych, prowadzących kolejno do haszy wyższego szczebla i ostatecznie do głównego bloku korzenia. Każda nowa transakcja musi zostać ujęta w drzewie i wpływa na jego całościowy obraz. Jeśli jej hasz nie będzie powiązany z haszami struktur nadrzędnych, zostanie ona odrzucona.
Struktura drzewa Merkle
Drzewo Merkle rozrasta się na każdym poziomie. Hasze danych w dolnym wierszu są określane jako „węzły liścia”, a hasze pośrednie są określane jako „węzły inne niż liście” lub „gałęzie”. Hasz najwyższego poziomu, uzyskany w wyniku zhaszowania wszystkich poniższych, określany jest jako „korzeń”.
Wewnątrz drzewa wszystkie transakcje pogrupowane są w pary. Każda para ma obliczony hasz (skrót), który jest przechowywany w węźle nadrzędnym. Te węzły są również pogrupowane w pary, po czym ich skrót jest przechowywany na wyższym poziomie. Proces ten trwa aż do osiągnięcia korzenia drzewa Merkle.
Elementy drzewa:
- Węzły liści (Leaf Nodes). Są to skróty każdej transakcji w bloku, zwane również identyfikatorami transakcji (TXID). Nie mają węzłów podrzędnych (dzieci), obsługują jedynie dane źródłowe.
- Węzły inne niż liście (Non-Leaf Nodes, Branches). W przeciwieństwie do węzłów liścia przechowują skrót węzłów podrzędnych (dzieci), nie zawierają zaś identyfikatorów transakcji. Mogą tworzyć wiele kolejnych poziomów.
- Korzeń Merkle (Merkle Root). Hasz, będący pośrednim skrótem wszystkich transakcji na blockchainie i zmieniający się wraz z każdą nową transakcją. Węzły liści (skróty transakcji) u podstawy drzewa Merkle można zweryfikować za pomocą korzenia Merkle. Jego zgodność zapewnia, że bloki danych są niezmienione, nieuszkodzone i całe.
Drzewo Merkle jest binarne, co oznacza, że całkowita liczba węzłów liścia musi być parzysta, aby drzewo było prawidłowo skonstruowane. Gdy istnieje nieparzysta liczba węzłów liścia, poprzedni skrót zostanie zduplikowany, aby zapewnić parzystą liczbę węzłów.
Drzewa Merkle mogą wyglądać odmiennie dla różnych blockchainów, różnią się np. dla Bitcoina i Ethereum, które używa odmiany nazwanej Merkle Patricia Tree.
Jaki z tego pożytek?
Jak wspomniano, każdy liść zawiera hasz określonego bloku danych, a każdy węzeł inny niż liść, zawiera hasze wszystkich swoich dzieci. Oznacza to, że dla każdego węzła innego niż liść można udowodnić, że węzły, które odwołują się do niego, naprawdę należą do rodziny tego węzła.
Dla dowolnego węzła w drzewie możemy samodzielnie obliczyć hasze wszystkich jego dzieci i zobaczyć, czy obejmujący je hasz zbiorczy pasuje do skrótu węzła. Jeśli tak – wszystko jest OK, jeśli nie – gdzieś kryje się kant.
Jeśli wydam na coś Bitcoina, dane o tym dodawane są do łańcucha bloków. Węzeł powyżej tego wpisu zawiera skrót mojego wpisu (i wszystkich innych, które trafiły do tego konkretnego bloku danych). W sieci istnieje zapis, że ja, adres A, przesłałem 1 BTC adresowi B.
Załóżmy teraz, że pojawia się adres C, kombinujący: zmodyfikuję dane, aby wskazywały, że adres A przesłał 1 BTC na adres C, nie B. Ten kant jednak się nie uda. Węzeł powyżej tej transakcji zawiera skrót swoich elementów potomnych, a ze względu na naturę hasza tylko poprawna transakcja jest w stanie wygenerować akceptowany podpis kryptograficzny. Adres C nie może udawać odbiorcy tego Bitcoina, transakcja nie przejdzie.
Zastosowanie drzewa Merkle
Drzewa Merkle służą więc do tworzenia niejako cyfrowych “odcisków palców” wszystkich danych w bloku. Tworząc skrót każdej transakcji w bloku, a następnie tworząc skrót wszystkich skrótów, uzyskujemy pojedynczy hasz – korzeń Merkle. Taki hasz zawarty jest w nagłówku każdego bloku. Jeśli dane w bloku zostaną zmodyfikowane, korzeń Merkle również ulegnie zmianie, a blok zostanie uznany za nieprawidłowy.
Drzewa Merkle są także używane do zmniejszania rozmiaru łańcucha blokowego, umożliwiając węzłom żądanie tylko tych danych, których potrzebują do walidacji. Pozwala to ograniczyć ilość danych, które muszą być przechowywane przez każdy węzeł, co zwiększa wydajność łańcucha bloków.
Ufff, przekonaliśmy się, że blockchain jest bezpieczny i nie tak łatwo jest wygenerować lewe BTC. Biorąc jednak pod uwagę, że Merkle Tree i transakcje na nim to elementarny element łańcucha bloków, zaczynam rozumieć, dlaczego tak dużo płacą programistom blockchain.
Powiązane wpisy:
Czym jest Blockchain? Wszystko co trzeba wiedzieć 
Czym jest sharding w sieci blockchain? 
Węzły blockchain: czym są Full Node, Light Node i Master Node? 
Warstwy blockchain – Layer 0, 1, 2, 3 – co to jest? 
Eksplorator blockchain – jak z niego korzystać? 
Mity krypto: 20 błędnych poglądów na temat kryptowalut i blockchain 
Blockchain jako usługa (BaaS), czy to nowy trend w krypto? 
Bluzelle (BLZ): czym jest i jak działa ta platforma blockchain? 
Avalanche (AVAX): badamy czym jest i jak działa ten blockchain 
Waves (WAVES): Czym jest ta platforma blockchain i co oferuje?
