Bitcoin Selfish Mining e Parole di Dyck: Una Dimostrazione Combinatoria

Indice dei Contenuti

1. Introduzione

Il Selfish Mining (SM) è una strategia di trattenimento dei blocchi in Bitcoin che sfrutta una falla nel meccanismo di aggiustamento della difficoltà del protocollo. A differenza dei miner onesti che estendono sempre la catena pubblica più lunga, un miner egoista trattiene i blocchi appena minati per creare un fork segreto, rilasciandoli strategicamente per massimizzare i ricavi. La metrica chiave per valutare tali strategie è l'hashrate apparente a lungo termine $\tilde{q}$, che rappresenta la frazione di blocchi nella blockchain ufficiale contribuiti dall'attaccante nel tempo.

Le analisi precedenti si basavano su complesse catene di Markov o tecniche di martingala. Questo lavoro presenta una dimostrazione combinatoria diretta utilizzando le parole di Dyck e i numeri di Catalan, rendendo la derivazione più accessibile ed elegante.

2. Ciclo d'Attacco e Parole di Dyck

Un ciclo d'attacco può essere modellato come una sequenza di eventi in cui ogni blocco viene minato dal miner egoista (S) o dai miner onesti (H).

2.1. Rappresentazione delle Sequenze

Esempio: La sequenza SSSHSHH indica che il miner egoista mina tre blocchi, poi i miner onesti ne minano uno, poi l'egoista uno, poi gli onesti due. Il ciclo termina quando il vantaggio del miner egoista si riduce, spingendolo a pubblicare il proprio fork.

2.2. Distribuzione di L

Sia $L$ il numero di blocchi aggiunti alla blockchain ufficiale per ciclo d'attacco.

Teorema 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, e per $n \geq 3$, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ dove $C_n = \frac{(2n)!}{n!(n+1)!}$ è l'$n$-esimo numero di Catalan.

Schema della Dimostrazione: Per $n \geq 3$, l'evento ${L=n}$ corrisponde a sequenze che iniziano con SS, terminano con H, e in cui la parte centrale, mappando S→"(" e H→")", forma una parola di Dyck (una stringa bilanciata di parentesi) di lunghezza $2(n-2)$. Il numero di Catalan $C_{n-2}$ conta tali parole di Dyck.

3. Risultati Matematici Fondamentali

3.1. Valore Atteso di L

Corollario 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.

Ciò deriva dalle note relazioni delle funzioni generatrici per i numeri di Catalan.

3.2. Formula dell'Hashrate Apparente

Sia $Z$ il numero di blocchi che l'attaccante aggiunge alla catena ufficiale per ciclo. L'hashrate apparente a lungo termine è $\tilde{q} = E[Z] / E[L]$.

Teorema 2.4: L'hashrate apparente per Bitcoin è: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ dove $p$ è l'hashrate dei miner onesti, $q$ è l'hashrate dell'attaccante ($p+q=1$, $q<1/2$), e $\gamma$ è la frazione di miner onesti che minano sul blocco dell'attaccante durante un fork.

4. Analisi Tecnica & Framework

4.1. Framework Matematico

L'innovazione principale è la mappatura delle sequenze d'attacco a cammini di Dyck (stringhe bilanciate di parentesi). Questo collega il selfish mining alla combinatoria consolidata, semplificando i calcoli di probabilità che precedentemente richiedevano processi stocastici.

Formula Chiave: La probabilità $P[L=n]$ per $n\geq3$ è direttamente proporzionale al numero di Catalan $C_{n-2}$, scalato per i pesi di probabilità $p$ e $q$: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. Esempio di Framework Analitico

Analisi del Caso per L=4:

