Drzewo Merkle

Drzewo Merkle (Merkle Tree) to struktura danych wykorzystująca funkcje skrótu kryptograficznego do efektywnego potwierdzania, że określone dane znajdują się w większym zbiorze i nie zostały zmienione.

Nazwa pochodzi od nazwiska Ralpha Merkle’a, który opatentował tę koncepcję w latach 70.

Drzewa Merkle są wykorzystywane między innymi w:

• blockchainach,
• kryptowalutach,
• systemach rozproszonych,
• systemach kontroli integralności danych,
• protokołach komunikacyjnych,
• systemach przechowywania dużych zbiorów danych.

Ich największą zaletą jest możliwość potwierdzenia obecności konkretnej informacji bez konieczności pobierania i sprawdzania całego zbioru danych.

Jak działa drzewo Merkle?

Drzewo Merkle składa się z kilku poziomów.

Na samym dole znajdują się dane, np. transakcje.

Każda transakcja jest przepuszczana przez funkcję hashującą.

Przykładowo:

Transakcja A → Hash A

Transakcja B → Hash B

Transakcja C → Hash C

Transakcja D → Hash D

Następnie hasze są łączone parami i ponownie haszowane:

Hash A + Hash B → Hash AB

Hash C + Hash D → Hash CD

Na kolejnym poziomie:

Hash AB + Hash CD → Merkle Root

Ostateczny hash znajdujący się na szczycie drzewa nazywa się:

Merkle Root

To właśnie on reprezentuje cały zestaw danych znajdujący się poniżej.

Prosty przykład

Załóżmy, że blok blockchaina zawiera cztery transakcje:

T1

T2

T3

T4

Najpierw obliczamy ich hasze:

H1 = hash(T1)

H2 = hash(T2)

H3 = hash(T3)

H4 = hash(T4)

Następnie:

H12 = hash(H1 + H2)

H34 = hash(H3 + H4)

Na końcu:

Merkle Root = hash(H12 + H34)

Można więc przedstawić strukturę w uproszczeniu:

                 Merkle Root
                /           \
             H12             H34
            /  \            /  \
          H1    H2         H3    H4
          |     |          |     |
          T1    T2         T3    T4

W rzeczywistych systemach drzewo może zawierać tysiące lub miliony elementów.

Czym jest Merkle Root?

Merkle Root to pojedynczy hash reprezentujący wszystkie dane znajdujące się w danym drzewie Merkle.

Jest to niezwykle ważne w blockchainie.

Jeżeli zmieni się choćby jedna transakcja, zmieni się jej hash.

To powoduje zmianę kolejnych hashy znajdujących się wyżej w drzewie.

W rezultacie zmieni się również:

Merkle Root

Można więc powiedzieć, że Merkle Root działa jak kryptograficzny odcisk całego zbioru danych.

Co się stanie po zmianie jednej transakcji?

Załóżmy, że mamy:

T1 → H1

Jeżeli ktoś zmieni T1 choćby o jeden znak:

T1 → T1′

otrzymamy zupełnie inny hash:

H1 → H1′

W konsekwencji zmieni się:

H12

a następnie:

Merkle Root

Schemat:

zmiana jednej transakcji → zmiana jej hash → zmiana gałęzi drzewa → zmiana Merkle Root

Dzięki temu można bardzo łatwo wykryć manipulację danymi.

Dlaczego wykorzystuje się funkcje hashujące?

Funkcja hashująca przekształca dane o dowolnej długości w ciąg znaków o określonej długości.

Przykładowo w Bitcoinie wykorzystywany jest między innymi:

SHA-256

Najważniejszą właściwością funkcji hashujących jest to, że nawet niewielka zmiana danych powinna prowadzić do zupełnie innego wyniku.

Dzięki temu zmiana pojedynczej transakcji powoduje zmianę całej ścieżki prowadzącej do Merkle Root.

Merkle Proof

Jedną z najważniejszych zalet drzewa Merkle jest możliwość stworzenia Merkle Proof, czyli dowodu potwierdzającego, że konkretne dane znajdują się w określonym drzewie.

Załóżmy, że chcemy udowodnić, że transakcja T2 znajduje się w bloku.

Nie musimy otrzymywać wszystkich transakcji.

Wystarczy nam:

• hash T2,
• hash T1,
• hash H34,
• Merkle Root.

