Merkle Tree w Go: generics i proof

Drzewo Merkle w Go: implementacja z generykami i dowód przynależności

W systemach z milionami rekordów, takich jak blockchainy, weryfikacja obecności konkretnego elementu wymagałaby przesłania całego zbioru danych. Drzewo Merkle rozwiązuje ten problem: zamiast miliona transakcji wystarczy O(log N) skrótów — około 20 dla miliona elementów. Struktura jest budowana jako drzewo binarne, gdzie każdy węzeł skrótuje swoich potomków, a korzeń sumuje cały zbiór.

Przykład: transakcje A, B, C, D. Bezpośredni skrót całego zbioru wymagałby od klienta wszystkich danych do weryfikacji. W drzewie klient otrzymuje sąsiednie skróty: H(B), H(CD) — i samodzielnie odtwarza skrót korzenia od liścia A do korzenia.

Podstawowe interfejsy i typy węzłów

Zacznij od interfejsu dla wszystkich węzłów drzewa, wspierającego generyki:

type Node[T any] interface {
    String() string
    StringIndent(level int) string
    AddChild(Node[T])
    GetBytes() []byte
    GetChildren() []Node[T]
}

Liście przechowują wartość i jej skrót. Do serializacji typu any użyj CBOR — format deterministyczny (RFC 8949), w przeciwieństwie do JSON z niestabilnym porządkiem kluczy w mapie.

type Leaf[T any] struct {
    Value     T
    ValueHash []byte
}

func NewLeaf[T any](value T, hash hash.Hash) (*Leaf[T], error) {
    hashedValue, err := valueToHash(value, hash)
    if err != nil {
        return nil, err
    }
    return &Leaf[T]{Value: value, ValueHash: hashedValue}, nil
}

func valueToHash(value any, hash hash.Hash) ([]byte, error) {
    encoded, err := cbor.Marshal(value)
    if err != nil {
        return nil, err
    }
    hash.Reset()
    hash.Write(encoded)
    return hash.Sum(nil), nil
}

Węzły binarne agregują lewe i prawe potomki:

type BinaryNode[T any] struct {
    Value []byte
    Right Node[T]
    Left  Node[T]
}

Budowanie drzewa z fabryką funkcji skrótu

Drzewem zarządza struktura z fabryką do tworzenia czystych instancji skrótu — hash.Hash ma stan, więc przekazuj funkcję:

type BinaryTree[T any] struct {
    newHash func() hash.Hash
}

func NewBinaryTree[T any](newHash func() hash.Hash) *BinaryTree[T] {
    return &BinaryTree[T]{newHash: newHash}
}

// Użycie
tree := NewBinaryTree[string](sha256.New)

Budowanie: liście skrótują wartości, wewnętrzne węzły — konkatenację skrótów potomków. H(AB) = SHA256(H(A) + H(B)). Korzeń — finalny skrót całego drzewa.

Dowód Merkle: generacja i weryfikacja

Dowód przynależności — kluczowy mechanizm. Klient zna skrót celu (H(A)) i skrót korzenia. Serwer dostarcza skróty sąsiadów na ścieżce od liścia do korzenia.

Algorytm generacji

• Od korzenia zejdź do docelowego liścia.
• Na każdym poziomie zapisz skrót węzła-sąsiada (lewego lub prawego, niebędącego na ścieżce).
• Dowód — lista tych skrótów.

Weryfikacja od dołu do góry:

• Zacznij od H(A).
• Sekwencyjnie skrótuj z sąsiadami, naprzemiennie strony (lewy/prawy).
• Osiągnij korzeń — zgodność potwierdza przynależność.

Dla 2^20 elementów (milion) dowód — 20 skrótów po 32 bajty, ~640 bajtów.

Zalety i zastosowania

• Złożoność logarytmiczna: O(log N) dla dowodu, idealnie dla klientów SPV.
• Minimalny ruch sieciowy: Bitcoin SPV weryfikuje transakcje bez pełnego bloku (500+ GB).

Zastosowania:

• Bitcoin: Transaction root w nagłówku bloku.
• Ethereum: State trie, transaction trie, receipt trie.
• Git: Tree objects w commitach.
• IPFS: Skrót treści jako korzeń fragmentów.
• Certificate Transparency: Audyt logów certyfikatów SSL.

Co jest ważne

• Drzewo Merkle dowodzi przynależności za O(log N) bez ujawniania innych danych.
• Używaj generyków w Go dla bezpieczeństwa typów; CBOR dla deterministycznego skrótowania any.
• Fabryka funkcji skrótu zapobiega race conditions od stanu hash.Hash.
• Dowód jest generowany na podstawie skrótów-sąsiadów ścieżki od liścia do korzenia.
• Skuteczne dla systemów rozproszonych: blockchainy, magazyny P2P.

— Editorial Team