Bitcoin Cinikin Mai Son Kai da Kalmomin Dyck: Hujjar Haɗin Kai

Teburin Abubuwan Ciki

1. Gabatarwa

Cinikin Mai Son Kai (SM) wata dabara ce ta riƙe tubalan a cikin Bitcoin wacce ke amfani da aibi a cikin tsarin daidaita wahalar yarjejeniyar. Ba kamar masu haƙo ma'adinai masu gaskiya waɗanda koyaushe suke tsawaita mafi tsayin sarkar jama'a ba, mai haƙo ma'adinai mai son kai yana riƙe sabbin tubalan da aka haƙa don ƙirƙirar reshe na sirri, yana sake su da dabara don haɓaka kuɗin shiga. Ma'auni mai mahimmanci don kimanta irin waɗannan dabarun shine ƙimar hashrate mai bayyana na dogon lokaci $\tilde{q}$, wanda ke wakiltar kaso na tubalan a cikin sarkar blockchain na hukuma da maharin ya ba da gudummawa a tsawon lokaci.

Binciken da ya gabata ya dogara ne akan sarkokin Markov masu sarkakkiya ko dabarun martingale. Wannan aikin yana gabatar da hujjar haɗin kai kai tsaye ta amfani da Kalmomin Dyck da Lambobin Catalan, wanda ya sa samuwar ta zama mafi sauƙi da kyau.

2. Zagayen Kai da Kalmomin Dyck

Ana iya ƙirƙirar zagayen kai a matsayin jerin abubuwan da suka faru inda kowane tubalan ya haƙa ko dai ta hanyar Mai haƙo ma'adinai mai son kai (S) ko Masu haƙo ma'adinai masu gaskiya (H).

2.1. Wakilcin Jerin

Misali: Jerin SSSHSHH yana nuna mai haƙo ma'adinai mai son kai ya haƙi tubalan uku, sannan masu haƙo ma'adinai masu gaskiya suka haƙi ɗaya, sannan mai son kai ɗaya, sannan masu gaskiya biyu. Zagayen yana ƙarewa lokacin da jagorancin mai haƙo ma'adinai mai son kai ya ragu, wanda ke sa su buga reshensu.

2.2. Rarraba L

Bari $L$ ya zama adadin tubalan da aka ƙara zuwa sarkar blockchain na hukuma a kowane zagayen kai.

Ka'idar 2.2: $P[L=1] = p$, $P[L=2] = pq + pq^2$, kuma ga $n \geq 3$, $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ inda $C_n = \frac{(2n)!}{n!(n+1)!}$ shine lambar Catalan ta $n$.

Ƙaramin Bayanin Hujja: Ga $n \geq 3$, lamarin ${L=n}$ yayi daidai da jerin da suka fara da SS, suna ƙarewa da H, kuma inda tsakiyar ɓangaren, lokacin da ake yin taswira S→"(" da H→")", ya zama kalmar Dyck (ma'auni na ma'auni na baka) mai tsayi $2(n-2)$. Lambar Catalan $C_{n-2}$ tana ƙidaya irin waɗannan kalmomin Dyck.

3. Sakamakon Lissafi na Asali

3.1. Ƙimar Da Ake Tsammani na L

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

Wannan ya biyo baya daga sanannun alaƙar aikin samarwa don lambobin Catalan.

3.2. Tsarin Hashrate Mai Bayyana

Bari $Z$ ya zama adadin tubalan da maharin ya ƙara zuwa sarkar hukuma a kowane zagaye. Ƙimar hashrate mai bayyana na dogon lokaci ita ce $\tilde{q} = E[Z] / E[L]$.

Ka'idar 2.4: Ƙimar hashrate mai bayyana don Bitcoin ita ce: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ inda $p$ shine ƙimar hashrate na masu haƙo ma'adinai masu gaskiya, $q$ shine ƙimar hashrate na maharin ($p+q=1$, $q<1/2$), kuma $\gamma$ shine kaso na masu haƙo ma'adinai masu gaskiya waɗanda ke haƙa kan tubalin maharin yayin reshe.

