Co to jest drzewo Merkle'a? Przewodnik dla początkujących po tym komponencie Blockchain

Drzewa Merkle są podstawowym składnikiem łańcuchów bloków, który leży u podstaw ich funkcjonalności. Pozwalają na skuteczną i bezpieczną weryfikację dużych struktur danych, a w przypadku blockchainów potencjalnie nieograniczonych zbiorów danych.

Implementacja drzew Merkle w blockchainach ma wiele skutków. Umożliwia im skalowanie, zapewniając jednocześnie architekturę opartą na skrótach, która pozwala zachować integralność danych i prosty sposób weryfikacji integralności danych.

Kryptograficzne funkcje mieszające to podstawowa technologia umożliwiająca działanie drzew Merkle, dlatego najpierw ważne jest, aby zrozumieć, czym są kryptograficzne funkcje mieszające.

Szybki werdykt: Drzewa Merkle to struktury danych złożone z kryptograficznych skrótów, które umożliwiają skuteczną weryfikację integralności i mapowanie dużych zbiorów danych, co czyni je integralnym elementem systemów takich jak łańcuchy bloków i rozproszona kontrola wersji.

Szybkie fakty

Kryptograficzne funkcje skrótu

Mówiąc najprościej, funkcja skrótu to dowolna funkcja używana do mapowania danych o dowolnym rozmiarze (wejściowych) na dane wyjściowe o stałym rozmiarze. Do danych wejściowych stosowany jest algorytm mieszający, a wynikowy wynik o stałej długości nazywany jest skrótem.

Wiele algorytmów mieszających jest powszechnie dostępnych i można je wybierać w zależności od potrzeb.

Wynikowy skrót z dowolnego wejścia ma nie tylko stałą długość, ale jest także całkowicie unikalny dla danych wejściowych, a sama funkcja jest deterministyczna. Oznacza to, że niezależnie od tego, ile razy uruchomisz funkcję na tym samym wejściu, wynik będzie zawsze taki sam.

Na przykład, jeśli jako dane wejściowe masz poniższe zestawy danych, wynikowe dane wyjściowe są unikalne dla każdego wejścia. Zwróć uwagę, że w drugim i trzecim przykładzie, mimo że różnica między danymi wejściowymi wynosi tylko jedno słowo, wynikowe wyniki są zupełnie inne.

Jest to bardzo ważne, gdyż pozwala na „odcisk palca” danych.

Kryptograficzna funkcja skrótu. Obraz z Wikipedii

Ponieważ długość danych wyjściowych (w przykładzie suma skrótu) jest zawsze taka sama, jak określona przez zastosowany algorytm mieszający, ogromne ilości danych można zidentyfikować wyłącznie na podstawie powstałego skrótu.

W przypadku systemów zawierających ogromne ilości danych korzyści wynikające z możliwości przechowywania i identyfikowania danych o stałej długości mogą zapewnić ogromne oszczędności w zakresie pamięci masowej i pomóc w zwiększeniu wydajności.

W łańcuchach bloków algorytmy mieszające służą do określenia stanu łańcucha bloków.

Blockchainy to połączone listy zawierające dane i wskaźnik skrótu wskazujący na poprzedni blok, tworząc łańcuch połączonych bloków, stąd nazwa „blockchain”.

Każdy blok jest połączony ze sobą za pomocą wskaźnika mieszającego, który jest skrótem danych znajdujących się w poprzednim bloku wraz z adresem poprzedniego bloku. Łącząc bloki danych w tym formacie, każdy wynikowy skrót poprzedniego bloku reprezentuje cały stan łańcucha bloków, ponieważ wszystkie zaszyfrowane dane z poprzednich bloków są mieszane w jeden skrót.

Jest to reprezentowane (w przypadku algorytmu SHA-256) przez wynik (hasz), taki jak ten:

b09a57d476ea01c7f91756adff1d560e579057ac99a28d3f30e259b30ecc9dc7

Powyższy skrót jest odciskiem palca całego stanu łańcucha bloków przed nim. Stan łańcucha bloków przed nowym blokiem (jako dane zahaszowane) stanowi dane wejściowe, a wynikowy skrót stanowi dane wyjściowe.

