Rigorous and Generalized Proof of Security of Bitcoin Protocol with Bounded Network Delay

1. Problema e Contesto

Il documento affronta la necessità di una dimostrazione rigorosa e corretta della sicurezza del protocollo Bitcoin in un modello di rete con ritardo limitato ($\Delta$-bounded delay).

• Stato dell'arte: Sebbene la sicurezza di Bitcoin fosse stata precedentemente dimostrata (es. in [7] e [8]), l'articolo identifica un errore fondamentale nella prova di [7]. Tale errore consisteva nell'assumere che la sequenza delle variabili casuali che rappresentano la differenza tra la lunghezza della catena dell'avversario e quella onesta fosse un random walk (cammino casuale). Gli autori dimostrano tramite un controesempio che questa assunzione è errata.
• Limiti delle prove precedenti: Le prove esistenti erano spesso complesse, non intuitive o basate su modelli semplificati che non consideravano blocchi con punteggi diversi (tipi di blocchi eterogenei).
• Obiettivo: Fornire una prova corretta, rigorosa e generalizzata che dimostri la sicurezza di Bitcoin (e di una sua variante chiamata "Merged Bitcoin") sotto l'ipotesi che il tasso di crescita dei blocchi onesti (con ritardo massimo $\Delta$) superi quello dell'avversario.

2. Metodologia e Modello

Gli autori introducono un modello generalizzato e una nuova tecnica di analisi probabilistica:

• Modello Generalizzato:

  • Il protocollo permette l'estrazione di blocchi di diversi tipi, ciascuno con un punteggio (score) diverso ($c_i$).
  • La regola di scelta della forchetta (fork-choice rule) seleziona la catena con il punteggio totale più alto.
  • Modello di Ritardo: Viene considerato un modello di rete con ritardo limitato $\Delta$. L'avversario può ritardare la trasmissione dei blocchi onesti fino a $\Delta$ e può mantenere i propri blocchi privati. Una volta che un blocco onesto viene visto da un minatore onesto, la sua diffusione è ritardata al massimo di $\Delta$ verso gli altri.

• Definizioni Chiave:

  • $\lambda_h$: Tasso di crescita del punteggio della catena onesta quando è soggetta al ritardo massimo $\Delta$ (fully-delayed).
  • $\lambda_a$: Tasso di crescita del punteggio della catena dell'avversario.
  • Blocco Nakamoto: Un blocco onesto che, una volta inserito, rimane nella catena canonica per sempre.
  • Intervallo Nakamoto: Un intervallo di tempo in cui si verifica un blocco onesto "loner" (isolato) e le condizioni di crescita del punteggio onesto superano quelle dell'avversario sia nel passato che nel futuro.

• Tecnica Innovativa: Processo di Arrivo "Punctured" (Bucato):

  • Per correggere l'errore del random walk presente nelle prove precedenti, gli autori introducono un processo di arrivo punteggiato.
  • In questo processo, gli intervalli di tempo vengono suddivisi in segmenti di lunghezza $B$ seguiti da intervalli di cancellazione di lunghezza $\Delta$.
  • Questo crea una sequenza di variabili casuali indipendenti e identicamente distribuite (i.i.d.) per i punteggi dei blocchi, permettendo l'applicazione corretta della teoria del random walk (cammino casuale) e della Legge dei Grandi Numeri.

3. Risultati Chiave e Dimostrazioni

Il paper si articola in diverse fasi logiche per dimostrare la sicurezza:

1. Correzione dell'Errore del Random Walk:

   • Viene dimostrato che la differenza di lunghezza/punteggio tra le catene non è un random walk semplice.
   • Utilizzando il processo "punctured", si dimostra che il tasso di crescita medio $\lambda_h$ esiste quasi certamente e che, con probabilità maggiore di zero, il punteggio della catena onesta rimane vicino o sopra la media per tutto il tempo.

2. Esistenza degli Intervalli Nakamoto:

   • Viene dimostrato che, se $\lambda_h > \lambda_a$, esiste una probabilità strettamente maggiore di zero che un qualsiasi intervallo di tempo contenga un blocco Nakamoto.
   • Questo si basa sull'indipendenza degli eventi: la probabilità che un blocco sia un "loner" (isolato) e che la crescita onesta domini quella avversaria (eventi $E_1$ e $E_2$) è positiva.

3. Argomento di Bootstrap (Induzione):

   • Per passare dalla probabilità che un singolo blocco sia sicuro alla certezza che ci siano infiniti blocchi sicuri, gli autori utilizzano un argomento di induzione (bootstrap).
   • Dividono l'intervallo di tempo in segmenti e dimostrano che la probabilità che un intervallo non contenga blocchi sicuri decresce esponenzialmente con la lunghezza dell'intervallo.
   • Applicando il Lemma di Borel-Cantelli, si conclude che la probabilità che esistano infiniti intervalli senza blocchi sicuri è zero.

4. Teorema Principale (Sicurezza):

   • Teorema 42/Corollario 43: Se $\lambda_h > \lambda_a$, allora con probabilità 1 (quasi certamente), la catena canonica conterrà infiniti blocchi onesti.
   • Questo garantisce che la rete non venga mai completamente sovrastata dall'avversario, assicurando la liveness e la sicurezza del protocollo.

5. Regione di Insicurezza:

   • Teorema 44: Se $\lambda_a > \lambda_h$, il protocollo è insicuro. Viene dimostrato che un attacco di mining privato (private mining) permette all'avversario di dominare la catena con probabilità 100%, rendendo possibili attacchi di doppia spesa.

4. Contributi Principali

1. Correzione Rigorosa: Identificazione e correzione dell'errore matematico nella prova di [7] riguardante l'assunzione errata del random walk.
2. Generalizzazione del Modello: Estensione della prova di sicurezza a un modello in cui i blocchi hanno punteggi diversi (fondamentale per protocolli come "Merged Bitcoin").
3. Nuova Tecnica Analitica: Introduzione del "punctured arrival process" per rendere l'analisi probabilistica rigorosa e indipendente dalle dipendenze temporali complesse.
4. Semplificazione: La prova è presentata in modo più intuitivo rispetto a lavori precedenti, separando chiaramente la definizione degli intervalli di sicurezza dalla dimostrazione della loro infinità.

5. Significato e Impatto

Questo lavoro è fondamentale per la teoria della sicurezza delle blockchain perché:

• Fornisce la prima prova rigorosa e corretta della sicurezza di Bitcoin in un modello di rete asincrona con ritardo limitato, chiudendo le lacune delle prove precedenti.
• Stabilisce un limite di sicurezza preciso: la sicurezza è garantita se e solo se il tasso di crescita onesto (con ritardo) supera quello dell'avversario.
• Offre un quadro teorico generalizzato che può essere applicato a varianti avanzate di Bitcoin e protocolli di consenso ibridi, rendendo la ricerca futura più solida e meno soggetta a errori di modellazione.
• Conferma che, nonostante i ritardi di rete e gli attacchi strategici, la decentralizzazione e la sicurezza di Bitcoin sono matematicamente garantite sotto le condizioni di potenza di calcolo corrette.