Uchimbaji wa Kujipendelea Bitcoin na Maneno ya Dyck: Uthibitisho wa Kiuchanganyaji

Yaliyomo

1. Utangulizi

Uchimbaji wa Kujipendelea (SM) ni mkakati wa kukaa na vitalu katika Bitcoin unaotumia kasoro katika utaratibu wa kurekebisha ugumu wa itifaki. Tofauti na wachimbaji waaminifu ambao daima huongeza mnyororo mrefu zaidi wa umma, mchimbaji mwenye kujipendelea hukaa na vitalu vipya vilivyochimbwa ili kuunda tawi la siri, akivitolea kwa mikakati ili kuongeza mapato. Kipimo muhimu cha kutathmini mikakati kama hii ni kiwango cha muda mrefu cha hashrate kinachoonekana $\tilde{q}$, ambacho kinawakilisha sehemu ya vitalu katika mnyororo rasmi wa vitalu ambacho mshambuliaji amechangia kwa muda.

Uchambuzi wa awali ulitegemea mnyororo tata wa Markov au mbinu za martingale. Kazi hii inatoa uthibitisho wa moja kwa moja wa kiuchanganyaji kwa kutumia maneno ya Dyck na nambari za Catalan, na kufanya utaftaji uwe rahisi zaidi na mzuri.

2. Mzunguko wa Mashambulizi na Maneno ya Dyck

Mzunguko wa mashambulizi unaweza kuigwa kama mfuatano wa matukio ambapo kila kizuizi kinachimba ama na Mchimbaji Mwenye Kujipendelea (S) au Wachimbaji Waaminifu (H).

2.1. Uwakilishi wa Mfuatano

Mfano: Mfuatano SSSHSHH unaonyesha mchimbaji mwenye kujipendelea anachimba vitalu vitatu, kisha wachimbaji waaminifu wanachimba kimoja, kisha mwenye kujipendelea moja, kisha waaminifu wawili. Mzunguko unaisha wakati uongozi wa mchimbaji mwenye kujipendelea unapunguzwa, na kuwahimiza kuchapisha tawi lao.

2.2. Usambazaji wa L

Acha $L$ iwe idadi ya vitalu vilivyoongezwa kwenye mnyororo rasmi wa vitalu kwa kila mzunguko wa mashambulizi.

Nadharia 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, na kwa $n \geq 3$, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ ambapo $C_n = \frac{(2n)!}{n!(n+1)!}$ ni nambari ya $n$-th ya Catalan.

Mchoro wa Uthibitisho: Kwa $n \geq 3$, tukio ${L=n}$ linalingana na mfuatano unaoanza na SS, unaoisha na H, na ambapo sehemu ya kati, wakati wa kuweka ramani S→"(" na H→")", huunda neno la Dyck (mnyororo wa mabano yaliyowekwa sawa) wa urefu $2(n-2)$. Nambari ya Catalan $C_{n-2}$ inahesabu maneno kama haya ya Dyck.

3. Matokeo ya Kimsingi ya Kihisabati

3.1. Thamani ya Kutarajiwa ya L

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

Hii inafuata kutoka kwa uhusiano unaojulikana wa kazi za kuzalisha kwa nambari za Catalan.

3.2. Fomula ya Hashrate Inayoonekana

Acha $Z$ iwe idadi ya vitalu ambavyo mshambuliaji anaongeza kwenye mnyororo rasmi kwa kila mzunguko. Kiwango cha muda mrefu cha hashrate kinachoonekana ni $\tilde{q} = E[Z] / E[L]$.

Nadharia 2.4: Kiwango cha hashrate kinachoonekana kwa Bitcoin ni: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ ambapo $p$ ni kiwango cha hashrate cha wachimbaji waaminifu, $q$ ni kiwango cha hashrate cha mshambuliaji ($p+q=1$, $q<1/2$), na $\gamma$ ni sehemu ya wachimbaji waaminifu ambao wanachimba kwenye kizuizi cha mshambuliaji wakati wa tawi.

4. Uchambuzi wa Kiufundi & Mfumo

4.1. Mfumo wa Kihisabati

Uvumbuzi mkuu ni kuweka ramani ya mfuatano wa mashambulizi kwa njia za Dyck (mnyororo wa mabano yaliyowekwa sawa). Hii inaunganisha uchimbaji wa kujipendelea na uchanganyaji uliowekwa vizuri, na kurahisisha mahesabu ya uwezekano ambayo hapo awali yalihitaji michakato ya nasibu.

Fomula Muhimu: Uwezekano $P[L=n]$ kwa $n\geq3$ ni sawia moja kwa moja na nambari ya Catalan $C_{n-2}$, ikipimwa kwa uzito wa uwezekano $p$ na $q$: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. Mfano wa Mfumo wa Kuchambua

Uchambuzi wa Kesi kwa L=4:

