Уточнение стратегии майнинга для небольшой группы участников | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/22

Уточнение стратегии майнинга для небольшой группы участников

Ittay Eyal и Emin Gun Sirer описали стратегию проведения т. н. корыстного май-нинга, показывающую уязвимость протокола формирования цепочки блоков, реализованного в биткоине, к атаке со стороны группы участников майнинга, составляющей относительно небольшую часть от общего числа майнеров, и позволяющую ей получить вознаграждение, превышающее размер доли имеющихся у них вычислительных ресурсов. В настоящей работе предложена уточнённая вероятностно-автоматная марковская модель, основанная на предположении о независимости обеих групп участников.

Elaboration of selfish-mine strategy.pdf В работе приводится уточнение вероятностной модели стратегии поведения выделенной (корыстной) группы участников майнинга, у которой суммарная вычислительная мощность принадлежащих им ресурсов не превосходит половины от общей вычислительной мощности [1-3]. Пусть доля вычислительных ресурсов корыстной группы пропорциональна p = а < 1/2, а у второй группы, составленной из остальных участников, q = 1 - а. Авторы [1-3] исходят из предположения, что поведение групп участников моделируется биномиальным распределением с вероятностями p успешного подбора корыстной группой участников и q для случая успешного подбора группой остальных участников. В отличие от [3], будем предполагать, что обе группы участников действуют независимо, поэтому переходы между состояниями определяются не одной случайной величиной, а двумя независимыми случайными величинами £i и £2 с вероятностями успеха P[£i = 1] = p (для первой группы) и P[£2 = 1] = q (для второй группы) соответственно. При этом возможны не только ситуации, когда успех имеется у одной из сторон, но и ситуации, когда обе стороны одновременно добиваются успеха, а также когда успеха не добивается ни она из сторон. Общая идея стратегии корыстного майнинга состоит в том, что в случае успешного подбора цепочки из s блоков корыстная группа не обнародует результат, а держит его в тайне от остальных до тех пор, пока остальные участники сами не подберут очередной блок. В этом случае они поступают одним из следующих вариантов: - если s = 1 , то они обнародуют свой блок, создавая разветвление длины 1 и откладывая вопрос о том, какая из групп получит вознаграждение; - если s = 2, то корыстная группа раскрывает оба своих блока, тем самым получая вознаграждение за два блока и лишая вознаграждения группу остальных участников; - если s ^ 3, то они обнародуют блок, стоящий в начале своей сохраняемой в тайне цепочки, создавая разветвление из двух цепочек, либо увеличивая на 1 длину цепочки в существующем разветвлении, тем самым лишая группу остальных участников выигрыша. Такая стратегия моделируется с помощью автономного вероятностного автомата, множество состояний которого состоит из трёх групп. Первую группу составляют состояния Si, i = 0,1, 2,..., в которых у корыстной группы участников имеется преимущество в числе подобранных хеш-значений для блоков, равное номеру состояния. Отрицательные значения не рассматриваются, так как они соответствуют нулевому состоянию. Вторую группу составляют состояния Si,o, i ^ 2, в которых блокчейн допускает разветвление с двумя продолжениями, у которых длина цепочки, сформированной корыстной группой, содержит на i блоков больше, чем цепочка, сформированная группой остальных участников майнинга. Случай i = 1 также не рассматривается, так как в этом случае первая группа раскрывает свою цепочку и система переходит в нулевое состояние. Третью группу образуют состояния si,i при i ^ 1, которые соответствуют случаю разветвлений с двумя одинаковыми длинами продолжений исходной цепочки. Авторы [1] рассмотрели также случай, когда при наличии разветвления среди остальных участников найдётся подгруппа, составляющая (по мощности вычислительных ресурсов) долю, равную 7, 0 ^ 7 ^ 1, которая будет пытаться продолжить ветку, созданную выделенной группой, тем самым повышая вероятность получения вознаграждения корыстной группой за блоки, подобранные ею ранее. Модель [1] позволяет успешно рассчитать вероятность получения вознаграждения, превышающего долю имеющихся у группы вычислительных ресурсов - корыстная группа получает преимущество при выполнении неравенства 1 - Y 1 < a < -. 3 - 2y 2 Для анализа этой ситуации будем, как и раньше, рассматривать вероятностную модель, включающую две группы участников, осуществляющих майнинг с вероятностями успеха p и q. В тех случаях, когда для группы остальных участников имеется выбор того, для какой из цепочек строить продолжение, будем предполагать, что вероятность успешного подбора продолжения для цепочки, содержащей блоки, найденные групп-пой корыстных участников, равна yq, а для второй цепочки в разветвлении блокчейна она равна (1 - y)q. Поэтому для тех состояний, которые соответствуют разветвлению блокчейна, должно быть не четыре, а шесть вариантов перехода в другие состояния: (два варианта для корыстной группы) х (три варианта для группы остальных участников). Это моделируется случайной величиной, принимающей три значения 0, 1, 2 с вероятностями p, qY, q(1 - y) соответственно. Граф переходов вероятностного автомата, моделирующего поведение двух групп участников, приведён на рис. 1. Вершины графа переходов помечены индексами соответствующих состояний, а переходы - парами ab, соответствующими значениям случайных величин = a и = b (a,b Е {0,1, 2}). Из состояний первой группы имеются только четыре возможных перехода (табл. 1), а для состояний второй и третьей групп - шесть (табл. 2). Для изображения рёбер используются линии трёх типов: жирной линией нарисованы рёбра, соответствующие событиям, в которых корыстная группа гарантирует для себя вознаграждение, пунктиром - в которых вознаграждение получает группа остальных участников, а тонкие линии указывают, что ни одна из групп ничего не получает. Таблица 1 Переходы из состояний первой группы Метка Вероятность Событие перехода 00 qp Ни одна группа не нашла продолжения 01 q2 Вторая группа нашла продолжение второй цепочки 10 p2 Корыстная группа нашла продолжение своей цепочки 11 pq Обе группы нашли продолжение для своих цепочек Таблица 2 Переходы из состояний второй и третьей групп Метка Вероятность Событие перехода 00 qp Ни одна группа не нашла продолжения 01 q2 y Вторая группа нашла продолжение первой цепочки 02 q2 (1 - y) Вторая группа нашла продолжение второй цепочки 10 p2 Корыстная группа нашла продолжение своей цепочки 11 pqY Обе группы нашли продолжение первой цепочки 12 pq(1 - y) Обе группы нашли продолжение для своих цепочек Рис. 1. Граф переходов состояний при 0 ^ y ^ 1 Для удобства соберём в одну таблицу возможные переходы автомата (табл. 3). Для оценки вероятностей выигрыша каждой из групп необходимо сначала вычислить вероятности pi (i = 0,1,...), p^0 (i = 2, 3,...) и p^ (i = 1,2,...) нахождения системы в каждом из состояний. Будем исходить из предположения, что соответствующая цепь Маркова является стационарной, т. е. эти вероятности не зависят от момента времени. Поэтому вероятности нахождения системы в каждом из состояний должны удовлетворять следующей системе уравнений: Р0 = (p2 + q2) Е Pi,i + qP0 + pqp1 + q2 (P2 + P2,0) , Pi = pqpi + p2pi-1, i ^ 1, P1,1 = qpp1,1 + pqp0 + q2P1 + pq7 Epj,j, j>1 Pi,i = pqpi,i + pq(1 - y) Pi-1,i-1, i ^ 2, (1) P2,0 = qpp2,0 + q2P3,0 + pqp2,0 + pqp2 + q2P3, Pi,0 = qppi,0 + p2pi-1,0 + q2Pi+1,0 + pqpi,0 + pqpi + q2Pi+1, i ^ 3, EPi + E pi,i + E pi,0 = 1. i^0 i^2 Найдём выражения для всех вероятностей через вероятность p1 и значения параметров p, q и y. Таблица 3 Переходы модифицированного графа Исходное Метка Верояность Следующее Выигрыш состояние ребра перехода состояние обеих групп si (i > 0) 00 qp si (0,0) so 01 q2 so (0,1) si 01 q2 si,i (0,0) S2 01 q2 so (2,0) Si (i > 3) 01 q2 si-i,o (1,0) Si (i > 0) 10 p2 si+i (0,0) so 11 pq si,i (0,0) Si 11 pq so (2,0) si (i > 2) 11 pq si,o (1,0) si,i 00 pq si,i (0,0) si,i 01 q2 y so (i, 1) si,i 02 q2 (1 - y ) so (0,i +1) si,i 10 p2 so (i + 1, 0) sii 11 pqY si,i (i, 0) si,i 12 pq(1 - y ) si+i,i+i (0,0) si,o 00 qp si,o (0,0) s2,0 01 2 q y so (2,0) si,o (i > 2) 01 q2 y si-i,o (1,0) s2,0 02 q2 (1 - y ) so (2,0) si,o (i > 2) 02 q2 (1 - y ) si-i,o (1,0) si,o 10 p2 si+i,o (0,0) si,o 11 pqY si,o (1,0) si,o 12 pq(1 - y ) si,o (1,0) Утверждение 1. 1) Вероятности pi при i ^ 0 удовлетворяют соотношению p2 Pi+i = i-Pi. 1 - pq 2) Вероятности piti при i ^ 1 удовлетворяют соотношениям q(l - pq(2 - 7)) pq(1 - 7) Pi,i = p-w;-^, pi+i,i+i = -j-pi,i. p(1 - pq)(1 - 2pq) 1 - pq 3) Вероятности pi,o при i ^ 2 вычисляются по формулам 3 /2\\ i/ ,2/2 p° / p \\ p + q2 I q2 p2,0 = pi^-Г , pi+1,0 = pi\\ ~2 1--1q2(1 - pq) \\q2J \\1 - pq \\1 - pq Оценим величину R = r0/(r0 + rl) доли корыстной группы в общей сумме вознаграждения, полученной при применении описанной стратегии майнинга. Вознаграждение первой группы в этом случае определяется как p2 Г0 = pi(2pq + q2 ---+ q2p2fl) + q Е pi + q E pi,0 + p2 E (i + 1)pii + q7 E ipi,i. 1 - pq i^2 i^2 i^l i^l Для второй группы вознаграждение равно 1 - pq ri = q (p0 + (1 - y)pisi + yEpm) = q pi-2-+ (1 - 7) E(i + 1)pii + yEpm i^l \\ p i^l i^l Утверждение 2. Суммы вероятностей вычисляются по следующим формулам: p2 l^Pi = Р1 -, i^2 q q l^Pii = P1-г,-тг^;, i>1 p(1 - 2pq) Yd + i)p. . = p-,_q(2 - pq(3 - 7))_ + 1)pi,i = p1 p(1 - 2pq)(1 - pq(2 - 7)), j2ip-- = pi_q(1 - pq)_ i>1 v 1 p(1 - 2pq)(1 - pq(2 - y)) , ^ p3 2^pi,o = p^-г. i^2 q(q - p) Заметим, что выражение для R не зависит от p1. Само значение вероятности p1 находится из последнего равенства системы (1) с использованием соотношения ph ^ + p3 q + 1. p2q p(p2 + q2) q(q - p) Приведённые формулы позволяют вычислить значение доли R при произвольных значениях параметров 0 ^ p < 1/2 и 0 ^ 7 ^ 1. Результаты вычислений приведены на рис. 2-4. 0,5 Рис. 2 На рис. 2 показан график зависимости от параметра 7 минимального значения вероятности p, при котором впервые выполняется условие R > 1/2. Вычисления показывают, что выигрыш корыстной группы превышает при соответствующем значении 7 выигрыш остальной группы при значениях вероятности p в пределах 0,358 ^ p ^ 0,449. Наибольшее значение достигается при 7 = 0, а наименьшее при 7 =1. На рис. 3 показан аналогичный график зависимости от параметра 7 минимального значения вероятности p, при котором впервые выполняется условие R > p. Получаем, что выигрыш корыстной группы при соответствующем значении 7 превышает выигрыш, полученный ими при честном выполнении протокола, при значениях вероятности p в пределах 0

Ключевые слова

блокчейн, майнинг, марковская модель, вероятностный автомат, stream cipher, filter generator, combiner generator, gamma, Boolean function

Авторы

ФИООрганизацияДополнительноE-mail
Черемушкин Александр ВасильевичАкадемия криптографии РФдоктор физико-математических наук, профессор, член-корреспондентavc238@mail.ru
Всего: 1

Ссылки

Ittay E. and Emin G. S. Majority is Not Enough: Bitcoin Mining is Vulnerable. arXiv:1311.0243. 2013. http://arxiv.org/abs/1311.0243.
Ittay E. and Emin G. S. Majority is not enough: bitcoin mining is vulnerable // Financial Cryptography and Data Security: 18th Intern. Conf. Christ Church, Barbados, March 3-7, 2014. P. 436-454.
Ittay E. and Emin G. S. Majority is not enough: bitcoin mining is vulnerable // Commun. ACM. 2018. V.61. No. 7. P. 95-102. https://doi.org/10.1145/3212998.
 Уточнение стратегии майнинга для небольшой группы участников | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/22

Уточнение стратегии майнинга для небольшой группы участников | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/22