Game theoretical analysis of DAG-ledgers backbone

Blockchains are one of the most appealing technologies over the last years, both for scientists and the general public. Blockchains are distributed ledgers that aim to offer transparency, integrity and many more advantages over their centralised counterparts. Blockchains were “revealed” and became popular thanks to the creation and rise of the cryptocurrency Bitcoin. Over the years, blockchain technologies become more and more popular with an exceptional peak in 2017. However there are some limits in the classical blockchain structure such as scalability and high transaction fees that represent strong barriers for a lot of applications. Among the traditional blockchain alternatives, an interesting class is the DAG-based blockchains, in which the sequential list of blocks is substituted by a Directed Acyclic Graph. DAG-based blockchains have many advantages, for example, they do not need huge computations to work, and they guarantee consistency under known conditions by relying on research from distributed systems. In this thesis, we propose $DAG$-based protocols that can be used as black box for DAG-based ledgers. We study the rational behaviours of participants in DAG-based Distributed Ledgers. We analyze generic algorithms that encapsulate the main actions of participants in a DAG-based distributed ledger: voting for a block, and checking its validity. Knowing that those actions have costs, and validating a block gives rewards to users who participated in the validation procedure, we study using game theory how strategic participants behave while trying to maximize their gains. We consider scenarios with different type of participants and investigate if there exist equilibria where the properties of the protocols are guaranteed. The analysis is focused on the study of equilibria with trembling participants (i.e. rational participants that can do unintended actions with a low probability). We found that in presence of trembling participants, there exist equilibria where protocols properties may be violated.

Blockchains sono una delle tecnologie più discusse e studiate negli ultimi anni, attirando l'attenzione sia di esperti del settore e scienziati sia da parte del grande pubblico. Blockchains consistono in distributed ledgers (registri distribuiti) che hanno l'obiettivo di fornire trasparenza, integrità, e molti altri vantaggi rispetto a sistemi centralizzati. Le blockchains sono diventate popolari grazie alla creazione e all'ascesa della crypto moneta Bitcoin. Negli anni queste nuove tecnologie sono diventate sempre più conosciute raggiungendo l'apice nel 2017. Tuttavia ci sono alcuni limiti che si sono riscontrati in blockchain, in particolare si parla di scalabilità e costi di transazione che rappresentano spesso barriere per molti tipi di applicazioni. Tra le diverse alternative alla tradizionale blockchain, una classe interessante è rappresentata dalle DAG-based blockchains, dove la sequenza lineare di blocchi è sostituita da un Grafo Diretto Aciclico. Le DAG-based blockchains hanno diversi vantaggi, ad esempio non richiedono un enorme sforzo in termini di energia computazionale, e garantiscono consistenza sotto certe condizioni date dallo studio dei sistemi distribuiti. In questa tesi, vengono proposti protocolli DAG-based che possono essere usati come black box per DAG-based ledgers. In particolare vengono studiati i comportamenti di partecipanti razionali in DAG-Based Distributed Ledgers. Sono analizzati algoritmi molto generali che descrivono le possibili azioni di utenti in $DAG$-based distributed ledger: votare una transazione, e controllare la sua validità. Sapendo che queste azioni hanno un costo, e introducendo un premio per ogni transazione validata per tutti gli utenti che hanno collaborato in questo processo, si è studiato, utlizzando concetti di Teoria dei Giochi, come un utente si possa comportare cercando di massimizzare il proprio guadagno. Sono stati considerati scenari con diversi tipi di partecipanti e si è studiato se esistessero equilibri dove le proprietà dei diversi protocolli fossero garantite. L'analisi si è concentrata sullo studio di equilibri quando le transazioni sono proposte da utenti "trembling" (i.e. un partecipante razionale che potrebbe commettere azioni involontarie con una certa probabilità). Si è dimostrato che in presenza di utenti "trembling", esistono equilibri dove gli invarianti dei protocolli sono garantiti. Tuttavia esistono equilibri che possono violare alcune di queste proprietà.