2.1.1. Percorsi di audit Merkle

2.1.1. Percorsi di audit Merkle

Un percorso di audit Merkle per una foglia in un albero di hash Merkle è la lista più breve di nodi aggiuntivi nell'albero Merkle necessari per calcolare l'hash dell'albero Merkle per quell'albero. Ogni nodo nell'albero è o un nodo foglia o è calcolato dai due nodi immediatamente sotto di esso (cioè, verso le foglie). Ad ogni passo verso l'alto dell'albero (verso la radice), un nodo del percorso di audit è combinato con il nodo calcolato finora. In altre parole, il percorso di audit consiste nella lista dei nodi mancanti necessari per calcolare i nodi che portano da una foglia alla radice dell'albero. Se la radice calcolata dal percorso di audit corrisponde alla vera radice, allora il percorso di audit è la prova che la foglia esiste nell'albero.

Data una lista ordinata di n input all'albero, D[n] = {d(0), ..., d(n-1)}, il percorso di audit Merkle PATH(m, D[n]) per il (m+1)-esimo input d(m), 0 <= m < n, è definito come segue:

Il percorso per la singola foglia in un albero con una lista di input di un elemento D[1] = {d(0)} è vuoto:

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

Per n > 1, sia k la più grande potenza di due minore di n. Il percorso per il (m+1)-esimo elemento d(m) in una lista di n > m elementi è quindi definito ricorsivamente come

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

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

dove : è la concatenazione di liste e D[k1:k2] denota la lista di lunghezza (k2 - k1) {d(k1), d(k1+1),..., d(k2-1)} come prima.