Merkle Tree in Go: Generics und Proof

Merkle-Baum in Go: Implementierung mit Generics und Inklusionsnachweis

In Systemen mit Millionen von Datensätzen, wie Blockchains, erfordert die Überprüfung der Anwesenheit eines bestimmten Elements normalerweise die Übertragung des gesamten Datensatzes. Der Merkle-Baum löst dieses Problem: Anstelle einer Million Transaktionen werden nur O(log N) Hashes benötigt – etwa 20 für eine Million Elemente. Die Struktur wird als Binärbaum aufgebaut, wobei jeder Knoten seine Kinder hasht und die Wurzel die gesamte Menge zusammenfasst.

Beispiel: Transaktionen A, B, C, D. Das direkte Hashen der gesamten Menge erfordert, dass der Client alle Daten zur Überprüfung hat. Im Baum erhält der Client benachbarte Hashes: H(B), H(CD) – und rekonstruiert unabhängig den Wurzelhash von Blatt A zur Wurzel.

Grundlegende Schnittstellen und Knotentypen

Beginnen Sie mit einer Schnittstelle für alle Baumknoten, die Generics unterstützt:

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

Blätter speichern den Wert und seinen Hash. Für die Serialisierung von Werten beliebigen Typs verwenden Sie CBOR – ein deterministisches Format (RFC 8949), im Gegensatz zu JSON mit instabiler Schlüsselreihenfolge in Maps.

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äre Knoten aggregieren linke und rechte Kinder:

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

Aufbau des Baums mit einer Hash-Funktionsfabrik

Der Baum wird von einer Struktur mit einer Fabrik zur Erstellung sauberer Hash-Instanzen verwaltet – hash.Hash hat Zustand, also übergeben Sie eine Funktion:

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

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

// Verwendung
tree := NewBinaryTree[string](newHash)

Konstruktion: Blätter hashen Werte, interne Knoten hashen die Verkettung der Kinderhashes. H(AB) = SHA256(H(A) + H(B)). Die Wurzel ist der finale Hash des gesamten Baums.

Merkle-Nachweis: Erzeugung und Verifizierung

Der Inklusionsnachweis ist ein Schlüsselmechanismus. Der Client kennt den Zielhash (H(A)) und den Wurzelhash. Der Server liefert benachbarte Hashes entlang des Pfads vom Blatt zur Wurzel.

Generierungsalgorithmus

• Von der Wurzel aus zum Zielblatt absteigen.
• Auf jeder Ebene den Hash des Geschwisterknotens speichern (links oder rechts, nicht Teil des Pfads).
• Der Nachweis ist eine Liste dieser Hashes.

Verifizierung von unten nach oben:

• Beginnen Sie mit H(A).
• Sequenziell mit Nachbarn hashen, Seiten wechselnd (links/rechts).
• Erreichen Sie die Wurzel – eine Übereinstimmung bestätigt die Inklusion.

Für 2^20 Elemente (eine Million) ist der Nachweis 20 Hashes von je 32 Bytes, ~640 Bytes.

Vorteile und Anwendungen

• Logarithmische Komplexität: O(log N) für den Nachweis, ideal für SPV-Clients.
• Minimaler Datenverkehr: Bitcoin SPV verifiziert Transaktionen ohne den vollen Block (500+ GB).

Anwendungen:

• Bitcoin: Transaktionswurzel im Blockheader.
• Ethereum: State-Trie, Transaktions-Trie, Receipt-Trie.
• Git: Baumobjekte in Commits.
• IPFS: Inhaltshash als Wurzel von Chunks.
• Certificate Transparency: Überwachung von SSL-Zertifikatsprotokollen.

Wichtige Erkenntnisse

• Merkle-Baum beweist Inklusion in O(log N) ohne Offenlegung anderer Daten.
• Verwenden Sie Generics in Go für Typsicherheit; CBOR für deterministisches Hashen von beliebigen Werten.
• Hash-Funktionsfabrik verhindert Race Conditions durch hash.Hash-Zustand.
• Nachweis wird aus Geschwisterhashes entlang des Pfads vom Blatt zur Wurzel generiert.
• Effizient für verteilte Systeme: Blockchains, P2P-Speicher.

— Editorial Team