Riepilogo Tecnico: Acquisizione Adversariale nelle Blockchain

Enunciato del Problema

Il documento affronta la sfida dell'acquisizione adversariale nei protocolli blockchain, in particolare nel contesto di progetti emergenti che sfruttano l'asimmetria computazionale tra l'esecuzione e la verifica dei compiti (ad esempio, le prove a conoscenza zero, o SNARK). In questi sistemi, un protocollo deve esternalizzare compiti computazionali costosi (come la generazione di una prova di validità per un blocco) a un insieme di $n$ prover pseudonimi e non fidati.

Il problema centrale consiste nel progettare un meccanismo che:

1. Incentivi almeno un prover a eseguire il compito (garantendo la liveness).
2. Minimizzi la perdita economica nello scenario peggiore in cui fino a $n-h$ prover sono adversariali (bizantini) e possono deviare dal protocollo per causare un guasto alla liveness (nessuna prova consegnata) o indurre un sovrappagamento.
3. Operi senza fiducia, poiché i prover non hanno reputazione e non possono impegnarsi in modo credibile ad azioni future.

Gli autori modellano questo come un problema di progettazione di meccanismi in cui il progettista del protocollo mira a minimizzare la somma dei pagamenti effettuati e della penalità $C$ sostenuta se non viene consegnata alcuna prova, assumendo che un avversario controlli un sottoinsieme di prover e agisca per massimizzare la perdita del protocollo.

Metodologia

Gli autori formalizzano il problema utilizzando un quadro teorico-giochistico:

