Co to jest drzewo Merkle? Wszystko co musisz wiedzieć

ikona publikacji - ciemny
Opublikowano: 28 lipca 2022
ikona autora biały
drzewo merkle

Drzewo Merkle (drzewo hasz lub drzewo skrótów) jest algorytmem, który produkuje pojedynczy hasz dla wielu fragmentów danych. Metoda ta służy do określania integralności pliku i weryfikacji informacji.

Drzewo hasz można przedstawić jako strukturę z gałęziami rozchodzącymi się od jego podstawy do węzłów pośrednich. Na końcach gałęzi znajdują się liście reprezentujące fragmenty danych. U podstawy drzewa znajduje się root hash (korzeń Merkle). Jest on obowiązkowym elementem nagłówka bloku bitcoina.

Hash root pozwala na weryfikację każdej transakcji. Do weryfikacji należy pobrać jedynie nagłówek bloku i ścieżkę uwierzytelniania. 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 Merkle jest profesor Ralph Merkle. W 1979 roku wymyślił on sposób reprezentacji podpisów cyfrowych. Patent na tę technologię posiada Uniwersytet Stanforda.

Naukowiec zaproponował wykorzystanie binarnego drzewa haszującego. Merkle wniósł również znaczący wkład w rozwój kryptografii. Jest on znany z publikacji z 1987 roku zatytułowanej "A digital signature based on a conventional encryption function".


Do czego służy drzewo Merkle?

Scentralizowany system 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. Musi więc 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ż używany 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". Konkatenacja służy do łączenia danych. Operacja jest powtarzana dla węzłów kolejnych poziomów aż do uzyskania jednego hasha. Jeśli liczba elementów jest nieparzysta, jeden z nich jest powielany lub przenoszony na następny poziom bez zmian.

Po zbudowaniu drzewa uzyskuje się pojedynczy hash, który nazywany jest korzeniem Merkle. Reprezentuje on 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ść pozwala na weryfikację dużych ilości danych bez konieczności przeliczania hasha 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.


Jak drzewo Merkle jest wykorzystywane w Bitcoinie?

Blockchain Bitcoina jest tworzony z fragmentów, które są zapisywane na końcu łańcucha. Zawierają one dane o transferach między użytkownikami. Liczba transakcji, jak i ilość informacji jest zmienna, więc blok nie ma stałego rozmiaru.

Węzły Bitcoina tworzą nagłówki w celu optymalizacji obliczeń. Zawierają one następujące elementy:

  • numer wersji bloku;
  • hash poprzedniego bloku;
  • korzeń drzewa Merkle;
  • znacznik czasu;
  • cel trudności wydobycia;
  • jednorazowy kod (nonce) użyty do wygenerowania bloku.
drzewo merkle skrótu
źrodło: bitcoin.org

Nagłówek nie zawiera transakcji i zajmuje 80 bajtów. Ponieważ są one generowane co dziesięć minut, ilość danych wzrasta o 4,2 megabajta rocznie.

Informacje o transakcjach są haszowane, aby uzyskać identyfikatory transakcji. Dane transferowe zapisywane są w formacie szesnastkowym. Hash główny reprezentuje wszystkie transakcje w bloku. W celu jego znalezienia buduje się drzewo Merkle. Dane są przetwarzane zgodnie z algorytmem:

  1. Znajdowane są hash(identyfikatory) transakcji zawartych w bloku: hash(L1), hash(L2), hash(L3) i tak dalej. Tworzą one liście drzewa.
  2. Hasze z sumy dwóch sąsiadujących identyfikatorów umieszczane są na kolejnym poziomie: hash(hash(L1) + hash(L2)). W drzewie binarnym liczba węzłów na każdym poziomie musi być parzysta. W przeciwnym razie hash z ostatniej komórki jest duplikowany i umieszczany w dodatkowym elemencie.
  3. Proces haszowania sumy danych jest powtarzany aż do uzyskania korzenia Merkle.