Chociaż możliwe jest użycie skrótów kryptograficznych bez drzew Merkle, jest to niezwykle nieefektywne i nieskalowalne. Używanie skrótów do przechowywania danych w bloku w formacie szeregowym jest czasochłonne i kłopotliwe.

Jak zobaczysz, drzewa Merkle pozwalają na proste rozpoznawanie integralności danych, a także mapowanie tych danych w całym drzewie za pomocą dowodów Merkle'a.

Drzewa Merkle i dowody Merkle

Nazwane na cześć Ralpha Merkle'a, który opatentował tę koncepcję w 1979 r., drzewa Merkle są zasadniczo drzewami struktur danych, w których każdy węzeł inny niż liść jest skrótem odpowiednich węzłów podrzędnych.

Węzły liściowe to najniższy poziom węzłów w drzewie. Na początku może się to wydawać trudne do zrozumienia, ale jeśli spojrzysz na powszechnie używany rysunek poniżej, stanie się to znacznie łatwiejsze do zrozumienia.

Przykład binarnego drzewa skrótów, obraz z Wikipedii

Co ważne, zwróć uwagę, że węzły lub „gałęzie” inne niż liście (reprezentowane przez Hash 0-0 i Hash 0-1) po lewej stronie są skrótami ich odpowiednich dzieci L1 i L2. Ponadto zwróć uwagę, jak gałąź Hash 0 jest skrótem jej połączonych dzieci, gałęzi Hash 0-0 i Hash 0-1.

Powyższy przykład jest najczęstszą i najprostszą formą drzewa Merkle, znanego jako binarne drzewo Merkle. Jak widać, istnieje najwyższy hash, będący hashem całego drzewa, znany jako hash root. Zasadniczo drzewa Merkle to struktura danych, która może przyjmować „n” liczbę skrótów i reprezentować je za pomocą jednego skrótu.

Struktura drzewa pozwala na efektywne mapowanie dowolnie dużych ilości danych i umożliwia łatwą identyfikację miejsca, w którym zachodzą zmiany w tych danych. Koncepcja ta umożliwia przeprowadzenie dowodów Merkle’a, dzięki którym można sprawdzić, czy hashowanie danych jest spójne na całej długości drzewa i we właściwej pozycji, bez konieczności patrzenia na cały zestaw skrótów.

Zamiast tego mogą sprawdzić, czy fragment danych jest spójny ze skrótem głównym, sprawdzając tylko niewielki podzbiór skrótów, a nie cały zestaw danych.

Dopóki skrót główny jest publicznie znany i godny zaufania, każdy, kto chce przeprowadzić wyszukiwanie w bazie danych pary klucz-wartość, może skorzystać z dowodu Merkle w celu sprawdzenia pozycji i integralności fragmentu danych w bazie danych, która ma konkretny korzeń.

Gdy dostępny jest skrót główny, drzewo skrótów można pobrać z dowolnego niezaufanego źródła i pobrać jedną gałąź drzewa na raz z natychmiastową weryfikacją integralności danych, nawet jeśli całe drzewo nie jest jeszcze dostępne.

Jedną z najważniejszych zalet struktury drzewa Merkle jest możliwość uwierzytelniania dowolnie dużych zbiorów danych poprzez podobny mechanizm mieszający, który służy do weryfikacji znacznie mniejszych ilości danych.

Drzewo jest korzystne w przypadku dystrybucji dużych zestawów danych na mniejsze części, którymi można zarządzać, gdzie bariera weryfikacyjna integralności jest znacznie zmniejszona pomimo ogólnego większego rozmiaru danych.

Skrót główny może służyć jako odcisk palca dla całego zestawu danych, w tym całej bazy danych lub reprezentujący cały stan łańcucha bloków. W kolejnych sekcjach omówimy, w jaki sposób Bitcoin i inne systemy wdrażają drzewa Merkle.

Drzewa Merkle w Bitcoinie