1. Mfuatano lazima uanze na SS na uishe na H.
2. Nafasi mbili za kati lazima ziunde neno la Dyck la urefu 2: ni SH au HS tu? Hebu tuangalie: Kwa L=4, n=4, kwa hivyo n-2=2. Tunahitaji maneno ya Dyck ya urefu 2*(2)=4 herufi katikati? Subiri, makini: Nadharia inasema kwa n≥3, P[L=n] inalingana na mfuatano wa fomu w = SS X1...X_{2(n-2)} H, ambapo X huunda neno la Dyck la urefu 2(n-2). Kwa n=4, urefu ni 2*(4-2)=4. Kwa hivyo sehemu ya kati ina herufi 4 zinazounda neno la Dyck. Mfano: SS(SHSH)H? Kuweka ramani S→(, H→). Sehemu ya kati "SHSH" inakuwa "()()", ambayo ni neno la Dyck. Uzito wa uwezekano ni p^{#S} q^{#H} = p^3 q^3? Hebu tuhesabu S na H katika w=SS S H S H H: S inaonekana mara 4? Kweli: SS S H S H H: nafasi: S,S,S,H,S,H,H. Hiyo ni S 4 na H 3. Kwa hivyo p^4 q^3. Fomula inatoa p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4. Kuna tofauti. PDF inasema "Idadi ya herufi 'S' (mtawalia 'H') katika w ni n (mtawalia n-1). Kwa hivyo, tunapata P[L=n] = p^{n-1} q^n C_{n-2}". Kwa n=4, hiyo ni p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4. Hii inalingana na fomula. Kwa hivyo mfuatano wa mfano SS S H S H H una S 4 na H 3, ambayo ni p^4 q^3, sio p^3 q^4. Kwa hivyo SS S H S H H sio mfuatano halali kwa L=4 chini ya hali ya neno la Dyck? Huenda haukuwazi sawa. Hebu tuweke ramani: S→(, H→). SS S H S H H inakuwa ((( ) ( ) ). Hiyo haijawazi sawa (tatu wazi, mbili funga). Kwa hakika, mfuatano halali ni wale ambao jumla ya hesabu ya S ni n na hesabu ya H ni n-1, NA katikati ni neno la Dyck. Hali ya Dyck inalazimisha usawa, na kusababisha hesabu maalum. Kwa hivyo mfumo huu unashika kwa ustadi njia halali za mashambulizi.

Mfumo huu unaruhusu hesabu ya utaratibu na mahesabu ya uwezekano bila kuiga mnyororo wa Markov.

5. Matokeo na Maana

Fomula iliyotolewa ya $\tilde{q}_B$ inapima kizingiti cha faida kwa uchimbaji wa kujipendelea. Kwa mfano, kwa $\gamma=0$, mshambuliaji anahitaji $q > \takriban 0.25$ ili kupata faida, chini ya dhana ya $q>0.5$ ya kawaida. Hii inaangazia udhaifu muhimu wa itifaki.

Maelezo ya Chati: Grafu ya $\tilde{q}_B$ dhidi ya $q$ kwa thamani tofauti za $\gamma$ ingeonyesha: 1) $\tilde{q}_B > q$ kwa $q$ juu ya kizingiti, ikionyesha faida. 2) $\gamma$ ya juu zaidi (muunganisho bora kwa mshambuliaji) hupunguza kizingiti cha faida na kuongeza faida ya kiwango cha hashrate kinachoonekana.

6. Mtazamo wa Mchambuzi wa Sekta

Uelewa wa Msingi: Uzuri wa karatasi hii ni kupunguza mashambulizi magumu, yenye hali nyingi kuwa mfumo safi wa kiuchanganyaji. Inafunua kwamba faida ya uchimbaji wa kujipendelea sio tu kuhusu kiwango cha hashrate ghafi, lakini kuhusu muunganisho wa kimuundo kati ya mfuatano wa mashambulizi na vitu vya kawaida vya kiuchanganyaji (maneno ya Dyck). Hii sio hila ya hisabati tu; inafunua udhaifu wa itifaki ya Bitcoin kama tatizo la lugha rasmi—usalama wake unategemea usambazaji wa uwezekano wa muundo fulani wa mnyororo katika mbio ya vitalu.

Mtiririko wa Kimantiki: Waandishi wanaanza kwa kuweka mzunguko wa mashambulizi kama mnyororo (mfuatano wa S/H). Hatua muhimu ni kutambua kwamba mashambulizi yanayofanikiwa (ambapo mshambuliaji anapata vitalu vyote kukubaliwa) yanalingana na mnyororo ambao kimsingi ni maneno ya Dyck yaliyofungwa na wanaoanza/kumaliza maalum. Hii inawaruhusu kutumia moja kwa moja mashine kubwa ya uchanganyaji wa Catalan kwa hesabu na uzalishaji wa uwezekano, na kuzuia hitaji la kutatua milinganyo ya usawa kwa mnyororo wa Markov. Fomula ya mwisho inatokana kwa kuunganisha thamani ya kutarajia ya L (kupitia kazi za kuzalisha za Catalan) na thamani ya kutarajia ya Z (kuzingatia kesi za makali kama L=1,2).

