Bitcoin'de Bencil Madencilik ve Dyck Kelimeleri: Kombinatoryal Bir İspat

İçindekiler

1. Giriş

Bencil Madencilik (BM), Bitcoin protokolünün zorluk ayarlama mekanizmasındaki bir açıktan yararlanan bir blok saklama stratejisidir. Her zaman en uzun genel zinciri uzatan dürüst madencilerin aksine, bencil bir madenci, gelirini maksimize etmek için yeni çıkarılan blokları saklayarak gizli bir çatal oluşturur ve bunları stratejik olarak yayınlar. Bu tür stratejileri değerlendirmek için kilit metrik, uzun vadeli görünür hash gücü $\tilde{q}$'dir; bu, zaman içinde saldırgan tarafından resmi blok zincirine eklenen blokların oranını temsil eder.

Önceki analizler karmaşık Markov zincirlerine veya martingale tekniklerine dayanıyordu. Bu çalışma, türetimi daha erişilebilir ve zarif hale getiren Dyck kelimeleri ve Catalan sayılarını kullanan anlaşılır bir kombinatoryal ispat sunmaktadır.

2. Saldırı Döngüsü ve Dyck Kelimeleri

Bir saldırı döngüsü, her bloğun Bencil madenci (S) veya Dürüst madenciler (H) tarafından çıkarıldığı bir olay dizisi olarak modellenebilir.

2.1. Dizi Temsili

Örnek: SSSHSHH dizisi, bencil madencinin üç blok çıkardığını, ardından dürüst madencilerin bir blok, sonra bencil bir blok ve ardından dürüst madencilerin iki blok çıkardığını gösterir. Döngü, bencil madencinin öncülüğü azaldığında ve çatalını yayınlamaya zorladığında sona erer.

2.2. L'nin Dağılımı

$L$, saldırı döngüsü başına resmi blok zincirine eklenen blok sayısı olsun.

Teorem 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$ ve $n \geq 3$ için, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ burada $C_n = \frac{(2n)!}{n!(n+1)!}$, $n$-inci Catalan sayısıdır.

İspat Taslağı: $n \geq 3$ için, ${L=n}$ olayı, SS ile başlayan, H ile biten ve ortadaki kısmın S→"(" ve H→")" eşleştirmesi yapıldığında uzunluğu $2(n-2)$ olan bir Dyck kelimesi (dengeli parantez dizisi) oluşturan dizilere karşılık gelir. Catalan sayısı $C_{n-2}$ bu tür Dyck kelimelerini sayar.

3. Temel Matematiksel Sonuçlar

3.1. L'nin Beklenen Değeri

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

Bu, Catalan sayıları için bilinen üreteç fonksiyon ilişkilerinden gelir.

3.2. Görünür Hash Gücü Formülü

$Z$, saldırganın döngü başına resmi zincire eklediği blok sayısı olsun. Uzun vadeli görünür hash gücü $\tilde{q} = E[Z] / E[L]$'dir.

Teorem 2.4: Bitcoin için görünür hash gücü şudur: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ burada $p$ dürüst madencilerin hash gücü, $q$ saldırganın hash gücüdür ($p+q=1$, $q<1/2$) ve $\gamma$, bir çatal sırasında saldırganın bloğu üzerinde madencilik yapan dürüst madencilerin oranıdır.

4. Teknik Analiz ve Çerçeve

4.1. Matematiksel Çerçeve

Temel yenilik, saldırı dizilerini Dyck yollarına (dengeli parantez dizileri) eşlemektir. Bu, bencil madenciliği yerleşik kombinatoryal teoriye bağlayarak, daha önce stokastik süreçler gerektiren olasılık hesaplarını basitleştirir.

Anahtar Formül: $n\geq3$ için $P[L=n]$ olasılığı, Catalan sayısı $C_{n-2}$ ile doğru orantılıdır ve $p$ ve $q$ olasılık ağırlıklarıyla ölçeklenir: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. Analitik Çerçeve Örneği

L=4 için Durum Analizi:

1. Dizi SS ile başlamalı ve H ile bitmelidir.
2. Ortadaki iki pozisyon uzunluğu 2 olan bir Dyck kelimesi oluşturmalıdır: sadece SH veya HS mi? Kontrol edelim: L=4 için, n=4, yani n-2=2. Ortada 2*(2)=4 karakter uzunluğunda Dyck kelimelerine mi ihtiyacımız var? Dikkat: Teorem, n≥3 için, P[L=n]'nin w = SS X1...X_{2(n-2)} H formundaki dizilere karşılık geldiğini belirtir; burada X'ler uzunluğu 2(n-2) olan bir Dyck kelimesi oluşturur. n=4 için uzunluk 2*(4-2)=4'tür. Yani orta kısım Dyck kelimesi oluşturan 4 karaktere sahiptir. Örnek: SS(SHSH)H? S→(, H→) eşleştirmesi. Ortadaki "SHSH" "()()" olur, bu bir Dyck kelimesidir. Olasılık ağırlığı p^{#S} q^{#H} = p^3 q^3 mü? w=SS S H S H H'deki S ve H'leri sayalım: S 4 kez mi görünüyor? Aslında: SS S H S H H: pozisyonlar: S,S,S,H,S,H,H. Bu 4 S ve 3 H'dir. Yani p^4 q^3. Formül p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4 verir. Bir tutarsızlık var. PDF'de "w'daki 'S' harflerinin (sırasıyla 'H') sayısı n'dir (sırasıyla n-1). Böylece, P[L=n] = p^{n-1} q^n C_{n-2} elde ederiz" diyor. n=4 için, bu p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4'tür. Bu formülle eşleşir. Yani örnek dizi SS S H S H H 4 S ve 3 H'ye sahiptir, bu p^4 q^3'tür, p^3 q^4 değil. Yani SS S H S H H, Dyck kelimesi koşulu altında L=4 için geçerli bir dizi değil mi? Dengeli olmayabilir. Eşleştirelim: S→(, H→). SS S H S H H ((( ) ( ) ) olur. Bu dengeli değildir (üç açık, iki kapalı). Yani gerçekten de, geçerli diziler toplam S sayısının n ve H sayısının n-1 olduğu VE ortasının bir Dyck kelimesi olduğu dizilerdir. Dyck koşulu dengeyi zorunlu kılar ve belirli sayıya yol açar. Yani çerçeve, geçerli saldırı yollarını zarif bir şekilde yakalar.

Bu çerçeve, Markov zincirlerini simüle etmeden sistematik numaralandırma ve olasılık hesaplamasına olanak tanır.

5. Sonuçlar ve Çıkarımlar

$\tilde{q}_B$ için türetilen formül, bencil madencilik için kâr eşiğini nicelendirir. Örneğin, $\gamma=0$ ile, saldırganın kâr etmesi için $q > \approx 0.25$'e ihtiyacı vardır; bu, saf $q>0.5$ varsayımından daha düşüktür. Bu, kritik bir protokol güvenlik açığını vurgular.

Grafik Açıklaması: Farklı $\gamma$ değerleri için $\tilde{q}_B$'nin $q$'ya karşı çizimi şunu gösterir: 1) Eşiğin üzerindeki $q$ için $\tilde{q}_B > q$, kârlılığı gösterir. 2) Daha yüksek $\gamma$ (saldırgan için daha iyi bağlantı), kârlılık eşiğini düşürür ve görünür hash gücü kazancını artırır.

6. Sektör Analisti Perspektifi

Temel İçgörü: Makalenin zarafeti, karmaşık, durumlu bir saldırının temiz bir kombinatoryal modele indirgenmesidir. Bencil madenciliğin kârlılığının sadece ham hash gücüyle değil, aynı zamanda saldırı dizileri ile kanonik kombinatoryal nesneler (Dyck kelimeleri) arasındaki yapısal bağlaşım ile ilgili olduğunu ortaya koyar. Bu sadece bir matematik hilesi değildir; Bitcoin protokolünün güvenlik açığını bir biçimsel dil problemi olarak ortaya koyar—güvenliği, blok yarışındaki belirli dizi desenlerinin olasılık dağılımına bağlıdır.

Mantıksal Akış: Yazarlar, saldırı döngüsünü bir dizi (S/H dizisi) olarak çerçeveleyerek başlar. Anahtar hamle, başarılı saldırıların (saldırganın tüm blokların kabul edildiği) temelde belirli başlangıç/bitişlerle çevrili Dyck kelimeleri olan dizilere karşılık geldiğini fark etmektir. Bu, bir Markov zinciri için denge denklemlerini çözme ihtiyacını atlayarak, sayma ve olasılık üretimi için Catalan kombinatoryal teorisinin geniş araçlarına doğrudan erişmelerini sağlar. Son formül, L'nin beklenen değerini (Catalan üreteç fonksiyonları aracılığıyla) ve Z'nin beklenen değerini (L=1,2 gibi uç durumları dikkate alarak) bağlayarak türetilir.