schemat budowy drzewka Merkle
źródło: Wikipedia

Uzyskany w ten sposób hash potwierdza ważność każdej transakcji. Węzły używają tylko nagłówków poprzednich bloków podczas tworzenia blockchaina.

W sierpniu 2017 r. wdrożono aktualizację protokołu Segregated Witness. Wykorzystuje ona inną strukturę danych transakcyjnych, co zmniejsza rozmiar bloku. Przyjęcie aktualizacji zmniejszyło obciążenie blockchaina bitcoina.


Jakie są korzyści z zastosowania drzewa Merkle?

Drzewa hasz ułatwiają weryfikację przynależności transakcji do konkretnego bloku oraz zapewniają integralność przesyłanych informacji. 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 spore zasoby obliczeniowe, może pobrać wszystkie bloki i znaleźć hash każdej transakcji. Następnie generowane są drzewa Merkle. 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.

Klienci light 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 hashe 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.


Jaki rodzaj drzewa hasz jest używany w Ethereum?

Drzewo binarne Merkle jest dobre dla tablicy reprezentowanej jako lista. Jego struktura pozostaje niezmieniona, co jest wygodne dla transakcji haszujących. Ethereum używa innego sposobu reprezentacji danych - drzewa prefiksów.

Pozwala ono na przechowywanie informacji w tablicy skojarzeniowej. Ciągi są kluczami, które określają pozycje jego elementów. Aby utworzyć strukturę, gałęzie drzewa są oznaczone różnymi symbolami, tak aby klucz elementu jednoznacznie go identyfikował.

schemat drzewa Merkle używany w Ethereum
źródło: Wikipedia

W przeciwieństwie do bitcoina, blockchain Ethereum używa trzech drzew hasz:

  • transakcji;
  • stanu;
  • drzewo zawierające dane o wynikach transakcji.

W nagłówku bloku znajdują się trzy hashe główne. Ethereum pozwala na tworzenie lekkich klientów zdolnych do wykonywania podstawowego zestawu operacji:

  • sprawdzić istnienie transakcji w bloku;
  • sprawdzić istnienie danego adresu;
  • aby określić stan konta użytkownika;
  • znać wynik transakcji lub smart kontraktu.

Powyższe czynności wykonywane są bez pełnego obciążenia bloku. Drzewa hasz upraszczają obliczenia, pozwalając lekkim klientom działać na komputerach PC, laptopach i smartfonach.

Algorytm przetwarzania transakcji w Ethereum jest podobny do tego w bitcoinie. Interakcja z drzewem stanu jest bardziej złożona. Kluczowy element tablicy określa adres użytkownika, a jego wartość reprezentuje stan konta.

Cechą charakterystyczną drzewa hasz jest konieczność częstych aktualizacji oraz konieczność dodawania i usuwania adresów. Do realizacji algorytmu wymagana jest modyfikowalna struktura. Jego parametry są ograniczone, aby zapobiec atakowi DDoS pozwalającemu atakującemu na stworzenie zbyt głębokiego drzewa. W przeciwnym razie aktualizacja struktury i wykonywanie operacji zajęłoby sporo czasu.

Korzeń drzewa musi być określony wyłącznie przez dane i nie może zależeć od ich parametrów. W związku z tym musi istnieć możliwość dokonywania aktualizacji w dowolnej kolejności.

Drzewo prefiksowe rozwiązuje te trudności. W Ethereum każdy element struktury ma 16 dzieci. Takie podejście jest optymalne dla kodowania węzłów w formacie szesnastkowym.

W drzewie prefiksowym, aby uzyskać klucz, należy kolejno podać znaki odpowiadające gałęziom. Określają one ścieżkę od korzenia do wybranego elementu. Wartość klucza jest dynamiczna, co pozwala na dodawanie lub usuwanie nowych węzłów.

Dawid Kucharczyk

Absolwent Uniwersytetu Ekonomicznego we Wrocławiu. Pasjonat nowych technologii, od 3 lat aktywnie uczestniczący w świecie krypto. Instruktor narciarstwa oraz amator gry w squasha. Zwolennik idei decentralizacji.

