استخراج خودخواهانه بیت‌کوین و کلمات دیک: یک اثبات ترکیبیاتی

فهرست مطالب

1. مقدمه

استخراج خودخواهانه (SM) یک استراتژی نگهداری بلوک در بیت‌کوین است که از یک نقص در مکانیسم تنظیم سختی پروتکل سوءاستفاده می‌کند. برخلاف ماینرهای صادق که همیشه طولانی‌ترین زنجیره عمومی را گسترش می‌دهند، یک ماینر خودخواه بلوک‌های تازه استخراج شده را مخفی نگه می‌دارد تا یک فورک مخفی ایجاد کند و آن‌ها را به‌صورت استراتژیک منتشر کند تا درآمد خود را حداکثر کند. معیار کلیدی برای ارزیابی چنین استراتژی‌هایی، نرخ هش ظاهری بلندمدت $\tilde{q}$ است که نشان‌دهنده سهم بلوک‌های مهاجم در بلاک‌چین رسمی در طول زمان است.

تحلیل‌های قبلی بر زنجیره‌های مارکوف پیچیده یا تکنیک‌های مارتینگال متکی بودند. این کار یک اثبات ترکیبیاتی سرراست را با استفاده از کلمات دیک و اعداد کاتالان ارائه می‌دهد که استخراج نتایج را در دسترس‌تر و ظریف‌تر می‌سازد.

2. چرخه حمله و کلمات دیک

یک چرخه حمله را می‌توان به‌عنوان دنباله‌ای از رویدادها مدل کرد که در آن هر بلوک یا توسط ماینر خودخواه (S) یا توسط ماینرهای صادق (H) استخراج می‌شود.

2.1. نمایش دنباله

مثال: دنباله SSSHSHH نشان می‌دهد که ماینر خودخواه سه بلوک استخراج می‌کند، سپس ماینرهای صادق یک بلوک، سپس ماینر خودخواه یک بلوک، و سپس ماینرهای صادق دو بلوک استخراج می‌کنند. چرخه زمانی پایان می‌یابد که برتری ماینر خودخواه کاهش یابد و او را وادار به انتشار فورک خود کند.

2.2. توزیع L

فرض کنید $L$ تعداد بلوک‌های اضافه شده به بلاک‌چین رسمی در هر چرخه حمله باشد.

قضیه 2.2: $P[L=1] = p$، $P[L=2] = pq + pq^2$، و برای $n \geq 3$، $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$ که در آن $C_n = \frac{(2n)!}{n!(n+1)!}$ عدد کاتالان $n$ام است.

طرح اثبات: برای $n \geq 3$، رویداد ${L=n}$ مربوط به دنباله‌هایی است که با SS شروع می‌شوند، با H پایان می‌یابند و در آن بخش میانی، با نگاشت S→"(" و H→")"، یک کلمه دیک (رشته‌ای از پرانتزهای متوازن) به طول $2(n-2)$ را تشکیل می‌دهد. عدد کاتالان $C_{n-2}$ تعداد چنین کلمات دیکی را می‌شمارد.

3. نتایج ریاضی اصلی

3.1. مقدار مورد انتظار L

نتیجه 2.3: $E[L] = 1 + \frac{p^2 q}{p - q}$.

این نتیجه از روابط تابع مولد شناخته شده برای اعداد کاتالان به دست می‌آید.

3.2. فرمول نرخ هش ظاهری

فرض کنید $Z$ تعداد بلوک‌هایی باشد که مهاجم در هر چرخه به زنجیره رسمی اضافه می‌کند. نرخ هش ظاهری بلندمدت $\tilde{q} = E[Z] / E[L]$ است.

قضیه 2.4: نرخ هش ظاهری برای بیت‌کوین به این صورت است: $$\tilde{q}_B = \frac{[(p-q)(1+pq)+pq]q - (p-q)p^2q(1-\gamma)}{pq^2 + p - q}$$ که در آن $p$ نرخ هش ماینرهای صادق، $q$ نرخ هش مهاجم است ($p+q=1$، $q<1/2$) و $\gamma$ سهم ماینرهای صادقی است که در طول یک فورک روی بلوک مهاجم استخراج می‌کنند.

4. تحلیل فنی و چارچوب

4.1. چارچوب ریاضی

نوآوری اصلی، نگاشت دنباله‌های حمله به مسیرهای دیک (رشته‌های پرانتز متوازن) است. این کار، استخراج خودخواهانه را به ترکیبیات جاافتاده متصل می‌کند و محاسبات احتمالی را که قبلاً نیازمند فرآیندهای تصادفی بود، ساده می‌سازد.

فرمول کلیدی: احتمال $P[L=n]$ برای $n\geq3$ مستقیماً متناسب با عدد کاتالان $C_{n-2}$ است که با وزن‌های احتمالی $p$ و $q$ مقیاس شده است: $P[L=n] = p q^2 (pq)^{n-2} C_{n-2}$.

4.2. مثال چارچوب تحلیلی

تحلیل موردی برای L=4:

