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

Złe wiadomości dla bitcoina? Dolar może ponownie wzrosnąć

Dolar amerykański (USD) przeszedł w ostatnich tygodniach sporą korektę. Światowa waluta rezerwowa spadła o około 8% w stosunku do euro. Tymczasem jednak wojna na Ukrainie wciąż się nie skończyła, globalna sytuacja gospodarcza jest fatalna, a w krainie kryptowalut panuje spora niepewność po problemach FTX. Również dolar zaczął dziś ponownie rosnąć w stosunku do euro. Dla […]

Liczba osób korzystających z kryptowalut wzrosła w 2022 roku o 37,8%

Według danych Datareportal, liczba osób posiadających jakąś formę kryptowalut wzrosła w tym roku o 37,8%. Jeden na 10 internautów w wieku od 16 do 64 lat posiada obecnie cyfrowe aktywa. Kryptowaluty w krajach rozwijających się Posiadanie kryptowalut jest popularne głównie w krajach rozwijających się. Zwłaszcza w tym, gdzie waluta jest bardziej wrażliwa na duże wahania […]

Grayscale nie chce przedstawiać swoich rezerw

Przemysł kryptowalutowy został zbudowany w oparciu o jeden slogan: "nie ufaj, zweryfikuj". Ale Grayscale różni się od reszty firm związanych z kryptowalutami. W niedawnym wątku na Twitterze zastanawiającym się nad potrzebą przejrzystości w branży po upadku FTX, Grayscale próbował uspokoić obawy swoich inwestorów, zapewniając ich, że regulacje, które mają zastosowanie do różnych podmiotów, sprawiają, iż […]

Tether zapewnia, że nie ma ryzyka ze strony USDT na Solanie

Największy na świecie emitent stablecoinów, Tether, zapewnił, że nie ma żadnych zagrożeń ze strony USDT w sieci Solana. 18 listopada Tether wydał oświadczenie, że USDT emitowany w Alamedzie był bezpieczny względem wszelkich wypadków zarażenia ze strony upadłej giełdy FTX. Według raportu przejrzystości Tethera, Solana jest trzecią co do wielkości siecią dla stablecoina po Tron i […]

Sam Bankman-Fried komentuje upadek FTX

Założyciel FTX i były CEO Sam Beckman-Fried skomentował upadek swojej firmy podczas wywiadu dla The New York Times. Jak twierdzi przedsiębiorca, ciężko pracował nad rozwojem biznesu i nie zwracał uwagi na pierwsze sygnały o fundamentalnych problemach na giełdzie. Kierownik podkreślił, że powinien był bardziej wszechstronnie i wnikliwie ocenić sytuację. W piątek platforma złożyła formalny wniosek […]

Co to jest automatyczny animator rynku (AMM)?

Automated Market Maker (AMM) to algorytm oprogramowania do kontrolowania płynności i wyceny kryptowalut na zdecentralizowanych giełdach. Systemy AMM są szeroko stosowane w DeFi, szczególnie w zdecentralizowanych giełdach (DEX), takich jak w tym Uniswap, Balancer, Bancor i Curve. Aby stworzyć zdecentralizowane rynki, AMM wykorzystuje płynność w kryptowalutowych publicznych pulach wielu tokenów zablokowanych w specjalnych inteligentnych kontraktach. […]

Co to są BTokeny i jak je pożyczać na Binance?

Binance to nie tylko giełda kryptowalut. To cały ekosystem, na który składa się wiele różnych produktów. Jednym z nich jest BNB Chain, czyli blockchain Binance. Na jego potrzeby giełda ta zaczęła "opakowywać" swoje tokeny. Tak jak np. na Ethereum możemy przechowywać Bitcoina w formie WBTC, tak w przypadku BNB Chain również możemy posiadać tzw. BTokeny. […]

Co to jest Binance Swap Farming i jak z niego korzystać?

Jeżeli korzystasz z giełdy Binance z całą pewnością wiesz, że nie jest to jedynie klasyczna giełda. Jest to cały ekosystem złożony z wielu różnych ciekawych produktów. Jednym z nich jest Binance Swap Farming i to na nim skupimy się w tym poradniku. Wyjaśnimy czym on dokładnie jest, jak działa, jakie ma zalety oraz ryzyko oraz […]

Co to jest Hashflow (HFT)? Nowy projekt na Binance Launchpool

Dziś porozmawiamy o nowym projekcie, który pojawił się na platformie Binance Launchpool, a mianowicie Hashflow (HFT). Ma on na celu poprawę efektywności działania automatycznych animatorów rynku w sektorze DeFi. Bez usług AMM usługi zdecentralizowanych finansów po prostu nie byłyby możliwe. To właśnie one były katalizatorem ostatniej hossy, ale wciąż są dalekie od ideału. DeFi miało […]

Kryptowaluta Aptos (APT): kolejna generacja platform blockchain?

Aptos to platforma blockchain oparta na algorytmie konsensusu AptosBFT. Aptos do tworzenia smart kontraktów używa unikalnego języka programowania o nazwie Move. Projekt został założony przez byłych pracowników Diem (dawniej Libra) - blockchaina firmy Meta Corporation, który został zakończony na początku 2022 roku. Konkretnie, Move został pierwotnie opracowany dla Diem. Według twórców, zastosowanie technologii równoległego wykonywania […]

Giełda kryptowalut bez weryfikacji

W poniższej instrukcji znajdziesz informacje o tym jak przyśpieszyć transakcje handlu bitcoina lub innej kryptowaluty z wykorzystaniem giełd kryptowalut i…

Co to jest automatyczny animator rynku (AMM)?

Automated Market Maker (AMM) to algorytm oprogramowania do kontrolowania płynności i wyceny kryptowalut na zdecentralizowanych giełdach. Systemy AMM są szeroko stosowane w DeFi, szczególnie w zdecentralizowanych giełdach (DEX), takich jak w tym Uniswap, Balancer, Bancor i Curve. Aby stworzyć zdecentralizowane rynki, AMM wykorzystuje płynność w kryptowalutowych publicznych pulach wielu tokenów zablokowanych w specjalnych inteligentnych kontraktach. […]

Co to są BTokeny i jak je pożyczać na Binance?

Binance to nie tylko giełda kryptowalut. To cały ekosystem, na który składa się wiele różnych produktów. Jednym z nich jest BNB Chain, czyli blockchain Binance. Na jego potrzeby giełda ta zaczęła "opakowywać" swoje tokeny. Tak jak np. na Ethereum możemy przechowywać Bitcoina w formie WBTC, tak w przypadku BNB Chain również możemy posiadać tzw. BTokeny. […]

Binance Simple Earn - czyli połączenie Binance Savings i Staking!

Giełda Binance od niemal początku swojego istnienia oferowała inwestorom funkcje Stakingu oraz Oszczędności. Niemniej jednak teraz postanowiła połączyć oba te produkty w jeden, nazwany Binance Simple Earn. Jak sama nazwa wskazuje pozwala on w łatwy sposób zarabiać na posiadanych już kryptowalutach. W tym artykule wyjaśnimy dokładniej czym jest ta funkcja i jak jej używać. Tak […]

Co to jest Binance Swap Farming i jak z niego korzystać?

Jeżeli korzystasz z giełdy Binance z całą pewnością wiesz, że nie jest to jedynie klasyczna giełda. Jest to cały ekosystem złożony z wielu różnych ciekawych produktów. Jednym z nich jest Binance Swap Farming i to na nim skupimy się w tym poradniku. Wyjaśnimy czym on dokładnie jest, jak działa, jakie ma zalety oraz ryzyko oraz […]
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