Начнем с примечания к именованию - мне откровенно не нравится название эгоистичный майнинг. Всякий майнинг блокчейнов эгоистичен и делается для получения дохода. Правильным и не требующим пояснений термином эгоистичный майнинг будет скрытый майнинг.
Я считаю, что Aviv Zohar обратил внимание на тот факт, что при использовании скрытого майнинга вы можете создать атаку с двойным расходом. По сути, вы держите майнинг-блок в стороне от основной цепочки. Поскольку в блокчейне действует правило, что самая длинная действительная цепочка считается реестром, если ваша цепочка окажется длиннее, чем обычная консенсусная цепочка, то транзакции там будут приняты, а не транзакции в глобальной цепочке. Скажем, у вас есть 25% мощности майнинга в сети, это может быть в пределах ~ 4096 10-минутных периодов - ›Примерно 280 дней, когда у вас будет такая возможность, что вы будете на 6 блоков впереди основной цепи. В этом случае вы можете организовать перевод большой суммы биткойнов в обмен на доллары США. Затем подождите, как указано в пользовательских 6 эпохах, чтобы транзакция считалась принятой. Затем вы вынимаете кролика из шляпы, отправляете свою скрытую цепочку и переопределяете основную цепочку, отменяя передачу биткойнов, сделанную ранее. Вы убегаете со своими долларами и проводите остаток своей жизни в Гватемале по неизвестным причинам.
Но сколько времени вам понадобится, чтобы выполнить эту схему быстрого обогащения?
Для этого я создал для вас калькулятор, который можно найти на Github.
Интересно объяснить математику, лежащую в основе этого расчета. На самом деле здесь происходит что-то вроде случайного блуждания. При вероятности p, p, являющейся вашей долей в общей мощности майнинга, вам удастся достичь блока раньше, чем это сделает остальной мир. С вероятностью 1-p они это сделают раньше вас. Затем, если вы достигнете 6, то есть вам удалось продвинуться на 6 блоков больше, чем остальной мир, вы выиграете. Это похоже на проблему разорения игрока - сколько времени потребуется игроку с ограниченными ресурсами X, чтобы закончить свои ресурсы, играя против казино. Но есть несколько отличий. Прежде всего, всякий раз, когда остальной мир получает преимущество над вами, вы можете вернуться к их цепочке. Никакого вреда не будет, вы начнете снова. Таким образом, случайное блуждание никогда не может уйти в отрицательную сторону оси. Учитывая это, вы не можете напрямую использовать формулы случайного блуждания.
Итак, вы строите рекурсивную формулу для вероятности оказаться на k шагов от начала координат после n эпох случайного блуждания. Ограничимся k ‹= 6. Формулы выглядят так:
F(n,k) = pF(n-1,k-1) + (1-p)F(n-1,k+1)
F(n,0)= (1-p)F(n-1,0) + (1-p)F(n-1,1)
Существуют и другие граничные случаи, например, F (1,2), очевидно, равно 0 - вы не можете добраться до расстояния 2 от начала координат всего за один шаг.
Нашей конечной целью было бы представить F (n, k) не как рекурсивную функцию, зависящую от других значений F, а как явную формулу в терминах p.
К сожалению, это сложная математика.
Но есть более простое решение с использованием динамического программирования. Вместо рекурсивного выполнения формулы, что приводит к вычислению экспоненциальной сложности, вы можете посмотреть на решето, созданное F, и перейти от нижних значений пар (n, k) вверх. Затем это становится операцией полиномиальной сложности.
Я реализовал это вычисление сита в Python, чтобы оценить для различных значений p количество времени, необходимое для генерации атаки в эпохи майнинга биткойнов. В основном то, что я делаю, - это массив Numpy, представляющий коэффициенты p для каждой комбинации n, k. Я бегу индуктивно, чтобы вычислить F для растущих значений n. Из соображений памяти и простоты я ограничиваю значение k до 6, поэтому приближение будет F (n, 6) = pF (n-1,5) + pF (n-1,6) вместо того, чтобы расширяться до более высоких значений k. . Это приближение фактически снижает вероятность успеха атаки, поэтому можно ожидать немного более высокую оценку эпох. Я оставил код открытым, чтобы расширить его до более высоких значений k, скажем, 12.
Есть несколько проблем, с которыми вы столкнетесь довольно быстро, когда реализуете его:
- Когда у вас есть сито, как найти точку, для которой вероятность достаточно высока? Для этого я использовал этот замечательный отрывок из Generic Binary search, который я нашел здесь.
- Размер памяти. Коэффициенты F растут линейно, поэтому для F (10000, k) у вас уже будет 10K коэффициентов, каждый из которых имеет максимальный размер с плавающей запятой, поэтому 16 байт. Это 160 КБ на каждую точку в сите, поэтому, учитывая, что размер сита при таком размере составляет около 60К, это можно оценить как до 1 ГБ ОЗУ… Это много. Что я сделал, чтобы справиться с этим, так это раздвинуло окно сита. Итак, я рассчитал первые 200 n-значений. Я проверяю, достаточно ли велика вероятность. Если это так, я выполняю двоичный поиск в текущем окне. Если нет, я генерирую следующее окно из 200 n-значений. Преимущество рекурсивной формулы заключается в том, что вычисление n зависит только от значений n-1. Так что на самом деле вам не нужно запоминать все сразу.
- Проблемы с плавающей запятой - все быстро. Я просто использовал longdouble numpy, который предположительно является наиболее точным из доступных чисел с плавающей запятой, без реализации моей собственной версии float, что было бы громоздко.
Наслаждайтесь симулятором!
