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.
ź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ł.

ź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.

Podobne tematy

Ankr pozyskuje strategiczną inwestycję od Binance Labs

Ankr to znany dostawca infrastruktury Web3. W skrócie, protokół działa w tle, ale umożliwia korzystanie ze zdecentralizowanych aplikacji, portfeli, a także gier opartych na kryptowalutach, łącząc je z blockchainami, z którymi muszą się komunikować. Projekt znany jest z ciągłego wsparcia dla BNB Chain, wprowadzenia BNB Liquid Staking, a także zbudowania niektórych z jego podstawowych infrastruktur, […]

Kurs Ethereum (ETH) przetestował 1900 USD

Druga pod względem kapitalizacji kryptowaluta zyskała 12,8% w ciągu ostatnich 24 godzin, według CoinGecko. Ethereum osiągnęło lokalny szczyt na poziomie 1918 dolarów. W chwili pisania tego tekstu, aktywo jest notowane w okolicach 1895 dolarów. W ciągu ostatnich siedmiu dni cena eteru wzrosła o 17%, a w ciągu 30 dni o 72,8% (według CoinGecko). Wzrost kryptowaluty […]

RPA prezentuje usługę transferu bitcoinów za pomocą SMS

Deweloper Kgotatso Ngako uruchomił w RPA usługę Machankura SMS. Umożliwia on przelewy bitcoinów bez dostępu do internetu. Machankura users can now redeem @Azteco_ (and 1 For You) Bitcoin vouchers using the USSD interface. pic.twitter.com/qkPRwGzkrL — Machankura 8333 (@Machankura8333) August 10, 2022 Ngako wyjaśnił w wywiadzie dla Cointelegraph: Każdy […] może przejść od nieposiadania bitcoina do […]

Wieloryb ETH kupił 12,28 mld SHIB w jednej transakcji

Shiba Inu (SHIB) po raz kolejny przykuła uwagę zamożnych inwestorów ETH, ponieważ cena popularnej kryptowaluty o psiej tematyce zbliżyła się do krytycznego poziomu oporu zlokalizowanego przy $0.00001 USD na wykresie dziennym. Serwis WhaleStats poinformował, że 95. największy wieloryb ETH "BlueWhale0113" dodał do swojego konta 12,28 mld tokenów SHIB o wartości 72 mln dolarów w jednej […]

Mailchimp blokuje krypto firmy

Serwis Mailchimp ponownie usunął ze swojej platformy firmy zajmujące się kryptowalutami bez żadnego ostrzeżenia. Założona w 2018 roku usługa marketingowa i mailingowa zakazała organizacjom zajmującym się aktywami cyfrowymi wykorzystywania swojej platformy do kampanii reklamowych, powołując się na "ponadprzeciętną liczbę skarg na nadużycia". Po Blockworks, nagle usunięto portal Decrypt, mimo że wcześniej spełniał on wszystkie kryteria […]

Jak stworzyć własne NFT na giełdzie Binance?

NFT to nowy trend, który w 2021 roku zaczął rosnąć jak na drożdżach. Ten rodzaj tokenów pozwala bowiem artystom i nie tylko na spieniężanie swojej sztuki. I chociaż mogłoby się wydawać, że stworzenie NFT jest skomplikowanym technicznie zadaniem, wcale tak nie jest. Zwłaszcza kiedy posiłkujesz się funkcjami największej na świecie giełdy kryptowalut - Binance. W […]

Co to jest wskaźnik MVRV? Wszystko co musisz wiedzieć

Market Cap Versus Realized Cap (MVRV) to popularny wskaźnik on-chain, który pomaga zidentyfikować dołki i szczyty cen bitcoina. Wskaźnik MVRV jest przeznaczony do analizy długoterminowych trendów i cykli. Jest on wykorzystywany jako narzędzie do wykrywania dwóch głównych faz rynku - akumulacji i dystrybucji. MVRV opiera się na idei dwóch rodzajów uczestników rynku - spekulantów i […]

Co to jest wskaźnik Hash Ribbons? Wszystko co musisz wiedzieć

