Drzewo Merkle’a
Drzewo Merkle’a, po angielsku Merkle tree, to struktura danych, która używa hashy do reprezentowania dużego zbioru elementów jednym root hashem.
Czym jest drzewo Merkle’a
Drzewo Merkle’a bierze wiele elementów danych, hashuje je, a następnie łączy hashe parami i hashuje ponownie aż do uzyskania jednego końcowego hasha.
Ten końcowy hash nazywa się Merkle root albo root hash. Reprezentuje cały zbiór danych.
Jeśli zmieni się choć jeden element na dole drzewa, zmieni się też ścieżka hashy prowadząca do root hasha.
Elementy drzewa Merkle’a
- Liść
- Najniższy element drzewa, zwykle hash pojedynczej transakcji albo danych.
- Hash pośredni
- Hash powstały z połączenia dwóch niższych hashy.
- Root hash
- Końcowy hash reprezentujący cały zbiór.
- Ścieżka
- Zestaw hashy potrzebny do sprawdzenia, czy element należy do drzewa.
- Dowód Merkle’a
- Kompaktowy dowód przynależności elementu do drzewa.
Po co blockchainom drzewa Merkle’a
Blockchainy muszą reprezentować duże zbiory transakcji i danych w sposób możliwy do sprawdzenia.
Bitcoin umieszcza Merkle root w nagłówku bloku. Dzięki temu nagłówek może odnosić się do wszystkich transakcji w bloku bez przechowywania każdego hasha osobno w nagłówku.
Light client albo bridge może użyć dowodu Merkle’a, żeby sprawdzić wybrany element bez pobierania całego zbioru.
Ethereum i warianty Merkle
Ethereum używa struktur pokrewnych Merkle tree w bardziej wyspecjalizowany sposób, m.in. do stanu kont i danych.
W praktyce użytkownik nie musi znać wszystkich wariantów technicznych. Najważniejsza idea pozostaje ta sama: root hash zobowiązuje do określonego zbioru danych.
Mosty, rollupy i systemy ZK często korzystają z Merkle-like commitments, bo pozwalają tanio sprawdzać fragment dużego stanu.
Najczęstsze błędne założenia
- Drzewo Merkle’a nie jest zwykłym indeksem bazy danych.
- Root hash reprezentuje zbiór danych, ale nie wyjaśnia sam, skąd ten zbiór pochodzi.
- Dowód Merkle’a sprawdza przynależność elementu, a nie pełną historię łańcucha.
- Zmiana jednego liścia powinna zmienić root hash.
- Różne protokoły mogą używać różnych wariantów drzew i kodowania danych.
Root hash kompresuje cały zbiór
Drzewo Merkle’a pozwala reprezentować tysiące elementów jednym hashem i później sprawdzać pojedyncze elementy przez krótki dowód.