Nguvu na Kasoro:
Nguvu: Uthibitisho ni mfupi sana na unaweza kufikiwa. Inafafanua fomula ya mapato ya uchimbaji wa kujipendelea. Kuunganisha na maneno ya Dyck kunaweza kuchochea uchambuzi mpya wa mashambulizi mengine ya blockchain (k.m., mashambulizi ya usawa, mashambulizi ya kupatwa) kwa kutumia nadharia ya lugha rasmi. Inaimarisha thamani ya mbinu za kuvuka taaluma (crypto + uchanganyaji).
Kasoro: Mfano unadhania mshambuliaji tuli, endelevu na q ya mara kwa mara. Haishiki kukabiliana kwa nguvu, kuingia/kutoka kwa wachimbaji, au athari ya wachimbaji wengi wenye kujipendelea (tatizo linalowezekana la oligopoly). Kigezo $\gamma$ ni rahisi sana; muundo wa mtandao wa ulimwengu halisi na ucheleweshaji wa kueneza ni magumu zaidi. Kama ilivyoelezwa katika utafiti unaofuata kama "Mikakati Bora ya Uchimbaji wa Kujipendelea katika Bitcoin" (Gervais et al., Financial Crypto 2016), mkakati wa awali wa uchimbaji wa kujipendelea sio bora kila wakati; kuna mikakati zaidi ya kukabiliana. Mchango wa karatasi hii ni wa msingi, sio wa kukamilika.

Uelewa Unaoweza Kutekelezwa:

1. Kwa Wabunifu wa Itifaki: Sababu ya msingi ni kanuni ya "kwanza kuonekana" na uenezi wa polepole wa vitalu. Suluhisho kama "Freshness Preferred" ya Gervais au "Compact Block Relay" ya Decker na Wattenhofer (kama ilivyotumika katika Bitcoin Core) zinalenga kupunguza $\gamma$ na tofauti ya uenezi. Fomula ya karatasi hii inatoa kipimo kinachoweza kupimika cha kujaribu marekebisho kama hayo.
2. Kwa Vyanzo vya Uchimbaji: Hesabu ya kizingiti ($q$ ~0.25) ni mstari mwekundu. Vyanzo vinavyokaribia ukubwa huu vinapaswa kukaguliwa. Utofauti sio kiitikadi tu; ni kigezo cha usalama katika fomula ya $\tilde{q}$.
3. Kwa Wachambuzi: Kuweka ramani ya neno la Dyck ni kiolezo chenye nguvu. Tafuta mifumo mingine ya makubaliano ambapo vitendo vya washiriki huunda mfuatano unaoweza kuchambuliwa na madarasa ya lugha rasmi (ya kawaida, ya muktadha). Mifumo ya Uthibitisho wa Hisa, na mfuatano wao wazi wa kupiga kura, inaweza kuwa tayari kwa uchambuzi sawa.

Hitimisho: Usalama wa Blockchain sasa ni eneo la wanahisabati walio tumika na wanaanuai, sio tu wafichaji. Karatasi hii ni mfano bora wa mabadiliko hayo.

7. Matumizi ya Baadaye na Mwelekeo

1. Mfano Ulioongezwa wa Mashambulizi: Mfumo wa neno la Dyck unaweza kubadilishwa ili kuchambua aina za uchimbaji wa kukataa au uchimbaji wa nyuma, ambapo mkakati wa kuchapisha wa mshambuliaji unatofautiana.

2. Itifaki Nyingine za Makubaliano: Kutumia mbinu sawa za kiuchanganyaji kwa Uthibitisho wa Hisa (k.m., Casper ya Ethereum) au itifaki zinazotegemea DAG (k.m., IOTA, Avalanche) kunaweza kutoa ufahamu mpya kuhusu uthabiti wao dhidi ya mashambulizi ya kukaa.

3. Uthibitishaji wa Otomatiki wa Usalama: Zana zinaweza kutengenezwa ili kutafsiri moja kwa moja kanuni za itifaki ya makubaliano kuwa sarufi rasmi na kuangalia uwepo wa "sarufi za mashambulizi yenye faida" zinazofanana na muundo wa Dyck uliopatikana hapa.

4. Ujumuishaji wa Mienendo ya Mtandao: Kazi ya baadaye inaweza kujumuisha mifano ya kweli zaidi ya mtandao (k.m., kutumia mifano ya ugonjwa wa kuambukiza kwa uenezi wa vitalu) katika uzito wa uwezekano wa kiuchanganyaji, na kuendelea zaidi ya kigezo rahisi cha $\gamma$.

8. Marejeo

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.