Co to są drzewa Merkle?
Merkle Tree (również Hash Tree) to struktura przechowująca hashe danych w formie drzewa, która pozwala na szybką weryfikację ich integralności. Jest to struktura często wykorzystywana w komunikacji peer-to-peer, gdzie dwie niezaufane strony wymieniają się danymi, które następnie są sprawdzane pod kątem ich poprawności. Mało tego, za pomocą drzewa Merkle, możemy jeszcze przed odebraniem danych sprawdzić czy dane przesyłane przez drugą stronę będą poprawne!
Praktyczne zastosowanie drzew Merkle znajdziemy między innymi w sieci Bitcoin, Ethereum, protokole BitTorrent, czy systemie kontroli wersji GIT.
Podstawowym elementem tworzącym drzewa Merkle są kryptograficzne funkcje skrótu. Jeśli o nich nie słyszałeś, przeczytaj najpierw nasz artykuł o hashowaniu.
Struktura
Tak naprawdę jest to odwrócone drzewo. Strukturę danych tworzymy od pojedynczych liści hashujących dane, do korzenia na samej górze. Na powyższym schemacie najniższa warstwa “Bloki danych” nie wchodzi w skład struktury drzewa. W tradycyjnym przesyłaniu plików, duży plik zazwyczaj dzielony jest na mniejsze bloki danych, które pobierane są równolegle przez klienta. Pozwala to na skrócenie czasu pobierania danych oraz na szybszą reakcję w przypadku błędów przesyłu lub celowym działaniu.
Przykład tworzenia drzewa
Na podstawie bloków danych (L1, L2, L3, L4) tworzone są pierwsze liście w drzewie poprzez obliczanie funkcji skrótu (np. H(L1)) dla każdego bloku z osobna. Niezależnie od wielkości bloku danych, wygenerowany hash jest stałej długości (np. SHA256 wygeneruje 256 bitowy hash). Hash pełni rolę podpisu danych. Jakakolwiek modyfikacja danych skutkować będzie wygenerowaniem zupełnie innego hasha w liściu.
Merkle Tree to zazwyczaj drzewa binarne, gdzie każdy węzeł ma dwójkę dzieci. Kolejne wierzchołki drzewa, aż do korzenia na samej górze, generowane są poprzez wyliczenia hasha ze swoich dzieci. Na przykładzie schematu widzimy, że węzeł S12 wyliczył hash na podstawie hashy węzłów S1 oraz S2: H(S1 || S2).
Na samej górze znajduje się korzeń drzewa – Merkle root. Struktura drzewa jest bardzo wrażliwa na najmniejszą zmianę w bloku danych. Jakakolwiek zmiana w którymkolwiek bloku danych, będzie skutkowała inną wartością hasha w korzeniu!
Tylko na podstawie korzenia drzewa jesteśmy w stanie zweryfikować, czy plik jaki chcemy pobrać w sieci p2p z niezaufanego źródła jest poprawny. Korzeń drzewa zazwyczaj pobierany jest z zewnętrznego zaufanego źródła. Jest to ogromne efektywne rozwiązanie, ponieważ na podstawie krótkiego hasha (np. 256 bitów) jesteśmy w stanie podjąć decyzję, czy rozpoczniemy pobieranie pliku z konkretnego źródła.
Zastosowanie w blockchain
Tak jak dąb jest symbolem stabilności, tak drzewa Merkle budują stabilną sieć blockchain. Przeanalizujemy teraz praktyczne zastosowanie drzew w najpopularniejszej sieci Bitcoin.
Głównym celem drzew Merkle w blockchain jest możliwość szybkiej weryfikacji transakcji. Drzewo budowane jest na podstawie identyfikatorów transakcji umieszczonych w bloku. Następnie wyliczony korzeń drzewa jest zapisywany w nagłówku bloku.
Dla przypomnienia. Sieć blockchain jak sama nazwa wskazuje przechowuje połączone ze sobą bloki danych. Każdy blok danych zawiera zgrupowane transakcje. Każda transakcja posiada unikalny identyfikator.
Ale po co nam w ogóle drzewa Merkle do weryfikacji transakcji? Bez tej struktury danych sprawdzenie, czy konkretna transakcja została zawarta w danym bloku (a tym samym potwierdzona) wymagałaby pobrania dużej ilości danych oraz przeprowadzenia na nich operacji. W Bitcoin pojedynczy blok może zawierać nawet kilka tysięcy transakcji. Ten narzut danych i konieczność porównywania pojedynczych rekordów mogłaby uniemożliwić powstanie wydajnej sieci blockchain.
Dzięki zastosowaniu drzew Merkle możliwe jest oddzielenie procesu walidacji danych od samych danych. Weryfikacja transakcji nie wymaga posiadania kompletnej kopii blockchain (342 GB – stan na 04.04.2021). Umożliwiło to wprowadzenie uproszczonej weryfikacji płatności (Simplified Payment Verification – SPV), która znalazła zastosowanie w lekkich klientach Bitcoin (Light Node – np. portfele na telefonach komórkowych).
Przeprowadzimy teraz przykładową walidację, czy wykonana przez nas transakcja została już umieszczona w nowym bloku.
- Hash identyfikatora naszej transakcji to h(D).
- Aby wyliczyć węzeł nadrzędny h(CD), potrzebujemy hash transakcji h(C).
- Do kolejnego węzła nadrzędnego potrzebujemy hash h(AB) i wyliczamy h(ABCD).
- Finalnie aby wyliczyć korzeń drzewa, potrzebujemy hash h(EFGH) reprezentujący prawą stronę drzewa.
Wyliczony w kroku 4 korzeń drzewa, porównujemy z korzeniem w nagłówku danego bloku. Jeśli hashe są identyczne, mamy pewność, że nasza transakcja została umieszczona w bloku. Zastosowanie struktury drzew Merkle do walidacji danych pozwoliło na zredukowanie ilości przesłanych danych do niezbędnych 3 hashy (h(C), h(AB), h(ERGH)) i zredukowała ilość operacji hashowania do 3 (h(CD), h(ABCD), h(ABCDEFGH)). Brakujące dane do weryfikacji pobierane są od klientów podłączonych do sieci przechowujących kompletny blockchain (np. górnicy). Warto zwrócić uwagę, że przykładowa walidacja dotyczy drzewa Merkle zbudowanego na podstawie tylko 8 transakcji. Typowy blok w sieci Bitcoin zawiera nawet kilka tysięcy transakcji!
Przykładowy nagłówek bloku 677989 zawierający korzeń drzewa Merkle wyliczony na podstawie 2974 transakcji:
Podsumowanie
Mimo, że minęło już ponad 40 lat (rok 1979) odkąd Ralph Merkle opatentował swoją strukturę danych, cały czas cieszy się ona dużą popularnością. Bez wątpienia drzewa Merkle ułatwiły utworzenie oraz dynamiczny rozwój pierwszej kompletnej kryptowaluty Bitcoin zapewniając wydajną weryfikacją oraz integralność transakcji. Na czas pisania artykułu struktura danych odpowiada za bezpieczeństwo prawie 1.5 biliona dolarów aktywów przechowywanych w blockchainie Bitcoin oraz Ethereum!
