Przewodnik po drzewach Merkle

Czy słyszałeś o drzewach Merkle, kiedy omawialiśmy technologię blockchain? Dzieje się tak, ponieważ drzewo Merkle jest rdzeniem samej technologii. 

Więc co to właściwie jest?

W tym artykule szczegółowo omówimy drzewo Merkle i zrozumiemy jego rolę w zapewnianiu sukcesu technologii blockchain.

Zacznijmy.

 

Co to jest drzewo Merkle?

Drzewo Merkle to struktura danych używana do bezpiecznej weryfikacji danych w dużej puli zawartości. Jest również skuteczny i spójny w weryfikacji danych.

Ethereum i Bitcoin używają drzew Merkle.

Problem: U podstaw scentralizowanej sieci dostęp do danych można uzyskać z jednej kopii. Oznacza to, że nie muszą dużo robić, aby przechowywać dane lub uzyskiwać do nich dostęp. Jednak w przypadku zdecentralizowanej sieci blockchain sytuacja idzie na marne, ponieważ wszystkie dane są kopiowane między węzłami. Zatem skuteczny dostęp do danych jest wyzwaniem. Wyzwaniem jest również wykonanie kopii danych i udostępnienie ich między węzłami. Ponadto udostępnione dane muszą zostać zweryfikowane dla każdego z węzłów odbierających.

Rozwiązanie: Drzewa Merkle umożliwiają zdecentralizowanym łańcuchom bloków udostępnianie danych, weryfikowanie ich i zwiększanie ich wiarygodności. Porządkuje dane w taki sposób, że do udostępniania i weryfikacji danych nie potrzeba dużej mocy obliczeniowej. Ułatwia również bezpieczną transakcję dzięki zastosowaniu funkcji skrótu i ​​kryptografii.

Satoshi Nakamoto był pierwszą osobą, która wdrożyła drzewa Merkle w technologii blockchain za pośrednictwem Bitcoin. Jego użycie otworzyło nową gałąź informatyki, w której nie ma potrzeby scentralizowanej władzy. W nadmiernym stopniu używał również drzew Merkle i drzew Fast Merkle.

Jednak koncepcja została po raz pierwszy wprowadzona przez Ralpha Merkle, który opatentował ją w 1979 roku. Została nazwana jego imieniem.

Przeczytaj także, Hyperledger Cactus: A New Hyperledger Framework


Kryptograficzne funkcje skrótu

Zanim omówimy drzewa Merkle, musimy lepiej zrozumieć kryptograficzną funkcję skrótu.

Funkcja skrótu jest odpowiedzialna za mapowanie dowolnej formy dowolnych danych o dowolnej długości na dane wyjściowe o stałym rozmiarze. Jest to funkcja kryptograficzna i dlatego jest szeroko stosowana w kryptografii.

Funkcje skrótu są wydajne i znane ze swojej jednej właściwości, tj. Funkcji nie można cofnąć. Jest to funkcja jednokierunkowa, zaprojektowana do działania tylko w ten sposób. 

Haszowanie ma wiele zastosowań, w tym

  • Ochrona hasła
  • Sprawdzanie i weryfikacja integralności plików
  • Kryptowaluta

Istnieje wiele rodzin skrótów, w tym Message Direct (MD), Secure Hash Function (SHF) i RIPE Message Direct (RIPEMD).

Jeśli użyjesz algorytmu skrótu SHA256 i przekażesz 101Blockchains jako dane wejściowe, otrzymasz następujące dane wyjściowe

fbffd63a60374a31aa9811cbc80b577e23925a5874e86a17f712bab874f33ac9

Podsumowując, kluczowe właściwości funkcji skrótu obejmują:

  • Deterministyczne
  • Odporny na obraz wstępny
  • Wydajne obliczeniowo
  • Nie można odwrócić inżynierii
  • Odporny na kolizje

Jeśli chcesz dowiedzieć się więcej o kryptograficznych funkcjach skrótu, zapoznaj się ze szczegółowymi artykułami tutaj: 

Jak działają drzewa Merkle?

Teraz, gdy już dość dobrze rozumiemy funkcje skrótu, nadszedł czas, aby dowiedzieć się więcej o drzewach Merkle.

Z technicznego punktu widzenia drzewa Merkle to drzewa struktury danych, w których węzeł nie będący liściem jest zdefiniowany jako wartość skrótu odpowiednich węzłów podrzędnych.

Oznacza to również, że drzewo Merkle jest odwrócone w dół, gdzie węzły liści są najniższym węzłem. 

