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:

Sieć Ethereum jest na minusie po raz pierwszy od roku

Pamiętacie "Merge"? Sieć Ethereum (ETH) dokonała przejścia z systemu proof of work na system proof of stake we wrześniu ubiegłego roku. Zamiast energochłonnych obliczeń, od tego czasu to stakerzy przetwarzają transakcje na Ethereum. Od momentu Merge sieć Ethereum co miesiąc odnotowuje zyski. Nie chodzi tu o wartość cenową, ale o przychody z samej sieci. Blockwork […]

Rocznica aktualizacji Ethereum Merge: wszystkie zmiany w skrócie

Dziś mija dokładnie rok, odkąd sieć Ethereum (ETH) dokonała przejścia z Proof-of-Work (PoW) na Proof-of-Stake (PoS). 15 września 2022 r. miała miejsce długo oczekiwana aktualizacja Merge, uważana przez wielu za najważniejsze wydarzenie w całej historii Ethereum. W tym artykule przyjrzymy się głównym zmianom i ich rezultatom, a także spojrzymy w przyszłość. Ethereum Merge: co się […]

Cena bitcoina jest nudna, ale dane nadal pokazują pozytywny obraz

Teraz, gdy cena bitcoina powróciła do poziomów z połowy czerwca, rynek ponownie zaczyna się zastanawiać, czy mamy do czynienia z hossą. Kurs spadł już o 16% od lokalnego szczytu z sierpnia ubiegłego roku, a od szczytu do dołka o ponad 20%. Mimo to, zgodnie z danymi on-chain, nie musimy się tak bardzo martwić. Bardzo niewiele […]

Jak zdobyć darmowe bitcoiny i kryptowaluty za rejestrację w 2023 roku?

Jeśli chcesz zacząć inwestować w bitcoin i kryptowaluty, najpierw musisz założyć konto na giełdzie i dokonać wpłaty walut fiat. Ale czy wiesz, że podczas rejestracji wiele platform oferuje darmowe bonusy? W dzisiejszym artykule omówimy 3 platformy, które oferują nowym użytkownikom darmowe kryptowaluty lub Bitcoin za rejestrację: Binance, Bybit i Bitget! Tak więc, zaczynajmy! Darmowe kryptowaluty […]

Kurs Bitcoina w tarapatach. Inflacja w USA wyższa niż oczekiwano

Indeks cen konsumpcyjnych (CPI) w Stanach Zjednoczonych wyniósł dziś 3,7%, podczas gdy oczekiwano wyniku na poziomie 3,6%. Oznaczałoby to już wzrost o 0,4% w porównaniu z lipcowym wynikiem 3,2%, ale inflacja spadła nawet bardziej niż początkowo oczekiwano. Dlaczego więc inflacja może nagle ponownie wzrosnąć i co to oznacza dla kursu bitcoina? Dlaczego inflacja może ponownie […]

Najlepsza aplikacja do kryptowalut na smartfona (Ranking 2023)

Rynek kryptowalut rozwija się w bardzo szybkim tempie. Wraz z rozwojem ekosystemu, budowane wokół niego jest wiele różnych produktów. Przykładem mogą być chociażby aplikacje do kryptowalut, które pozwalają nam na przechowywanie, handel, staking krypto oraz wiele innych opcji bezpośrednio z naszego samartfona. Ale jaka jest najlepsza aplikacja do kryptowalut? Sprawdzimy to w dzisiejszym poradniku! Aplikacje […]

Jak zdobyć darmowe bitcoiny i kryptowaluty za rejestrację w 2023 roku?

Jeśli chcesz zacząć inwestować w bitcoin i kryptowaluty, najpierw musisz założyć konto na giełdzie i dokonać wpłaty walut fiat. Ale czy wiesz, że podczas rejestracji wiele platform oferuje darmowe bonusy? W dzisiejszym artykule omówimy 3 platformy, które oferują nowym użytkownikom darmowe kryptowaluty lub Bitcoin za rejestrację: Binance, Bybit i Bitget! Tak więc, zaczynajmy! Darmowe kryptowaluty […]

Czym jest agregator DeFi i jak działa?

