Arbre de Merkle Patricia

Dernière modification: @Im-SpiETH(opens in a new tab), 8 décembre 2023

Un arbre de Merkle Patricia produit une structure des données cryptographiquement authentifiée pouvant être utilisée pour sauvegarder toutes les paires (key, value).

Les arbres de Merkle Patricia sont entièrement déterministes, ce qui signifie que deux arbres possédant la même paire (clé, valeur) sont garantis identiques -- jusqu'au dernier octet. Cela signifie également qu'ils ont le même hachage racine, ce qui permet d'atteindre le "Graal" de l'efficacité O(log(n)) pour les insertions, les consultations et les suppressions. Enfin, ils sont plus simples à appréhender ainsi qu'à coder que les alternatives basées sur les comparaisons, comme les arbres rouge-noir.

Prérequis

Pour mieux comprendre cette page, il serait utile d'avoir des connaissances de base sur les hachages(opens in a new tab), les arbres de Merkle(opens in a new tab), les arbres(opens in a new tab) et la sérialisation(opens in a new tab).

Arbres radix de base

Dans un arbre radix de base, chaque nœud se présente comme suit :

1    [i_0, i_1 ... i_n, value]

Là où i0 ... in représentent les symboles de l'alphabet (souvent binaires ou hexagonaux), value est la valeur terminale du nœud, et les valeurs dans les créneaux i0 ... in sont soit NULL soit des pointeurs vers (dans notre cas, des hashs) d'autres nœuds. Cela forme un registre de base (key, value).

Supposons que vous souhaitiez utiliser une structure de données d'arborescence radix pour maintenir une commande sur un ensemble de paires de valeurs clés. Pour connaître la valeur actuellement associée à dog dans le tableau, vous devriez d'abord convertir dog en lettres de l'alphabet (ce qui donne 64 6f 67), puis descendre dans l'arbre en suivant ce chemin jusqu'à ce que vous trouviez la valeur. C'est-à-dire que vous commencez par chercher le hachage racine dans une base de données/valeur plate pour trouver le nœud racine de l'arbre. Il se présente sous la forme d'un tableau de clés pointant vers d'autres nœuds. Vous utilisez ensuite la valeur à l'index 6 comme clé et la recherchez dans la base de données clé/valeur pour obtenir le nœud un niveau plus bas. Ensuite, choisissez l'index 4 pour rechercher la valeur suivante, puis choisissez l'index 6, et ainsi de suite, jusqu'à ce que, une fois suivi le chemin : racine -> -> -> 6 - > 6 -> 15 -> 6 -> 7, vous cherchiez la valeur du nœud et retourniez le résultat.

Il y a une différence entre rechercher quelque chose dans l'"arbre" et la "base de données" plate sous-jacente (clé/valeur). Ils définissent tous deux des combinaisons clé/valeur, mais la base de données sous-jacente peut rechercher une clé en une seule étape basique. La recherche d'une clé dans le tableau nécessite plusieurs consultations de la base de données sous-jacente pour obtenir la valeur finale décrite ci-dessus. Faisons référence à ce dernier comme à un path (chemin) pour éliminer toute ambiguïté.

Les opérations de mise à jour et de suppression pour les arbres radix peuvent être définies comme suit :

1    def update(node,path,value):
2        if path == '':
3            curnode = db.get(node) if node else [ NULL ] * 17
4            newnode = curnode.copy()
5            newnode[-1] = value
6        else:
7            curnode = db.get(node) if node else [ NULL ] * 17
8            newnode = curnode.copy()
9            newindex = update(curnode[path[0]],path[1:],value)
10            newnode[path[0]] = newindex
11        db.put(hash(newnode),newnode)
12        return hash(newnode)
13
14    def delete(node,path):
15        if node is NULL:
16            return NULL
17        else:
18            curnode = db.get(node)
19            newnode = curnode.copy()
20            if path == '':
21                newnode[-1] = NULL
22            else:
23                newindex = delete(curnode[path[0]],path[1:])
24                newnode[path[0]] = newindex
25
26            if all(x is NULL for x in newnode):
27                return NULL
28            else:
29                db.put(hash(newnode),newnode)
30                return hash(newnode)
Afficher tout

Un arbre Radix « Merkle» est construit en reliant les nœuds à l'aide des diagrammes de hachage cryptographiques générés de manière déterministe. Cette adresse de contenu (dans la base de données clé/valeur key == keccak256(rlp(value))) fournit une garantie d'intégrité cryptographique des données stockées. Si le hash racine d'un arbre donné est connu publiquement, alors tout le monde ayant accès à cette feuille peut fournir une preuve que l'arbre inclut une valeur donnée à un endroit spécifique, en fournissant les hachages de chaque nœud reliant une valeur spécifique à la racine de l'arborescence.

Il est impossible pour un attaquant de fournir une preuve d'une paire de (path, value) qui n'existe pas car le hachage racine est basé en fin de compte sur tous les hachages situés au-dessous. Toute modification sous-jacente modifierait le hash racine. Vous pouvez considérer le hash comme une représentation compressée des informations structurelles sur les données, sécurisée par la protection de pré-image de la fonction de hachage.