Aby lepiej zrozumieć, co próbuję przekazać, spójrzmy na przykład drzewa Merkle:

Źródło: Wikipedia

W rdzeniu drzew Merkle musimy nauczyć się trzech ważnych terminów. Są jak poniżej:

  • Merkle Root
  • Węzły liściowe
  • Węzły bez liści

Jeśli spojrzeć na całe drzewo Merkle, jest to drzewo odwrócone do góry nogami. Drzewo jest w stanie samo podsumować cały zestaw transakcji. Oznacza to, że użytkownik może zweryfikować, czy transakcja jest częścią bloku, czy nie.

Aby drzewa Merkle działały, używane jest haszowanie. Po prostu wielokrotnie haszuje pary węzłów, aż pozostanie tylko jedna wartość skrótu. Lewa wartość skrótu jest znana jako Merkle Root lub Root Hash. Drzewo jest tworzone od dołu do góry przy użyciu skrótów poszczególnych transakcji. Poszczególne skróty transakcji są również nazywane identyfikatorami transakcji. 

Węzły liści to węzły zawierające skróty danych transakcyjnych. W przypadku węzłów niebędących liśćmi przechowują one skrót dwóch poprzednich skrótów.

Inną ważną właściwością drzew Merkle jest ich binarny charakter. Oznacza to, że wymaga, aby węzły liści były równe, aby działało. W przypadku, gdy istnieje nieparzysta liczba węzłów liści, po prostu powieli ostatni hash i sprawi, że będzie parzysty.

 

Przykład

Spróbujmy to zrozumieć na przykładzie.

Przykład drzewa Merkle

Tutaj widzimy, że w bloku miały miejsce cztery transakcje. Te transakcje są nazywane X, Y, Z i W.Transakcje są następnie haszowane, a następnie przechowywane w węzłach liści, które nazywamy Hash X, Hash Y, Hash Z i Hash W..

Po zakończeniu węzły liści Hash X, Y, Z i W są ponownie haszowane i tworzone w połączonym skrócie XY i ZW. Wreszcie, te dwa skróty są używane do tworzenia Merkle Root lub Root Hash.

Cały proces haszowania można wykonać na bardzo dużym zbiorze danych, co sprawia, że ​​struktura danych Merkle Trees jest przydatna w przypadku zdecentralizowanych sieci.

Jak omówiliśmy wcześniej, użycie algorytmów haszowania zależy od implementacji. Jednak jedna z najczęściej używanych funkcji skrótu obejmuje kryptograficzną funkcję skrótu SHA-2. 

Tak więc transakcję można zweryfikować, czy poprzednie transakcje są weryfikowalne, dzięki wartościom skrótu.

 

A co z integralnością danych??

Drzewo Merkle jest idealne dla integralności danych. Nie ma też potrzeby przechodzenia przez całą transakcję, aby zobaczyć jej weryfikowalność. Transakcje można zweryfikować za pomocą informacji zapisanych w nagłówku bloku. Wartość korzenia Merkle również zmienia się w zależności od poprzednich transakcji.

Oznacza to również, że wartości główne są często zmieniane i mogą być używane do niemal natychmiastowego weryfikowania transakcji. 

Wszystko to może brzmieć trochę podobnie do listy skrótów, jednak nie jest to prawdą. Aby uzyskać listę skrótów, musisz pobrać pełną listę, aby zweryfikować transakcje lub dane.

W przypadku drzewa Merkle możesz pobrać gałąź, a następnie użyć jej do weryfikacji transakcji.

Nie ma potrzeby pobierania całego drzewa w celu weryfikacji transakcji. Oznacza to również, że całe drzewo można podzielić na małe bloki danych, które można wykorzystać do weryfikacji transakcji w całej sieci. Pojęcie to jest znane jako Dowody Merkle.

Możesz również sprawdzić python drzewa Merkle – implementację drzewa Merkle w Pythonie artykuł.

 

Jak działają drzewa Merkle w Bitcoinie

Bitcoin był pierwszą kryptowalutą, która skutecznie wykorzystywała drzewa Merkle. Aby upewnić się, że wartości skrótu są chronione i nie można ich łatwo odwrócić, wykorzystuje słynny algorytm bezpiecznego haszowania SHA-256. Oznacza to również, że wyjściowe wartości skrótu mają długość 256 bitów. Zasadniczo drzewa Merkle służą do przechowywania danych, a także do przycinania transakcji.

Przeczytaj także, jak zacząć korzystać z Blockchain