Powiązane tematy:

Co to jest BNB Vault? Jak korzystać z tej funkcji?

Binance to nie tylko giełda. To cały ekosystem produktów. Jednym z nich jest BNB Vault - agregator zysków, który pozwala zarabiać odsetki od posiadanych już kryptowalut. Funkcja ta umożliwia też w inwestowanie w ciekawe, nowe krypto projekty na wczesnym etapie poprzez Launchpool. W dzisiejszym artykule omówimy BNB Vault szczegółowo. Wyjaśnimy co to jest, jak działa […]

PIXEL w Binance Launchpool. HODLować czy sprzedać?

Binance ogłosiło właśnie 46. projekt, który zostanie uruchomiony na platformie Binance Launchpool. Tym razem jest to PIXEL, natywny token gry Pixels. W dzisiejszym artykule sprawdzimy czym jest PIXEL oraz jak farmić te tokeny na Binance. Na koniec spróbujemy odpowiedzieć na pytanie czy warto je HODLować, czy może sprzedać od razu po rozpoczęciu handlu. Najpierw jednak […]

Co to jest Binance Earn? Środy pełne zarabiania

Jesteś długoterminowym HODLerem? Być może masz w portfelu trochę kryptowalut i nie planujesz ich sprzedawać w najbliższym czasie? Czy wiesz, że istnieje sposób, aby zarabia za ich pomoc pasywny dochód? Pozwala na to np. platforma Binance Earn. Co to jest? Jak działa? Jakie daje możliwości? O tym w dzisiejszym artykule! Czym wyróżnia się Binance Earn? […]

Binance odzyskuje udział w rynku i stabilnie się rozwija

Giełda kryptowalut Binance zaczęła odzyskiwać swój udział w rynku. Sytuacja ma miejsce zaledwie kilka miesięcy po rozstrzygnięciu sprawy z Departamentem Sprawiedliwości Stanów Zjednoczonych i zapłaceniu grzywny w wysokości 4,3 miliarda dolarów. Według danych firmy badawczej Kaiko, udział Binance w rynku pod względem wolumenu obrotu wzrósł do 49% dwa miesiące po tym, jak giełda rozstrzygnęła sprawę […]

Tłusto o Krypto 2 - Poznań otwiera drzwi do świata kryptowalut

Już 8 lutego 2024 roku odbędzie się kolejne krypto wydarzenie w Poznaniu - "Tłusto o krypto 2". Wstęp jest zupełnie darmowy, jednak liczba miejsc mocno ogrniczona. Jeżeli chcesz zdobyć wiedzę dot. cyfrowych aktywów, poznać nowych ludzi czy też po prostu dobrze się bawić, zarejestruj się już teraz! Szczegóły wydarzenia Organizatorem "Tłusto o Krypto 2" jest […]

Co to jest BNB Vault? Jak korzystać z tej funkcji?

Binance to nie tylko giełda. To cały ekosystem produktów. Jednym z nich jest BNB Vault - agregator zysków, który pozwala zarabiać odsetki od posiadanych już kryptowalut. Funkcja ta umożliwia też w inwestowanie w ciekawe, nowe krypto projekty na wczesnym etapie poprzez Launchpool. W dzisiejszym artykule omówimy BNB Vault szczegółowo. Wyjaśnimy co to jest, jak działa […]

Bitcoin jak zacząć – gdzie inwestować w kryptowaluty: poradnik dla początkujących

Bitcoin (BTC) to dla Ciebie nowość i nie wiesz jak zacząć? To nic trudnego, nawet jeżeli dopiero zaczynasz interesować się…

Oszustwa telefoniczne Bitcoin - jak nie wpaść w sidła oszustów?