Kryptograficzna funkcja skrótu wykorzystywana przez Bitcoin to algorytm SHA-256. Oznacza to „Secure Hashing Algorithm”, którego dane wyjściowe mają stałą długość 256 bitów. Podstawową funkcją drzew Merkle w Bitcoinie jest przechowywanie i ostatecznie przycinanie transakcji w każdym bloku.

Jak wspomniano wcześniej, bloki w łańcuchu bloków są połączone poprzez skróty poprzedniego bloku. W Bitcoin każdy blok zawiera wszystkie transakcje w tym bloku, a także nagłówek bloku, który składa się z:

• Zablokuj numer wersji
• Poprzedni blok hasz
• Sygnatura czasu
• Cel trudności wydobycia
• Chwilowo
• Hash korzeniowy Merkle

Poniższy obraz pochodzi z białej księgi Bitcoin i ilustruje, jak drzewo Merkle pasuje do każdego bloku.

Transakcje są grupowane przez górników w bloki i szyfrowane jako część drzewa Merkle, co prowadzi do korzenia Merkle przechowywanego w nagłówku bloku. Ten projekt ma wiele wyraźnych zalet.

Przede wszystkim, jak opisano w dokumencie, pozwala to na istnienie węzłów prostej weryfikacji płatności (SPV), zwanych także „klientami lekkimi”. Węzły te nie muszą pobierać całego łańcucha bloków Bitcoin, jedynie nagłówki bloków najdłuższego łańcucha.

Węzły SPV mogą to osiągnąć, wysyłając zapytania do swoich węzłów równorzędnych, dopóki nie zostaną przekonane, że przechowywane nagłówki bloków, na których działają, stanowią część najdłuższego łańcucha. Węzeł SPV może następnie określić status transakcji, korzystając z dowodu Merkle, aby zmapować transakcję na określone drzewo Merkle za pomocą skrótu głównego tego odpowiedniego drzewa Merkle w nagłówku bloku, który jest częścią najdłuższego łańcucha.

Dodatkowo, implementacja drzew Merkle w Bitcoinie pozwala na przycięcie łańcucha bloków w celu zaoszczędzenia miejsca. Dzieje się tak dlatego, że w nagłówku bloku przechowywany jest tylko skrót główny, dlatego stare bloki można wyczyścić, usuwając niepotrzebne gałęzie drzewa Merkle, zachowując jedynie te potrzebne do dowodu Merkle.

Implementacja drzew Merkle w innych blockchainach i systemach

Chociaż Bitcoin był pierwszym łańcuchem bloków, który zaimplementował drzewa Merkle, wiele innych łańcuchów bloków implementuje podobne struktury drzewa Merkle lub nawet bardziej złożone wersje.

Co więcej, implementacja drzewa Merkle nie ogranicza się tylko do łańcuchów bloków i jest stosowana w wielu innych systemach.

Ethereum, będąc drugą najbardziej rozpoznawalną kryptowalutą, jest także doskonałym przykładem innej implementacji drzewa Merkle. Ponieważ Ethereum jest kompletną platformą do budowania znacznie bardziej złożonych aplikacji, wykorzystuje bardziej złożoną wersję drzewa Merkle zwaną drzewem Merkle Patricia, które w rzeczywistości składa się z 3 oddzielnych drzew Merkle używanych do trzech rodzajów obiektów. Więcej o tych drzewach można dowiedzieć się tutaj.

Wreszcie drzewa Merkle są ważnym składnikiem rozproszonych systemów kontroli wersji, takich jak Git i IPFS. Ich zdolność do łatwego zapewnienia i sprawdzenia integralności danych udostępnianych pomiędzy komputerami w formacie P2P sprawia, że ​​są one nieocenione dla tych systemów.

Wnioski

Drzewa Merkle są integralnym składnikiem łańcuchów bloków i skutecznie umożliwiają im funkcjonowanie z możliwą do udowodnienia niezmiennością i integralnością transakcji.

Zrozumienie roli, jaką odgrywają w sieciach rozproszonych oraz leżącej u ich podstaw technologii kryptograficznych funkcji skrótu, ma kluczowe znaczenie dla zrozumienia podstawowych koncepcji kryptowalut w miarę ich dalszego rozwoju w większe i bardziej złożone systemy.