Możemy wtedy samodzielnie obliczyć:

H12 = hash(H1 + H2)

a następnie:

Root = hash(H12 + H34)

Jeżeli otrzymany wynik jest identyczny z zapisanym Merkle Root, możemy potwierdzić, że T2 należy do tego drzewa.

Dlaczego Merkle Proof jest wydajny?

To jedna z najważniejszych zalet całej konstrukcji.

Załóżmy, że blok zawiera:

1 000 000 transakcji.

Aby udowodnić obecność jednej transakcji, nie trzeba przekazywać miliona transakcji.

W przypadku zbalansowanego drzewa potrzebujemy w przybliżeniu:

log₂(n)

hashy.

Dla miliona elementów jest to około:

20 hashy.

Zamiast sprawdzać milion danych, możemy więc zweryfikować stosunkowo niewielki dowód.

To ogromna oszczędność danych i czasu.

Drzewa Merkle w Bitcoinie

Drzewa Merkle są jednym z ważnych elementów konstrukcji Bitcoina.

Transakcje znajdujące się w bloku są organizowane w drzewo Merkle.

Z drzewa powstaje:

Merkle Root

który jest następnie zapisywany w nagłówku bloku (block header).

Nagłówek zawiera między innymi:

• hash poprzedniego bloku,
• Merkle Root,
• timestamp,
• difficulty target,
• nonce.

Dzięki temu Merkle Root jest kryptograficznie powiązany z zawartością bloku.

Merkle Root a blockchain

Merkle Root pozwala powiązać zawartość bloku z jego nagłówkiem.

Jeżeli ktoś zmodyfikuje transakcję w bloku:

zmieni się Merkle Root

a więc zmieni się również nagłówek bloku.

Ponieważ nagłówek jest częścią mechanizmu zabezpieczającego blockchain, manipulowanie historią staje się bardzo trudne.

Zmiana danych w jednym bloku może również wymagać przeliczenia kolejnych bloków, ponieważ każdy blok zawiera hash poprzedniego.

Powstaje więc wielopoziomowe zabezpieczenie integralności danych.

Merkle Tree a SPV

Drzewa Merkle są szczególnie istotne dla SPV (Simplified Payment Verification).

SPV pozwala użytkownikowi zweryfikować określone informacje bez przechowywania całego blockchaina.

Zamiast pobierać wszystkie transakcje ze wszystkich bloków, klient może otrzymać:

nagłówki bloków + Merkle Proof

i sprawdzić, czy określona transakcja znajduje się w konkretnym bloku.

Dzięki temu urządzenie nie musi przechowywać pełnej historii blockchaina.

To szczególnie przydatne w przypadku:

• portfeli mobilnych,
• lekkich klientów,
• urządzeń o ograniczonej pamięci,
• systemów o ograniczonej przepustowości.

Merkle Tree a decentralizacja

Merkle Tree nie zapewnia samodzielnie decentralizacji.

Jest natomiast elementem technicznym, który pomaga efektywnie weryfikować integralność danych w systemach rozproszonych.

Blockchain łączy wiele mechanizmów:

• kryptografię,
• funkcje hashujące,
• konsensus,
• sieć peer-to-peer,
• drzewa Merkle.

Każdy z tych elementów pełni inną funkcję.

Co jeśli liczba elementów jest nieparzysta?

W praktycznej implementacji drzewa Merkle może pojawić się sytuacja, w której liczba elementów na danym poziomie jest nieparzysta.

Przykładowo mamy:

T1, T2, T3

Nie można wtedy po prostu utworzyć trzech par.

Sposób rozwiązania zależy od konkretnego protokołu.

W przypadku Bitcoina, gdy na danym poziomie pozostaje nieparzysta liczba hashy, ostatni hash jest duplikowany.

Powstaje więc:

H3 + H3 → H33

Następnie proces jest kontynuowany.

To ważny szczegół, ponieważ sposób budowania drzewa musi być jednoznaczny, aby każdy uczestnik sieci otrzymał ten sam Merkle Root.

Merkle Tree a bezpieczeństwo

Drzewo Merkle zapewnia przede wszystkim integralność danych i efektywną weryfikację ich przynależności do zbioru.

Nie oznacza to jednak, że samo drzewo szyfruje dane.

To istotna różnica.

Hash:

nie szyfruje informacji

i nie pozwala na jej późniejsze „odszyfrowanie”.