• Configurazione: Esistono $n$ prover, di cui $h$ sono onesti. Il costo di generazione di una prova è normalizzato a 1. Se non viene prodotta alcuna prova, il protocollo subisce una penalità di liveness $C$.
• Modello dell'Avversario: L'avversario può corrompere fino a $a = n-h$ prover. L'avversario osserva il meccanismo e sceglie il comportamento peggiore (o rifiuta di consegnare le prove per attivare la penalità $C$, o consegna le prove per manipolare i pagamenti).
• Obiettivo: Minimizzare la perdita nello scenario peggiore $\ell(p, s)$, definita come il costo totale atteso (pagamenti + penalità) sotto la strategia avversariale peggiore, soggetto al vincolo che il meccanismo sia incentrato-compatibile (i prover onesti massimizzano l'utilità seguendo il protocollo).

Per rendere il problema trattabile, gli autori:

1. Derivano una funzione di limite inferiore $g(s)$ sulla perdita ottimale del protocollo, parametrizzata dal vettore di strategia $s$ (la probabilità con cui ogni prover consegna una prova). Questo limite assume un avversario "indebolito" che sceglie tra due strategie estreme: agire completamente onestamente o rifiutarsi completamente di consegnare.
2. Analizzano i minimizzatori di questo limite inferiore, caratterizzandoli come Equilibri di Comitato Uniforme Designato (un leader deterministico + un comitato di randomizzatori) o Equilibri di Comitato Simmetrici (un comitato di randomizzatori senza un leader designato).
3. Indagano la realizzabilità: determinare se esiste una regola di pagamento che induca questi equilibri raggiungendo al contempo il costo del limite inferiore.
4. Estendono l'analisi per includere pagamenti negativi (slashing/staking), dove i prover depositano garanzie che possono essere confiscate se il protocollo rileva un attacco.

Contributi e Risultati Chiave

1. Caratterizzazione degli Equilibri Ottimali

Il documento dimostra che i minimizzatori del limite inferiore $g(s)$ sono esclusivamente di due tipi:

• Equilibri Designati: Un prover è designato per consegnare con probabilità 1, mentre un comitato di dimensione $k$ consegna con probabilità $s \in (0, 1)$.
• Equilibri Simmetrici: Un comitato di dimensione $k$ consegna con probabilità $s$, e nessun singolo prover è designato.

2. Garanzie di Approssimazione

• Approssimazione Additiva 1: Gli autori dimostrano che per qualsiasi regola di pagamento ed equilibrio, esiste un equilibrio designato la cui perdita è al massimo di 1 unità (il costo di una singola prova) superiore alla perdita ottimale (Teorema 3.1).
• Realizzabilità: Tutti gli equilibri designati sono realizzabili con una semplice regola di pagamento (Lemma 3.4). Al contrario, gli equilibri simmetrici sono realizzabili solo in condizioni specifiche (ad esempio, quando $C$ è sufficientemente grande rispetto a $n$ e $h$) e spesso richiedono strutture di pagamento complesse o pagamenti negativi per essere fattibili.

3. Scalabilità Asintotica

• Scalabilità Logaritmica: La perdita nello scenario peggiore dell'equilibrio designato ottimale scala come $O(\frac{\log C}{\tau})$, dove $\tau = h/n$ è la frazione di prover onesti. Ciò indica che anche con una frazione fissa di avversari, il costo del protocollo cresce solo logaritmicamente con la severità della penalità di liveness.
• Impatto dello Staking: L'introduzione di una posta totale $B$ (garanzia) migliora significativamente la scalabilità. Se $B$ è proporzionale a $C$, la perdita scala come $O(1/\tau)$, diventando effettivamente costante rispetto a $C$.

4. Dinamiche di Transizione

Il documento analizza la transizione tra l'ottimalità designata e quella simmetrica in funzione di $C$ (entità della penalità) e $\tau$ (frazione di onestà).

• Per piccoli valori di $C$ o alti valori di $\tau$, il meccanismo designato è ottimale.
• Per valori di $C$ molto grandi, il meccanismo simmetrico diventa ottimale nell'analisi del limite inferiore.
• Tuttavia, a causa dei vincoli di realizzabilità, il meccanismo designato rimane spesso la scelta pratica anche in regimi in cui il limite inferiore simmetrico è più basso, poiché la soluzione simmetrica può richiedere pagamenti negativi che sono inattuabili o complessi da implementare.

Significato e Raccomandazioni Pratiche

Il documento sostiene che i risultati teorici forniscono indicazioni attuabili per i progettisti di protocolli blockchain, in particolare per zk-EVM (Zero-Knowledge Ethereum Virtual Machine) e altri mercati di esternalizzazione verificabile.

• Raccomandazione: Gli autori raccomandano vivamente l'adozione dell'equilibrio di comitato uniforme designato ottimale. Questo design assegna un singolo "leader" (o lavoratore primario) per produrre la prova in modo deterministico, supportato da un comitato di "backup" che producono prove con una probabilità calcolata $s$.
• Giustificazione:
  1. Semplicità: La regola di pagamento è intuitiva e assomiglia ai meccanismi di consenso esistenti (ad esempio, consenso basato su leader con comitati di attestazione).
  2. Quasi-Ottimalità: La perdita è al massimo di un costo di prova lontano dall'ottimo teorico, il che è trascurabile dati i costi attuali di prova (spesso frazioni di dollaro).
  3. Robustezza: Gestisce efficacemente il comportamento avversariale peggiore, scalando logaritmicamente con la penalità $C$.
  4. Fattibilità: A differenza dei meccanismi simmetrici che possono richiedere pagamenti complessi di tipo lotteria o pagamenti negativi (slashing) per essere ottimali, i meccanismi designati sono sempre realizzabili con pagamenti positivi.

Il documento conclude che, sebbene i meccanismi simmetrici siano teoricamente interessanti e ottimali in specifici regimi asintotici, il meccanismo designato offre il miglior equilibrio tra ottimalità teorica, realizzabilità e familiarità per la comunità blockchain. Gli autori notano che il loro modello si applica ampiamente a qualsiasi problema di delega senza permessi che coinvolga guasti alla liveness, inclusa l'inferenza AI verificabile e i calcoli basati su TEE.