W bitcoinie każdy blok jest połączony z poprzednimi blokami za pomocą wartości skrótu. Tak powstaje cały blockchain. W bloku znajdują się nagłówki bloków, które zawierają ważne informacje, takie jak:

  • Merkle Root Hash
  • Numer wersji bloku
  • Znak czasu
  • Chwilowo
  • Docelowy poziom trudności wydobycia
  • Poprzedni Block Hash

Aby lepiej zrozumieć, spójrzmy na poniższy diagram. Jest pobierany z Oficjalny dokument dotyczący Bitcoin samo.

Podpis: Drzewa Merkle w Bitcoinie

Jak widać, wymaga to od górników uwzględnienia transakcji w bloku. Po zakończeniu jest haszowany i staje się częścią drzewa Merkle.

W ten sposób użycie drzew Merkle może przynieść wiele korzyści. Obejmuje to jedną godną uwagi korzyść, tj. Prostą weryfikację płatności (SPV). Te SVP to węzły, które można również określić jako lekkich klientów. Więc co oni robią? Po prostu pobierają najdłuższe nagłówki bloków łańcuchowych, dzięki czemu nie muszą pobierać całego łańcucha bloków. Aby to wszystko zrobić, muszą sprawdzić, czy ma zapisane nagłówki bloków dla najdłuższego łańcucha. W ten sposób implementacja drzewa Merkle odbywa się w bitcoinie.

Na koniec SPV może następnie skorzystać z Merkle Proof of Map i zweryfikować transakcję przy użyciu głównego skrótu drzewa Merkle. 

Jak drzewa Merkle są używane w Ethereum

Ethereum blockchain wykorzystuje również drzewa Merkle. Jednak podejście tutaj jest inne niż to, w jaki sposób wykorzystał go bitcoin. W Ethereum używane jest drzewo Merkle Patricia, które jest złożoną wersją drzewa Merkle. Jest to możliwe, ponieważ Ethereum jest kompletne w Turingu.

Jeśli chcesz dowiedzieć się więcej o tym, jak działają drzewa Merkle w Ethereum, zapoznaj się ze szczegółowym wpisem tutaj.

Inne implementacje drzew Merkle: przypadki użycia

Istnieją oczywiście inne implementacje drzew Merkle. Jednym z najpopularniejszych jest Git – rozproszony system kontroli wersji. Jest używany przez programistów z całego świata do zarządzania swoimi projektami. 

Inna przydatna implementacja jest widoczna w Międzyplanetarny system plików – rozproszony protokół peer-to-peer. Jest również open source i umożliwia urządzeniom komputerowym łączenie się z wszechobecnym systemem plików i korzystanie z niego.

Nawet urzędy certyfikacji wykorzystują drzewa Merkle na swoją korzyść. Wykorzystują to w mechanizmie do tworzenia weryfikowalnych dzienników przejrzystości certyfikatów. Ponieważ dziennik jest ogromny, drzewa Merkle umożliwiają komputerom jego weryfikację bez marnowania czasu i wysiłku.

Ostatnim przypadkiem użycia, który będziemy omawiać, są systemy baz danych, takie jak Amazon DynamoDB i Apache Cassandra. Te rozproszone bazy danych No-SQL przejmują kontrolę nad niespójnościami przy użyciu drzew Merkle podczas procesu replikacji danych. Jeśli wystąpią jakiekolwiek problemy, może zaktualizować lub naprawić dane za pomocą procesu naprawy antyentropii.

Krótko mówiąc, zastosowanie przypadków drzew Merkle obejmuje

  • Synchronizacja danych
  • Weryfikacja danych
  • Weryfikacja spójności

Zalety drzew Merkle

W tej sekcji przyjrzymy się szybko zaletom drzewa Merkle.

  • Sprawdź integralność danych: Można go skutecznie wykorzystać do weryfikacji integralności danych.
  • Zajmuje mało miejsca na dysku: Drzewo Merkle zajmuje mało miejsca na dysku w porównaniu z innymi strukturami danych.
  • Małe informacje w sieciach: Drzewa Merkle można podzielić na drobne informacje do weryfikacji.
  • Skuteczna weryfikacja: Struktura danych jest wydajna i weryfikacja integralności danych zajmuje tylko chwilę.

Wniosek

Drzewo Merkle jest jednym z ważnych pojęć w informatyce. Jest szeroko stosowany w wielu przypadkach użycia, a jego użycie w kryptowalutach dało początek rewolucyjnej technologii – blockchain.

Więc co wiesz o drzewach Merkle? Skomentuj poniżej i daj nam znać.

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me
Like this post? Please share to your friends:
Adblock
detector
map