1. دنباله باید با SS شروع شود و با H پایان یابد.
2. دو موقعیت میانی باید یک کلمه دیک به طول 2 تشکیل دهند؟ فقط SH یا HS؟ بیایید بررسی کنیم: برای L=4، n=4، بنابراین n-2=2. ما به کلمات دیک به طول 2*(2)=4 کاراکتر در بخش میانی نیاز داریم؟ صبر کنید، با دقت: قضیه بیان می‌کند برای n≥3، P[L=n] مربوط به دنباله‌هایی به شکل w = SS X1...X_{2(n-2)} H است، که در آن Xها یک کلمه دیک به طول 2(n-2) تشکیل می‌دهند. برای n=4، طول 2*(4-2)=4 است. بنابراین بخش میانی 4 کاراکتر دارد که یک کلمه دیک تشکیل می‌دهد. مثال: SS(SHSH)H؟ با نگاشت S→(، H→). بخش میانی "SHSH" به "()()" تبدیل می‌شود که یک کلمه دیک است. وزن احتمال p^{#S} q^{#H} = p^3 q^3؟ بیایید تعداد S و H را در w=SS S H S H H بشماریم: S چهار بار ظاهر می‌شود؟ در واقع: SS S H S H H: موقعیت‌ها: S,S,S,H,S,H,H. این 4 تا S و 3 تا H است. بنابراین p^4 q^3. فرمول به ما p q^2 (pq)^{2} C_2 = p q^2 * p^2 q^2 * 2 = 2 p^3 q^4 می‌دهد. یک ناهمخوانی وجود دارد. فایل PDF می‌گوید "تعداد حروف 'S' (به ترتیب 'H') در w برابر n (به ترتیب n-1) است. بنابراین، ما P[L=n] = p^{n-1} q^n C_{n-2} به دست می‌آوریم". برای n=4، این می‌شود p^3 q^4 C_2 = p^3 q^4 * 2 = 2 p^3 q^4. این با فرمول مطابقت دارد. بنابراین دنباله مثال SS S H S H H دارای 4 S و 3 H است که p^4 q^3 است، نه p^3 q^4. بنابراین SS S H S H H یک دنباله معتبر برای L=4 تحت شرط کلمه دیک نیست؟ ممکن است متوازن نباشد. بیایید نگاشت کنیم: S→(، H→). SS S H S H H به ((( ) ( ) ) تبدیل می‌شود. این متوازن نیست (سه باز، دو بسته). بنابراین در واقع، دنباله‌های معتبر آنهایی هستند که در آن تعداد کل S برابر n و تعداد H برابر n-1 است، و بخش میانی یک کلمه دیک است. شرط دیک، توازن را اعمال می‌کند و منجر به شمارش خاص می‌شود. بنابراین چارچوب به ظرافت مسیرهای حمله معتبر را ثبت می‌کند.

این چارچوب اجازه شمارش سیستماتیک و محاسبه احتمال را بدون شبیه‌سازی زنجیره‌های مارکوف فراهم می‌کند.

5. نتایج و پیامدها

فرمول استخراج شده برای $\tilde{q}_B$ آستانه سودآوری برای استخراج خودخواهانه را کمّی می‌کند. برای مثال، با $\gamma=0$، مهاجم به $q > \approx 0.25$ نیاز دارد تا سود کند، که کمتر از فرض ساده‌انگارانه $q>0.5$ است. این یک آسیب‌پذیری بحرانی پروتکل را برجسته می‌سازد.

توضیح نمودار: یک نمودار از $\tilde{q}_B$ در مقابل $q$ برای مقادیر مختلف $\gamma$ نشان می‌دهد که: 1) $\tilde{q}_B > q$ برای $q$ بالاتر از یک آستانه، که نشان‌دهنده سودآوری است. 2) $\gamma$ بالاتر (اتصال بهتر برای مهاجم) آستانه سودآوری را کاهش می‌دهد و سود نرخ هش ظاهری را افزایش می‌دهد.

6. دیدگاه تحلیلگر صنعت

بینش اصلی: ظرافت مقاله در کاهش یک حمله پیچیده و دارای حالت به یک مدل ترکیبیاتی تمیز است. این نشان می‌دهد که سودآوری استخراج خودخواهانه فقط مربوط به نرخ هش خام نیست، بلکه درباره اتصال ساختاری بین دنباله‌های حمله و اشیاء ترکیبیاتی متعارف (کلمات دیک) است. این فقط یک ترفند ریاضی نیست؛ بلکه آسیب‌پذیری پروتکل بیت‌کوین را به عنوان یک مسئله زبان صوری آشکار می‌سازد - امنیت آن به توزیع احتمال الگوهای رشته خاص در رقابت بلوک بستگی دارد.

