2.1. Alberi di hash Merkle

2.1. Alberi di hash Merkle

I log utilizzano un albero di hash Merkle binario per un audit efficiente. L'algoritmo di hashing è SHA-256 [FIPS.180-4] (si noti che questo è fisso per questo esperimento, ma si prevede che ogni log possa specificare un algoritmo di hash). L'input dell'albero di hash Merkle è un elenco di voci di dati; queste voci verranno sottoposte a hash per formare le foglie dell'albero di hash Merkle. L'output è un singolo hash dell'albero Merkle di 32 byte. Data una lista ordinata di n input, D[n] = {d(0), d(1), ..., d(n-1)}, l'hash dell'albero Merkle (MTH) è quindi definito come segue:

L'hash di una lista vuota è l'hash di una stringa vuota:

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

L'hash di una lista con una voce (noto anche come hash foglia) è:

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

Per n > 1, sia k la più grande potenza di due minore di n (cioè, k < n <= 2k). L'hash dell'albero Merkle di una lista di n elementi D[n] è quindi definito ricorsivamente come

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

dove || è la concatenazione e D[k1:k2] denota la lista {d(k1), d(k1+1),..., d(k2-1)} di lunghezza (k2 - k1). (Si noti che i calcoli di hash per le foglie e i nodi differiscono. Questa separazione di dominio è necessaria per dare resistenza alla seconda preimmagine.)

Si noti che non richiediamo che la lunghezza della lista di input sia una potenza di due. L'albero Merkle risultante potrebbe quindi non essere bilanciato; tuttavia, la sua forma è determinata in modo univoco dal numero di foglie. (Nota: Questo albero Merkle è essenzialmente lo stesso della proposta dell'albero di storia [CrosbyWallach], tranne che la nostra definizione gestisce gli alberi non completi in modo diverso.)