Treść
Co to jest drzewo Merkle?
Jak zbudowane są drzewa Merkle?
Dlaczego korzenie Merkle są używane w Bitcoinie?
Górnictwo
Weryfikacja
Wznawiać
Co to jest drzewo Merkle?
Koncepcja drzewa Merkle została zaproponowana na początku lat 80. XX wieku przez Ralpha Merkle’a, informatyka znanego z pracy nad kryptografią klucza publicznego.
Drzewo Merkle'a to struktura służąca do weryfikacji danych w zbiorze. Jest szeroko stosowany w sieciach peer-to-peer, gdzie uczestnicy muszą wymieniać informacje i poddawać je niezależnej weryfikacji.
Struktura drzewa Merkle opiera się na funkcjach skrótu, dlatego zalecamy zapoznanie się z artykułem „Co to jest haszowanie?”, a następnie powrót do tego tematu.
Jak zbudowane są drzewa Merkle?
Załóżmy, że pobierasz duży plik. Korzystając z programu typu open source, musisz sprawdzić, czy hash pobranego pliku jest zgodny z hashem opublikowanym przez programistów. Jeśli pasuje, oznacza to, że plik na Twoim komputerze jest dokładnie taki sam, jak plik na Twoim komputerze.
Jeśli skróty są różne, oznacza to, że albo pobrałeś złośliwy plik udający program, albo został on pobrany niepoprawnie i nie będzie działać. Problemy z ładowaniem również mogą być kłopotliwe, zwłaszcza jeśli zajmuje to dużo czasu. W takim przypadku będziesz musiał pobrać plik ponownie i mieć nadzieję, że tym razem wszystko pójdzie dobrze.
Pewnie myślisz: „Czy to naprawdę takie skomplikowane?” Na szczęście z pomocą przychodzą drzewa Merkle, które pozwalają nam podzielić plik na części. Na przykład plik o rozmiarze 50 GB można podzielić na 100 fragmentów po 0,5 GB. W takim przypadku zostanie on pobrany w częściach, podobnie jak pliki pobierane są przez torrent.
Głównym celem tego procesu jest uzyskanie pojedynczego skrótu zwanego korzeniem Merkle, który reprezentuje każdą część danych w pliku. Używając korzenia Merkle, możemy znacznie uprościć walidację danych.
Jako przykład weźmy plik o wielkości 8 GB podzielony na 8 części. Każdemu fragmentowi nadawana jest nazwa od A do H, a następnie przepuszczana przez funkcję skrótu w celu uzyskania 8 różnych skrótów.
Każdy z ośmiu fragmentów przechodzi przez funkcję skrótu w celu wygenerowania skrótu.
Więc mamy to z głowy. Otrzymaliśmy hash wszystkich fragmentów, co oznacza, że możemy porównać go z oryginałem i dowiedzieć się, który z nich jest wadliwy, prawda? Jest to możliwe, ale byłoby wyjątkowo nieskuteczne. W naszym pliku jest tylko osiem fragmentów, ale gdyby było ich tysiące, czy mógłbyś je wszystkie zahaszować i porównać wyniki?
Ledwie. Zamiast tego musisz wziąć każdą parę skrótów, połączyć je i zmieszać razem. Zatem mieszamy hA + hB, hC + hd, hE + hF i hG + hH i otrzymujemy cztery skróty. Następnie przeprowadzamy kolejną rundę mieszania, tak aby powstały dwa skróty. Na koniec haszujemy pozostałą parę i otrzymujemy główny skrót - korzeń Merkle (lub skrót główny).
Konstrukcja przypomina odwrócone drzewo. W dolnym rzędzie znajdują się „liście”, które przechodzą w węzły, które trafiają do korzenia.
Mamy więc korzeń Merkle reprezentujący pobrany plik. Teraz możemy porównać hash główny z hashem oryginalnego twórcy. Jeśli pasują, wszystko jest świetnie! Jeśli skróty są różne, oznacza to, że dane zostały zmienione, czyli jeden lub więcej fragmentów utworzyło inny hash. Zatem jakakolwiek modyfikacja danych spowoduje utworzenie zupełnie innego pierwiastka Merkle.
Na szczęście bez problemu znajdziemy nieprawidłowy fragment. Powiedzmy, że to jest on. Najpierw sprawdź dwa ostatnie skróty, które utworzyły korzeń Merkle (hABCD i hEFGH). Twoje hABCD będzie takie samo jak oryginał, ponieważ w tym segmencie nie ma błędów, ale Twoje hEFGH będzie inne i należy je sprawdzić. Następnie żądamy hEF i hGH i porównujemy je z naszymi. Ponieważ hGH będzie pasował, potrzebujemy hEF. Na koniec porównujemy skróty hE i hF. Dowiedzieliśmy się więc, że nieprawidłowym fragmentem jest hE, co oznacza, że musimy go pobrać ponownie.
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. System ten ułatwia sprawdzenie, czy każda część danych jest w porządku. W następnej sekcji przyjrzymy się innym możliwym zastosowaniom.
Zastanawiasz się jak zacząć przygodę z kryptowalutami? Kup Bitcoin na Binance!
Dlaczego korzenie Merkle są używane w Bitcoinie?
Drzewa Merkle mają wiele zastosowań, ale na razie interesuje nas ich zastosowanie w blockchainie. Drzewa Merkle są niezbędne w pracy z Bitcoinem i wieloma innymi kryptowalutami; stanowią integralną część każdego bloku i znajdują się w nagłówkach bloków. Aby uzyskać liście drzewa, używamy skrótu każdej transakcji (TXID) zawartego w bloku.
W tym przypadku korzeń Merkle wykonuje kilka zadań. Następnie przyjrzymy 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órej rozmiar jest zwykle znacznie większy niż nagłówek, ale może się różnić.
Górnicy muszą wielokrotnie hashować dane, aby uzyskać wynik spełniający określone warunki i wydobyć prawidłowy blok. Znalezienie go może wymagać bilionów prób, ponieważ górnicy muszą zmienić losową liczbę w nagłówku bloku (jednorazową), aby uzyskać nowy wynik, ale większość bloku pozostanie taka sama. W bloku mogą znajdować się tysiące transakcji i wszystkie z nich będą musiały być zaszyfrowane za każdym razem.
Korzeń Merkle znacznie upraszcza ten proces. Podczas wydobycia wszystkie niezbędne transakcje są umieszczane w drzewie Merkle. Hash główny (32 bajty) jest umieszczany w nagłówku bloku, po czym hashowany jest tylko nagłówek bloku, a nie cały blok.
Ta metoda jest zabezpieczona przed manipulacją i skutecznie podsumowuje wszystkie transakcje w bloku w kompaktowym formacie. Nie jest jednak możliwe znalezienie prawidłowego nagłówka bloku, a następnie zmiana listy transakcji, ponieważ spowoduje to zmianę katalogu głównego Merkle. Kiedy blok jest wysyłany do innych węzłów, obliczają one pierwiastek z listy transakcji. Jeżeli nie pasuje do katalogu głównego w nagłówku, blok zostaje odrzucony.
Weryfikacja
Przyjrzyjmy się kolejnej przydatnej właściwości korzeni Merkle, która dotyczy uproszczonych węzłów (takich, które nie zawierają pełnej kopii blockchainu). Jeśli uruchamiasz węzeł na urządzeniu z ograniczonymi zasobami, niekoniecznie musisz pobierać i hashować wszystkie transakcje w bloku. Zamiast tego możesz po prostu poprosić pełny węzeł o dowód Merkle – dowód, że Twoja transakcja znajduje się w określonym bloku. Ta metoda została szczegółowo opisana przez Satoshi Nakamoto w białej księdze Bitcoin i często nazywana jest uproszczoną weryfikacją płatności (SPV).
Aby sprawdzić HD, potrzebne są tylko czerwone skróty.
Załóżmy, że potrzebujemy informacji o transakcji, której TXID to hd. Biorąc pod uwagę hC, możemy obliczyć hCD. Następnie potrzebujemy hAB do obliczenia hABCD. Na koniec można użyć hEFGH do sprawdzenia, czy powstały korzeń Merkle'a pasuje do pierwiastka w nagłówku bloku. Jeśli tak, to dowodzi to, że transakcja została uwzględniona w bloku, ponieważ utworzenie tego samego skrótu z różnymi danymi jest prawie niemożliwe.
W powyższym przykładzie hashowaliśmy tylko trzy razy, podczas gdy bez dowodu Merkle’a trzeba by to zrobić siedem razy. Ponieważ bloki mogą zawierać tysiące transakcji, użycie dowodów Merkle może zaoszczędzić dużo czasu i zasobów obliczeniowych.
Wznawiać
Drzewa Merkle udowodniły swoją skuteczność w technologii komputerowej. Są niezwykle przydatne w blockchainach i umożliwiają łatwą weryfikację informacji w systemach rozproszonych bez przeciążania sieci niepotrzebnymi danymi.
Bez drzew Merkle (i korzeni Merkle) bloki Bitcoina i innych kryptowalut byłyby bardzo nieporęczne. Chociaż lekkie węzły mogą budzić obawy związane z prywatnością i bezpieczeństwem, dowody Merkle mogą w opłacalny sposób stwierdzić, czy transakcje zostały uwzględnione w bloku.