جریان منطقی: نویسندگان با قالب‌بندی چرخه حمله به عنوان یک رشته (دنباله S/H) شروع می‌کنند. حرکت کلیدی، تشخیص این است که حملات موفق (جایی که مهاجم تمام بلوک‌ها را پذیرفته می‌شود) مربوط به رشته‌هایی است که اساساً کلمات دیکی هستند که با شروع‌کننده‌ها/پایان‌دهنده‌های خاص محدود شده‌اند. این به آن‌ها اجازه می‌دهد مستقیماً به ماشین‌آلات گسترده ترکیبیات کاتالان برای شمارش و تولید احتمال دسترسی پیدا کنند و از نیاز به حل معادلات تعادل برای یک زنجیره مارکوف عبور کنند. فرمول نهایی با اتصال مقدار مورد انتظار L (از طریق توابع مولد کاتالان) و مقدار مورد انتظار Z (با در نظر گرفتن موارد حاشیه‌ای مانند L=1,2) به دست می‌آید.

نقاط قوت و ضعف:
نقاط قوت: اثبات به‌طور قابل توجهی مختصر و در دسترس است. این فرمول درآمد استخراج خودخواهانه را رمززدایی می‌کند. پیوند دادن به کلمات دیک می‌تواند تحلیل‌های جدیدی از سایر حملات بلاک‌چین (مانند حملات متوازن‌سازی، حملات خورشیدگرفتگی) با استفاده از نظریه زبان‌های صوری الهام بخشد. این ارزش رویکردهای بین‌رشته‌ای (رمزنگاری + ترکیبیات) را تقویت می‌کند.
نقاط ضعف: مدل فرض می‌کند مهاجم ایستا، پایدار و با q ثابت است. این مدل سازگاری پویا، ورود/خروج ماینرها، یا تأثیر چندین ماینر خودخواه (یک مشکل بالقوه الیگارشی) را ثبت نمی‌کند. پارامتر $\gamma$ ساده‌انگارانه است؛ توپولوژی شبکه واقعی و تأخیرهای انتشار پیچیده‌تر هستند. همانطور که در تحقیقات بعدی مانند "استراتژی‌های بهینه استخراج خودخواهانه در بیت‌کوین" (Gervais و همکاران، Financial Crypto 2016) اشاره شده است، استراتژی اصلی استخراج خودخواهانه همیشه بهینه نیست؛ استراتژی‌های سازگارتر وجود دارند. سهم این مقاله بنیادی است، نه جامع.

بینش‌های عملی:

1. برای طراحان پروتکل: علت ریشه‌ای، قاعده "اولین مشاهده" و انتشار آهسته بلوک است. راه‌حل‌هایی مانند "اولویت تازگی" Gervais یا "انتقال بلوک فشرده" Decker و Wattenhofer (همانطور که در Bitcoin Core مستقر شده است) هدف کاهش $\gamma$ و واریانس انتشار را دارند. فرمول این مقاله یک متریک کمّی برای آزمایش چنین اصلاحاتی ارائه می‌دهد.
2. برای استخرهای استخراج: محاسبه آستانه ($q$ ~0.25) یک خط قرمز است. استخرهایی که به این اندازه نزدیک می‌شوند باید مورد بررسی دقیق قرار گیرند. تمرکززدایی فقط ایدئولوژیک نیست؛ بلکه یک پارامتر امنیتی در فرمول $\tilde{q}$ است.
3. برای تحلیلگران: نگاشت کلمه دیک یک الگوی قدرتمند است. به دنبال سایر مکانیسم‌های اجماع باشید که در آن اقدامات شرکت‌کنندگان دنباله‌هایی ایجاد می‌کنند که توسط کلاس‌های زبان صوری (منظم، مستقل از متن) قابل تحلیل هستند. سیستم‌های اثبات سهام، با دنباله‌های رأی‌دهی صریحشان، ممکن است برای تحلیل مشابه آماده باشند.

نتیجه‌گیری: امنیت بلاک‌چین به طور فزاینده‌ای زمینه‌ای برای ریاضیدانان و زبان‌شناسان کاربردی است، نه فقط رمزنگاران. این مقاله نمونه‌ای بارز از این تغییر است.

7. کاربردها و جهت‌های آینده

1. مدل‌های حمله گسترش‌یافته: چارچوب کلمه دیک را می‌توان برای تحلیل انواع استخراج لجبازانه یا استخراج دنباله‌ای تطبیق داد، جایی که استراتژی انتشار مهاجم متفاوت است.

2. سایر پروتکل‌های اجماع: اعمال روش‌های ترکیبیاتی مشابه به اثبات سهام (مانند Casper اتریوم) یا پروتکل‌های مبتنی بر DAG (مانند IOTA، Avalanche) می‌تواند بینش‌های جدیدی در مورد مقاومت آن‌ها در برابر حملات نگهداری به دست دهد.

3. تأیید امنیت خودکار: می‌توان ابزارهایی توسعه داد تا قواعد یک پروتکل اجماع را به یک دستور زبان صوری ترجمه کنند و وجود "دستور زبان‌های حمله سودآور" مشابه ساختار دیک یافت شده در اینجا را بررسی کنند.

4. ادغام پویایی شبکه: کار آینده می‌تواند مدل‌های شبکه واقعی‌تر (مانند استفاده از مدل‌های اپیدمی برای انتشار بلوک) را در وزن‌های احتمال ترکیبیاتی ادغام کند و فراتر از پارامتر ساده $\gamma$ حرکت کند.

8. مراجع

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.