Drzewo Merkle

Co to jest drzewo Merkle?

Drzewo Merkle to struktura danych używana w aplikacjach informatycznych. W bitcoinach i innych kryptowalutach drzewa Merkle służą do kodowania danych łańcucha blokowego wydajniej i bezpieczniej.

Nazywa się je również „binarnymi drzewami mieszania”.

Rozbijanie drzewa Merkle

W łańcuchu bloków Bitcoin blok transakcji jest przeprowadzany przez algorytm w celu wygenerowania skrótu, który jest ciągiem cyfr i liter, które można wykorzystać do sprawdzenia, czy dany zestaw danych jest taki sam jak oryginalny zestaw transakcji, ale nie uzyskać oryginalnego zestawu transakcji. Oprogramowanie Bitcoin nie obsługuje jednak całego bloku danych transakcyjnych – reprezentujących średnio 10 minut transakcji – za pośrednictwem funkcji skrótu jednocześnie. Zamiast tego każda transakcja jest haszowana, a następnie każda para transakcji jest łączona i mieszana razem, i tak dalej, aż do uzyskania jednego skrótu dla całego bloku. (Jeśli istnieje nieparzysta liczba transakcji, jedna transakcja jest podwajana, a jej skrót jest łączony ze sobą).

Wizualizowana struktura przypomina drzewo. Na poniższym diagramie „T” oznacza transakcję, a „H” skrót. Zwróć uwagę, że obraz jest bardzo uproszczony; przeciętny blok zawiera ponad 500 transakcji, a nie osiem.

Skróty w dolnym rzędzie nazywane są „liśćmi”, skróty pośrednie jako „gałęzie”, a skrót na górze jako „korzeń”. Katalog główny Merkle danego bloku jest przechowywany w nagłówku: na przykład katalog główny Merkle bloku nr 482819 to e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f71c8. Korzeń jest łączony z innymi informacjami (wersja oprogramowania, hash poprzedniego bloku, sygnatura czasowa, docelowa trudność i numer jednorazowy), a następnie przechodzi przez funkcję skrótu w celu utworzenia unikatowego skrótu bloku: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1b5c3c33c2b0895. Ten hash nie jest faktycznie zawarty w odpowiednim bloku, ale w następnym; różni się od korzenia Merkle.

Drzewo Merkle jest przydatne, ponieważ pozwala użytkownikom zweryfikować konkretną transakcję bez pobierania całego łańcucha blokowego (ponad 130 gigabajtów na koniec sierpnia 2017). Na przykład załóżmy, że chcesz sprawdzić, czy transakcja T D  jest zawarta w bloku na powyższym schemacie. Jeśli masz główny hash (H ABCDEFGH ), proces jest jak gra w sudoku: pytasz sieć o H D i zwraca H C, H AB i H EFGH. Drzewo Merkle pozwala sprawdzić, czy wszystko jest rozliczane za pomocą trzech skrótów: dane H AB, H C, H EFGH i korzeń H ABCDEFGH, H D  (jedyny brakujący hash) muszą być obecne w danych.

Drzewa Merkle zostały nazwane na cześć Ralpha Merkle’a, który zaproponował je w artykule z 1987 roku zatytułowanym „ Podpis cyfrowy oparty na konwencjonalnej funkcji szyfrowania ”. Merkle wynalazł również haszowanie kryptograficzne.