Riepilogo Tecnico: Codici di Cancellazione Monotoni

1. Enunciato del Problema

I codici di cancellazione tradizionali, come i codici Reed-Solomon (MDS), operano sotto un'assunzione di guasto a soglia. In questi sistemi, i dati sono divisi in $k$ pezzi e codificati in $n$ frammenti in modo tale che qualsiasi insieme di $k$ frammenti sia sufficiente per la ricostruzione. Questo modello assume che qualsiasi sottoinsieme di $k$ nodi abbia la stessa probabilità di essere disponibile o di fallire, indipendentemente dall'identità specifica dei nodi.

Tuttavia, i moderni sistemi distribuiti, in particolare nelle blockchain e nelle criptovalute (ad esempio Stellar, XRP Ledger), utilizzano assunzioni di guasto generalizzate o sistemi di quorum bizantini. In questi contesti, la fiducia non è uniforme; alcuni nodi sono più affidabili di altri e i pattern di guasto non sono puramente casuali ma dipendono da specifici sottoinsiemi di nodi. I codici esistenti basati sulla soglia non possono accommodare efficientemente queste assunzioni di fiducia arbitrarie senza un significativo sovraccarico o una discrepanza strutturale. Il documento affronta la necessità di codici di cancellazione che rispettino strutture di accesso monotone arbitrarie, dove specifici sottoinsiemi di nodi (insiemi di accesso) garantiscono la ricostruzione dei dati, mentre altri potrebbero non farlo.

2. Metodologia

Il documento introduce i Codici di Cancellazione Monotoni, una generalizzazione dei codici di cancellazione classici progettata per funzionare con strutture di accesso arbitrarie $\mathcal{A} \subseteq 2^{\mathcal{P}}$, dove $\mathcal{P}$ è l'insieme dei nodi.

2.1 Definizioni e Formalismo

• Codice di Cancellazione Monotono: Uno schema costituito dagli algoritmi Encode e Decode. Encode mappa un file $f$ in un vettore di frammenti $(g_1, \dots, g_n)$, dove i frammenti possono avere dimensioni diverse. Decode ricostruisce $f$ da qualsiasi sottoinsieme di frammenti corrispondente a un insieme di accesso $A \in \mathcal{A}$.
• Efficienza: Misurata dal sovraccarico $\beta = (\mu - \kappa) / \kappa$, dove $\kappa$ è la dimensione del file di input e $\mu$ è la dimensione totale di tutti i frammenti. L'obiettivo è minimizzare $\beta$.
• Codici di Cancellazione Monotoni Lineari: Una classe specifica in cui la codifica e la decodifica sono operazioni lineari su un campo finito $\mathbb{F}_q$. La codifica è definita da una matrice generatrice $G$ e da una funzione di etichettatura $\phi$ che mappa le colonne di $G$ ai nodi. Un insieme di nodi è sufficiente se la sottomatrice di $G$ corrispondente a quei nodi ha rango completo ($k$).

2.2 Approcci di Costruzione

Il documento presenta tre metodi distinti per costruire questi codici:

1. Costruzione Base (Non Ottimale):

   • Basata su una Formula Booleana Monotona (MBF) che rappresenta la struttura di accesso.
   • L'algoritmo attraversa ricorsivamente l'albero di accesso. Per un nodo AND, il file viene diviso in chunk; per un nodo OR, il file viene replicato.
   • Risultato: Garantisce la completezza ma spesso comporta un elevato sovraccarico a causa della replicazione ridondante nella struttura ad albero.