4. Bincike na Fasaha & Tsarin Aiki

4.1. Tsarin Lissafi

Ƙirƙira ta asali ita ce yin taswira jerin kai zuwa Hanyoyin Dyck (ma'auni na ma'auni na baka). Wannan yana haɗa cinikin mai son kai da ingantaccen haɗin kai, yana sauƙaƙe lissafin yuwuwar da a baya yake buƙatar hanyoyin stochastic.

Tsari Mai Muhimmanci: Yuwuwar $P[L=n]$ ga $n\geq3$ tana daidai kai tsaye da lambar Catalan $C_{n-2}$, wanda aka auna ta hanyar ma'auni na yuwuwar $p$ da $q$: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. Misalin Tsarin Bincike

Binciken Hali don L=4:

1. Dole ne jerin ya fara da SS kuma ya ƙare da H.
2. Matsayin tsakiya biyu dole ne su zama kalmar Dyck mai tsayi 2: kawai SH ko HS? Bari mu duba: Ga L=4, n=4, don haka n-2=2. Muna buƙatar kalmomin Dyck mai tsayi 2*(2)=4 haruffa a tsakiya? Dakata, a yi hankali: Ka'idar ta bayyana cewa ga n≥3, P[L=n] yayi daidai da jerin siffar w = SS X1...X_{2(n-2)} H, inda X's suka zama kalmar Dyck mai tsayi 2(n-2). Ga n=4, tsayi shine 2*(4-2)=4. Don haka ɓangaren tsakiya yana da haruffa 4 waɗanda suka zama kalmar Dyck. Misali: SS(SHSH)H? Yin taswira S→(, H→). Tsakiyar "SHSH" ta zama "()()", wanda shine kalmar Dyck. Ma'aunin yuwuwar shine p^{#S} q^{#H} = p^3 q^3? Bari mu ƙidaya S da H a cikin w=SS S H S H H: S ya bayyana sau 4? A zahiri: SS S H S H H: matsayi: S,S,S,H,S,H,H. Wannan shine S 4 da H 3. Don haka p^4 q^3. Tsarin yana ba da p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4. Akwai bambanci. Fayil ɗin PDF ya ce "Adadin haruffa 'S' (daidai da 'H') a cikin w shine n (daidai da n-1). Don haka, mun sami P[L=n] = p^{n-1} q^n C_{n-2}". Ga n=4, wannan shine p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4. Wannan ya dace da tsarin. Don haka misalin jerin SS S H S H H yana da S 4 da H 3, wanda shine p^4 q^3, ba p^3 q^4 ba. Don haka SS S H S H H ba ingantaccen jerin bane ga L=4 a ƙarƙashin sharuɗɗan kalmar Dyck? Wataƙila ba ma'auni bane. Bari mu yi taswira: S→(, H→). SS S H S H H ya zama ((( ) ( ) ). Wannan ba ma'auni bane (buɗe uku, rufe biyu). Don haka hakika, jerin da suka dace su ne waɗanda jimlar ƙidaya S shine n kuma ƙidaya H shine n-1, KUMA tsakiya shine kalmar Dyck. Sharuɗɗan Dyck suna tilasta ma'auni, wanda ke haifar da takamaiman ƙidaya. Don haka tsarin yana ɗaukar ingantattun hanyoyin kai da kyau.

Wannan tsarin yana ba da damar ƙididdigewa na tsari da lissafin yuwuwar ba tare da kwaikwayon sarkokin Markov ba.

5. Sakamako & Abubuwan Da Ke Tattare Da Su

Tsarin da aka samo don $\tilde{q}_B$ yana ƙididdige ƙofar riba don cinikin mai son kai. Misali, tare da $\gamma=0$, maharin yana buƙatar $q > \approx 0.25$ don samun riba, ƙasa da zato na $q>0.5$. Wannan yana nuna muhimmin rauni a cikin yarjejeniya.

Bayanin Ginshiƙi: Zane na $\tilde{q}_B$ da $q$ don ƙimar $\gamma$ daban-daban zai nuna: 1) $\tilde{q}_B > q$ ga $q$ sama da ƙofa, yana nuna riba. 2) Mafi girman $\gamma$ (mafi kyawun haɗin kai ga maharin) yana rage ƙofar riba kuma yana haɓaka ribar ƙimar hashrate mai bayyana.

