2.1 Considerazioni sul Pruned Merkle tree Ottimizzazione del Merkle Hash Tree C 2

28

C

2

Ottimizzazione del Merkle Hash Tree

In questo capitolo saranno presentati due metodi, computazionalmente migliori di quello usato da CECInA, per la verifica dei payload packets. Si descriverà, inoltre, la procedura per un ulteriore sfoltimento del Pruned Merkle Tree.

2.1 Considerazioni sul Pruned Merkle tree

Consideriamo nuovamente la costruzione del Pruned Merkle Tree [6] (trattata nel primo capitolo). Proveremo ad analizzarlo da più punti di vista, mettendo in risalto le caratteristiche principali che porteranno alla costruzione dei pacchetti ed alla loro successiva identificazione, ad un ulteriore sfoltimento degli shares nei pacchetti per arrivare infine a metodi d’ordinamento nella consegna dei pacchetti alla rete.

Si assumerà di seguito, senza perdita di generalità, che n = 2t con t ≥ 1. Sia, inoltre, H(•) la funzione hash usata [7], come ad esempio SHA-1 [8].

Sia z = r + 1 (r è il numero di pacchetti ridondanti), un parametro che modella la perdita dei pacchetti sui canali di comunicazione, mentre assicura che almeno un pacchetto possa raggiungere la destinazione.

29

Figura 6: Esempio di Merkle tree, per n = 16 payload packets.

P0 = {0, S0, v16, v8, v4, v2} P1 = {1, S1, v15} P2 = {2, S2, v18, v7} P3 = {3, S3, v17} P4 = {4, S4, v20, v10, v3} P5 = {5, S5, v19} P6 = {6, S6, v22, v9} P7 = {7, S7, v21} P8 = {8, S8, v24, v12, v6, v1} P9 = {9, S9, v23} P10 = {10, S10, v26, v11} P11 = {11, S11, v25} P12 = {12, S12, v28, v14, v5} P13 = {13, S13, v27} P14 = {14, S14, v30, v13} P15 = {15, S15, v29}

Figura 7: Pruned Packets per il Merkle Tree in Fig. 6, con z = 1.

P0 = {0, S0, v16, v8, v4, v2} P1 = {1, S1, v15, v8, v4, v2} P2 = {2, S2, v18, v7, v4, v2} P3 = {3, S3, v17, v7} P4 = {4, S4, v20, v10, v3} P5 = {5, S5, v19, v10, v3} P6 = {6, S6, v22, v9, v3} P7 = {7, S7, v21, v9} P8 = {8, S8, v24, v12, v6, v1} P9 = {9, S9, v23, v12, v6, v1} P10 = {10, S10, v26, v11, v6, v1} P11 = {11, S11, v25, v11} P12 = {12, S12, v28, v14, v5} P13 = {13, S13, v27, v14, v5} P14 = {14, S14, v30, v13, v5} P15 = {15, S15, v29, v13}

30

Prima d’addentrarsi nel merito d’eventuali ottimizzazioni, occorre definire delle notazioni preliminari, facendo riferimento, quando occorre maggiore chiarezza, al Merkle tree di Fig. 6.

Un insieme di n simboli Si induce alla costruzione d’altrettanti payload packets Pi del relativo Merkle tree. La profondità (o altezza) dell’albero è log n, per un totale di n+(n-1) nodi, di cui n sono foglie ed n-1 nodi interni (chiamati shares).

Ai nodi vi sono assegnati gli indici i ∈ [0,…, n+(n-2)] in modo crescente, cominciando dalla radice e proseguendo dall’alto verso il basso e da sinistra a destra, cosicché la radice sarà sempre v0.

I figli di uno share vi (che sarà, in questo caso, il padre) sono i due nodi di livello immediatamente successivo connessi direttamente con vi: v2i+1 il figlio sinistro e

v2i+2 il figlio destro.

Si definisce nodo fratello di vi quel nodo che ha in comune lo stesso padre. In particolare, se i è dispari il fratello sarà vi+1, mentre se i è pari sarà vi-1.

Nell’esempio di Fig. 6, in cui n = 16, il Merkle tree è alto 4 (log 16), composto da 31 nodi, di cui 16 sono foglie e 15 sono shares. La radice v0 ha due nodi figli: v1 e

v2, che a loro volta sono radici, rispettivamente, dei sottoalberi sinistro e destro di

v0.

Un simbolo Si (con i ∈ [0,…,n-1]) è associato, in ordine crescente da sinistra a destra, ad un corrispettivo nodo foglia del Merkle tree; le foglie, infatti, rappresentano il valore hash H(Si) del relativo simbolo. Si noti che il primo nodo foglia (posto a livello log n) è vn-1; di conseguenza, nella costruzione del Merkle

