Drzewa Merkle’a: integralność transakcji na dużą skalę

Blok Bitcoina zawiera około 2000 transakcji. Aby udowodnić, że transakcja T jest w nim zawarta, bez pobierania wszystkich 2000 transakcji, potrzebujemy zwięzłego dowodu. Drzewa Merkle'a rozwiązują ten problem: rozmiar dowodu wynosi O(log n) skrótów zamiast O(n) transakcji.

Liście: SHA256d (podwójny SHA-256) każdej transakcji. Węzeł nadrzędny: SHA256d(left_child_hash || right_child_hash). Powtarzaj aż do uzyskania jednego skrótu korzenia. Jeśli liczba węzłów jest nieparzysta, zduplikuj ostatni węzeł. Korzeń Merkle'a jest przechowywany w nagłówku bloku (32 bajty).

import hashlib def sha256d(x): return hashlib.sha256(hashlib.sha256(x).digest()).digest() def merkle_root(txids): if len(txids)%2: txids.append(txids[-1]) while len(txids)>1: txids=[sha256d(txids[i]+txids[i+1]) for i in range(0,len(txids),2)] return txids[0].hex()

Aby udowodnić, że transakcja T znajduje się na pozycji i, należy podać skróty rodzeństwa na każdym poziomie — od liścia T do korzenia (O(log n) skrótów). Weryfikator ponownie oblicza korzeń na podstawie T i ścieżki skrótów rodzeństwa. Jeśli obliczony korzeń jest zgodny z korzeniem Merkle'a w nagłówku bloku, zawarcie T zostaje udowodnione.

1024 transakcje → dowód Merkle'a = 10 skrótów = 320 bajtów. Pełny blok = około 1 MB. Klienci SPV pobierają tylko 80-bajtowy nagłówek i 320-bajtowy dowód Merkle'a dla każdej interesującej ich transakcji — oszczędność przepustowości wynosi 99,97% w porównaniu z pobraniem całego bloku.

Jeśli zmieni się dowolna transakcja w drzewie, zmieni się skrót jej liścia, a zmiana będzie propagować się w górę aż do zmiany korzenia Merkle'a. Zmieniony korzeń nie będzie już zgodny z nagłówkiem bloku (zabezpieczonym za pomocą PoW). Każdą modyfikację można wykryć, obliczając korzeń na podstawie transakcji.

Ethereum rozszerza drzewa Merkle'a o trie (Patricia Merkle Trie): trie typu radix z kodowaniem prefiksu szesnastkowego, w którym każdy węzeł jest haszowany za pomocą Merkle'a. Stosuje się go do: trie stanu (salda kont), trie transakcji i trie potwierdzeń. Umożliwia wydajne udowadnianie stanu konta bez danych pełnego węzła.

Merkle Mountain Range (MMR) to struktura Merkle'a przeznaczona do danych podobnych do logów, dołączana wyłącznie w trybie dopisywania. Nowe elementy są dopisywane, a wierzchołki (korzenie poddrzew o rozmiarach będących potęgami liczby 2) są utrzymywane. Stosuje się ją w Grin/MimbleWimble i ZCash do tworzenia wydajnych, zwięzłych dowodów dla logu dołączanego wyłącznie w trybie dopisywania.

Drzewa Verkle'a zastąpią drzewa Merkle'a w planach rozwoju Ethereum (EIP-6800): zamiast skrótów wykorzystują zobowiązania wektorowe (zobowiązania wielomianowe KZG). Rozmiar dowodu: O(1) zamiast O(log n) w przypadku Merkle'a. Umożliwia to klientom bezstanowym weryfikowanie stanu bez przechowywania całego trie.

Certificate Transparency (RFC 6962) wykorzystuje dołączany wyłącznie w trybie dopisywania log Merkle'a: każdy certyfikat wydany przez CA jest liściem. Dowody zawarcia potwierdzają, że certyfikat został zapisany w logu. Dowody spójności potwierdzają, że log był prowadzony wyłącznie przez dopisywanie (bez usuwania ani wstawiania). Producenci przeglądarek weryfikują SCT za pomocą tego logu.

Drzewa Gita (migawki katalogów) są drzewami Merkle'a: każdy węzeł drzewa haszuje swoje obiekty blob plików i poddrzewa. Skrót commita jednoznacznie identyfikuje cały stan bazy kodu. Dlatego git checkout zawsze zwraca dokładnie te same pliki.

Ilu skrótów wymaga dowód Merkle'a, aby potwierdzić zawarcie elementu w drzewie z 1024 liśćmi?

Drzewa Merkle'a umożliwiają dowody zawarcia o rozmiarze O(log n). Bitcoin przechowuje korzeń Merkle'a w nagłówkach bloków, a klienci SPV korzystają z dowodów. Ethereum rozszerza tę koncepcję o Patricia Merkle Trie. Drzewa Verkle'a zastąpią drzewa Merkle'a, zapewniając dowody O(1). Następny temat: wydobywanie z użyciem Proof of Work i trudność.