2. Cryptographic Components (Componenti crittografiche)
2. Cryptographic Components (Componenti crittografiche)
2.1 Merkle Hash Trees (Alberi di hash Merkle)
I log usano un binary Merkle Hash Tree (albero di hash Merkle binario) per una verifica efficiente. L'algoritmo di hash è SHA-256 [FIPS.180-4] (si noti che è fisso per questo esperimento, ma si prevede che ciascun log possa specificare un algoritmo di hash). L'input del Merkle Tree Hash è una lista di data entries (voci dati); tali voci saranno sottoposte ad hash per formare le foglie del Merkle Hash Tree. L'output è un singolo Merkle Tree Hash di 32 byte. Data una lista ordinata di n input, D[n] = {d(0), d(1), ..., d(n-1)}, il Merkle Tree Hash (MTH) è così definito:
L'hash di una lista vuota è l'hash di una stringa vuota:
MTH({}) = SHA-256().
L'hash di una lista con una voce (nota anche come leaf hash, hash di 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). Il Merkle Tree Hash di una lista di n elementi D[n] è allora 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 foglie e nodi differiscono. Questa domain separation (separazione di dominio) è richiesta per dare second preimage resistance, resistenza alla seconda preimmagine.)
Si noti che non richiediamo che la lunghezza della lista di input sia una potenza di due. L'albero di Merkle risultante può quindi non essere bilanciato; tuttavia, la sua forma è univocamente determinata dal numero di foglie. (Nota: questo albero di Merkle è essenzialmente lo stesso della proposta history tree [CrosbyWallach], salvo che la nostra definizione gestisce alberi non pieni in modo diverso.)
2.1.1 Merkle Audit Paths (Percorsi di verifica Merkle)
Un Merkle audit path (percorso di verifica Merkle) per una foglia in un Merkle Hash Tree è la lista più corta di nodi aggiuntivi nell'albero di Merkle necessari per calcolare il Merkle Tree Hash per quell'albero. Ogni nodo nell'albero è o una foglia o è calcolato dai due nodi immediatamente sottostanti (cioè, verso le foglie). Ad ogni passo verso l'alto nell'albero (verso la radice), un nodo dal audit path viene combinato con il nodo calcolato fino a quel punto. In altre parole, il audit path consiste nella lista dei nodi mancanti richiesti per calcolare i nodi che vanno da una foglia alla radice dell'albero. Se la radice calcolata dal audit path coincide con la radice vera, allora il audit path è prova che la foglia esiste nell'albero.
Data una lista ordinata di n input all'albero, D[n] = {d(0), ..., d(n-1)}, il Merkle audit path PATH(m, D[n]) per l'(m+1)-esimo input d(m), 0 <= m < n, è definito come segue:
Il percorso per l'unica foglia in un albero con lista di input a 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 l'(m+1)-esimo elemento d(m) in una lista di n > m elementi è allora definito ricorsivamente come
PATH(m, D[n]) = PATH(m, D[0:k]) : MTH(D[k:n]) for m < k; and
PATH(m, D[n]) = PATH(m - k, D[k:n]) : MTH(D[0:k]) for 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.
2.1.2 Merkle Consistency Proofs (Prove di coerenza Merkle)
Le Merkle consistency proofs (prove di coerenza Merkle) dimostrano la proprietà append-only dell'albero. Una Merkle consistency proof per un Merkle Tree Hash MTH(D[n]) e un hash precedentemente annunciato MTH(D[0:m]) delle prime m foglie, m <= n, è la lista di nodi nel Merkle Tree richiesta per verificare che i primi m input D[0:m] siano uguali in entrambi gli alberi. Pertanto, una consistency proof deve contenere un insieme di nodi intermedi (cioè, commitments, impegni agli input) sufficiente a verificare MTH(D[n]), tale che (un sottoinsieme degli) stessi nodi possa essere usato per verificare MTH(D[0:m]). Si definisce un algoritmo che produce la (unica) minimal consistency proof (prova di coerenza minimale).
Data una lista ordinata di n input all'albero, D[n] = {d(0), ..., d(n-1)}, la Merkle consistency proof PROOF(m, D[n]) per un precedente Merkle Tree Hash MTH(D[0:m]), 0 < m < n, è definita come:
PROOF(m, D[n]) = SUBPROOF(m, D[n], true)
La subproof per m = n è vuota se m è il valore per cui PROOF è stata originariamente richiesta (significando che il subtree Merkle Tree Hash MTH(D[0:m]) è noto):
SUBPROOF(m, D[m], true) = {}
La subproof per m = n è il Merkle Tree Hash 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 subproof è allora definita ricorsivamente.
Se m <= k, le voci del sottoalbero destro D[k:n] esistono solo nell'albero corrente. Si dimostra che le voci del sottoalbero sinistro D[0:k] sono coerenti e si aggiunge un commitment 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. Si dimostra che le voci del sottoalbero destro D[k:n] sono coerenti e si aggiunge un commitment 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.
2.1.3 Example (Esempio)
L'albero di Merkle binario con 7 foglie:
hash
/ \
/ \
/ \
/ \
/ \
k l
/ \ / \
/ \ / \
/ \ / \
g h i j
/ \ / \ / \ |
a b c d e f d6
| | | | | |
d0 d1 d2 d3 d4 d5
Il audit path per d0 è [b, h, l].
Il audit path per d3 è [c, g, l].
Il audit path per d4 è [f, j, k].
Il audit path per d6 è [i, k].
Lo stesso albero, costruito incrementalmente in quattro passi:
hash0 hash1=k
/ \ / \
/ \ / \
/ \ / \
g c g h
/ \ | / \ / \
a b d2 a b c d
| | | | | |
d0 d1 d0 d1 d2 d3
hash2 hash
/ \ / \
/ \ / \
/ \ / \
/ \ / \
/ \ / \
k i k l
/ \ / \ / \ / \
/ \ e f / \ / \
/ \ | | / \ / \
g h d4 d5 g h i j
/ \ / \ / \ / \ / \ |
a b c d a b c d e f d6
| | | | | | | | | |
d0 d1 d2 d3 d0 d1 d2 d3 d4 d5
La consistency proof tra hash0 e hash è PROOF(3, D[7]) = [c, d, g, l]. c, g sono usati per verificare hash0, e d, l sono inoltre usati per mostrare che hash è coerente con hash0.
La consistency proof tra hash1 e hash è PROOF(4, D[7]) = [l]. hash può essere verificato usando hash1=k e l.
La consistency proof tra hash2 e hash è PROOF(6, D[7]) = [i, j, k]. k, i sono usati per verificare hash2, e j è inoltre usato per mostrare che hash è coerente con hash2.
2.1.4 Signatures (Firme)
Varie strutture dati sono firmate. Un log DEVE usare firme su curva ellittica con la curva NIST P-256 (Sezione D.1.2.3 del Digital Signature Standard [DSS]) oppure firme RSA (RSASSA-PKCS1-V1_5 con SHA-256, Sezione 8.2 di [RFC3447]) con una chiave di almeno 2048 bit.