Hash Ribbons to wskaźnik przeznaczony do określania globalnego dna cenowego bitcoina. Metryka ocenia sentyment rynkowy i możliwość kapitulacji górników z powodu spadku ceny pierwotnej kryptowaluty lub wzrostu kosztów operacyjnych wydobycia. Hash Ribbons opiera się na założeniu, że górnicy są najbardziej odporni na zachwiania kursu i wrażliwi na ożywienie rynku. Kto opracował wskaźnik Hash Ribbons? Hash […]

Co to jest drzewo Merkle? Wszystko co musisz wiedzieć

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 […]

Co to jest Etherscan? Jak korzystać?

Etherscan to platforma przeglądania i analizy blockchaina Ethereum. Projekt został uruchomiony w 2015 roku przez zespół deweloperów z Malezji. Jest to niezależna organizacja, która nie jest finansowana przez Ethereum Foundation. Usługa ma za zadanie umożlwiać nawigację po publicznych danych sieci: śledzi transakcje i wyświetla wyniki jak wyszukiwarka. Platforma zawiera szczegóły dotyczące adresów, smart kontraktów, bloków, […]

Jak stworzyć własne NFT na giełdzie Binance?

NFT to nowy trend, który w 2021 roku zaczął rosnąć jak na drożdżach. Ten rodzaj tokenów pozwala bowiem artystom i nie tylko na spieniężanie swojej sztuki. I chociaż mogłoby się wydawać, że stworzenie NFT jest skomplikowanym technicznie zadaniem, wcale tak nie jest. Zwłaszcza kiedy posiłkujesz się funkcjami największej na świecie giełdy kryptowalut - Binance. W […]

Czym są blockchainowe wyrocznie? Wszystko co musisz wiedzieć

Wyrocznie blockchain to algorytmy, które służą jako przewodnik danych między inteligentnym kontraktem a źródłem spoza sieci, w której jest on wdrożony. Technologia wyroczni jest szeroko stosowana przez zdecentralizowane aplikacje, takie jak DeFi, GameFi, ubezpieczenia, NFT i inne. Największym dostawcą wyroczni blockchain jest Chainlink. W tym segmencie działają również projekty Band Protocol, Berry Data, Kylin Protocol, […]

Kim jest Sam Bankman-Fried (SBF)? Wszystko co musisz wiedzieć

Sam Bankman-Fried, znany również jako SBF, jest założycielem giełdy instrumentów pochodnych kryptowalut FTX i Alameda Research. Został uznany za jednego z 100 najlepszych influencerów TIME w 2022 roku. Jest również jednym z najbogatszych ludzi w branży blockchain i kryptowalut według Forbes. Sam Bankman-Fried posiada osobisty majątek o wartości około 24 miliardów dolarów. Jest również jedynym […]

Co to jest wskaźnik MVRV? Wszystko co musisz wiedzieć

Market Cap Versus Realized Cap (MVRV) to popularny wskaźnik on-chain, który pomaga zidentyfikować dołki i szczyty cen bitcoina. Wskaźnik MVRV jest przeznaczony do analizy długoterminowych trendów i cykli. Jest on wykorzystywany jako narzędzie do wykrywania dwóch głównych faz rynku - akumulacji i dystrybucji. MVRV opiera się na idei dwóch rodzajów uczestników rynku - spekulantów i […]

Co to jest wskaźnik Hash Ribbons? Wszystko co musisz wiedzieć

Hash Ribbons to wskaźnik przeznaczony do określania globalnego dna cenowego bitcoina. Metryka ocenia sentyment rynkowy i możliwość kapitulacji górników z powodu spadku ceny pierwotnej kryptowaluty lub wzrostu kosztów operacyjnych wydobycia. Hash Ribbons opiera się na założeniu, że górnicy są najbardziej odporni na zachwiania kursu i wrażliwi na ożywienie rynku. Kto opracował wskaźnik Hash Ribbons? Hash […]
0 0 Głosy
Oceń artykuł
guest
0 komentarzy
Inline Feedbacks
View all comments
Kryptowaluty2.pl 2020 Wszelkie prawa zastrzeżone
starcrossmenuchevron-downarrow-right
linkedin facebook pinterest youtube rss twitter instagram facebook-blank rss-blank linkedin-blank pinterest youtube twitter instagram