Design and Analysis of Erasure Correcting Codes in Blockchain Data Availability Problems

In questo lavoro viene affrontato il concetto di Blockchain e Bitcoin, con enfasi sugli attacchi alla disponibilità riguardanti le transazioni, nel caso in cui nella rete vengano considerati alcuni nodi detti "light nodes", che migliorano la scalabilità del sistema. Quindi, si analizza il funzionamento della Blockchain di Bitcoin quando la struttura dati "Merkle Tree" viene codificata, in modo da aumentare la probabilità dei light nodes di rilevare cancellazioni di transazioni, attuate da parte di nodi attaccanti. Attraverso una codifica con erasure codes, in particolare con codici low density parity check (LDPC), si riesce ad aumentare la probabilità di detection di una cancellazione e, grazie alla decodifica iterativa è possibile recuperare tale cancellazione. Viene affrontato il problema degli stopping sets, cioè quelle strutture che impediscono il recupero dei dati tramite decodifica iterativa e si progetta un algoritmo per l'enumerazione di tali strutture. Sono poi testate, in modo empirico, alcune soluzioni teoriche presenti in letteratura. Successivamente vengono progettati nuovi codici, seguendo un metodo di design diverso da quello presente in letteratura. Tali codici comportano un miglioramento delle performance, in quanto il minimo stopping set per tali codici risulta più alto di quello di codici già analizzati. In questo modo eventuali attacchi alla disponibilità risultano, in probabilità, più difficili. Come conseguenza, il throughput della rete risulta più stabile dato che, con minori attacchi che vanno a buon fine, la frequenza di generazione di nuovi codici, per un nuovo processo di codifica delle transazioni, tende ad essere più bassa. Infine vengono proposti dei possibili miglioramenti.