Merkle Tree v Go: generics a proof

Merkleho strom v Go: implementace s generics a důkaz zařazení

V systémech s miliony záznamů, jako jsou blockchainy, vyžaduje ověření přítomnosti konkrétního prvku přenos celé datové sady. Merkleho strom tento problém řeší: místo milionu transakcí stačí O(log N) hashů – přibližně 20 pro milion prvků. Struktura je postavena jako binární strom, kde každý uzel hashuje své potomky a kořen sumarizuje celou sadu.

Příklad: transakce A, B, C, D. Přímý hash celé sady vyžaduje od klienta všechna data pro ověření. Ve stromě klient obdrží sousední hashe: H(B), H(CD) – a sám obnoví kořenový hash od listu A až ke kořeni.

Základní rozhraní a typy uzlů

Začněte rozhraním pro všechny uzly stromu, které podporuje generics:

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

Listy ukládají hodnotu a její hash. Pro serializaci any-typu použijte CBOR – deterministický formát (RFC 8949), na rozdíl od JSON s nestabilním pořadím klíčů v mapě.

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
}

Binární uzly agregují levé a pravé potomky:

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

Vytváření stromu s továrnou hashovacích funkcí

Strom je řízen strukturou s továrnou pro vytváření čistých instancí hash – hash.Hash má stav, proto předávejte funkci:

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

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

// Použití
tree := NewBinaryTree[string]

Stavba: listy hashují hodnoty, vnitřní uzly – konkatenaci hashů potomků. H(AB) = SHA256(H(A) + H(B)). Kořen – finální hash celého stromu.

Merkleho důkaz: generování a ověření

Důkaz zařazení – klíčový mechanismus. Klient zná hash cíle (H(A)) a kořenový hash. Server poskytne hashe sousedů na cestě od listu ke kořeni.

Algoritmus generování

• Od kořene sestupte k cílovému listu.
• Na každé úrovni uložte hash sourozeneckého uzlu (levého nebo pravého, který není na cestě).
• Důkaz – seznam těchto hashů.

Ověření zdola nahoru:

• Začněte s H(A).
• Postupně hashujte se sousedy, střídejte strany (left/right).
• Dosáhněte kořene – shoda potvrdí zařazení.

Pro 2^20 prvků (milion) důkaz – 20 hashů po 32 bajtech, ~640 bajtů.

Výhody a použití

• Logaritmická složitost: O(log N) pro důkaz, ideální pro SPV-klienty.
• Minimální provoz: Bitcoin SPV ověřuje transakce bez celého bloku (500+ GB).

Použití:

• Bitcoin: Transaction root v hlavičce bloku.
• Ethereum: State trie, transaction trie, receipt trie.
• Git: Tree objects v commitu.
• IPFS: Hash obsahu jako kořen chunků.
• Certificate Transparency: Audit logů SSL certifikátů.

Co je důležité

• Merkleho strom dokazuje zařazení za O(log N) bez odhalení dalších dat.
• Použijte generics v Go pro typovou bezpečnost; CBOR pro deterministické hashování any.
• Továrna hashovacích funkcí zabraňuje race conditions od stavu hash.Hash.
• Důkaz je generován podle sourozeneckých hashů cesty od listu ke kořeni.
• Efektivní pro distribuované systémy: blockchainy, P2P-úložiště.

— Editorial Team