Co to jest drzewo Merkle?
Koncepcję drzewa Merkle’a zaproponował na początku lat 80. Ralph Merkle – informatyk znany z prac nad kryptografią klucza publicznego.
Drzewo Merkle'a to struktura służąca do skutecznej weryfikacji integralności danych w zestawie. Są szczególnie interesujące w kontekście sieci peer-to-peer, w których uczestnicy muszą dzielić się i niezależnie weryfikować informacje.
Funkcje mieszające stanowią rdzeń struktur drzewa Merkle, dlatego zalecamy sprawdzenie Co to jest haszowanie? przed kontynuowaniem.
Jak działają drzewa Merkle?
Załóżmy, że chcesz pobrać duży plik. W przypadku oprogramowania typu open source zazwyczaj chcesz sprawdzić, czy skrót pobranego pliku odpowiada hashowi udostępnionemu publicznie przez programistów. Jeśli tak, wiesz, że plik, który masz na swoim komputerze, jest dokładnie taki sam jak plik na Twoim komputerze.
Jeśli skróty nie pasują, masz problem. Albo pobrałeś złośliwy plik udający oprogramowanie, albo nie został on pobrany poprawnie i dlatego nie będzie działać. W tym drugim przypadku prawdopodobnie nie będziesz zbyt szczęśliwy, jeśli będziesz musiał poczekać trochę czasu na pobranie pliku. Teraz musisz ponownie uruchomić proces i mieć nadzieję, że nie ulegnie on ponownemu uszkodzeniu.
Myślisz, że gdyby tylko można było to zrobić w prostszy sposób. Na szczęście tu właśnie pojawiają się drzewa Merkle. Dzięki jednemu z nich plik zostanie podzielony na kawałki. Jeśli był to plik o rozmiarze 50 GB, można go podzielić na sto części, tak aby każda miała rozmiar 0,5 GB. Następnie byłby pobierany kawałek po kawałku. Zasadniczo to robisz, gdy torrentujesz pliki.
W takim przypadku Twoje źródło udostępni Ci skrót znany jako korzeń Merkle. Ten pojedynczy skrót reprezentuje każdą porcję danych tworzących plik. Ale korzeń Merkle znacznie ułatwia weryfikację danych.
Dla uproszczenia weźmy przykład, w którym używamy pliku o wielkości 8 GB podzielonego na osiem części. Nazwij różne fragmenty od A do H. Każdy fragment jest następnie przepuszczany przez funkcję skrótu, co daje nam osiem różnych skrótów.
Przekazujemy każdy z naszych ośmiu fragmentów przez funkcję skrótu, aby uzyskać ich skróty.
OK, więc mamy coś, co ma trochę większy sens. Mamy skrót wszystkich fragmentów, więc jeśli któryś jest wadliwy, dowiemy się tego, porównując go z fragmentem źródła, prawda? Być może, ale jest to również niezwykle nieefektywne. Jeśli Twój plik składa się z tysięcy fragmentów, czy naprawdę zamierzasz je wszystkie zahaszować i skrupulatnie porównać wyniki?
Nie. Zamiast tego weźmiemy każdą parę skrótów, połączymy je, a następnie połączymy razem. Zatem mieszamy hA + hB, hC + hd, hE + hF i hG + hH. Kończymy z czterema skrótami. Następnie wykonujemy kolejną rundę mieszania z nimi, aby otrzymać dwa. Na koniec haszujemy pozostałe dwa, aby uzyskać nasz główny skrót – korzeń Merkle (lub skrót główny).
Konstrukcja przypomina odwrócone drzewo. W dolnym rzędzie mamy liście, które łączy się, tworząc węzły i na koniec korzeń.
Mamy teraz katalog główny Merkle reprezentujący pobrany plik. Możemy porównać ten skrót główny z hashem dostarczonym przez źródło. Jeśli pasuje, idealnie! Jeśli jednak skróty są różne, możemy być pewni, że dane zostały zmodyfikowane. Innymi słowy, jeden lub więcej fragmentów utworzyło inny skrót. Zatem każda niewielka modyfikacja danych da nam zupełnie inny pierwiastek Merkle.
Na szczęście istnieje wygodny sposób, aby sprawdzić, który fragment jest uszkodzony. W naszym przypadku powiedzmy, że jest to hE. Zacząłbyś od zapytania partnera o dwa skróty, które utworzyły korzeń Merkle (hABCD i hEFGH). Twoja wartość hABCD powinna odpowiadać ich wartości, ponieważ w tym poddrzewie nie ma błędu. Ale hEFGH tego nie zrobi, więc wiesz, żeby się tam sprawdzić. Następnie żądasz hEF i hGH i porównujesz je ze swoimi. hGH będzie wyglądać dobrze, więc wiesz, że hEF jest naszym winowajcą. Na koniec porównujesz skróty hE i hF. Teraz wiesz, że hE jest niepoprawne, więc możesz ponownie pobrać ten fragment.
Podsumowując, drzewo Merkle tworzy się poprzez podzielenie danych na wiele części, które następnie są wielokrotnie mieszane w celu utworzenia korzenia Merkle. Można wtedy skutecznie zweryfikować, czy coś poszło nie tak z fragmentem danych. Jak zobaczymy w następnej sekcji, istnieją również inne interesujące aplikacje.
Chcesz zacząć przygodę z kryptowalutą? Kup Bitcoin na Binance!
Dlaczego korzenie Merkle są używane w Bitcoinie?
Istnieje kilka przypadków użycia drzew Merkle, ale tutaj skupimy się na ich znaczeniu w blockchainach. Drzewa Merkle są niezbędne w Bitcoinie i wielu innych kryptowalutach. Są integralną częścią każdego bloku i można je znaleźć w nagłówkach bloków. Aby uzyskać liście dla naszego drzewa, używamy skrótu transakcji (TXID) każdej transakcji zawartej w bloku.
Korzeń Merkle służy w tym przypadku kilku celom. Przyjrzyjmy się ich zastosowaniu w wydobywaniu kryptowalut i weryfikacji transakcji.
Górnictwo
Blok Bitcoin składa się z dwóch części. Pierwsza część to nagłówek bloku, segment o stałym rozmiarze zawierający metadane bloku. Druga część to lista transakcji, których rozmiar jest zmienny, ale zwykle jest znacznie większy niż nagłówek.
Górnicy muszą wielokrotnie hashować dane, aby uzyskać wynik spełniający określone warunki w celu wydobycia prawidłowego bloku. Mogą podjąć tryliony prób, zanim je znajdą. Przy każdej próbie zmieniają losową liczbę w nagłówku bloku (jednorazówkę), aby uzyskać inny wynik. Ale znaczna część bloku pozostaje taka sama. Transakcji może być tysiące, a mimo to za każdym razem trzeba je hashować.
Korzeń Merkle znacznie usprawnia ten proces. Kiedy rozpoczynasz wydobycie, zestawiasz wszystkie transakcje, które chcesz uwzględnić, i konstruujesz drzewo Merkle. Umieszczasz wynikowy skrót główny (32 bajty) w nagłówku bloku. Następnie podczas wydobywania wystarczy zahaszować nagłówek bloku, a nie cały blok.
To działa, ponieważ jest odporne na manipulacje. Skutecznie podsumowujesz wszystkie transakcje bloku w kompaktowym formacie. Nie możesz znaleźć prawidłowego nagłówka bloku i później zmienić listy transakcji, ponieważ spowodowałoby to zmianę katalogu głównego Merkle. Gdy blok jest wysyłany do innych węzłów, obliczają one pierwiastek z listy transakcji. Jeśli nie pasuje do tego w nagłówku, odrzucają blok.
Weryfikacja
Istnieje jeszcze jedna interesująca właściwość korzeni Merkle, którą możemy wykorzystać. Ten dotyczy klientów lekkich (węzłów, które nie przechowują pełnej kopii łańcucha bloków). Jeśli uruchamiasz węzeł na urządzeniu z ograniczonymi zasobami, nie chcesz pobierać i szyfrować wszystkich transakcji bloku. Zamiast tego możesz po prostu poprosić o dowód Merkle – dowód dostarczony przez pełny węzeł, który potwierdza, że Twoja transakcja znajduje się w określonym bloku. Jest to powszechnie określane jako uproszczona weryfikacja płatności lub SPV i zostało szczegółowo opisane przez Satoshi Nakamoto w białej księdze Bitcoin.
Aby sprawdzić HD, potrzebujemy tylko skrótów pokazanych na czerwono.
Rozważmy scenariusz, w którym chcemy poznać informacje o transakcji, której TXID to hd. Jeśli zostanie nam dostarczone hC, możemy wyliczyć hCD. Następnie potrzebujemy hAB do obliczenia hABCD. Na koniec, za pomocą hEFGH, możemy sprawdzić, czy powstały korzeń Merkle'a pasuje do tego z nagłówka bloku. Jeśli tak, jest to dowód, że transakcja została uwzględniona w bloku – utworzenie tego samego skrótu z różnymi danymi byłoby prawie niemożliwe.
W powyższym przykładzie musieliśmy hashować tylko trzy razy. Bez dowodu Merkle musielibyśmy to zrobić siedem razy. Ponieważ obecnie bloki zawierają tysiące transakcji, korzystanie z dowodów Merkle oszczędza nam mnóstwo czasu i zasobów obliczeniowych.
Zamykanie myśli
Drzewa Merkle okazały się bardzo przydatne w szeregu zastosowań informatycznych – jak widzieliśmy, są niezwykle cenne w blockchainach. W systemach rozproszonych drzewa Merkle pozwalają na łatwą weryfikację informacji bez zalewania sieci niepotrzebnymi danymi.
Bez drzew Merkle (i korzeni Merkle) bloki Bitcoina i innych kryptowalut nie byłyby tak zwarte jak obecnie. I chociaż lekkim klientom brakuje elementów zapewniających prywatność i bezpieczeństwo, dowody Merkle umożliwiają użytkownikom sprawdzenie, czy ich transakcje zostały uwzględnione w bloku przy minimalnym nakładzie pracy.