Otrzymałeś niedawno telefon od osoby twierdzącej, że masz szansę na szybką wypłatę znacznej kwoty z tytułu posiadanych Bitcoinów? Jeśli rozmówca sugeruje użycie programu typu AntyDesk lub prosi o przedpłatę na rzekomy podatek, w Twojej głowie powinien zapalić się alarm! To typowy przykład oszustwa telefonicznego związanego z Bitcoinem. Metoda ta zyskuje na popularności wśród przestępców. W […]

Xai - nowy projekt w Binance Launchpool

Giełda kryptowalut Binance ogłosiła kolejny projekt, który będzie dostępny na platformie Binance Launchpool. Tym razem jest to Xai. Między 5 stycznia a 8 stycznia o 23:59 użytkownicy będą mogli zarabiać tokeny Xai (XAI) na Binance po prostu stakując BNB, FDUSD lub TUSD. Postawione monety można wypłacić w dowolnym momencie, a nagrody w postaci tokenów XAI […]

Adresy Proof of Reserve największych giełd kryptowalut

Transparentność i bezpieczeństwo są kluczowymi aspektami w świecie krypto. Od upadku FTX jednym z elementów budujących zaufanie do giełd jest tzw. proof of reserve, czyli dowód posiadania rezerw. W tym artykule przyjrzymy się, czym dokładnie jest proof of reserve, dlaczego giełdy publikują taki dowód, oraz przedstawimy listę adresów proof of reserve największych giełd kryptowalut. Co […]

Co to jest BNB Vault? Jak korzystać z tej funkcji?

Binance to nie tylko giełda. To cały ekosystem produktów. Jednym z nich jest BNB Vault - agregator zysków, który pozwala zarabiać odsetki od posiadanych już kryptowalut. Funkcja ta umożliwia też w inwestowanie w ciekawe, nowe krypto projekty na wczesnym etapie poprzez Launchpool. W dzisiejszym artykule omówimy BNB Vault szczegółowo. Wyjaśnimy co to jest, jak działa […]

Kryptowaluty na Revolut - czy warto? Opinie

Revolut to bardzo popularna aplikacja neobankowa w Polsce, tak więc z całą pewnością obiła Ci się już o uszy. Aplikacja Revolut pozwala inwestować w kryptowaluty, ale nie jest to optymalne rozwiązanie jeżeli chodzi i ich zakup i sprzedaż, o czym wiedzą bardziej zaawansowani użytkownicy kryptowalut. Odpowiemy na pytanie czy opłaca się kupować kryptowaluty na Revolut, […]

Bitcoin jak zacząć – gdzie inwestować w kryptowaluty: poradnik dla początkujących

Bitcoin (BTC) to dla Ciebie nowość i nie wiesz jak zacząć? To nic trudnego, nawet jeżeli dopiero zaczynasz interesować się…

Binance Web3 Wallet - Czy warto korzystać?

8 listopada 2023 roku Binance wydała swój Web3 Wallet. Zapewnia on łatwy i bezpieczny dostęp do zdecentralizowanego świata technologii blockchain, pozwalając jednocześnie na zarządzanie aktywami Web3 bezpośrednio z poziomu Binance. W dzisiejszym artykule sprawdzimy co ma do zaoferowania Binance Web3 Wallet i czy warto z niego skorzystać. Najpierw jednak wyjaśnijmy co to jest portfel kryptowalut […]

Kraken - opinie użytkowników i recenzja giełdy (2024)

Kraken to giełda kryptowalut, która zjadła zęby na tym rynku. Istnieje bowiem od 2011 roku i od tego czasu nigdy nie padła ofiarą hakerów. Co więcej, stale się rozwija i wprowadza nowe usługi. Ale czym Kraken wyróżnia się na tle konkurencji? Jakie funkcje oferuje? Jakie ma opłaty i prowizje i co najważniejsze, jakie opinie o […]
0 0 Głosy
Oceń artykuł
Subscribe
Powiadom o
guest
0 komentarzy
Inline Feedbacks
View all comments
Kryptowaluty2.pl 2023 Wszelkie prawa zastrzeżone
starcrossmenuchevron-down
linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram