Co to jest Drzewo Merkle (Merkle Tree) w blockchainie?

Siemanko. Dobrze kminisz, wiekszość z tego co napisałeś to w zasadzie czysta prawda. Widzę, że odrobiłeś zadanie domowe, bo pytając co to jest Drzewo Merkle (Merkle Tree) w blockchainie, sam już sobie w dużej mierze odpowiedziałeś. Ale spoko, rozwinę temat, bo ta mega specyficzna struktura danych to absolutny fundament tego, dlaczego krypto w ogóle ma rację bytu, jest bezpieczne i się po prostu nie sypie.

Zacznijmy od podstaw, czyli jak to fizycznie powstaje i jak wygląda z perspektywy kodu. Wyobraź sobie Drzewo Merkle jako taką drabinkę pucharową na mistrzostwach w gałę, tylko odwróconą do góry nogami. Na samym dole tej drabinki (czyli w liściach drzewa) masz surowe dane – w naszym przypadku to są po prostu pojedyncze transakcje w sieci, np. że portfel X przelał na portfel Y dwa bitcoiny. Zamiast rozgrywać mecz, te transakcje są przepuszczane przez algorytm kryptograficzny. W przypadku Bitcoina używa się podwójnego haszowania SHA-256. Funkcja skrótu mieli taką transakcję, bez względu na jej rozmiar, i wypluwa zawsze stałej długości ciąg znaków, czyli tak zwany hash.

I tu wjeżdża cała magia algorytmów haszujących. Te wygenerowane na samym dole hasze łączą się ze sobą w pary. Hash z transakcji A i hash z transakcji B są sklejane w jeden ciąg, a potem znów przepuszczane przez funkcję skrótu. Z tych dwóch powstaje jeden, zupełnie nowy hash poziomu wyżej. Ten nowy skrót znowu szuka sobie sąsiada z pary obok, sklejają się i tworzą kolejny hash wyższego poziomu. I tak to idzie w górę i w górę, drabinka się zwęża, aż na samym szczycie tej kryptograficznej piramidy zostaje nam tylko jeden, samotny, ostateczny ciąg znaków. Ten boss na samej górze to właśnie Merkle Root.

Możesz tu zapytać – a co jeśli liczba transakcji w danym bloku łańcucha bloków jest nieparzysta i na dole brakuje komuś pary? Wtedy algorytm po prostu bierze tę ostatnią, samotną transakcję, duplikuje jej hash i łączy go z samym sobą. Mega prosty trick, a domyka całą strukturę drzewa skrótów. Ten końcowy korzeń drzewa Merkle jest potem na sztywno wklejany do nagłówka bloku i koparki zaczynają go mielić, żeby znaleźć Proof of Work.

Pytasz, po co to wszystko tak komplikować i dlaczego nie wrzucić po prostu transakcji luzem? Odpowiedź to brutalna optymalizacja i wydajność sieci. Pomyśl, że główny łańcuch waży grubo ponad pół terabajta. Chciałbyś to pobierać na swojego smartfona tylko po to, żeby sprawdzić, czy kumpel oddał ci hajs za wczorajszą pizzę? No napewno nie. Nikt by z tego nie korzystał. I tu na biało wjeżdżają lekkie portfele krypto oparte na SPV (Simple Payment Verification), o których tak słusznie wspomniałeś.

Taki lekki węzeł na telefonie w ogóle nie pobiera ciał bloków z transakcjami. On pobiera tylko same nagłówki. Każdy nagłówek waży śmieszne 80 bajtów i zawiera w sobie ten nasz ostateczny Merkle Root. Kiedy twoja apka chce zrobić weryfikację transakcji, wykonuje proces zwany dowodem Merklego (Merkle Proof). Łączy się z jakimś grubym full nodem i mówi: "Siema, daj mi tylko te kilka haszy z drabinki pucharowej, które są potrzebne, żeby wyliczyć drogę od mojej konkretnej transakcji prosto do korzenia na górze". Apka na telefonie dostaje te kilka ciągów znaków (to są ułamki kilobajtów!), sama skleja je w pary, podwójnie haszuje i idzie w górę. Jeśli ostateczny wynik wyszedł jej identyczny z tym, co jest wbite w nagłówek bloku, to portfel ma 100% kryptograficznej pewności, że ta transakcja tam siedzi i została zatwierdzona. Nie musisz ufać nodowi na słowo, sam to udowodniłeś matematyką bez pobierania całego, gigantycznego bloku ważącego megabajty. To jest po prostu genialne.