tree, la foglia vi+n-1 deterrà il valore di H(Si). In riferimento alla Fig. 6, il simbolo

S0 sarà associato al primo nodo foglia v15 = H(S0), mentre ad S2 sarà associato v17 = H(S2).

Ogni payload packet Pi, oltre al simbolo Si, porta con sé i witness (nodi vi del Merkle tree) necessari per l’autenticazione del simbolo stesso. Il numero di witness dipenderà dal parametro z e varia da pacchetto a pacchetto. Studiando le affinità trai i payload packets si può notare che due pacchetti Pi e Pi+1, con i pari o

31

uguale a 0, contengono due nodi foglia fratelli: rispettivamente vi+n in Pi e vi+n-1 in

Pi+1. Nel seguito si adotterà il termine contiguo per descrivere il pacchetto Pi (oppure Pi+1) rispetto a Pi+1 (ovvero Pi) che rispecchi tale proprietà. In Fig. 8, i pacchetti contigui sono (P0, P1), (P2, P3), (P8, P9) e cosi via.

I payload packets che trasportano l’insieme completo dei witness (CWS – Complete Witness Set) saranno definiti CWS packets.

La costruzione del PMT è indotta da una regola di assegnamento degli shares nei pacchetti che segue un modello leftmost [6]. Ogni share vi è necessario in η

pacchetti per formare il loro CWS. Con il metodo leftmost ogni share sarà replicato in min{η,z} pacchetti, in modo tale da diminuire la ridondanza introdotta dal Merkle Tree, mentre sarà sempre assicurata la ricostruzione, da parte del destinatario, del CWS di ogni legittimo pacchetto, anche in presenza di un attacco DoS con iniezione di pacchetti. La regola d’assegnamento leftmost induce la costruzione di esattamente 2z CWS packets: i primi z dei rispettivi sottoalberi di radice v1 (come dimostrato nel lemma 4 in [6]) e v2; in particolare, saranno Pi, con 0 ≤ i ≤ z–1, e Pj, con n/2 ≤ j ≤ n/2+z–1. In Fig. 8, per esempio, dove z = 3 e n = 16, i CWS packets sono Pi, con 0 ≤ i ≤ 2, e Pj, con 8 ≤ j ≤ 10.

Si vedrà, di seguito, una procedura di sfoltimento del Merkle tree che indurrà, tra l’altro, l’eliminazione di uno share dai primi z payload packets del sottoalbero di radice v2 (facendogli perdere la proprietà dei CWS packets), in modo da assicurare, comunque, l’autenticazione di tutti i payload packets in arrivo.

I CWS packets sono essenziali per l’autenticazione degli altri pacchetti e per questo, indipendentemente dal loro grado di ridondanza, è necessario che almeno uno arrivi al destinatario prima di tutti gli altri payload packets10. Nel caso che, per ipotesi, non arrivi nessun CWS packet, il destinatario dovrebbe concatenare gli shares dei pacchetti già ricevuti per ottenere gli shares mancanti, ma nel caso

10 _{Anche quando il mittente li invia per primi, il loro arrivo è sempre legato ad eventuali ritardi di} comunicazione.

32

di un injection attack [6] quest’operazione potrebbe richiedere un tempo polinomiale (ma non lineare) nel numero di pacchetti invalidi.

S’illustrerà di seguito come potere eseguire uno sfoltimento del PMT senza aumentare la complessità di riconoscimento dei simboli, ma prima saranno presentate delle procedure d’autenticazione computazionalmente più efficienti di quella che fa uso della funzione Root [6].

2.2 OHA – One Hash Authentication

Il destinatario sfrutterà la proprietà dei payload packets contigui Pi e Pj (con |i – j| = 1) per velocizzare il controllo dei simboli. Tale proprietà si basa sulla particolarità che Pi e Pj contengono due nodi (witness) fratelli, rispettivamente

vj+n-1 e vi+n-1, che sono che gli hash dei simboli che i pacchetti trasportano. In particolare, H(Si) = vi+n-1 (il witness contenuto in Pj) mentre H(Sj) = vj+n-1 (il witness contenuto in Pi).

Si ricordi che nel momento in cui un payload packet Pi è autenticato, lo sono anche i witness che trasporta.

33

Si descriverà nel dettaglio, partendo da quest’ultima notazione, la procedura d’autenticazione del payload packet Pj contiguo a Pi, con v' fratello di v'':