1. La sequenza deve iniziare con SS e terminare con H.
2. Le due posizioni centrali devono formare una parola di Dyck di lunghezza 2: solo SH o HS? Controlliamo: Per L=4, n=4, quindi n-2=2. Abbiamo bisogno di parole di Dyck di lunghezza 2*(2)=4 caratteri nella parte centrale? Attenzione: Il teorema afferma che per n≥3, P[L=n] corrisponde a sequenze della forma w = SS X1...X_{2(n-2)} H, dove le X formano una parola di Dyck di lunghezza 2(n-2). Per n=4, la lunghezza è 2*(4-2)=4. Quindi la parte centrale ha 4 caratteri che formano una parola di Dyck. Esempio: SS(SHSH)H? Mappando S→(, H→). La parte centrale "SHSH" diventa "()()", che è una parola di Dyck. Il peso di probabilità è p^{#S} q^{#H} = p^3 q^3? Contiamo S e H in w=SS S H S H H: S appare 4 volte? In realtà: SS S H S H H: posizioni: S,S,S,H,S,H,H. Sono 4 S e 3 H. Quindi p^4 q^3. La formula dà p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4. C'è una discrepanza. Il PDF dice "Il numero di lettere 'S' (risp. 'H') in w è n (risp. n-1). Quindi, otteniamo P[L=n] = p^{n-1} q^n C_{n-2}". Per n=4, è p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4. Questo corrisponde alla formula. Quindi la sequenza di esempio SS S H S H H ha 4 S e 3 H, che è p^4 q^3, non p^3 q^4. Quindi SS S H S H H non è una sequenza valida per L=4 sotto la condizione di parola di Dyck? Potrebbe non essere bilanciata. Mappiamo: S→(, H→). SS S H S H H diventa ((( ) ( ) ). Non è bilanciata (tre aperte, due chiuse). Quindi effettivamente, le sequenze valide sono quelle in cui il conteggio totale di S è n e di H è n-1, E la parte centrale è una parola di Dyck. La condizione di Dyck impone il bilanciamento, portando al conteggio specifico. Quindi il framework cattura elegantemente i percorsi d'attacco validi.

Questo framework consente l'enumerazione sistematica e il calcolo delle probabilità senza simulare catene di Markov.

5. Risultati & Implicazioni

La formula derivata per $\tilde{q}_B$ quantifica la soglia di profitto per il selfish mining. Ad esempio, con $\gamma=0$, l'attaccante necessita di $q > \approx 0.25$ per essere profittevole, inferiore all'assunzione ingenua di $q>0.5$. Ciò evidenzia una vulnerabilità critica del protocollo.

Descrizione del Grafico: Un grafico di $\tilde{q}_B$ vs. $q$ per diversi valori di $\gamma$ mostrerebbe: 1) $\tilde{q}_B > q$ per $q$ sopra una certa soglia, indicando profittabilità. 2) Un $\gamma$ più alto (migliore connettività per l'attaccante) abbassa la soglia di profittabilità e aumenta il guadagno in hashrate apparente.

6. Prospettiva dell'Analista di Settore

Intuizione Fondamentale: L'eleganza del paper è la riduzione di un attacco complesso e con stato in un modello combinatorio pulito. Rivela che la profittabilità del selfish mining non dipende solo dall'hashrate grezzo, ma dall'accoppiamento strutturale tra le sequenze d'attacco e oggetti combinatori canonici (parole di Dyck). Non è solo un trucco matematico; espone la vulnerabilità del protocollo Bitcoin come un problema di linguaggio formale—la sua sicurezza dipende dalla distribuzione di probabilità di certi pattern di stringhe nella corsa ai blocchi.

Flusso Logico: Gli autori iniziano inquadrando il ciclo d'attacco come una stringa (sequenza S/H). La mossa chiave è riconoscere che gli attacchi di successo (dove l'attaccante vede accettati tutti i blocchi) corrispondono a stringhe che sono essenzialmente parole di Dyck delimitate da specifici iniziatori/finitori. Ciò permette di attingere direttamente al vasto apparato della combinatoria di Catalan per il conteggio e la generazione di probabilità, aggirando la necessità di risolvere equazioni di equilibrio per una catena di Markov. La formula finale è derivata collegando il valore atteso di L (tramite le funzioni generatrici di Catalan) e il valore atteso di Z (considerando casi limite come L=1,2).