Nous allons faire référence à une unité atomique d'un arbre radix (par exemple un seul caractère hexadécimal, ou un nombre binaire de 4 bits) en tant que "nibble". Lorsque l'on parcourt un chemin un nibble à la fois, comme décrit ci-dessus, les nœuds peuvent faire référence à 16 enfants au maximum, mais peuvent également inclure un élément value. Nous les représentons donc comme un tableau de longueur 17. Nous appelons ces tableaux à 17 éléments des "nœuds de branches".

Arbre de Merkle de Patricia

Cependant, les arbres radix ont une limitation majeure : ils sont inefficaces. Si vous voulez stocker une seule liaison (path, value) où le chemin est, comme dans Ethereum, long de 64 caractères (nombre de nibbles dans bytes32), vous aurez besoin de plus d'un kilooctet d'espace supplémentaire pour stocker un niveau par caractère, et chaque consultation ou suppression prendra les 64 étapes complètes. L'arbre de Patricia présenté dans ce qui suit résout ce problème.

Optimisation

Un nœud dans un arbre de Merkle Patricia correspond à l'un des éléments suivants :

NULL (représenté comme une chaîne vide)
branch Un nœud de 17 éléments [ v0 ... v15, vt ]
leaf Un nœud de 2 éléments [ encodedPath, value ]
extension Un nœud de 2 éléments [ encodedPath, key ]

Avec 64 chemins de caractères, il est inévitable qu'après avoir traversé les premières couches de l'arbre, vous atteigniez un nœud où aucun chemin divergent n'existe sur au moins une partie de la descente. Pour éviter de devoir créer jusqu'à 15 nœuds NULL épars le long du chemin, nous raccourcissons la descente en créant un nœud extension de la forme [ encodedPath, key ], où encodedPath contient le "chemin partiel" à sauter (à l'aide d'un codage compact décrit ci-dessous), et où la key est destinée à la consultation suivante de la base de données.

Pour un nœud feuille, qui peut être marqué par un drapeau dans la première pièce du encodedPath, le chemin encode tous les fragments de chemin du nœud précédent et nous pouvons consulter la valeur directement.

Cette optimisation introduit toutefois une ambiguïté.

Lors de la traversée de chemins en nibbles, nous pourrions nous retrouver avec un nombre impair de nibbles à traverser, mais comme toutes les données sont stockées au format bytes, il est possible que le nombre de nibbles à parcourir soit impair. Il n'est pas possible de différencier entre, par exemple, le nibble 1, et les nibbles 01 (les deux doivent être stockés sous la forme <01>). Pour spécifier une longueur impaire, le chemin partiel est précédé d'un drapeau.

Spécification : Codage compact d'une séquence hexagonale avec terminateur optionnel

Le marquage de la longueur du chemin partiel restante impaire ou paire et de la feuille ou nœud d'extension, tel que décrit ci-dessus, se trouve dans le premier élément du chemin partiel de tout nœud à deux éléments. Cela se traduit comme suit :

1hex char    bits    |    node type partial     path length
2----------------------------------------------------------
3   0        0000    |       extension              even
4   1        0001    |       extension              odd
5   2        0010    |   terminating (leaf)         even
6   3        0011    |   terminating (leaf)         odd

Pour une longueur de chemin restante paire (0 ou 2), un autre nibble de "remplissage" de 0 suivra toujours.

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term: hexarray = hexarray[:-1]
4        oddlen = len(hexarray) % 2
5        flags = 2 * term + oddlen
6        if oddlen:
7            hexarray = [flags] + hexarray
8        else:
9            hexarray = [flags] + [0] + hexarray
10        // hexarray now has an even length whose first nibble is the flags.
11        o = ''
12        for i in range(0,len(hexarray),2):
13            o += chr(16 * hexarray[i] + hexarray[i+1])
14        return o
Afficher tout

Exemples :

1    > [ 1, 2, 3, 4, 5, ...]
2    '11 23 45'
3    > [ 0, 1, 2, 3, 4, 5, ...]
4    '00 01 23 45'
5    > [ 0, f, 1, c, b, 8, 10]
6    '20 0f 1c b8'
7    > [ f, 1, c, b, 8, 10]
8    '3f 1c b8'

Voici le code étendu pour obtenir un nœud dans l'arbre de Merkle Patricia :

1    def get_helper(node,path):
2        if path == []: return node
3        if node = '': return ''
4        curnode = rlp.decode(node if len(node) < 32 else db.get(node))
5        if len(curnode) == 2:
6            (k2, v2) = curnode
7            k2 = compact_decode(k2)
8            if k2 == path[:len(k2)]:
9                return get(v2, path[len(k2):])
10            else:
11                return ''
12        elif len(curnode) == 17:
13            return get_helper(curnode[path[0]],path[1:])
14
15    def get(node,path):
16        path2 = []
17        for i in range(len(path)):
18            path2.push(int(ord(path[i]) / 16))
19            path2.push(ord(path[i]) % 16)
20        path2.push(16)
21        return get_helper(node,path2)
Afficher tout