Świat DeFi jest pełen niesamowitych możliwości. Istnieją zdecentralizowane giełdy, różne protokoły pożyczkowe i oczywiście platformy oferujące różne formy dodatkowego zarobki z kryptowalut, czy to w formie stakingu, wydobywania płynności czy zaawansowanego yield farmingu. Wiele z nich jest zorientowanych na różne sieci, a ponieważ ich poziom wykorzystania jest dyktowany przede wszystkim przez społeczność. Różnią się one […]

Binance Coin (BNB)

Co to jest Binance Coin Binance Coin, znany również jako BNB, to kryptowaluta wyemitowana przez giełdę Binance. Jest to jedna z najpopularniejszych giełd kryptowalut na świecie. BNB początkowo opierał się na sieci Ethereum, ale z czasem przekształcił się w natywną walutę dedykowanego blockchaina Binance, zwanego Binance Chain. BNB został stworzony jako token umożliwiający korzystanie z […]

Czy warto kupić kartę graficzną po koparce kryptowalut?

Bbranża kryptowalut została dotknięta spadkiem Bitcoina, a następnie spadkiem Ethereum. To wszystko sprawiło, że wydobywanie GPU stało się nieopłacalne. W rezultacie rynek wtórny został zalany tanimi kartami graficznymi. Chociaż mogą one być o 50%, a nawet 70% tańsze niż w sklepach, należy dwa razy zastanowić się, czy warto kupować kartę graficzną po kopaniu kryptowalut. Praca […]

Najlepsza aplikacja do kryptowalut na smartfona (Ranking 2023)

Rynek kryptowalut rozwija się w bardzo szybkim tempie. Wraz z rozwojem ekosystemu, budowane wokół niego jest wiele różnych produktów. Przykładem mogą być chociażby aplikacje do kryptowalut, które pozwalają nam na przechowywanie, handel, staking krypto oraz wiele innych opcji bezpośrednio z naszego samartfona. Ale jaka jest najlepsza aplikacja do kryptowalut? Sprawdzimy to w dzisiejszym poradniku! Aplikacje […]

Jak zdobyć darmowe bitcoiny i kryptowaluty za rejestrację w 2023 roku?

Jeśli chcesz zacząć inwestować w bitcoin i kryptowaluty, najpierw musisz założyć konto na giełdzie i dokonać wpłaty walut fiat. Ale czy wiesz, że podczas rejestracji wiele platform oferuje darmowe bonusy? W dzisiejszym artykule omówimy 3 platformy, które oferują nowym użytkownikom darmowe kryptowaluty lub Bitcoin za rejestrację: Binance, Bybit i Bitget! Tak więc, zaczynajmy! Darmowe kryptowaluty […]

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. Pozwala ona także inwestować w kryptowaluty. Nie jest to jednak najlepsze rozwiązanie. Dużo taniej jest kupić cyfrowe aktywa na giełdzie, która pozwala w łatwy sposób wpłacić środki przez Revolut. Przykładem takiej platformy jest www.bybit.com lub www.binance.com. […]

Jak wypłacić Ethereum ze stakingu?

Na skutek aktywacji aktualizacji Shapella w sieci głównej Ethereum, użytkownicy otrzymali możliwość wycofania kryptowaluty ze stakingu. Ale jak to konkretnie zrobić? Czym jest staking Ethereum? Staking to sposób generowania pasywnego dochodu z monet w oparciu o algorytm konsensusu Proof-of-Stake (PoS) i jego warianty. Staking w prostym języku to udział w potwierdzaniu transakcji i produkcji nowych […]

Staking kryptowalut na Binance: Kompletny poradnik

W ciągu ostatnich kilku lat kryptowaluty naprawdę zawładnęły światem mainstreamu. NFT, giełdy kryptowalutowe i cały szereg różnych narzędzi związanych z kryptowalutami powstają jak grzyby po deszczu! W dzisiejszym poradniku skupimy się jednak na jednej z najciekawszych koncepcji, a mianowicie stakingu na giełdzie Binance. Jest to bowiem proces, który pozwala zarabiać kryptowaluty w sposób pasywny! Staking […]
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