A co z bezpieczeństwem sieci i oszukiwaniem? Zadałeś mega trafne pytanie o modyfikacje na samym dole. Otóż cała architektura oparta o Drzewo Merkle całkowicie uniemożliwia wciśnięcie jakiejś fałszywki. Działa tu kryptograficzny efekt lawinowy. Załóżmy, że ktoś kombinuje i chce zmienić chociażby jeden, malutki bit w kwocie przelewu gdzieś tam w historii. Co się dzieje? Funkcja skrótu jest tak zrobiona, że zmiana nawet przecinka w pliku wejściowym generuje całkowicie, diametralnie inny hash. Więc hash tej zepsutej transakcji się zmienia. Skoro zmienił się on, to w połączeniu z sąsiadem wygeneruje zły hash wyższego rzędu. Ta modyfikacja kaskadowo leci w górę drabinki i w ułamku sekundy całkowicie zmienia ostateczny Merkle Root.

Kiedy taki zmieniony nagłówek trafi do reszty sieci, uczciwe węzły sprawdzają go i widzą ewidentny wał. Wynik z drzewa haszy po prostu im się nie zgadza z resztą łańcucha, więc cały zmanipulowany blok dostaje natychmiastowego bana i zostaje odrzucony przez algorytm konsensusu. Żeby wziąść i skutecznie podmienić jedną transakcję w starym bloku, haker musiałby przeliczyć od zera całe to kryptograficzne drzewo, potem przegenerować hash całego bloku, a potem przeliczyć wszystkie bloki, które nastąpiły po nim. Fizycznie niemożliwe przy dzisiejszej mocy obliczeniowej.

Chciałeś jeszcze życiowego przykładu. Kojarzysz pobieranie torrentów? Kiedy ściągasz jakiś ciężki plik, nie leci on do ciebie jako jedna wielka bryła. Plik jest szatkowany na tysiące małych paczuszek. Każda paczka ma swój własny identyfikator, a wszystkie one połączone są w strukturę bazującą... tak, zgadłeś, na drzewie skrótów. Kiedy pobierasz te dane od losowych ludzi w sieci (peer-to-peer), klient torrenta cały czas na bieżąco sprawdza ich hasze z korzeniem zdefiniowanym w małym pliczku .torrent. Jak jakiś wredny seeder podsunie ci uszkodzony kawałek z wirusem, program widzi, że hash tego małego fragmentu nie pasuje do układanki. Wtedy po prostu wyrzuca tylko ten jeden zepsuty kawałeczek i pobiera go od kogoś innego. Nie musisz wywalać całego 10-gigowego filmu. Satoshi Nakamoto zaadaptował ten sam mechanizm sprawdzania integralności danych dla struktury danych w swoim whitepaperze i tak powstał nowoczesny łańcuch bloków.

Mam nadzieję, że teraz temat jest dla ciebie dużo bardziej zrozumiały. To w gruncie rzeczy brutalnie prosta matematyka oparta na sprytnym parowaniu danych i redukcji kosztów sprzętowych. Jak wciąż łakniesz wiedzy, obczaj sobie na YouTube filmiki gościa, który zwie się Andreas Antonopoulos. Tłumaczy te najcięższe krypto zagadnienia, rysując wszystko na zwykłej białej tablicy z flamastrem w ręku – czysta poezja i zero nudnego bełkotu. Trzymaj się w tej króliczej norze i jak coś to pytaj dalej!

Siema! Kolega wyżej rozwalił system tym przykładem z torrentami, więc ja już nie będę wałkował samego core'u BTC i tego jak koparki to mielą. Ale dorzucę wam nieco inną perspektywę. Bo jak tak serio zastanawiasz się, co to jest Drzewo Merkle (Merkle Tree) w blockchainie, to warto wiedzieć, że to nie jest tylko jakiś archaiczny wymysł Satoshiego do lekkich portfeli na komórki. Ten patent przydaje się mega mocno tu i teraz, w obecnych realiach web3, zwłaszcza jak bawisz się w DeFi, airdropy czy mintowanie NFT na Ethereum.