6. Ra'ayi na Mai Binciken Masana'antu

Fahimta ta Asali: Kyawun takardar shine rage girman kai mai rikitarwa zuwa ingantaccen ƙirar haɗin kai. Ya bayyana cewa ribar cinikin mai son kai ba kawai game da ƙimar hashrate ba ce, amma game da haɗin ginin tsakanin jerin kai da abubuwan haɗin kai na al'ada (Kalmomin Dyck). Wannan ba dabara ce ta lissafi kawai ba; yana bayyana raunin yarjejeniyar Bitcoin a matsayin matsalar harshe na yau da kullun—tsaronta ya dogara da rarraba yuwuwar wasu tsarin kirtani a cikin tseren tubalan.

Kwararar Hankali: Marubutan sun fara ne da tsara zagayen kai a matsayin kirtani (jerin S/H). Babban motsi shine gane cewa nasarar kai (inda maharin ya sami duk tubalan da aka yarda da su) suna daidaitawa da kirtani waɗanda ainihin kalmomin Dyck ne waɗanda aka haɗa su ta hanyar masu farawa/ƙarewa na musamman. Wannan yana ba su damar shiga kai tsaye cikin babban injin haɗin kai na Catalan don ƙidaya da samar da yuwuwar, tare da ƙetare buƙatar warware daidaitattun lissafi don sarkar Markov. An samo tsarin ƙarshe ta hanyar haɗa ƙimar da ake tsammani na L (ta hanyar ayyukan samar da Catalan) da ƙimar da ake tsammani na Z (la'akari da matsanancin hali kamar L=1,2).

Ƙarfi & Kurakurai:
Ƙarfi: Hujjar tana da taƙaitaccen bayani kuma mai sauƙin fahimta. Yana bayyana tsarin kuɗin shiga na cinikin mai son kai. Haɗawa da Kalmomin Dyck na iya ƙarfafa sabbin bincike na wasu hare-haren blockchain (misali, hare-haren daidaitawa, hare-haren kusuf) ta amfani da ka'idar harshe na yau da kullun. Yana ƙarfafa ƙimar hanyoyin da suka haɗa fannoni daban-daban (crypto + haɗin kai).
Kurakurai: Ƙirar tana ɗauka cewa maharin mai tsayayye, mai dorewa tare da q akai-akai. Ba ta ɗauki daidaitawar motsi, shigar/ fita mai haƙo ma'adinai, ko tasirin masu haƙo ma'adinai masu son kai da yawa (matsala mai yuwuwar oligopoly). Ma'aunin $\gamma$ yana da sauƙi; yanayin hanyar sadarwa na ainihin duniya da jinkirin yaduwa sun fi sarkakiya. Kamar yadda aka lura a cikin bincike mai biyo baya kamar "Dabarun Cinikin Mai Son Kai Mafi Kyau a cikin Bitcoin" (Gervais et al., Financial Crypto 2016), dabarar cinikin mai son kai ta asali ba koyaushe ta fi dacewa ba; akwai ƙarin dabarun daidaitawa. Gudunmawar wannan takardar ta asali ce, ba cikakkiya ba.

Fahimta Mai Aiki:

1. Ga Masu Ƙirar Yarjejeniya: Tushen dalili shine ka'idar "farko-gani" da jinkirin yaduwar tubalan. Magani kamar "An Fi So Sabo" na Gervais ko "Rike Rike na Rike" na Decker da Wattenhofer (kamar yadda aka tura a cikin Bitcoin Core) suna nufin rage $\gamma$ da bambancin yaduwa. Tsarin wannan takardar yana ba da ma'auni mai ƙima don gwada irin waɗannan gyare-gyaren.
2. Ga Tafkunan Haƙo Ma'adinai: Lissafin ƙofa ($q$ ~0.25) layin ja ne. Tafkunan da ke gabatowa wannan girman yakamata a bincika su. Rarraba ba kawai akida ba ce; ma'auni ne na tsaro a cikin tsarin $\tilde{q}$.
3. Ga Masu Bincike: Taswirar kalmar Dyck samfuri ne mai ƙarfi. Nemi wasu hanyoyin yarjejeniya inda ayyukan mahalarta suka haifar da jerin da za a iya bincika su ta hanyar azuzuwan harshe na yau da kullun (na yau da kullun, marasa mahalli). Tsarin Tabbacin Hatsari, tare da takamaiman jerin zaɓe, na iya zama cikakke don irin wannan bincike.

Abin da za a ɗauka: Tsaron Blockchain yana ƙara zama fanni ga masana lissafi da masana harshe, ba kawai masu ɓoyayyen bayanai ba. Wannan takarda babban misali ne na wannan canji.

7. Aikace-aikace na Gaba & Jagorori

1. Ƙirar Kai Mai Tsanani: Za a iya daidaita tsarin kalmar Dyck don bincika bambance-bambancen cinikin taurin kai ko cinikin sawu, inda dabarun buga maharin ya bambanta.

2. Sauran Yarjejeniyoyin Yarjejeniya: Yin amfani da irin waɗannan hanyoyin haɗin kai ga Tabbacin Hatsari (misali, Casper na Ethereum) ko yarjejeniyoyin tushen DAG (misali, IOTA, Avalanche) na iya haifar da sabbin fahimta game da juriyarsu ga hare-haren riƙewa.

3. Tabbatar da Tsaro ta atomatik: Ana iya haɓaka kayan aiki don fassara ka'idojin yarjejeniyar yarjejeniya ta atomatik zuwa nahawu na yau da kullun kuma a duba don samuwar "nahawon kai mai riba" mai kama da tsarin Dyck da aka samo a nan.

4. Haɗin Dynamics na Cibiyar Sadarwa: Aikin gaba zai iya haɗa ƙarin ƙirar cibiyar sadarwa na gaske (misali, ta amfani da ƙirar annoba don yaduwar tubalan) cikin ma'auni na yuwuwar haɗin kai, tare da wucewa fiye da sauƙi na ma'aunin $\gamma$.

8. Nassoshi

1. Eyal, I., & Sirer, E. G. (2014). Mafi rinjaye bai isa ba: Haƙo ma'adinan Bitcoin yana da rauni. A cikin Kuɗin Kuɗi da Tsaron Bayanai (shafi na 436-454). Springer.
2. Stanley, R. P. (2015). Lambobin Catalan. Jami'ar Cambridge Press.
3. Nakamoto, S. (2008). Bitcoin: Tsarin kuɗi na kan layi tsakanin mutane.
4. Grunspan, C., & Pérez-Marco, R. (2018). Akan ribar cinikin mai son kai. arXiv preprint arXiv:1805.08281.
5. Gervais, A., Karame, G. O., Wüst, K., Glykantzis, V., Ritzdorf, H., & Capkun, S. (2016). A kan tsaro da aikin tabbacin aikin blockchain. A cikin Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (shafi na 3-16).
6. Bitcoin Wiki. Wahala. https://en.bitcoin.it/wiki/Difficulty.
7. Decker, C., & Wattenhofer, R. (2013). Yaduwar bayanai a cikin hanyar sadarwar Bitcoin. A cikin IEEE P2P 2013 Proceedings (shafi na 1-10). IEEE.