Nella terminologia di IOTA vengono indicate come tips le foglie del grafo, cio´e le transazioni che ancora non hanno ricevuto alcuna approvazione e quin- di verso cui non ´e indirizzato alcun arco. In Figura 2.18 la transazione X ´e
´e proprio l’algoritmo che viene utilizzato per scegliere le tip da approvare da parte delle nuove transazioni.
Un concetto importante per comprendere l’algoritmo di scelta delle tips ´e quello del processo di Poisson, che modella una situazione nella quale ab- biamo eventi del tutto indipendenti che avvengono in maniera continua nel tempo. Questo tipo di processo segue la distribuzione di Poisson, che defi- nisce una serie di eventi che si verificano successivamente all’interno di un determinato intervallo di tempo, sapendo che mediamente il numero ´e pari a λ. La probabili´a di avere n eventi in un determinato intervallo di tempo, quando mediamente ne abbiamo λ viene data come:
Pλ(n) =
λn n! · e
−λ
(2.6) Questo processo viene usato per rappresentare una serie consequenziale di eventi random che avvengono all’interno di un intervallo di tempo prefissato, ed ´e utilizzabile per rappresentare l’arrivo delle transazioni al Tangle, sup- ponendo quindi che vi possano essere intervalli in cui ne arrivano un numero maggiore e intervalli in cui non ne arrivano affatto.
Figura 2.19: Arrivo delle transazioni secondo un processo di Poisson [18] Modellando il sistema in questo modo possiamo supporre che, sia l’in- tervallo temporale pari a 1 secondo e il valore di λ = 2 allora mediamente occorranno 50 secondi per effettuare 100 transazioni.
Il Tangle di IOTA inoltre ´e costruito per inserire un delay pari ad h ad ogni transazione; questo delay indica quanto tempo la transazione necessi- ta per essere propagata all’intera rete dopo essere stata effettuata, e quindi
quanti slot temporali ´e necessario attendere prima di poterla confermare. Senza la presenza di questo delay si presenterebbe la possibilit´a per cui, a bassi valori di λ, il DAG diventi una semplice catena dove ogni transazione vede come unica tip la transazione subito precedente e conferma solo quella poich´e non ne trova altre effettuate nello stesso istante temporale che non siano confermate.
Possiamo quindi supporre che per decidere a quale tip collegare una nuova transazione (aggiungendo quindi un arco dalla nuova alla tip) si possa seguire un cammino che parta dalla transazione di genesi e percorra il grafo per valori crescenti dell’asse dei tempi; questo viene detto “unweighted random walk”. Posizionando un “walker” alla transazione di genesi percorriamo quindi il cammino all’indietro scegliendo ogni volta l’arco da seguire; nei casi in cui ad un vertice arrivi pi´u di un arco, e quindi sia confermato da pi´u di una transazione, si suppone inizialmente che siano equiprobabili.
Nel caso riportato in Figura 2.20, partendo dalla tranzazione 0 ci si sposta prima su 1 e poi su 2 con probabilit´a pari ad uno; da 2 abbiamo poi tre transazioni in cui spostarci per cui la probabilit´a di ogni arco ´e pari ad 1/3.
Figura 2.20: Percorso dalla genesi ad una tip seguendo un unweighted random walk [18]
Supponendo che venga scelta 5, l’unica transazione verso cui ci si pu´o spostare sar´a quindi 6, che rappresenta anche una tip, a cui collegare la ge- nerica transazione 13 in arrivo, in quanto le transazioni 9,12,11 sono ancora invisibili a 13 a causa del delay introdotto.
Alternativa a questo algoritmo potrebbe anche essere una selezione com- pletamente casuale della tip da approvare, con le nuove transazioni che ne approvino una completamente causale. Questo porta tuttavia al problema delle cosiddette “lazy-tips”, cio´e quelle che approvano transazioni molto vec- chie invece di quelle recenti (in Figura 2.21, 14 ´e una lazy-tip); questo, usando
sazioni recenti. Una lazy-tip non partecipa attivamente al mantenimento del network in quanto non approva nuove transazioni ma semplicemente immette dati propri sfruttando informazioni molto vecchie.
Figura 2.21: Creazione di una lazy-tip a causa della scelta di un algoritmo di selezione random [18]
Nel caso di un algoritmo casuale una lazy-tip ha la stessa probabilit´a di essere confermata di ogni altra, compromettendo quindi il corretto funziona- mento del sistema. In aggiunta, nel caso in cui venga usato un algoritmo di unweighted random walk, una lazy-tip ha addirittura una probabilit´a pi´u alta di essere approvata rispetto ad una tip recente.
Una soluzione al problema delle lazy-tips potrebbe consistere nell’imporre la conferma solo di transazioni recenti, ma questo sarebbe in contrasto con il concetto di decentralizzazione. La soluzione consiste nel costruire il sistema in modo che il comportamento sia scoraggiato in maniera automatica; per effettuare questa operazione viene utilizzato il cumulative weight delle tran- sazioni.
Il random walk viene quindi polarizzato introducendo una regola secondo la quale ´e pi´u probabile includere nel cammino transazioni con un alto peso cu- mulativo rispetto alle altre. Per un questione di semplicit´a supponiamo che ogni transazione abbia peso pari ad 1, in modo che il suo peso cumulativo sia pari al numero di transazioni che la approvano pi´u uno. Nell’esempio in Figura 2.22 la transazione 16 ´e una lazy-tip per cui, quando il random walker giunge a 7 deve decidere tra 16 e 9, la situazione sar´a la seguente: poich´e 16 ha peso cumulativo pari ad uno mentre 9 pari a sette sar´a molto pi´u probabile che il cammino proceda in quella direzione.
Figura 2.22: Percorso dalla genesi ad una tip seguendo un weighted random walk [18]
Per decidere quanto sia maggiore questa proababilit´a viene usato un para- metro α, che indica sostanzialmente quanto ´e importante scegliere un vertice con peso cumulativo rispetto ad uno inferiore. Se questo valore risulta troppo alto si ha il caso in cui viene sempre scelta la transazione con peso maggiore, inserendo nel grafico una serie di transazioni a peso inferiore che non ver- ranno mai approvate; al contrario se si sceglie un parametro troppo basso si ritorna al caso dell’unweighted random walk e il numero delle lazy-tips diven- ta paragonabile, su base statistica, a quelle normali.
Un metodo di questo tipo, che si basa su una regola che stabilisca la pro- babilit´a di ogni passo in un random walk, ´e definito “Markov Chain Monte Carlo Technique” [19] e non verr´a ulteriormente approfondito.