Hash służy przede wszystkim do:

• identyfikacji danych,
• wykrywania zmian,
• tworzenia dowodów integralności.

Merkle Tree a kryptografia

Drzewa Merkle wykorzystują kryptografię, ale same w sobie nie są osobnym algorytmem szyfrującym.

Ich działanie opiera się przede wszystkim na funkcjach hashujących.

Można więc traktować je jako:

strukturę danych + funkcje kryptograficzne

pozwalające efektywnie reprezentować i weryfikować duże zbiory danych.

Merkle Tree w Ethereum

Drzewa Merkle lub struktury oparte na podobnej idei są również wykorzystywane w ekosystemie Ethereum.

W Ethereum tradycyjna struktura danych nie jest jednak identyczna z prostym drzewem Merkle używanym do organizowania transakcji w Bitcoinie.

Ethereum wykorzystuje między innymi bardziej zaawansowane struktury Merkle Patricia Trie, które pozwalają reprezentować i weryfikować stan sieci.

W blockchainach można więc spotkać różne warianty struktur opartych na idei Merkle.

Merkle Patricia Trie

Merkle Patricia Trie (MPT) łączy właściwości:

• drzewa Merkle,
• trie,
• mechanizmów efektywnego przechowywania klucz-wartość.

W Ethereum struktury tego typu są wykorzystywane między innymi do reprezentowania:

• stanu kont,
• przechowywanych danych,
• transakcji,
• receiptów.

Podobnie jak w klasycznym drzewie Merkle, zmiana danych wpływa na hash korzenia struktury.

Merkle Tree poza blockchainem

Drzewa Merkle nie zostały stworzone wyłącznie dla kryptowalut.

Mogą być wykorzystywane wszędzie tam, gdzie trzeba efektywnie sprawdzać integralność dużych zbiorów danych.

Przykładowe zastosowania obejmują:

• systemy rozproszone,
• rozproszone systemy plików,
• synchronizację danych,
• kontrolę integralności,
• protokoły P2P,
• systemy przechowywania danych.

Ich główna zaleta pozostaje taka sama:

możliwość szybkiego udowodnienia, że dana informacja należy do określonego zbioru.

Merkle Tree a zwykła suma kontrolna

Merkle Tree jest znacznie bardziej rozbudowaną konstrukcją niż pojedyncza suma kontrolna.

Jeżeli mam jeden hash całego pliku, mogę sprawdzić, czy cały plik został zmieniony.

Jeżeli jednak mam ogromny zbiór danych, drzewo Merkle pozwala efektywnie tworzyć dowody dotyczące pojedynczych elementów tego zbioru.

To właśnie Merkle Proof stanowi jedną z największych praktycznych zalet tej konstrukcji.

Merkle Tree – najważniejsza idea

Najprościej można zapamiętać działanie drzewa Merkle w czterech krokach:

1. Dane są haszowane.

2. Hasze są łączone parami.

3. Powstałe wyniki są ponownie haszowane.

4. Proces trwa aż do uzyskania jednego hasha – Merkle Root.

W efekcie:

wiele danych → jeden reprezentujący je hash

Jednocześnie można zachować możliwość szybkiego udowodnienia, że konkretny element znajduje się w tym zbiorze.

Drzewo Merkle – podsumowanie

Drzewo Merkle (Merkle Tree) to struktura kryptograficzna, która pozwala efektywnie reprezentować duży zbiór danych i sprawdzać jego integralność.

Jego najważniejszym elementem jest:

Merkle Root

czyli pojedynczy hash reprezentujący całą zawartość drzewa.

Największą zaletą jest możliwość tworzenia:

Merkle Proof

czyli krótkiego dowodu potwierdzającego, że konkretny element znajduje się w określonym zbiorze danych.

W blockchainie ma to ogromne znaczenie.

W Bitcoinie transakcje w bloku są organizowane w drzewo Merkle, a Merkle Root trafia do nagłówka bloku. Dzięki temu można efektywnie powiązać zawartość bloku z jego nagłówkiem i weryfikować transakcje bez konieczności pobierania całej zawartości blockchaina.

Dla mnie najprostsze porównanie jest takie:

Merkle Root jest jak cyfrowy odcisk całego zbioru danych, a Merkle Proof pozwala udowodnić, że konkretny element znajduje się w tym zbiorze bez pokazywania całej jego zawartości.