2.1.2. Prove di coerenza Merkle

2.1.2. Prove di coerenza Merkle

Le prove di coerenza Merkle dimostrano la proprietà di solo aggiunta dell'albero. Una prova di coerenza Merkle per un hash dell'albero Merkle MTH(D[n]) e un hash precedentemente annunciato MTH(D[0:m]) delle prime m foglie, m <= n, è la lista dei nodi nell'albero Merkle necessari per verificare che i primi m input D[0:m] siano uguali in entrambi gli alberi. Quindi, una prova di coerenza deve contenere un insieme di nodi intermedi (cioè, impegni agli input) sufficienti per verificare MTH(D[n]), in modo tale che (un sottoinsieme di) gli stessi nodi possano essere utilizzati per verificare MTH(D[0:m]). Definiamo un algoritmo che produce la prova di coerenza minima (unica).

Data una lista ordinata di n input all'albero, D[n] = {d(0), ..., d(n-1)}, la prova di coerenza Merkle PROOF(m, D[n]) per un hash dell'albero Merkle precedente MTH(D[0:m]), 0 < m < n, è definita come:

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

La sottoprova per m = n è vuota se m è il valore per cui PROOF è stato originariamente richiesto (il che significa che l'hash dell'albero Merkle del sottoalbero MTH(D[0:m]) è noto):

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

La sottoprova per m = n è l'hash dell'albero Merkle che impegna gli input D[0:m]; altrimenti:

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

Per m < n, sia k la più grande potenza di due minore di n. La sottoprova è quindi definita ricorsivamente.

Se m <= k, le voci del sottoalbero destro D[k:n] esistono solo nell'albero corrente. Dimostriamo che le voci del sottoalbero sinistro D[0:k] sono coerenti e aggiungiamo un impegno a D[k:n]:

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

Se m > k, le voci del sottoalbero sinistro D[0:k] sono identiche in entrambi gli alberi. Dimostriamo che le voci del sottoalbero destro D[k:n] sono coerenti e aggiungiamo un impegno a D[0:k].

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

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

Il numero di nodi nella prova risultante è limitato superiormente da ceil(log2(n)) + 1.