Эгоистичный майнинг в Bitcoin и слова Дика: Комбинаторное доказательство

Содержание

1. Введение

Эгоистичный майнинг (ЭМ) — это стратегия удержания блоков в Bitcoin, эксплуатирующая недостаток в механизме регулирования сложности протокола. В отличие от честных майнеров, которые всегда расширяют публичную самую длинную цепочку, эгоистичный майнер удерживает вновь добытые блоки, чтобы создать секретный форк, и публикует их стратегически для максимизации дохода. Ключевой метрикой для оценки таких стратегий является долгосрочный видимый хешрейт $\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: Видимый хешрейт для Bitcoin: $$\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 встречается 4 раза? На самом деле: 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. Взгляд отраслевого аналитика

Ключевая идея: Элегантность статьи заключается в сведении сложной, сохраняющей состояние атаки к чистой комбинаторной модели. Она показывает, что прибыльность эгоистичного майнинга зависит не только от сырого хешрейта, но и от структурной связи между последовательностями атаки и каноническими комбинаторными объектами (словами Дика). Это не просто математический трюк; это раскрывает уязвимость протокола Bitcoin как проблему формального языка — его безопасность зависит от распределения вероятностей определённых строковых паттернов в гонке блоков.

Логический поток: Авторы начинают с представления цикла атаки как строки (последовательности S/H). Ключевой шаг — осознание, что успешные атаки (где атакующий добивается принятия всех своих блоков) соответствуют строкам, которые по сути являются словами Дика, обрамлёнными определёнными начальными и конечными символами. Это позволяет им напрямую использовать обширный аппарат каталановой комбинаторики для подсчёта и генерации вероятностей, минуя необходимость решения уравнений равновесия для цепи Маркова. Итоговая формула выводится путём связи математического ожидания L (через производящие функции Каталана) и математического ожидания Z (с учётом крайних случаев, таких как L=1,2).

Сильные стороны и недостатки:
Сильные стороны: Доказательство удивительно лаконично и доступно. Оно демистифицирует формулу дохода от эгоистичного майнинга. Связь со словами Дика может вдохновить на новые анализы других атак на блокчейн (например, атак на баланс, eclipse-атак) с использованием теории формальных языков. Это усиливает ценность междисциплинарных подходов (криптография + комбинаторика).
Недостатки: Модель предполагает статичного, постоянного атакующего с постоянным q. Она не учитывает динамическую адаптацию, вход/выход майнеров или влияние нескольких эгоистичных майнеров (потенциальная проблема олигополии). Параметр $\gamma$ упрощён; реальная топология сети и задержки распространения сложнее. Как отмечено в последующих исследованиях, таких как "Оптимальные стратегии эгоистичного майнинга в Bitcoin" (Gervais et al., Financial Crypto 2016), исходная стратегия эгоистичного майнинга не всегда оптимальна; существуют более адаптивные стратегии. Вклад данной статьи является фундаментальным, а не исчерпывающим.

Практические выводы:

1. Для разработчиков протоколов: Коренная причина — правило "первого увиденного" и медленное распространение блоков. Решения, такие как "Freshness Preferred" от Gervais или "Compact Block Relay" от Decker и Wattenhofer (развёрнутые в Bitcoin Core), направлены на снижение $\gamma$ и вариативности распространения. Формула из данной статьи предоставляет измеримую метрику для тестирования таких исправлений.
2. Для майнинг-пулов: Расчёт порога ($q$ ~0.25) — это красная линия. Пулы, приближающиеся к такому размеру, должны подвергаться тщательной проверке. Децентрализация — это не просто идеология; это параметр безопасности в формуле $\tilde{q}$.
3. Для аналитиков: Отображение на слова Дика — мощный шаблон. Ищите другие механизмы консенсуса, где действия участников создают последовательности, анализируемые классами формальных языков (регулярные, контекстно-свободные). Системы Proof-of-Stake с их явными последовательностями голосования могут быть готовы для подобного анализа.

Вывод: Безопасность блокчейна всё больше становится областью для прикладных математиков и лингвистов, а не только криптографов. Данная статья — яркий пример этого сдвига.

7. Будущие применения и направления

1. Расширенные модели атак: Методология слов Дика может быть адаптирована для анализа вариантов упрямого майнинга или следового майнинга, где стратегия публикации атакующего отличается.

2. Другие протоколы консенсуса: Применение аналогичных комбинаторных методов к Proof-of-Stake (например, Casper в Ethereum) или 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.