Root hash pozwala na weryfikację każdej transakcji. Do weryfikacji należy pobrać jedynie nagłówek bloku i ścieżkę uwierzytelniania transakcji. Drzewo Merkle zmniejsza ilość wymaganych obliczeń, umożliwiając wdrożenie uproszczonej weryfikacji płatności (SPV).
Kto i kiedy wymyślił koncepcję drzewa Merkle?
Twórcą koncepcji drzewa jest profesor Ralph Merkle. W 1979 roku wymyślił sposób reprezentacji podpisów cyfrowych. Uniwersytet Stanforda posiada patent na tę technologię. Naukowiec zaproponował wykorzystanie binarnego drzewa haszowania. Merkle wniósł również znaczący wkład w rozwój kryptografii. Znany jest z publikacji z 1987 roku "A digital signature based on a conventional encryption function".
Do czego służy drzewo Merkle?
System scentralizowany dostarcza dane z jednego źródła, na którym polegają wszyscy użytkownicy. Ten ostatni zapewnia, że otrzymane informacje są poprawne.
Blockchain to rozproszona baza danych. Przechowuje informacje o wielu niezależnych węzłach (nodach). Węzeł nie może przyjmować wiadomości od innych uczestników bez ich weryfikacji. Węzeł musi określić, czy blok zawiera ważne transakcje.
Drzewa Merkle mogą być wykorzystane do zmniejszenia kosztów obliczeniowych. Zmniejszają one ilość danych do pobrania i optymalizują walidację danych poprzez haszowanie.
Metoda ta jest stosowana w sieciach Bitcoin, Ethereum i innych kryptowalut. Tworzy ciąg danych, który weryfikuje grupę transakcji. Algorytm ten jest również stosowany w systemach plików i bazach danych. Drzewa Merkle są wykorzystywane do sprawdzania informacji pod kątem błędów i wykonywania synchronizacji.
Jak działa drzewo Merkle?
Drzewo Merkle jest budowane od dołu do góry. Wartości w węzłach liściowych są uzyskiwane poprzez haszowanie fragmentów danych. Węzły następnego poziomu zawierają hash z sumy dwóch węzłów dziecięcych. Konkatenacja służy do łączenia danych. Operacja jest powtarzana dla węzłów kolejnych poziomów aż do uzyskania jednego hasza. Jeśli liczba elementów jest nieparzysta, jeden z nich jest powielany lub przenoszony na następny poziom w niezmienionej postaci.
Po zbudowaniu drzewa uzyskuje się pojedynczy hasz, który nazywany jest korzeniem Merkle. Ten ostatni reprezentuje wszystkie fragmenty danych. Zatem drzewo Merkle jest jednokierunkową funkcją haszującą.
Algorytm umożliwia budowę struktury binarnej, w której wartości węzłów tworzone są z dwóch ciągów. Ta ostatnia właściwość umożliwia weryfikację dużych ilości danych bez konieczności ponownego obliczania hasza dla wszystkich fragmentów. Koszt obliczeniowy określenia autentyczności pojedynczego elementu w tym przypadku jest znacznie niższy.
Aby zweryfikować poprawność i integralność tablicy, należy porównać root hash z wartością referencyjną. Fragmenty mogą być danymi transakcji lub częściami plików.
Jakie są zalety drzewa Merkle?
Drzewa haszowania ułatwiają weryfikację przynależności transakcji do konkretnego bloku oraz zapewniają integralność informacji podczas jej przesyłania. Metoda ta jest niezbędna do uproszczonej weryfikacji płatności. Satoshi Nakamoto zasugerował użycie SPV w białej księdze bitcoina.
Jeśli węzeł ma znaczne zasoby obliczeniowe, może pobrać wszystkie bloki i znaleźć hasz każdej transakcji. Następnie generowane są drzewa Merkle. Te ostatnie pozwalają mu na sprawdzenie integralności danych i ważności każdej transakcji. Jeśli węzeł ma ograniczone zasoby, może zażądać jedynie nagłówka bloku i identyfikatorów transakcji.
Lekcy klienci pobierają nagłówek i ścieżkę uwierzytelniania (Merkle proof) dla sprawdzanej transakcji. Żądają one informacji od pełnego węzła. Ścieżka uwierzytelniania zawiera hasze z każdej pary węzłów drzewa na ścieżce od węzła do transakcji.
W celu weryfikacji transakcji należy znaleźć korzeń Merkle. Transakcja jest zatwierdzona, jeśli uzyskany hash pasuje do ciągu zawartego w nagłówku bloku. Znalezienie wymaganego korzenia Merkle z innego zestawu danych jest prawie niemożliwe, co gwarantuje ważność transakcji.
Metoda SPV pozwala lekkiemu klientowi na efektywną interakcję z blockchainem i zmniejsza ilość przesyłanych informacji. Na przykład blok z pięcioma transakcjami może mieć rozmiar 500 kilobajtów, podczas gdy dowód Merkle zajmuje tylko 140 bajtów.