Zawartość
Co to jest drzewo Merkle?
Jak działają drzewa Merkle?
Dlaczego korzenie Merkle są używane w Bitcoinie?
Górnictwo
Weryfikacja
Końcowe przemyślenia
Co to jest drzewo Merkle?
Pomysł drzewa Merkle zrodził się na początku lat 80. XX wieku przez Ralpha Merkle’a – informatyka najbardziej znanego ze swojej pracy w dziedzinie kryptografii klucza publicznego.
Drzewo Merkle to struktura służąca do skutecznej weryfikacji integralności danych w danym zbiorze danych i jest szczególnie istotna w kontekście sieci peer-to-peer, w których uczestnicy muszą samodzielnie dzielić się i weryfikować informacje.
Funkcje skrótu są istotną częścią struktur drzewa Merkle, dlatego zalecamy przeczytanie artykułu pt. Co to jest Hash? Zanim będziesz kontynuować czytanie tego artykułu.
Jak działają drzewa Merkle?
Załóżmy, że chcesz pobrać duży plik. W przypadku oprogramowania typu open source zazwyczaj warto sprawdzić, czy wartość skrótu pobranego pliku odpowiada wartości udostępnionej publicznie przez programistów. Jeśli tak, to wiesz, że plik, który masz na swoim komputerze, pasuje do ich pliku.
Jeśli wartości skrótu nie pasują, oznacza to problem. Albo pobrałeś plik złośliwego oprogramowania podszywający się pod program, albo pobieranie nie powiodło się, więc nie działa. Jeśli pobieranie nie powiedzie się, prawdopodobnie nie będziesz zadowolony, jeśli będziesz musiał chwilę poczekać na pobranie pliku. Będziesz wtedy musiał rozpocząć proces od nowa i mieć nadzieję, że tym razem pójdzie dobrze.
Być może zastanawiałeś się w tym przypadku, gdyby tylko istniał łatwiejszy sposób na zrobienie tego. Na szczęście tu z pomocą przychodzi drzewo Merkle. Za jego pomocą plik jest dzielony na części. Jeśli rozmiar pliku wynosi 50 GB, możesz podzielić go na 100 części o rozmiarze 0,5 GB każda i pobrać fragment po kawałku. Zasadniczo to robisz, gdy używasz plików torrent.
W takim przypadku źródło pliku zapewni wartość skrótu znaną jako korzeń Merkle. Ta pojedyncza wartość reprezentuje każdą część danych tworzącą plik, ale korzeń Merkle znacznie ułatwia weryfikację danych.
Aby to uprościć, przyjrzymy się temu przykładowi, w którym używamy pliku o rozmiarze 8 GB podzielonego na 8 części i oznaczymy te różne części literami od A do H. Następnie każda część przejdzie przez funkcję skrótu, co daje 8 różnych wartości skrótu.
Przekażemy każdą z ośmiu części przez funkcję skrótu, aby uzyskać ich wartości skrótu.
Cóż, teraz mamy coś, co ma trochę większy sens. Mamy wartości skrótu wszystkich części, więc jeśli któraś z nich jest błędna, dowiesz się o tym, porównując ją ze źródłową wartością skrótu, prawda? Być może, ale jest to również niezwykle nieefektywne. Jeśli plik składa się z tysięcy części, czy naprawdę zamierzasz je wszystkie podzielić na partycje, a następnie tak dokładnie porównać wyniki?
Nie, zamiast tego weźmiemy każdą parę wartości skrótu, dodamy je do siebie, a następnie zmieszamy. Zatem mieszamy hA + hB, hC + hD, hE + hF i hG + hH, tak aby otrzymać 4 wartości skrótu, a następnie wykonujemy kolejną rundę mieszania dla tych wartości, ostatecznie osiągając 2 wartości skrótu. Na koniec haszujemy pozostałe dwie wartości, aby uzyskać główną wartość skrótu – korzeń Merkle (lub wartość skrótu głównego).
Struktura wygląda jak odwrócone drzewo, gdzie w ostatnim rzędzie mamy liście, które łączą się, tworząc węzły i ostatecznie korzeń.
Mamy teraz katalog główny Merkle reprezentujący pobrany plik. Tę wartość skrótu głównego można porównać z wartością podaną przez źródło i jeśli są zgodne, świetnie! Ale jeśli wartości skrótu są różne, mamy pewność, że dane zostały zmodyfikowane, to znaczy, że jedna lub więcej części wygenerowało inną wartość skrótu, więc każda prosta modyfikacja danych da nam zupełnie inny pierwiastek Merkle .
Na szczęście każdy z nas może w prosty sposób sprawdzić, która część jest nieprawidłowa. W tym przypadku powiedzmy, że ta część to hE. Najpierw poproś innego użytkownika o dwie wartości skrótu, które dały korzeń Merkle (hABCD i hEFGH). Twoja wartość hABCD powinna być zgodna z jego wartością, ponieważ w tym poddrzewie nie ma błędu. Nie dotyczy to jednak wartości hEFGH, dlatego warto sprawdzić tę wartość. Następnie żądasz wartości hEF i hGH i porównujesz je z własnymi wartościami. Przekonasz się, że wartość hGH jest w porządku, a potem zdasz sobie sprawę, że przyczyną problemu jest wartość hEF. Na koniec porównasz wartości skrótu hE i hF i już wiesz, że hE jest nieprawidłowe, więc możesz ponownie pobrać ten fragment.
Krótko mówiąc, drzewo Merkle jest tworzone poprzez podzielenie danych na kilka części, które następnie są iteracyjnie mieszane w celu utworzenia korzenia Merkle. Można wtedy skutecznie sprawdzić, czy wystąpił błąd w odniesieniu do fragmentu danych. Jak zobaczymy w następnej sekcji, istnieje również kilka innych interesujących zastosowań.
Chcesz rozpocząć handel walutami cyfrowymi? Kup Bitcoin (BTC) na Binance już teraz!
Dlaczego korzenie Merkle są używane w Bitcoinie?
Istnieje kilka przypadków użycia drzew Merkle, ale tutaj skupimy się na ich znaczeniu w łańcuchach bloków. Drzewa Merkle mają ogromne znaczenie dla Bitcoina i innych kryptowalut. Stanowi główny element każdego bloku, ponieważ znajduje się w partycjach pamięci bloku. Aby uzyskać dostęp do liści drzewa, używamy skrótu transakcji (identyfikatora transakcji) każdej transakcji w bloku.
W tym przypadku korzeń Merkle służy kilku celom, a poniżej dokonamy przeglądu jego zastosowań w wydobywaniu kryptowalut i weryfikacji transakcji.
Górnictwo
Blok Bitcoin składa się z dwóch części. Pierwsza część to partycja do przechowywania bloków, która jest częścią o stałym rozmiarze zawierającą metadane bloku. Druga część to lista transakcji o zmiennym rozmiarze, ale zwykle ma ona znacznie większy rozmiar niż partycja pamięci blokowej.
Górnicy muszą wielokrotnie hashować dane, aby uzyskać dane wyjściowe spełniające określone warunki wydobywania prawidłowego bloku. Mogą wykonać biliony prób, zanim znajdą właściwy blok. Przy każdej próbie zmieniają losową liczbę w sekcji przechowywania bloku (kod prywatny), aby uzyskać inny wynik. Jednak duża część masy pozostaje taka sama. Liczba transakcji może wynosić tysiące transakcji i za każdym razem będziesz musiał je hashować.
Korzeń Merkle znacznie ułatwia ten proces, gdy rozpoczynasz wydobycie, umieszczasz w wierszu wszystkie transakcje, które chcesz uwzględnić, i tworzysz drzewo Merkle. Następnie umieszczasz wynikową wartość skrótu głównego (32 bajty) na partycji pamięci blokowej. Następnie podczas wydobywania wszystko, co musisz zrobić, to zahaszować partycję przechowywania bloków zamiast całego bloku.
Ta metoda działa, ponieważ nie można jej zmienić, skutecznie podsumowując wszystkie transakcje blokowe w kompaktowym formacie. Nie można znaleźć prawidłowej partycji do przechowywania bloków, a następnie zmienić później listę transakcji, ponieważ spowodowałoby to zmianę katalogu głównego Merkle. Kiedy blok jest wysyłany do innych węzłów, oblicza korzeń z listy transakcji, a jeśli nie jest zgodny z tym, co podano w sekcji przechowywania bloków, blok jest odrzucany.
Weryfikacja
Istnieje jeszcze jedna interesująca właściwość korzeni Merkle, z której możemy skorzystać. Ta funkcja jest ważna w przypadku prostego oprogramowania węzłów (węzłów, które nie przenoszą pełnej kopii łańcucha blockchain). Jeśli uruchamiasz węzeł na maszynie o ograniczonych zasobach, nie chcesz pobierać i szyfrować wszystkich transakcji bloku. Zamiast tego możesz poprosić o dowód Merkle – dowód dostarczony przez cały węzeł, który potwierdza, że transakcja istnieje w konkretnym bloku. Nazywa się to często uproszczoną weryfikacją płatności (SPV) i zostało szczegółowo wyjaśnione przez Satoshi Nakamoto w raporcie technicznym Bitcoin.
Aby zweryfikować hd, potrzebujemy tylko wartości skrótu pokazanych na czerwono.
Rozważmy na przykład scenariusz, w którym chcemy poznać informacje o transakcji o identyfikatorze transakcji hD. Jeśli mamy dostępną wartość hC, możemy znaleźć hCD. Następnie potrzebujemy hAB do obliczenia hABCD. Na koniec, w przypadku hEFGH, możemy sprawdzić, czy powstały korzeń Merkle pasuje do tego w partycji pamięci blokowej. Jeśli jest zgodny, jest to dowód na to, że transakcja istniała w bloku – ponieważ wygenerowanie tej samej wartości skrótu przy różnych danych byłoby prawie niemożliwe.
W poprzednim przykładzie musieliśmy wykonać hash tylko trzy razy, a bez dowodu Merkle’a musielibyśmy wykonać go 7 razy. Ponieważ dzisiejsze bloki zawierają tysiące transakcji, wykorzystanie dowodu Merkle'a pozwala zaoszczędzić dużo czasu i zasobów obliczeniowych.
Końcowe przemyślenia
Drzewa Merkle okazały się niezwykle przydatne w szeregu zastosowań informatycznych – i jak widzieliśmy, mają ogromne znaczenie dla blockchainów. W systemach rozproszonych drzewa Merkle ułatwiają weryfikację informacji bez zalewania sieci potokiem niepotrzebnych danych.
Bez drzew Merkle (i korzeni Merkle) bloki Bitcoina i innych kryptowalut nie byłyby tak małe jak obecnie. Chociaż prostemu oprogramowaniu kontraktowemu brakuje prywatności i bezpieczeństwa, dowód Merkle pozwala użytkownikom sprawdzić, czy ich transakcje dołączyły do bloku przy minimalnych kosztach.