Güçlü ve Zayıf Yönler:
Güçlü Yönler: İspat son derece öz ve erişilebilirdir. Bencil madencilik gelir formülünün gizemini ortadan kaldırır. Dyck kelimelerine bağlantı, biçimsel dil teorisi kullanarak diğer blok zinciri saldırılarının (örneğin, dengeleme saldırıları, güneş tutulması saldırıları) yeni analizlerine ilham verebilir. Disiplinler arası yaklaşımların (kripto + kombinatoryal) değerini pekiştirir.
Zayıf Yönler: Model, sabit q'ya sahip statik, kalıcı bir saldırgan varsayar. Dinamik uyarlamayı, madenci giriş/çıkışını veya birden fazla bencil madenci etkisini (potansiyel bir oligopol sorunu) yakalamaz. $\gamma$ parametresi basittir; gerçek dünya ağ topolojisi ve yayılım gecikmeleri daha karmaşıktır. "Optimal Selfish Mining Strategies in Bitcoin" (Gervais ve diğerleri, Financial Crypto 2016) gibi takip araştırmalarında belirtildiği gibi, orijinal bencil madencilik stratejisi her zaman optimal değildir; daha uyarlanabilir stratejiler vardır. Bu makalenin katkısı temel niteliktedir, kapsamlı değildir.

Uygulanabilir İçgörüler:

1. Protokol Tasarımcıları İçin: Kök neden "ilk görülen" kuralı ve yavaş blok yayılımıdır. Gervais'in "Tazelik Tercih Edilir" veya Decker ve Wattenhofer'ın "Kompakt Blok Rölesi" (Bitcoin Core'da dağıtıldığı gibi) gibi çözümler $\gamma$'yı ve yayılım varyansını azaltmayı amaçlar. Bu makalenin formülü, bu tür düzeltmeleri test etmek için nicelleştirilebilir bir metrik sağlar.
2. Madencilik Havuzları İçin: Eşik hesaplaması ($q$ ~0.25) bir kırmızı çizgidir. Bu boyuta yaklaşan havuzlar dikkatle incelenmelidir. Merkeziyetsizlik sadece ideolojik değildir; $\tilde{q}$ formülünde bir güvenlik parametresidir.
3. Analistler İçin: Dyck kelimesi eşlemesi güçlü bir şablondur. Katılımcı eylemlerinin biçimsel dil sınıfları (düzenli, bağlamdan bağımsız) tarafından analiz edilebilir diziler oluşturduğu diğer konsensüs mekanizmalarını arayın. Açık oylama dizileriyle Hisse Kanıtı sistemleri, benzer analizler için olgun olabilir.

Çıkarım: Blok zinciri güvenliği giderek kriptograflar için değil, uygulamalı matematikçiler ve dilbilimciler için bir alan haline geliyor. Bu makale, bu değişimin önemli bir örneğidir.

7. Gelecek Uygulamalar ve Yönler

1. Genişletilmiş Saldırı Modelleri: Dyck kelimesi çerçevesi, saldırganın yayınlama stratejisinin farklı olduğu inatçı madencilik veya iz madenciliği varyantlarını analiz etmek için uyarlanabilir.

2. Diğer Konsensüs Protokolleri: Benzer kombinatoryal yöntemlerin Hisse Kanıtı'na (örneğin, Ethereum'un Casper'ı) veya DAG tabanlı protokollere (örneğin, IOTA, Avalanche) uygulanması, saklama saldırılarına karşı dayanıklılıklarına dair yeni içgörüler sağlayabilir.

3. Otomatik Güvenlik Doğrulama: Bir konsensüs protokolünün kurallarını otomatik olarak biçimsel bir dilbilgisine çeviren ve burada bulunan Dyck yapısına benzer "kârlı saldırı dilbilgilerinin" varlığını kontrol eden araçlar geliştirilebilir.

4. Ağ Dinamikleri Entegrasyonu: Gelecekteki çalışmalar, basit $\gamma$ parametresinin ötesine geçerek, daha gerçekçi ağ modellerini (örneğin, blok yayılımı için epidemik modeller kullanarak) kombinatoryal olasılık ağırlıklarına dahil edebilir.

8. Referanslar

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.