Pesi cumulativi e passeggiate aleatorie ponderate

Nello scorso articolo abbiamo imparato a conoscere la camminata aleatoria non ponderata, ed oggi conosceremo il suo cugino più avanzato: la passeggiata aleatoria ponderata.

Cominciamo con qualche motivazione per studiarla. Una delle cose che vogliamo che faccia il nostro algoritmo di selezione dei tip, è evitare i tip pigri. Un tip pigro è quello che approva le vecchie transazioni piuttosto che quelle recenti. È pigro perché non si preoccupa di tenere il passo con il più recente stato del Tangle e trasmette solo le proprie transazioni basate su dati vecchi. Questo non aiuta la rete, poiché non vengono confermate nuove transazioni.

Nell’esempio precedente, la transazione 14 è un tip pigro, che approva alcune transazioni molto vecchie. Se usiamo l’algoritmo uniforme di selezione casuale del tip, la transazione 14 ha le stesse probabilità di essere approvata come qualsiasi altra, quindi non viene penalizzata affatto. Utilizzando la passeggiata non ponderata, questo cattivo comportamento è addirittura incoraggiato, almeno in questo particolare esempio.

Come possiamo affrontare questo problema? Una cosa che non possiamo fare è costringere i partecipanti ad approvare solo le transazioni recenti, poiché ciò si scontrerebbe con l’idea della decentralizzazione. Le transazioni possono approvare chi vogliono. Inoltre, non abbiamo un modo affidabile per dire esattamente quando ogni transazione è arrivata, quindi non possiamo applicare una tale regola. La nostra soluzione è quella di costruire il nostro sistema con incentivi integrati contro tale comportamento, in modo che i tip pigri difficilmente saranno approvati da chiunque.

La nostra strategia sarà quella di polarizzare la nostra passeggiata aleatoria, quindi siamo meno propensi a scegliere tip pigri. Useremo il termine peso cumulativo per indicare l’importanza di una transazione. Siamo più propensi a passeggiare verso una transazione pesante rispetto ad una transazione leggera. La definizione di peso cumulativo è molto semplice: contiamo quanti approvatori ha una transazione e ne aggiungiamo uno. Contiamo sia gli approvatori diretti che indiretti. Nell’esempio che segue, la transazione 3 ha un peso cumulativo di cinque, perché ha quattro transazioni che la approvano (5 direttamente; 7, 8 e 10 indirettamente).

Perché funziona? Diamo un’occhiata ad un’altra situazione di tip pigro. Nell’esempio che segue, la transazione 16 è un tip pigro. Al fine per 16 di ottenere l’approvazione, il camminatore casuale deve raggiungere la transazione 7, e quindi scegliere la transazione 16 sulla transazione 9. Ma è improbabile che ciò accada, perché la transazione 16 ha un peso cumulativo di 1, e la transazione 9 ha un peso cumulativo di 7! Questo è un modo efficace per scoraggiare i comportamenti pigri.

A questo punto ci si potrebbe chiedere: abbiamo bisogno di casualità? Possiamo inventare la passeggiata aleatoria super ponderata, dove ad ogni incrocio scegliamo la transazione più pesante, senza alcuna probabilità. Otterremo qualcosa del genere:

La passeggiata super ponderata. Camminiamo sempre verso le transazioni più pesanti

I quadrati grigi sono tip, con zero approvazioni. Anche se è normale avere alcuni tip sull’estremità destra del diagramma, è un problema vederne così tanti sparsi lungo la linea temporale. Questi tip sono transazioni che vengono lasciati indietro e non saranno mai approvati. Questo è il lato negativo nel condizionare troppo la nostra passeggiata: se insistiamo per scegliere solo la transazione più pesante in un dato punto, un’ampia percentuale dei suggerimenti non sarà mai approvata. Ci rimane solo un corridoio centrale di transazioni approvate e di suggerimenti dimenticati a margine.

Abbiamo bisogno di un metodo per definire la probabilità di passeggiare verso un particolare approvatore in un determinato incrocio. La formula esatta che scegliamo non è importante, fintanto che diamo una certa parzialità alle transazioni più pesanti, e abbiamo un parametro per controllare quanto sia forte questa parzialità. Questo introduce il nostro nuovo parametro α, che definisce l’importanza del peso cumulativo di una transazione. La sua esatta definizione si trova nel white paper, e se c’è una richiesta potrei scrivere un post futuro fornendo alcuni dettagli su di esso.

La passeggiata aletoria ponderata: ogni transazione blu mostra il suo peso cumulativo e la sua probabilità di essere scelta come passo successivo della passeggiata.

Se si imposta α a zero, si ritorna alla passeggiata non ponderata. Se si imposta α ad essere molto alto, si ottiene la passeggiata super ponderata. In mezzo, possiamo trovare un buon equilibrio tra il punire i comportamenti pigri e non lasciare alle spalle troppi tip. Determinare un valore ideale per α è un importante argomento di ricerca nello IOTA.

Questo metodo di impostazione di una regola per decidere la probabilità di ogni passo in una passeggiata aleatoria è chiamata tecnica Markov Chain Monte Carlo, o MCMC. In una catena Markov ogni passo non dipende dalla precedente, ma segue una regola che viene decisa in anticipo.

Come sempre, abbiamo una simulazione per dimostrare queste nuove idee. Consigliamo di giocare con i valori di α e λ e di vedere che tipo di Tangle interessanti si possono creare. Nella prossima parte andremo più in dettaglio su cosa significa dire che la transazione A approva la transazione B, e definiremo quando una transazione è considerata confermata.

Parte 1: Introduzione illustrata al Tangle
Parte 2: Tassi di transazione, latenza e passeggiate aleatorie
Parte 4: Approvazioni, saldi e doppie spese
Parte 5: Consenso, fiducia della conferma ed il coordinatore


Il testo originale in lingua inglese si trova qui: https://blog.iota.org/the-tangle-an-illustrated-introduction-f359b8b2ec80


Da oggi è possibile dare il vostro supporto su Patreon https://www.patreon.com/antonionardella

Per ulteriori informazioni in italiano o tedesco trovate i miei contatti a questa pagina.
Se avete trovato utile la mia libera traduzione, accetto volentieri delle donazioni 😉

IOTA:
QOQJDKYIZYKWASNNILZHDCTWDM9RZXZV9DUJFDRFWKRYPRMTYPEXDIVMHVRCNXRSBIJCJYMJ9EZ9USHHWKEVEOSOZB
BTC:
1BFgqtMC2nfRxPRge5Db3gkYK7kDwWRF79

Non garantisco nulla e mi libero da ogni responsabilità.


Also published on Medium.