Arbre Merkle en Go : génériques et preuve

Arbre de Merkle en Go : Implémentation avec génériques et preuve d'inclusion

Dans les systèmes contenant des millions d'enregistrements, comme les blockchains, vérifier la présence d'un élément spécifique nécessite généralement la transmission de l'ensemble des données. L'arbre de Merkle résout ce problème : au lieu d'un million de transactions, seuls O(log N) hachages sont nécessaires—environ 20 pour un million d'éléments. La structure est construite comme un arbre binaire, où chaque nœud hache ses enfants, et la racine résume l'ensemble complet.

Exemple : transactions A, B, C, D. Hacher directement l'ensemble complet oblige le client à disposer de toutes les données pour la vérification. Dans l'arbre, le client reçoit les hachages voisins : H(B), H(CD)—et reconstruit indépendamment le hachage racine de la feuille A à la racine.

Interfaces de base et types de nœuds

Commencez par une interface pour tous les nœuds de l'arbre, prenant en charge les génériques :

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

Les feuilles stockent la valeur et son hachage. Pour sérialiser des valeurs de tout type, utilisez CBOR—un format déterministe (RFC 8949), contrairement au JSON qui a un ordre des clés instable dans les 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
}

Les nœuds binaires agrègent les enfants gauche et droit :

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

Construction de l'arbre avec une fabrique de fonctions de hachage

L'arbre est géré par une structure avec une fabrique pour créer des instances propres de hachage—hash.Hash a un état, donc passez une fonction :

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

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

// Utilisation
tree := NewBinaryTree[string](sha256.New)

Construction : les feuilles hachent les valeurs, les nœuds internes hachent la concaténation des hachages des enfants. H(AB) = SHA256(H(A) + H(B)). La racine est le hachage final de l'arbre entier.

Preuve de Merkle : Génération et vérification

La preuve d'inclusion est un mécanisme clé. Le client connaît le hachage cible (H(A)) et le hachage racine. Le serveur fournit les hachages voisins le long du chemin de la feuille à la racine.

Algorithme de génération

• Depuis la racine, descendez vers la feuille cible.
• À chaque niveau, sauvegardez le hachage du nœud frère (gauche ou droit, ne faisant pas partie du chemin).
• La preuve est une liste de ces hachages.

Vérification de bas en haut :

• Commencez avec H(A).
• Hachez séquentiellement avec les voisins, en alternant les côtés (gauche/droit).
• Atteignez la racine—une correspondance confirme l'inclusion.

Pour 2^20 éléments (un million), la preuve est de 20 hachages de 32 octets chacun, ~640 octets.

Avantages et applications

• Complexité logarithmique : O(log N) pour la preuve, idéal pour les clients SPV.
• Trafic minimal : Bitcoin SPV vérifie les transactions sans le bloc complet (500+ Go).

Applications :

• Bitcoin : Racine des transactions dans l'en-tête du bloc.
• Ethereum : Trie d'état, trie des transactions, trie des reçus.
• Git : Objets arbre dans les commits.
• IPFS : Hachage de contenu comme racine des morceaux.
• Certificate Transparency : Audit des journaux de certificats SSL.

Points clés à retenir

• L'arbre de Merkle prouve l'inclusion en O(log N) sans révéler d'autres données.
• Utilisez les génériques en Go pour la sécurité des types ; CBOR pour le hachage déterministe de tout type.
• La fabrique de fonctions de hachage évite les conditions de course dues à l'état de hash.Hash.
• La preuve est générée à partir des hachages frères le long du chemin de la feuille à la racine.
• Efficace pour les systèmes distribués : blockchains, stockage P2P.

— Editorial Team