Czym jest Merkle Tree?

Merkle Tree to struktura danych, która kompresuje dużą liczbę rekordów do jednego krótkiego odcisku. Pozwala udowodnić, że element znajduje się na ogromnej liście, sprawdzając tylko kilka małych fragmentów zamiast całości. Wyobraź sobie drzewo genealogiczne, w którym każdy rodzic jest podsumowaniem swoich dzieci, a wszystko zbiera się w jednego wspólnego przodka.

Mit

Merkle Tree „przechowuje” wszystkie transakcje. Nie do końca. Przechowuje tylko zwarte odciski tych transakcji, a drzewo można odtworzyć z surowych rekordów w razie potrzeby.

Jak działa Merkle Tree

Wyobraź sobie blok płatności, który potrzebuje szybkiego i możliwego do zweryfikowania podsumowania. Oto, jak działa Merkle Tree w prostych słowach:

Krok 1: Zacznij od listy elementów, na przykład transakcji; każdy z nich to liść w drzewie.
Krok 2: Zamień każdy element w krótki odcisk, używając funkcji skrótu.
Krok 3: Sparuj sąsiednie odciski, połącz każdą parę i oblicz ich skrót ponownie, aby otrzymać węzeł rodzica.
Krok 4: Powtórz parowanie i obliczanie skrótów na kolejnych poziomach, aż pozostanie jeden najwyższy odcisk. To jest Merkle root tego zbioru.
Krok 5: Aby udowodnić, że element należy do zbioru, potrzebujesz tylko tego elementu oraz krótkiej ścieżki odcisków sąsiednich. Szybkie i niewielkie.

O to chodzi: krótkie dowody, duża pewność.

Dlaczego Merkle Tree ma znaczenie

Podsumowując duże ilości danych transakcji w jeden zwarty odcisk, Merkle Tree sprawia, że weryfikacja jest szybka i tania.

Zaleta: Możesz sprawdzić przynależność bez pobierania całego bloku, oszczędzając czas i przepustowość.
Perspektywa: Pasuje do obecnego klimatu internetu: ufaj, ale sprawdzaj; Rolex spotyka wątki Reddita.
Gdzie się pojawia: Spotkasz je w blokach Bitcoina, w stanie i potwierdzeniach transakcji Ethereum, na listach dozwolonych adresów NFT, w airdropach i w rollupach.

Wskazówka

Jeżeli liczba liści jest nieparzysta, wiele rozwiązań duplikuje ostatni liść przed obliczaniem skrótów w górę drzewa. Dodatkowo sprawdź dokładny proces haszowania, który stosuje Twoja sieć lub biblioteka, ponieważ drobne różnice w zasadach mogą zmienić dowody.

Główne cechy Merkle Tree

To, co czyni go wyjątkowym i przydatnym:

Wydajność: Dowody pozostają małe nawet przy ogromnych zbiorach danych, dzięki czemu lekkie węzły nie muszą pobierać dużo danych.
Integralność: Zmiana jednego bajtu w liściu powoduje efekt kaskadowy aż do korzenia, co sprawia, że manipulacja staje się widoczna.
Korzeń: Wszystko redukuje się do pojedynczego Merkle root, który można przechować lub podpisać do późniejszej weryfikacji.

Warianty

Merkle Tree ma kilka popularnych odmian, na które możesz trafić:

Binarne: Klasyczne drzewo oparte na parach, używane w blokach Bitcoina.
Merkle Patricia: Wersja oparta na trie do danych klucz i wartość, używana w stanie sieci i w potwierdzeniach transakcji Ethereum.
Rzadkie: Ogromne indeksowane drzewo, w którym większość liści jest pusta, dobre do zwięzłych dowodów przynależności i nieprzynależności.
Verkle: Młodszy krewny z krótszymi dowodami przy bardzo szerokim rozgałęzieniu, badany pod kątem przyszłych usprawnień.

Przypomnienie

Dowody Merkle Tree są warte tyle, ile nagłówek lub punkt kontrolny, któremu ufasz. Jeśli zaufasz niewłaściwemu korzeniowi, nawet najczystszy dowód nic nie znaczy.

Przykład

Lekki portfel w stylu Bitcoina może zweryfikować Twoją płatność, sprawdzając krótką ścieżkę skrótów od Twojej transakcji do nagłówka bloku, bez pobierania całej historii transakcji.

Ciekawostka

Ralph Merkle naszkicował ten pomysł pod koniec lat siedemdziesiątych jako projekt studencki, i przez lata krążył on w środowisku akademickim, zanim Satoshi zastosował go w Bitcoinie. Dowód, że dobre pomysły dobrze się starzeją.

Podsumowanie

W skrócie? Merkle Tree daje szybkie, niewielkie dowody, że coś należy do dużego zbioru, bez dramatów i bez potrzeby ciężkiego pobierania danych.

Merkle Tree