2. Costruzione Lineare Efficiente (Sub-Ottimale):

   • Utilizza un algoritmo ricorsivo che costruisce una matrice MDS a blocchi.
   • Costruisce la matrice di codifica combinando matrici di Vandermonde (per gli operatori a soglia) utilizzando prodotti di Kronecker e matrici identità per allineare le dimensioni.
   • Risultato: Computazionalmente efficiente (polinomiale nella dimensione dell'albero di accesso) ma non garantisce un sovraccarico minimo.

3. Costruzione Lineare Ottimale (tramite Programmazione Lineare):

   • Caso Generale: Formula il problema della ricerca della distribuzione ottimale dei frammenti come un Problema di Programmazione Lineare (LPP). L'obiettivo è minimizzare la somma dei pesi dei frammenti assegnati ai nodi, soggetto a vincoli per cui ogni insieme di accesso detiene almeno $k$ frammenti "base" (derivati da un codice MDS sottostante).
   • Strutture di Accesso Partizionate: Per una specifica classe di strutture (gerarchiche, dove ogni nodo appare esattamente una volta nell'MBF, ad esempio il modello di fiducia di Stellar), il documento fornisce un algoritmo specializzato ricorsivo (Algoritmo 2). Questo algoritmo risolve l'LPP efficientemente ($O(n^2)$) identificando quali sottoalberi includere o escludere per minimizzare il sovraccarico, determinando efficacemente un'assegnazione ottimale dei frammenti base.

2.3 Applicazione al Protocollo: GAVID

Il documento integra questi codici in un protocollo distribuito chiamato General Asynchronous Verifiable Information Dispersal (GAVID).

• Generalizzazione: Estende il classico protocollo AVID (Cachin e Tessaro) dai sistemi a soglia ai sistemi di quorum bizantini generali.
• Meccanismo: Utilizza il sistema kernel del sistema di quorum come struttura di accesso per il codice di cancellazione monotono.
• Concetti Chiave: Introduce gli Insiemi Affidabili (insiemi che contengono un kernel disgiunto da qualsiasi insieme guasto) per garantire disponibilità e consistenza nell'ambiente asincrono.
• Ottimizzazione: Propone GAVID-H, che sostituisce il vettore di verifica completo con la radice di un albero di Merkle, riducendo la complessità di comunicazione.

3. Contributi Chiave

1. Definizione dei Codici di Cancellazione Monotoni: Il documento definisce formalmente un nuovo primitivo di codifica che generalizza i codici di cancellazione classici a strutture di accesso monotone arbitrarie, consentendo assunzioni di fiducia non uniformi.
2. Algoritmi di Costruzione:
   • Fornisce un metodo computazionalmente efficiente per costruire codici di cancellazione monotoni lineari per qualsiasi struttura di accesso (sebbene non sempre ottimali in termini di sovraccarico).
   • Fornisce un metodo per costruire codici di cancellazione monotoni lineari ottimali risolvendo un problema di programmazione lineare derivato dalla struttura di accesso.
3. Strutture di Accesso Partizionate: Analizza il caso specifico delle strutture di accesso partizionate (comuni nella pratica) e presenta un algoritmo efficiente per costruire codici ottimali per esse, caratterizzandone il sovraccarico.
4. Protocollo GAVID: Formula un protocollo generale di dispersione verificabile asincrona delle informazioni (GAVID) che utilizza codici di cancellazione monotoni per realizzare una trasmissione affidabile bizantina efficiente in termini di comunicazione per sistemi di quorum arbitrari.

4. Risultati e Analisi

• Limiti del Sovraccarico: Per una struttura di accesso generale con dimensione minima dell'insieme di accesso $\tau$, il sovraccarico $\beta$ di un codice di cancellazione monotono lineare ottimale è limitato da $\beta \le (n - \tau)/\tau$ per grandi $k$. Ciò implica che se il più piccolo insieme di accesso è vicino al numero totale di nodi, il sovraccarico tende a zero.
• Efficienza della Costruzione Partizionata: L'algoritmo specializzato per le strutture di accesso partizionate esegue in tempo $O(n^2)$, che è significativamente più veloce rispetto alla risoluzione diretta dell'LPP generale quando il numero di insiemi di accesso è esponenziale.
• Complessità del Protocollo:
  • GAVID Disperse: Complessità dei messaggi $O(n^2)$; Complessità di comunicazione $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Ottimizzato con Merkle): Riduce la complessità di comunicazione a $O(n(1+\beta)|f| + n^2(\log n)|H|)$ e la complessità di archiviazione a $O((1+\beta)|f| + n(\log n)|H|)$.
• Correttezza: Il documento dimostra che GAVID soddisfa le proprietà di Terminazione, Accordo, Disponibilità e Correttezza per qualsiasi sistema di quorum bizantino, a condizione che esista un codice di cancellazione monotono per la struttura kernel del sistema.

5. Significato e Affermazioni

Il documento afferma che i codici di cancellazione monotoni sono un abilitatore critico per sistemi distribuiti consapevoli della fiducia. Spostandosi oltre il rigido modello a soglia "qualsiasi $k$ su $n$", questi codici permettono ai sistemi di:

• Ridurre la Ridondanza: Ottimizzare il sovraccarico di archiviazione e comunicazione assegnando più dati ai nodi affidabili e meno a quelli rischiosi, invece di trattare tutti i nodi in modo uguale.
• Supportare Modelli di Fiducia Complessi: Implementare direttamente le assunzioni di fiducia presenti nelle reti blockchain reali (come Stellar) dove la fiducia è gerarchica e non uniforme.
• Generalizzare i Protocolli: Fornire un primitivo fondamentale (GAVID) che permette ai protocolli esistenti di trasmissione e consenso efficienti di funzionare sotto sistemi di quorum bizantini generali, non solo sotto semplici modelli a soglia.

Gli autori notano che, sebbene forniscano una costruzione efficiente per le strutture partizionate, il problema di costruire un codice di cancellazione monotono ottimale per una struttura di accesso arbitraria (data come MBF con un numero esponenziale di insiemi) rimane una questione aperta. Suggeriscono inoltre lavori futuri sui codici dinamici e l'applicazione di altre tecniche della teoria dei codici (ad esempio, codici rateless) a questo contesto.