2.1. Arbres de hachage Merkle

2.1. Arbres de hachage Merkle

Les journaux utilisent un arbre de hachage Merkle binaire pour un audit efficace. L'algorithme de hachage est SHA-256 [FIPS.180-4] (notez que ceci est fixé pour cette expérimentation, mais il est anticipé que chaque journal pourra spécifier un algorithme de hachage). L'entrée de l'arbre de hachage Merkle est une liste d'entrées de données ; ces entrées seront hachées pour former les feuilles de l'arbre de hachage Merkle. La sortie est un unique hachage d'arbre Merkle de 32 octets. Étant donné une liste ordonnée de n entrées, D[n] = {d(0), d(1), ..., d(n-1)}, le hachage d'arbre Merkle (MTH) est ainsi défini comme suit :

Le hachage d'une liste vide est le hachage d'une chaîne vide :

MTH({}) = SHA-256().

Le hachage d'une liste avec une entrée (également connu sous le nom de hachage de feuille) est :

MTH({d(0)}) = SHA-256(0x00 || d(0)).

Pour n > 1, soit k la plus grande puissance de deux inférieure à n (c'est-à-dire, k < n <= 2k). Le hachage d'arbre Merkle d'une liste de n éléments D[n] est alors défini récursivement comme

MTH(D[n]) = SHA-256(0x01 || MTH(D[0:k]) || MTH(D[k:n])),

où || est la concaténation et D[k1:k2] dénote la liste {d(k1), d(k1+1),..., d(k2-1)} de longueur (k2 - k1). (Notez que les calculs de hachage pour les feuilles et les nœuds diffèrent. Cette séparation de domaine est requise pour donner une résistance à la deuxième préimage.)

Notez que nous n'exigeons pas que la longueur de la liste d'entrée soit une puissance de deux. L'arbre Merkle résultant peut donc ne pas être équilibré ; cependant, sa forme est uniquement déterminée par le nombre de feuilles. (Note : Cet arbre Merkle est essentiellement le même que la proposition d'arbre d'historique [CrosbyWallach], sauf que notre définition gère différemment les arbres non pleins.)