1. Pi = {i, Si, v', V} è stato precedentemente autenticato, dove V è l’insieme di altri eventuali witness contenuti nel pacchetto;

2. Alla ricezione del payload packet Pj = {j, Sj, v'', V'} contiguo al precedente, si calcolerà H(Sj);

3. Si confronterà il valore di H(Sj) con v' e se sono uguali il payload packet

Pj, e quindi il simbolo ed i witness che trasporta, sono autenticati; nel caso contrario il pacchetto Pj è corrotto e può essere eliminato.

Se il precedente controllo dà esito positivo, allora il pacchetto Pj è autenticato con

il solo costo del calcolo di un hash.

Un esempio servirà a far capire a fondo questo meccanismo d’autenticazione dei simboli.

In Fig. 10 è rappresentato un Merkle tree di altezza 4 in cui sono evidenziati i nodi interessati all’autenticazione del payload packet (vedi Fig. 8) legittimo P0 = {0, S0,

v16, v8, v4, v2} che, si supponga, sia il primo pacchetto ricevuto dal destinatario. In particolare, i nodi quadrati sono quelli inclusi nel pacchetto, mentre i nodi ottagonali sono ricavati dall’unione dei nodi figli, dal basso verso l’alto, mano a mano che si procede con la verifica.

34

Figura 10: Nodi quadrati e ottagonali attinenti all'autenticazione di P0, per n = 16 pacchetti e

z = 3.

Il pacchetto P0 ha il suo CWS, che garantisce l’autenticazione del simbolo S0 senza il bisogno d’ulteriori witness d’altri pacchetti. La verifica di P0 necessita della radice v0 dell’albero che, se è stata in precedenza identificata attraverso un signature packet, permette di inserire i nodi quadrati e ottagonali (oltre a v15) nell’insieme M dei Merkle shares autenticati. Il payload packet contiguo di P0 è P1 = {1, S1, v15, v8, v4, v2}: infatti, si avrà che v15 in P1 è il nodo fratello di v16 in P0. Nel momento in cui il destinatario riceverà il payload packet P1, potrà applicare immediatamente il metodo di riconoscimento descritto in precedenza. In particolare, calcolerà H(S1) e lo confronterà con v16. Se il confronto dà esito positivo, il pacchetto P1 è autenticato senza ulteriori costi, altrimenti sarà eliminato poiché si è dimostrato essere corrotto.

Si chiamerà questa procedura OHA – One Hash Authentication.

Poiché bisogna che sia già stato autenticato uno dei due witness fratelli dei pacchetti contigui, è evidente che questo procedimento non può essere usato per

35

tutti i payload packets. Alla meglio, quindi, si potranno autenticare, con il solo costo del calcolo dell’hash di un simbolo, n/2 payload packets.

2.3 LRA – Lowering Root Authentication

Il metodo OHA sarà rielaborato in modo da potere essere adottato per i rimanenti

n/2 simboli. Dopo l’autenticazione di un payload packet, gli hash che esso

trasporta saranno di conseguenza autenticati e memorizzati dal destinatario. L’idea è di verificare i pacchetti in arrivo, non rispetto alla radice v0, ma sulla base degli hash precedentemente memorizzati.

Sinora, il destinatario, per autenticare un payload packet ricevuto (che non permette l’utilizzo di OHA), doveva eseguire la funzione Root, che consiste nel calcolare l’hash delle concatenazioni dei witness “fratelli” (in parte inclusi nel payload packet), nel percorso che va dall’hash del simbolo alla radice v0. Nell’esempio di Fig. 10, per autenticare P0, il destinatario deve calcolare il valore

H(H(H(H(H(S2)|v16)|v8)|v4)|v2) e confrontarlo con la radice v0 del PMT. Se il confronto dà esito positivo, allora il pacchetto è autenticato. Questo tipo d’autenticazione, in realtà, è necessario solo la prima volta, quando l’insieme M dei Merkle shares autenticati è ancora vuoto. Per i successivi payload packets, infatti, si sfrutta l’autenticazione degli shares (contenuti in M) eseguita in precedenza.

In particolare, sia Pi il payload packet da autenticare: qualora non fosse possibile attuare il metodo OHA, il procedimento da seguire sarà uguale a quello implementato da Root, con la differenza che, invece di risalire sino alla radice v0 per il confronto, ci si fermerà al primo share vj (autenticato precedentemente), come se questo fosse effettivamente la radice cercata.

Per esempio (in riferimento alla Fig. 8), si assuma che dopo il payload packet P0, il secondo pacchetto ricevuto dal destinatario sia P2 = {2, S2, v18, v7, v4, v2}; non

36

potrà applicare OHA, poiché lo share v17 (fratello di v18), contenuto nel pacchetto contiguo P3, non è stato ancora autenticato. Si ha una situazione, infatti, in cui M = {v15 = H(S0), v16, v8, v4, v2, v7 = H(v15|v16), v3 = H(v7|v8), v1 = H(v3|v4), v0}. Il destinatario procederà, allora, ad individuare il primo share autenticato, nel percorso che va da v17 alla radice v0. Lo share in questione sarà v8 (vedi Fig. 10), che in pratica si sostituisce a v0 nella fase d’autenticazione. Il ricevente verificherà che v8 = H(H(S2)|v18); questo gli basterà per decidere se il payload packet P2 è legittimo o corrotto, con due calcoli della funzione hash in meno.

Il procedimento appena descritto equivale, in generale, ad “abbassare” virtualmente la radice dell’albero mano a mano che si autenticano i pacchetti in arrivo. Per il pacchetto P4 (dopo l’autenticazione di P0 e P2), ad esempio, il nodo di riferimento per l’autenticazione sarà v4, che equivale ad abbassare la radice v0 dell’albero di due livelli.

Riassumendo, il metodo può essere descritto dai seguenti passi:

1. Alla ricezione del payload packet Pi, il destinatario controllerà se esistono i presupposti per l’applicabilità di OHA, cioè se è stato autenticato il pacchetto contiguo di Pi. In questo caso si applicherà OHA per la verifica. 2. Qualora la procedura OHA non fosse adottabile, il destinatario risalirà il

Merkle tree, partendo dal nodo foglia vi+n-1 associato al pacchetto Pi, sino al primo nodo antenato vj (posto ad altezza t) che appartenga all’insieme

M.

3. Partendo dal nodo vi+n-1, il destinatario calcolerà gli hash (stesso procedimento della funzione Root) dei nodi necessari, secondo la costruzione del Merkle tree, per tentare d’ottenere il valore di vj =

H(v2j+1|v2j+2). Se il valore risultante è uguale a quello di vj contenuto in M, vorrà dire che il payload packet Pi è legittimo, ed è stato autenticato con t calcoli della funzione hash in meno di quelli previsti dalla funzione Root. In caso contrario Pi è considerato corrotto e sarà eliminato dal destinatario. Si chiamerà questa procedura LRA – Lowering Root Authentication.

37

2.4 Complessità di OHA e LRA

Si assuma che la fase di decodifica usi hash di h bits, e che il dato D, trasmesso dal mittente, sia di d bits, codificato con IDA di parametri n e r in simboli di d/n bits.

I metodi OHA e LRA saranno usati dal destinatario per verificare l’autenticità dei payload packets ricevuti. Il metodo OHA permette l’autenticazione di un pacchetto Pi a patto della previa autenticazione del pacchetto contiguo Pj; la procedura, quindi, potrà essere usata al massimo sulla metà dei pacchetti ricevuti. OHA prevede solo il calcolo della funzione hash sul simbolo: la complessità sarà, di conseguenza, O(d/n).

Il metodo LRA richiede una discussione più approfondita, poiché prevede che pacchetti diversi siano autenticati con complessità differenti.

La complessità della funzione Root [6] è data dal costo per valutare l’hash del simbolo incluso nel pacchetto (O(d/n)), più gli hash dei Merkle shares necessari per calcolare la radice (h log n). Posto C(k) = O(d/n + h·k), dove k indica il numero di applicazioni della funzione hash, la complessità di Root sarà C(log n), con (log n) uguale all’altezza del Merkle tree. Se, per esempio, la verifica di un payload packet, con il metodo LRA, facesse riferimento ad uno share vj (per il confronto) posto a livello t del Merkle tree, invece che alla radice v0, la complessità d’autenticazione del pacchetto sarebbe C(log n – t); questo permette il risparmio di t calcoli della funzione hash rispetto all’applicazione di Root.

Si ricordi che il metodo sarà usato sulla metà dei payload packets, ricevuti dal destinatario, sui quali non è applicabile OHA.

Il primo payload packet che il destinatario verificherà (quando l’insieme M dei Merkle shares autenticati è ancora vuoto) richiederà un costo C(log n), poiché si dovrà risalire sino alla radice per il confronto. Gli shares che di conseguenza saranno autenticati, si sostituiranno alla radice nella verifica dei rimanenti payload packets.

38

Si è detto come l’applicazione di LRA equivalga ad abbassare, in un certo senso, la radice del Merkle tree, prendendo in considerazione, al suo posto, uno share intermedio, che sarà diverso per ogni gruppo di pacchetti; in effetti è come se si avessero più alberi (sottoalberi del Merkle tree), differenti d’altezza e radice. Ogni autenticazione di un payload packet indurrà a riconsiderare l’insieme dei sottoalberi del Merkle tree. In Fig. 10 è rappresentato un Merkle tree d’altezza log

n = 4, con n = 16 payload packets; con riferimento a P0, i nodi quadrati sono i witness inclusi nel pacchetto stesso. Dopo l’autenticazione di P0 (con un costo

C(4)), questi nodi rappresenteranno le radici dei nuovi sottoalberi che coprono

tutti i pacchetti ancora da autenticare (vedi Fig. 11). Il Merkle tree d’altezza 4 darà vita a 3 sottoalberi d’altezza crescente da uno a tre; v16 è il nodo relativo al payload packet P1 contiguo a P0, che sarà autenticato usando la procedura OHA. L’autenticazione successiva di un altro pacchetto, appartenente ad un sottoalbero d’altezza l, avrà un costo C(l) e provocherà la disgregazione del sottoalbero che lo contiene in l-1 nuovi sottoalberi.

Figura 11: Sottoalberi ricavati dalla procedura LRA dopo la prima iterazione.

39

Si procederà, ricorsivamente, all’applicazione del metodo d’autenticazione sino a quando non saranno verificati tutti i payload packets (situazione in cui non si potranno più creare nuovi sottoalberi). Ogni nuova iterazione corrisponde all’autenticazione di un pacchetto ed alla creazione di nuovi sottoalberi (sino a quando è possibile). Nell’esempio, alla fine dell’autenticazione di tutti i payload packets, saranno stati creati in totale 4 sottoalberi d’altezza 1, 2 sottoalberi d’altezza 2 ed 1 sottoalbero d’altezza 3, per un costo totale di 4·C(1) + 2·C(2) +

C(3) + C(4). Si noti come la somma dei pacchetti autenticati11 sia n/2 (4+2+1+1=8). LRA ha permesso di risparmiare circa la metà dei calcoli hash rispetto all’applicazione, per le verifiche di tutti i pacchetti, della funzione Root. In particolare, in merito al variabile numero di calcoli hash previsti dalla funzione

C(•), si ha la seguente situazione:

Root 8·C(4) Æ 32 hash

LRA 4·C(1) + 2·C(2) + C(3) + C(4) Æ 15 hash

Questo modo di vedere l’autenticazione dei pacchetti induce a calcolare facilmente la complessità di verifica di n/2 dei payload packets per i quali è usato il metodo LRA:

C(log n) + ∑i=1...log n - 1 2i-1·C(log n – i).

Da notare come (1 + ∑i=1...log n -1 2i-1) = (1 + ∑i=0...log n -2 2i) = 2log n -1; poiché 2log n = n Ù 2log n -1 = n/2, ne consegue che (1 + ∑i=1...log n -1 2i-1) = n/2, cioè il numero dei

payload packets legittimi autenticabili con LRA; per gli altri n/2 (i pacchetti contigui a quelli autenticati) si adotterà il metodo OHA. Inoltre, è evidente dalla seguente disuguaglianza

[C(log n) + ∑i=1...log n - 1 2i-1·C(log n – i)] < [n/2·C(log n)]

40

come il metodo LRA permetta di risparmiare circa la metà dei calcoli hash rispetto all’applicazione della funzione Root.

Nel seguito si assumerà che il costo, approssimato superiormente12, per il controllo di un payload packet sia

CLRA = C( (log n)/2 ) = O(d/n + h·(log n)/2),

dove (log n)/2, nel caso che (log n) sia dispari, si intende approssimato all’intero superiore.

2.5 Sfoltimento del Pruned Merkle Tree

La regola leftmost usata per la costruzione dei payload packets, come già anticipato precedentemente, porterà alla costruzione di 2z CWS packets; si vedrà come sia necessario conservare la proprietà dei CWS packets solo nei pacchetti Pi, 0 ≤ i ≤ z–1.

L’idea alla base del procedimento di sfoltimento è di sfruttare le informazioni contenute nei primi z pacchetti P0, …, Pz-1 (con CWS). Ogni pacchetto di questo tipo contiene esattamente log n witness che permettono a loro volta di autenticarne altrettanti13 (vedi Fig. 10).

Si assumerà, nel seguito, che z ∈ [1,…,n/2] e che un attaccante possa cancellare al massimo z – 1 pacchetti. Questo implica che almeno un CWS packet legittimo, dell’insieme {P0, …, Pz-1}, arriverà a destinazione.

In generale gli shares sono calcolati come l’hash dell’unione dei loro figli. Di conseguenza quando si è sicuri di recuperare e quindi autenticare gli shares figli, il nodo padre può essere tranquillamente omesso dai pacchetti.

In precedenza si è accennato ai sottoalberi del Merkle tree; visto che avranno un ruolo fondamentale nello sfoltimento del PMT, si vedranno di seguito alcune loro

12 _{L’approssimazione nel numero di calcoli della funzione hash non andrà ad influenzare il costo} totale per la ricostruzione dell’informazione inviata dal mittente.

41

proprietà. Dato un Merkle tree T, con n foglie, un suo sottoalbero è costituito da un generico nodo vi e da tutti i suoi discendenti; vi è la radice del sottoalbero. Ne consegue che ogni nodo interno di T ha esattamente due sottoalberi (sinistro e destro); in particolare, il nodo vi ha un sottoalbero sinistro di radice v2i+1 e uno destro di radice v2i+2. Se vi è posto ad altezza l rispetto a T, il relativo albero avrà profondità (log n – l). Nel seguito si userà la notazione sottoalbero vi per indicare il sottoalbero, del Merkle tree, di radice vi.

La regola base della procedura di sfoltimento è di lasciare intatti, dopo la costruzione del PMT con il metodo leftmost, i primi z payload packets P0, …, Pz-1 (con CWS) perché, come già discusso nel paragrafo (1.7.4), il tempo per l’autenticazione dei pacchetti diventerebbe polinomiale (non lineare).

Si vedrà come il figlio sinistro della radice dell’albero e dei relativi sottoalberi, sotto determinate condizioni, sarà sicuramente autenticato dal primo gruppo di z pacchetti associati alle prime z foglie dell’albero (o sottoalbero) in questione. Di conseguenza il nodo può essere omesso, in fase di costruzione del Merkle tree, dai restanti pacchetti, perché risulta essere ridondante. Si proverà, con un esempio, a chiarire meglio questo concetto, facendo riferimento alla Fig.12. Supponendo di avere una ridondanza z = 2, il nodo v1 (figlio sinistro della radice v0) è contenuto nei payload packets P2 e P3, secondo la costruzione leftmost. Dato che, per ipotesi, possono essere persi z – 1 pacchetti, almeno uno tra P0 e P1 sarà ricevuto dal destinatario; da questo ne consegue che il nodo v1 sarà sicuramente autenticato grazie ad uno dei primi due pacchetti, rendendolo ridondante in P2 e P3, dai quali può essere omesso.

42

Figura 12: Merkle tree per n = 4 payload packets.

Lemma 1: Sia dato un Merkle tree T, d’altezza log n, per n payload packets e il

parametro z ∈ [1,…,n/2]. Si considerino, inoltre, i sottoalberi di T con radice vt ed

altezza l, tale che 2l > z. Sia S(t) = 2t + 1 il figlio sinistro del nodo vt. Il mittente

può sfoltire i payload packets Pz, …,Pn-1 omettendo da essi i nodi v1 e vS(t),

ridondanti ai fini dell’autenticazione.

Dimostrazione: Si analizzerà lo sfoltimento dei pacchetti dopo la costruzione,

da parte del mittente, del PMT e dei relativi payload packets con il metodo

leftmost.

La condizione 2l > z serve per assicurarci che un pacchetto non sia sfoltito più del necessario, cosa che impedirebbe la sua autenticazione da parte del ricevente. Considerando un sottoalbero d’altezza l con (di conseguenza) 2l payload packets, in una situazione in cui z > 2l, l’arrivo di questi pacchetti non è assicurato. Dato che la verifica di un payload packet Pi sfoltito sfrutta l’autenticazione di alcuni dei 2l – 1 pacchetti, se quest’ultimi non arrivassero a destinazione, Pi non potrebbe essere controllato.

Data la natura ricorsiva del lemma, si dimostrerà la sua validità per induzione sull’altezza dell’albero.

CASO BASE 1: Si consideri il Merkle tree per n = 2 payload packets, come in

43

Figura 13: CASO BASE 1. Merkle tree per n = 2 payload packets, con z = 1.

I due payload packets sono P0 = {0, S0, v2} e P1 = {1, S1, v1}. Assumiamo che il valore di z sia, in linea con la definizione del suo campo d’esistenza, uguale a 1; questo significa che la comunicazione è completamente sicura poiché non è prevista nessuna perdita di pacchetti (ipotesi poco realistica). In questo caso il nodo v1 può essere omesso da P1, poiché P0 sarà sicuramente ricevuto dal destinatario che autenticherà il simbolo S1 e il witness v1 trasportati dal pacchetto. Se z > 1 i payload packets non possono essere sfoltiti, dato che si violerebbe la condizione principale 2l > z, con l = 1.

CASO BASE 2: Si consideri il Merkle tree per n = 4 payload packets, come in

figura sottostante. L’albero ha profondità 2 ed ha due sottoalberi, rispettivamente di radice v1 e v2, mentre i payload packets sono quattro: P0,…,P3 (vedi Fig. 15).

44 z = 1 z = 2 P0 = {0, S0, v4, v2} P1 = {1, S1, v3} P2 = {2, S2, v6, v1} P3 = {3, S3, v5} P0 = {0, S0, v4, v2} P1 = {1, S1, v3, v2} P2 = {2, S2, v6, v1} P3 = {3, S3, v5, v1}

Figura 15: Pruned Packets Ridotti per il Merkle tree in Fig. 14.

Lo sfoltimento dei pacchetti sarà eseguito prendendo in considerazione uno (Merkle tree completo) o tre alberi (Merkle tree e i due sottoalberi), in funzione del valore di z. Di seguito si analizzeranno nel dettaglio questi casi:

1. Nella prima fase si sfoltiscono i pacchetti relativi al Merkle tree completo, prendendo in considerazione il nodo v1. In questo caso i CWS packets da lasciare inalterati sono {P0} se z = 1, {P0, P1} se z = 2, oppure {P0, P1, P2} se z = 3. Lo share v1 è antenato delle prime 2 foglie (associate ai primi 2 pacchetti). Poiché lo share in questione sarà autenticato, dopo l’esecuzione della funzione Root su uno qualsiasi dei legittimi CWS packets P0,...,Pz–1, come concatenazione dei suoi figli v3 e v4, v1 può essere omesso dai pacchetti Pz,…,P3 in cui viene ospitato.

2. I due sottoalberi del Merkle tree completo sono alti l = 1, con 2 payload packets a testa (vedi Fig. 14); saranno presi in considerazione, per lo sfoltimento, solo nel caso che z = 1, nel rispetto della condizione 2l > z. Per quanto riguarda il sottoalbero v1, il nodo S(t=1) da considerare è v3. In questa situazione (in cui z = 1) il canale è considerato sicuro e v3 sarà certamente autenticato da P0; ne consegue che v3 può essere omesso dal payload packet P1. Per il sottoalbero v2, il nodo S(t=2) da considerare è v5. Dopo la riduzione della fase precedente, i 2 payload packets relativi alle foglie v5 e v6 saranno, rispettivamente, P2 = {2, S2, v6} e P3 = {3, S3, v5}, in cui si può notare la mancanza del witness v1 rispetto alla loro originale costruzione con il metodo leftmost. Anche qui si ripete la situazione

45

verificatasi per il sottoalbero precedente, e per lo stesso motivo v5 sarà omesso dal pacchetto P3.

Nel caso che z > 3 nessun payload packets può essere sfoltito poiché non sarà rispettata la condizione 2l > z, neanche per il Merkle tree completo con l = 2.

CASO INDUTTIVO: Supponendo il lemma vero per il Merkle tree d’altezza m, si

dimostrerà la sua veridicità per il Merkle tree d’altezza m+1. Si può subito notare che la radice v0 di quest’albero ha come figli due sottoalberi, di radice rispettivamente v1 e v2, d’altezza m. Supponendo che questi sottoalberi abbiano n payload packets a testa, il Merkle tree d’altezza m+1 avrà, di conseguenza, 2n payload packets.

Lo share v1 è antenato delle prime z foglie associate ai primi z CWS packets. Ricordando che, per ipotesi, si possono perdere al massimo z – 1 pacchetti, il destinatario riceverà sicuramente almeno un CWS packet. L’autenticazione di uno di questi causerà la conseguente autenticazione di v1, che sarà omesso, se z < n, dai pacchetti Pn,…,Pn+z–1, oppure, nel caso che z ≥ n, dai pacchetti Pz,…,P2n–1 in cui v1 viene ospitato.

Nel caso che z < n si prenderanno in considerazione, per i successivi sfoltimenti, sia il sottoalbero di radice v1 che il sottoalbero v2. Se z ≥ n, invece, non si potranno più effettuare riduzioni, poiché tutti i sottoalberi del Merkle tree violerebbero la condizione 2l _{> z, con l l’altezza dei sottoalberi vagliati.}

Il discorso andrebbe esteso a tutti i sottoalberi di altezza l ∈ [1,...,m] (con 2l _{> z)}

ma, poiché questi sono presi in considerazione dai sottoalberi di radice v1 e v2, per cui è valida l’applicazione del lemma per ipotesi induttiva, si può dedurre che il lemma è valido anche per il Merkle tree d’altezza m+1 con 2n payload packets. ▄

Si mostrerà, con un esempio, l’applicazione di questa procedura con un Merkle tree per n = 16 pacchetti e con parametro z = 3 (vedi Fig. 16-17).

In Fig. 17 si possono notare i payload packets sfoltiti, rispetto alla loro precedente costruzione con il metodo leftmost, mentre sono lasciati intatti i CWS packets P0,

46

P1, P2. La procedura di sfoltimento inizia prendendo in considerazione lo share v1, figlio sinistro della radice del Merkle tree; v1 è antenato delle prime z = 3 foglie14, in accordo al passo induttivo della precedente dimostrazione. Quest’ultima proprietà, unitamente all’assicurazione cha almeno uno dei primi z CWS packets arriverà a destinazione, garantirà l’autenticazione dello share v1 da parte del destinatario, rendendo così ridondante l’informazione v1 nei pacchetti P8, P9 e P10. Nei passi successivi si prenderanno in considerazione i sottoalberi d’altezza decrescente l ∈ [3,2], nel rispetto della condizione 2l _{> 3. Per il sottoalbero v}

2,

S(2)=5 è l’indice del figlio sinistro di v2, cioè lo share v5. I pacchetti relativi alle foglie del sottoalbero v2 sono P8,…,P15; si noti come P8, P9 eP10 abbiano CWS rispetto al sottoalbero v2. Almeno uno di questi tre payload packets, poichè z = 3, raggiungerà il destinatario che provvederà all’autenticazione del simbolo e degli shares che il pacchetto trasporta, compreso v5 che sarà omesso, in fase di costruzione dei pacchetti, da P12, P13, P14 perché ridondante. Allo stesso modo sarà omesso dai pacchetti P4, P5 e P6 lo share v3, figlio sinistro del nodo v1 che a sua volta è la radice dell’altro sottoalbero di altezza 3 del Merkle tree. Quando si analizzeranno i quattro sottoalberi di altezza 2, saranno omessi, dai pacchetti che li contengono, gli shares v7, v9, v11, v13 poichè saranno autenticati da uno dei primi tre pacchetti che usano lo share in questione per la loro autenticazione.

47

Figura 16: Merkle tree per n = 16 payload packets; gli shares in rosso sono quelli interessati nella procedura di sfoltimento.

P0 = {0, S0, v16, v8, v4, v2} P1 = {1, S1, v15, v8, v4, v2} P2 = {2, S2, v18, v7, v4, v2} P3 = {3, S3, v17, v7} P4 = {4, S4, v20, v10, v3} P5 = {5, S5, v19, v10, v3} P6 = {6, S6, v22, v9, v3} P7 = {7, S7, v21, v9} P8 = {8, S8, v24, v12, v6, v1} P9 = {9, S9, v23, v12, v6, v1} P10 = {10, S10, v26, v11, v6, v1} P11 = {11, S11, v25, v11} P12 = {12, S12, v28, v14, v5} P13 = {13, S13, v27, v14, v5} P14 = {14, S14, v30, v13, v5} P15 = {15, S15, v29, v13}

Figura 17: Pruned Packets Sfoltiti per il Merkle Tree in Fig. 16, con z = 3.

Gli z payload packets Pn/2, …, Pn/2+z-1 (associati alle prime z foglie del sottoalbero

v2) non avranno più CWS (per via dell’eliminazione del nodo v1) ed il numero di shares che trasporteranno sarà quindi (log n) – 1. Lo share v2 sarà trasportato dai

48

CWS packets15 P0, …,Pz-1, che ne garantiranno l’autenticazione (giacché, per ipotesi, almeno uno degli z pacchetti arriverà a destinazione).

Nell’esempio, in cui si ha un Merkle tree per n = 16 pacchetti e z = 3 , si è riuscito a risparmiare 13 shares.

La procedura di sfoltimento sarà applicata dal mittente in sincronia alla costruzione dei pacchetti con la regola d’assegnamento leftmost, per evitare piccoli sprechi computazionali derivanti dall’ulteriore riduzione dei pacchetti immediatamente dopo la loro costruzione.

Lo sfoltimento del PMT può essere riassunto nei seguenti passi:

1. I primi z payload packets P0, …, Pz-1 saranno lasciati intatti: avranno CWS; 2. Si ometterà lo share v1 dai payload packets Pn/2, …, Pn/2+z-1;

3. S’identificheranno tutti i sottoalberi del Merkle tree d’altezza l che rispettano il vincolo 2l > z;

4. Per ogni sottoalbero di radice vt, si consideri il figlio sinistro vS(t) della

radice. Si ometterà vS(t) dai payload packets Pz, …,Pn-1 che lo contengono.

Questa procedura induce a costruire quello che chiameremo “Pruned Merkle Tree

Reduced” (PMTR).