Exemple d'arbre

Supposons que nous voulions un tableau contenant quatre couples chemin/valeur ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion').

Tout d'abord, nous convertissons les chemins et les valeurs en bytes (octets). Ci-dessous, les représentations réelles d'octets pour les chemins sont désignées par <>, bien que les valeurs soient toujours représentées sous forme de chaînes, désignées par '', pour une compréhension plus facile (elles aussi seraient en fait des octets) :

1    <64 6f> : 'verb'
2    <64 6f 67> : 'puppy'
3    <64 6f 67 65> : 'coin'
4    <68 6f 72 73 65> : 'stallion'

Nous construisons un tel arbre avec les paires clé/valeur suivantes dans la base de données sous-jacente :

1    rootHash: [ <16>, hashA ]
2    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
3    hashB:    [ <00 6f>, hashD ]
4    hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
5    hashE:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coin' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Lorsqu'un nœud est référencé à l'intérieur d'un autre nœud, ce qui est inclus est H(rlp.encode(x)), où H(x) = keccak256(x) if len(x) >= 32 else x et rlp.encode est la fonction d'encodage RLP.

Notez que lors de la mise à jour d'un arbre, on doit stocker la paire clé/valeur (keccak256(x), x)dans une table de consultation persistante si le nœud nouvellement créé a une longueur >= 32. Toutefois, si le nœud est plus court que cela, il n'est pas nécessaire de stocker quoi que ce soit, puisque la fonction f(x) = x est réversible.

Les arbres sur Ethereum

Tous les arbres Merkle dans la couche d'exécution d'Ethereum font appel à un arbre de Merkle Patricia.

L'en-tête d'un bloc comporte trois racines issues de trois de ces arbres.

stateRoot
transactionsRoot
receiptsRoot

Arbre d'état

Il n'existe qu'un seul arbre d'état global, qui est mis à jour à chaque fois qu'un client traite un bloc. Dans celui-ci, un path est toujours : keccak256(ethereumAddress) et une value est toujours : rlp(ethereumAccount). Plus précisément, un account ethereum est un tableau de 4 éléments de [nonce,balance,storageRoot,codeHash]. À ce stade, il convient de noter que ce storageRoot est la racine d'un autre arbre Patricia :

Arbre de stockage

C'est dans l'arbre de stockage que se situent toutes les données du contrat. Chaque compte dispose d'un arbre de stockage distinct. Pour récupérer des valeurs à des positions de stockage spécifiques et à une adresse donnée, l'adresse de stockage, la position entière des données stockées dans le stockage et l'ID du bloc sont nécessaires. Ceux-ci peuvent ensuite être transmis comme arguments à la fonction eth_getStorageAt définie dans l'API JSON-RPC, par exemple pour récupérer les données dans le créneau de stockage 0 pour l'adresse 0x295a70b2de5e3953354a6a8344e616ed314d7251 :

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}
4

La récupération d'autres éléments dans le stockage est un peu plus complexe, car il faut d'abord calculer la position dans l'arbre de stockage. La position est calculée comme le hachage keccak256 de l'adresse et de la position de stockage, toutes deux complétées à gauche par des zéros jusqu'à une longueur de 32 octets. Par exemple, la position des données dans l'emplacement de stockage 1 pour l'adresse 0x391694e7e0b0cce554cb130d723a9d27458f9298 est :

1keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

Dans une console Geth, cela peut être calculé comme suit:

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

Le path est donc keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). On peut maintenant l'utiliser pour récupérer les données de l'arbre de stockage comme précédemment :

1curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545
2
3{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Note : le storageRoot pour un compte Ethereum est vide par défaut s'il ne s'agit pas d'un compte de contrat.

Arbre de transactions

Il existe un arbre de transactions distinct pour chaque bloc, qui stocke à nouveau les paires (key, value) . Un chemin ici est : rlp(transactionIndex) qui représente la clé qui correspond à une valeur déterminée par :

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

Plus d'informations à ce sujet peuvent être trouvées dans la documentation EIP 2718(opens in a new tab).

Arbre de reçus

Chaque bloc a son propre arbre de reçus. Un path ici est : rlp(transactionIndex). transactionIndex est son indice dans le bloc qu'il a miné. Les arbres de reçus ne sont jamais mis à jour. De la même manière que pour les arbres de transactions, il existe des reçus actuels et des reçus hérités. Pour interroger un reçu spécifique dans la liste des reçus, l'indice de la transaction dans son bloc, les charges du reçu et le type de transaction sont nécessaires. Le reçu retourné peut être de type Reçu qui est défini comme la concaténation de TransactionType et ReceiptPayload ou il peut être de type LegacyReceipt qui est défini comme rlp([statut, cumulativeGasUsed, logsBloom, logs]).