2.1.1. Chemins d'audit Merkle

2.1.1. Chemins d'audit Merkle

Un chemin d'audit Merkle pour une feuille dans un arbre de hachage Merkle est la liste la plus courte de nœuds supplémentaires dans l'arbre Merkle requis pour calculer le hachage d'arbre Merkle pour cet arbre. Chaque nœud dans l'arbre est soit un nœud feuille, soit calculé à partir des deux nœuds immédiatement en dessous (c'est-à-dire, vers les feuilles). À chaque étape vers le haut de l'arbre (vers la racine), un nœud du chemin d'audit est combiné avec le nœud calculé jusqu'à présent. En d'autres termes, le chemin d'audit consiste en la liste des nœuds manquants requis pour calculer les nœuds menant d'une feuille à la racine de l'arbre. Si la racine calculée à partir du chemin d'audit correspond à la vraie racine, alors le chemin d'audit est la preuve que la feuille existe dans l'arbre.

Étant donné une liste ordonnée de n entrées dans l'arbre, D[n] = {d(0), ..., d(n-1)}, le chemin d'audit Merkle PATH(m, D[n]) pour la (m+1)ième entrée d(m), 0 <= m < n, est défini comme suit :

Le chemin pour la feuille unique dans un arbre avec une liste d'entrée à un élément D[1] = {d(0)} est vide :

PATH(0, {d(0)}) = {}

Pour n > 1, soit k la plus grande puissance de deux inférieure à n. Le chemin pour le (m+1)ième élément d(m) dans une liste de n > m éléments est alors défini récursivement comme

PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) pour m < k; et

PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) pour m >= k,

où : est la concaténation de listes et D[k1:k2] dénote la liste de longueur (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)} comme précédemment.