Drzewa Merkle: Jak pojedynczy hasz weryfikuje miliony rekordów

Jeden hash do weryfikacji wszystkiego

Drzewo Merkle’a, nazwane na cześć Ralph’a Merkela z jego patentu z 1979 roku, jest drzewem binarnym, w którym każdy liść zawiera kryptograficzny hash bloku danych, a każdy węzeł wewnętrzny zawiera hash konkatenacji hashów dwóch jego potomków. Rezultatem jest pojedynczy hash korzenia, który podsumowuje każdy bajt każdego bloku poniżej niego – zmiana jednego bitu gdziekolwiek w danych spowoduje zmianę haszu liścia, co z kolei wpłynie na jego rodzica, a następnie na jego rodzica, aż do zupełnie innego korzenia. To właśnie umożliwia systemom tak różnym jak Git, BitTorrent, ZFS, Certificate Transparency i każda duża sieć blockchain weryfikację ogromnych zbiorów danych przy użyciu jednego małego, ustalonego rozmiaru odcisk palca.

leaf0..leaf3 = H(block0)..H(block3)
node10 = H(leaf0 || leaf1)      node11 = H(leaf2 || leaf3)
root   = H(node10 || node11)
// flip one bit in block2 -> leaf2 changes -> node11 changes -> root changes

Weryfikacja przynależności bez całego zbioru danych

Właściwość, która sprawia, że drzewa Merkle są przydatne w praktyce, a nie tylko eleganckie, to dowód Merkle (zwany również ścieżką audytową lub dowodem przynależności): aby udowodnić, że określony blok należy do drzewa z znanym korzeniem, wystarczy dostarczyć ten blok oraz hash rodzącego się z niego na każdym poziomie drogi aż do korzenia — O(log n) haszy dla n liści, zamiast całego zbioru danych. Sprawdzający ponownie oblicza ścieżkę od bloku w górę i sprawdza, czy zgadza się ze znanym korzeniem.

// udowodnij, że liść2 znajduje się pod `korzeniem`, przy założeniu rodzących się z niego braci [liść3, węzeł10] h = H(liść2) h = H(h || liść3) // połączenie z bratem na poziomie 1 (liść2 jest lewym dzieckiem) h = H(węzeł10 || h) // połączenie z bratem na poziomie 2 (to poddrzewo jest prawym dzieckiem) assert(h === korzen) // O(log n) haszy udowadniają przynależność do zbioru n elementów Dla drzewa nad milionem liści, to około 20 obliczeń haszów, aby udowodnić przynależność — weryfikowalne w mikrosekundach nawet na telefonie, co jest dokładnie właściwością, na której opiera się Simplified Payment Verification (SPV) klient Bitcoina: lekki klient może potwierdzić, że transakcja znajduje się w bloku, sprawdzając ~20-haszowy dowód Merkle przeciwko nagłówkowi bloku, bez pobierania lub przechowywania całego bloku.

// prove leaf2 is under `root`, given siblings [leaf3, node10]
h = H(leaf2)
h = H(h || leaf3)     // combine with sibling at level 1 (leaf2 is left child)
h = H(node10 || h)    // combine with sibling at level 2 (this subtree is right child)
assert(h === root)    // O(log n) hashes prove membership in a set of n items

Dlaczego wykorzystuje się je w blockchainach

Każda blok w Bitcoinie i Ethereum przechowuje pierwiastek Merkle ze wszystkich swoich transakcji w nagłowie, a nie same transakcje w zakodowanym nagłowie. To oddziela rozmiar danych potrzebnych do osiągnięcia konsensusu (stały, mały nagłowy) od liczby transakcji w bloku i oznacza, że ​​każda ingerencja w dowolną transakcję, niezależnie od tego, jak głęboko w drzewie, jest wykrywalna z samego nagłowia. Ethereum idzie jeszcze dalej, wykorzystując pierwiastek Merkle Patricia trie – drzewo Merkle połączone z radix trie – aby sprawdzić cały rejestr kont/stanu i efektywnie aktualizować go krok po kroku, zamiast ponawiać haszowanie statycznej listy.

Odporność na kolizje stanowi cały model bezpieczeństwa

Każda gwarancja tutaj opiera się na odporności podległej funkcji haszującej na kolizje: musi być obliczeniowo niemożliwe znalezienie dwóch różnych wejść, które haszują do tego samego wyjścia. Jeśli atakujący mógłby znaleźć kolizję H(x) = H(y) dla x ≠ y, mógłby wymienić dane liścia bez zmiany korzenia, cicho tworząc dowód Merkle'a. Dlatego też drzewa Merkle'a odchodzą od MD5 i SHA-1, gdy udowodniono praktyczne kolizje przeciwko nim, a nowoczesne implementacje wykorzystują SHA-256 lub Keccak/SHA-3.

Bardziej subtelna atak, druga próba przedniej preimagi na drzewach Merkle'a, wykorzystuje fakt, że hasz wewnętrznego węzła i hasz liścia mogą wyglądać strukturalnie identycznie, jeśli ich nie rozróżnimy – atakujący może czasami przedstawić węzeł wewnętrzny jako liść i wygenerować wyglądający jak prawdziwy dowód dla danych, które nigdy nie były liściem. Standardową obroną, używaną przez BIP Bitcoina i RFC o Transparentności Certyfikatów, jest separacja domen: wstępne hasze liści oznaczaj byte'ami różnicującymi się (np. 0x00) a hasze węzłów wewnętrznych innym (0x01) przed haszowaniem, aby hash liścia nigdy nie mógł być mylony z ani zastąpiony przez hash węzła wewnętrznego.

Budowanie go wydajnie

Budowa drzewa od dołu, zaczynając od n liści, zajmuje łącznie O(n) operacji hashujących (n liści stają się n/2 węzłami wewnętrznymi, następnie n/4 i tak dalej – szereg geometryczny sumujący się w mniej niż 2n). W przypadku nieparzystej liczby liści na jakimś poziomie standardową praktyką jest powielenie ostatniej operacji hashującej zamiast pozostawiania jej niepołączonej, choć niektóre implementacje zamiast tego bezpośrednio ją promują – istotne jest, aby niezależnie od przyjętej konwencji, zarówno budowniczy drzewa jak i każdy weryfikator ją stosowali konsekwentnie, w przeciwnym razie dowody wygenerowane przez jednego nie będą mogły zostać zweryfikowane przeciwko drugiemu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Merkle Tree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.