Wyobraź sobie taką czysto praktyczną sytuację. Devowie od jakiegoś nowego, hajpowanego tokena chcą zrobić wielki airdrop dla 50 tysięcy ludzi. Albo organizują gigantyczną whitelistę na dropa jakiejś kolekcji. Gdyby chcieli wgrać te wszystkie 50k adresów bezposrednio w smart kontrakt na mainnecie, to by po prostu zbankrutowali na opłatach za gas. Zapisywanie dużej ilości danych bezpośrednio w łańcuchu kosztuje po prostu chore pieniądze. No i tutaj to nasze kryptograficzne drzewo wjeżdża całe na biało.

Programiści budują sobie całe to zestawienie u siebie na serwerze, czyli off-chain. Każdy liść na samym dole tej drabinki to adres portfela połączony z konkretną kwotą tokenów do odebrania. Haszują to w pary, pną się w górę tak jak poprzednik ci fajnie wytłumaczył, aż uzyskają ten jeden ostateczny Merkle Root. I wiesz co? Oni wrzucają w kod kontraktu TYLKO ten jeden malutki ciąg znaków.

Teraz ty wchodzisz na ich stronkę, żeby zgarnąć swoje darmowe krypto. Klikasz przycisk "Claim". W tle stronka odpytuje bazę danych devów i generuje dla twojego portfela tzw. dowód Merklego (Merkle proof). To jest taka krótka mapa drogowa z kilkoma haszami, która mówi kontraktowi: "hej, pacz, ten konkretny adres legitnie należy do naszej struktury danych". Twój portfel wysyła ten dowód do sieci. Smart kontrakt wogóle nie ma pojęcia, kto jest na pełnej liście z serwera. On tylko bierze twój adres, przepuszcza go przez te kilka haszy z dowodu, przelicza wszystko w ułamek sekundy i patrzy: "aha, wynik końcowy zgadza się w 100% z rootem, który mam zapisany na sztywno. Gość nie ściemnia, wypłacamy mu hajs". Genialne, nie? Zaoszczędzili miliony dolarów na opłatach sieciowych, a bezpieczeństwo pozostaje absolutnie kryptograficzne i odporne na wałki.

Poza tym, jak lubisz grzebać w bebechach technologii, to obczaj sobie, że taka sieć Ethereum używa trochę bardziej zmutowanej i zaawansowanej wersji tej struktury. Nazywa się to Merkle Patricia Trie. Główna różnica polega na tym, że w ETH masz aż trzy takie osobne drzewa skrótów w każdym pojedynczym bloku. Jedno jest od transakcji, drugie od paragonów (czyli tzw. transaction receipts), a trzecie i chyba najpotężniejsze to drzewo stanu (state trie). To ono trzyma aktualne info o tym, kto ile ma kasy na koncie i jaki jest stan wszystkich smart kontraktów. Dzięki takiemu podziałowi szybka weryfikacja transakcji w ekosystemie z setkami tysięcy różnych tokenów jest technicznie możliwa do ogarnięcia bez palenia serwerów.

Jak chciałbyś sprawdzić jak to fizycznie wygląda w kodzie, to polecam zajrzeć na GitHuba do repozytorium OpenZeppelin. Mają tam gotowe, audytowane biblioteki do weryfikacji takich drzew dla języka Solidity. Nawet jak nie jesteś jakimś mega zaawansowanym programistą, to przejrzenie tego jak parują te hasze w pętlach mocno otwiera oczy i skleja suchą teorię z praktyką.

A co do tego typa z tablicą - potwierdzam zdanie poprzednika, Andreas Antonopoulos to absolutny goat jeśli chodzi o tłumaczenie najtrudniejszych koncepcji krypto. Jego stare wykłady naprawde robią niesamowitą robotę. Dawaj znać, czy ten motyw z airdropami i kontraktami trochę ci pomógł złapać, o co w tym biega!