Punti di Forza & Debolezze:
Punti di Forza: La dimostrazione è notevolmente concisa e accessibile. Demistifica la formula dei ricavi del selfish mining. Il collegamento alle parole di Dyck potrebbe ispirare nuove analisi di altri attacchi blockchain (es. attacchi di bilanciamento, attacchi di eclissi) utilizzando la teoria dei linguaggi formali. Rafforza il valore degli approcci interdisciplinari (crittografia + combinatoria).
Debolezze: Il modello assume un attaccante statico e persistente con q costante. Non cattura l'adattamento dinamico, l'ingresso/uscita dei miner, o l'impatto di più miner egoisti (un potenziale problema di oligopolio). Il parametro $\gamma$ è semplicistico; la topologia di rete reale e i ritardi di propagazione sono più complessi. Come notato in ricerche successive come "Optimal Selfish Mining Strategies in Bitcoin" (Gervais et al., Financial Crypto 2016), la strategia originale di selfish mining non è sempre ottimale; esistono strategie più adattive. Il contributo di questo paper è fondazionale, non esaustivo.

Approfondimenti Pratici:

1. Per i Progettisti di Protocolli: La causa principale è la regola del "primo visto" e la lenta propagazione dei blocchi. Soluzioni come il "Freshness Preferred" di Gervais o il "Compact Block Relay" di Decker e Wattenhofer (implementato in Bitcoin Core) mirano a ridurre $\gamma$ e la varianza di propagazione. La formula di questo paper fornisce una metrica quantificabile per testare tali correzioni.
2. Per i Mining Pool: Il calcolo della soglia ($q$ ~0.25) è una linea rossa. I pool che si avvicinano a questa dimensione dovrebbero essere scrutinati. La decentralizzazione non è solo ideologica; è un parametro di sicurezza nella formula di $\tilde{q}$.
3. Per gli Analisti: La mappatura alle parole di Dyck è un potente modello. Cercare altri meccanismi di consenso in cui le azioni dei partecipanti creano sequenze analizzabili per classi di linguaggi formali (regolari, context-free). I sistemi Proof-of-Stake, con le loro sequenze esplicite di voto, potrebbero essere maturi per analisi simili.

La conclusione: La sicurezza blockchain è sempre più un campo per matematici applicati e linguisti, non solo crittografi. Questo paper è un esempio primario di questo cambiamento.

7. Applicazioni Future & Direzioni

1. Modelli d'Attacco Estesi: Il framework delle parole di Dyck può essere adattato per analizzare varianti come il stubborn mining o il trail mining, dove la strategia di pubblicazione dell'attaccante differisce.

2. Altri Protocolli di Consenso: Applicare metodi combinatori simili al Proof-of-Stake (es. Casper di Ethereum) o a protocolli basati su DAG (es. IOTA, Avalanche) potrebbe fornire nuove intuizioni sulla loro resilienza contro attacchi di trattenimento.

3. Verifica Automatica della Sicurezza: Potrebbero essere sviluppati strumenti per tradurre automaticamente le regole di un protocollo di consenso in una grammatica formale e verificare l'esistenza di "grammatiche d'attacco profittevoli" analoghe alla struttura di Dyck trovata qui.

4. Integrazione delle Dinamiche di Rete: Il lavoro futuro potrebbe incorporare modelli di rete più realistici (es. utilizzando modelli epidemici per la propagazione dei blocchi) nei pesi di probabilità combinatori, andando oltre il semplice parametro $\gamma$.

8. Riferimenti

1. Eyal, I., & Sirer, E. G. (2014). Majority is not enough: Bitcoin mining is vulnerable. In Financial Cryptography and Data Security (pp. 436-454). Springer.
2. Stanley, R. P. (2015). Catalan Numbers. Cambridge University Press.
3. Nakamoto, S. (2008). Bitcoin: A peer-to-peer electronic cash system.
4. Grunspan, C., & Pérez-Marco, R. (2018). On profitability of selfish mining. arXiv preprint arXiv:1805.08281.
5. Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). On the security and performance of proof of work blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (pp. 3-16).
6. Bitcoin Wiki. Difficulty. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Information propagation in the Bitcoin network. In IEEE P2P 2013 Proceedings (pp. 1-10). IEEE.