2.1.2. Preuves de cohérence Merkle

2.1.2. Preuves de cohérence Merkle

Les preuves de cohérence Merkle prouvent la propriété d'ajout uniquement de l'arbre. Une preuve de cohérence Merkle pour un hachage d'arbre Merkle MTH(D[n]) et un hachage précédemment annoncé MTH(D[0:m]) des premières m feuilles, m <= n, est la liste des nœuds dans l'arbre Merkle requis pour vérifier que les premières m entrées D[0:m] sont égales dans les deux arbres. Ainsi, une preuve de cohérence doit contenir un ensemble de nœuds intermédiaires (c'est-à-dire, des engagements sur les entrées) suffisant pour vérifier MTH(D[n]), de sorte que (un sous-ensemble de) les mêmes nœuds puissent être utilisés pour vérifier MTH(D[0:m]). Nous définissons un algorithme qui produit la preuve de cohérence minimale (unique).

Étant donné une liste ordonnée de n entrées dans l'arbre, D[n] = {d(0), ..., d(n-1)}, la preuve de cohérence Merkle PROOF(m, D[n]) pour un hachage d'arbre Merkle précédent MTH(D[0:m]), 0 < m < n, est définie comme :

PROOF(m, D[n]) = SUBPROOF(m, D[n], true)

La sous-preuve pour m = n est vide si m est la valeur pour laquelle PROOF a été initialement demandée (ce qui signifie que le hachage d'arbre Merkle du sous-arbre MTH(D[0:m]) est connu) :

SUBPROOF(m, D[m], true) = {}

La sous-preuve pour m = n est le hachage d'arbre Merkle engageant les entrées D[0:m] ; sinon :

SUBPROOF(m, D[m], false) = {MTH(D[m])}

Pour m < n, soit k la plus grande puissance de deux inférieure à n. La sous-preuve est alors définie récursivement.

Si m <= k, les entrées du sous-arbre droit D[k:n] existent uniquement dans l'arbre actuel. Nous prouvons que les entrées du sous-arbre gauche D[0:k] sont cohérentes et ajoutons un engagement sur D[k:n] :

SUBPROOF(m, D[n], b) = SUBPROOF(m, D[0:k], b) : MTH(D[k:n])

Si m > k, les entrées du sous-arbre gauche D[0:k] sont identiques dans les deux arbres. Nous prouvons que les entrées du sous-arbre droit D[k:n] sont cohérentes et ajoutons un engagement sur D[0:k].

SUBPROOF(m, D[n], b) = SUBPROOF(m - k, D[k:n], false) : MTH(D[0:k])

Ici, : est une 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.

Le nombre de nœuds dans la preuve résultante est borné supérieurement par ceil(log2(n)) + 1.