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.

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:

FTX uruchamia stronę internetową, aby spłacić europejskich klientów

FTX EU, europejska filia upadłej giełdy kryptowalutowej FTX, uruchomiła stronę internetową, aby spłacić wściekłych, europejskich klientów. Firma złożyła wniosek o upadłość prawie pięć miesięcy temu, powodując efekt domina innych upadających firm kryptowalutowych. W rzeczywistości FTX stał się tak duży, że wiele innych firm zaparkowało swoje pieniądze w tej giełdzie i w rezultacie zostało "zainfekowanych". Użytkownicy […]

Argentyńskie linie lotnicze Flybondi zaczynają wydawać bilety NFT

Argentyński tani przewoźnik Flybondi rozpoczął kampanię Ticket 3.0, w której zaczął wydawać bilety w formie niewymienialnych tokenów (NFT). Linia lotnicza powiedziała, że ta metoda "oferuje bardziej elastyczne doświadczenie podróży". Z kolei Flybondi będzie w stanie zmniejszyć koszty obsługi klienta i zwiększyć przychody dzięki prowizjom handlowym. Usługa ta stała się możliwa dzięki partnerstwu z TravelX, opartą […]

Rosja chce mieć własną walutę z Brazylią, Indiami, Chinami i RPA

Krążą pogłoski, że kraje BRICS chcą stworzyć własną walutę, aby ułatwić płatności między uczestniczącymi państwami. To może być ciężki cios dla dolara i może stwarzać możliwości dla Bitcoina. BRICS są wpływowe BRICS to skrót od krajów Brazylia, Rosja, Indie, Chiny i RPA. Kraje te mają znaczący wpływ na globalną gospodarkę ze względu na ich duże […]

Bitcoin może mocno wystrzelić w górę w 2024 roku z powodu halvingu i recesji

Mike McGlone twierdzi, że Bitcoin może mocno wystrzelić w górę w 2024 roku, a następnie nadejdzie halving i seria innych fundamentalnych wydarzeń. Analityk Bloomberga wyraził swoje prognozy podczas wywiadu ze Scottem Melkerem. Bitcoin i efekt halvingu Zanim zanurkujemy dalej w jego przewidywania, szybkie słowo na temat tego tak zwanego halvingu. Co cztery lata liczba nowo […]

Tim Draper radzi przedsiębiorcom, by kupowali Bitcoina

Amerykański miliarder i legenda inwestycji Tim Draper radzi przedsiębiorcom, aby kupili Bitcoin. Według niego jest to sposób na zabezpieczenie się przed potencjalnym kryzysem bankowym. Nawiasem mówiąc, Tim Draper nie jest osobą nową w świecie Bitcoina, ponieważ już w czerwcu 2014 roku kupił od rządu USA 30 000 Bitcoinów za 19 milionów dolarów. Te Bitcoiny zostały […]

WalletConnect - Co to jest i jak używać?

Jeśli masz jakiekolwiek doświadczenie z DeFi, być może napotkałeś już problem z połączeniem się z jedną ze zdecentralizowanych aplikacji. Portfele kryptowalutowe są bowiem bardzo liczne, podobnie jak aplikacje DeFi. Choć wiele z nich, czy to aplikacje, czy portfele, działa na tych samych sieciach, to jednak istnieją między nimi pewne różnice. Dlatego nawet najbardziej znane i […]

W jakie kryptowaluty inwestować? Nowe kryptowaluty 2023

Tematem naszego dzisiejszego przeglądu będą nowe kryptowaluty 2023. Jeśli myślisz, że krypto zima hamuje powstawanie nowych projektów to jesteś w błędzie. Na przykład Grin i Beam zostały uruchomione na początku 2019 roku. Wówczas to nie tylko sceptycy, ale wielu entuzjastów kryptowalut myślało, że to już koniec. Inwestor powinien zawsze przeprowadzić własny research. Ci, którzy zainwestują […]

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

Dlaczego warto sprzedawać NFT na Binance NFT? Oto powody

NFT niezwykle szybko zyskują na popularności, rozszerzając możliwości blockchaina. Użytkownicy mogą teraz kupować i sprzedawać prawie wszystko w formie NFT. Dotyczy to głównie cyfrowych dzieł sztuki, pamiątek, aktywów w grze, a nawet niektórych momentów historycznych. Zazwyczaj NFT określa się jako rodzaj kryptograficznego tokena na blockchainie, który reprezentuje unikalne aktywa. Mogą one być albo całkowicie cyfrowymi […]

Jak wysyłać pieniądze za granicę za darmo przy użyciu kryptowalut?

Wysyłanie pieniędzy za granicę może być drogim i czasochłonnym procesem. W tym przewodniku wyjaśnimy jednak, jak wykorzystać kryptowaluty do wysyłania pieniędzy za granicę za darmo - przy pomocy platformy Binance P2P. Tradycyjne metody, takie jak przelewy lub Western Union, często wiążą się z wysokimi opłatami i powolnym czasem przetwarzania, co utrudnia ludziom wysyłanie pieniędzy szybko […]

BNB Greenfield: Czym jest nowy, trzeci blockchain od Binance?

Giełda Binance w lutym zapowiedziała swój nowy produkt, a mianowicie nowy blockchain nazwany BNB Greenfield. W dzisiejszym artykule wyjaśniamy czym dokładnie on jest, jak będzie działał, jakie może mieć zastosowania oraz wiele więcej! Tak więc, zaczynajmy! Czym jest BNB Greenfield? BNB Greenfield to zdecentralizowana infrastruktura pamięci masowej w ramach szerszego ekosystemu BNB Chain, w którym […]

Testnet ZetaLabs: Jak przygotować się pod airdrop?

Testnety to zawsze okazja do zarobienia dodatkowych pieniędzy. Jakich? To zależy od projektu i jego możliwości. W tym poradniku opowiemy o ZetaChain - projekcie, który obecnie prowadzi testnet. Wyjaśnimy co musisz zrobić, aby zdobyć ewentualne dropy i darmowe NFT. Czym jest ZetaChain? ZetaChain to testnet dla nowych omnichain dApps i kluczowy element ekosystemu, który opiera […]

Zarabianie na NFT w 2023 roku: gdzie inwestować i gdzie szukać obiecujących kolekcji?

Pozytywny impet na początku 2023 roku ożywił rynek kryptowalut, co pomogło projektom odzyskać siły po ubiegłorocznych wpadkach i bankructwach. Segment NFT nie był wyjątkiem. Również przyciągnął uwagę wielu nowych graczy. Jednak NFT mają swoją własną specyfikę i nawet doświadczeni inwestorzy nie do końca rozumieją cechy tego rynku. W dzisiejszym artykule wyjaśnimy ci jak ma się […]
0 0 Głosy
Oceń artykuł
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