Атака double-spending в системе Биткоина

Когда осуществляется сделка за биткоины, то ожидается, что после перечисления монет отправитель получает в ответ продукт или услугу, которую он оплатил. Но что же делать, когда после получения продукта, отправителем генерируется новая конфликтующая транзакция, отправляющая эти же монеты самому себе? Выходит, пока получатель биткоинов не будет уверен, что монеты окончательно присвоятся ему и не смогут быть перенаправлены еще куда-то без его согласия, он не будет в безопасности, чтобы предоставить взамен полученных BTC продукт, который был куплен.

Атака «double-spending» (двойное расходование) заключается в том, что сначала продавец убеждается в проведении транзакции на оплату, после чего он передает свой товар, а после получения товара покупателем создается новая транзакция, которая и принимается сетью Биткоина вместо первой. У продавца не останется ни товара, ни денег - и то и другое будет у злоумышленника.

Проблема заключается в синхронизации: требуется какой-то универсальный сигнал, указывающий, что некая транзакция является конечной и никаких других конфликтующих транзакций принято не будет. Разработчики bitcoin защищают систему, утверждая, что подобная атака требует очень высоких вычислительных ресурсов. Однако, если злоумышленник все же обладает существенными вычислительными ресурсами, то атака возможна. В официальном документе Сатоши Накамото, описывающем биткоины, содержатся статистические рассуждения, касающиеся этой проблемы. Данная статья уточняет и расширяет данные рассуждения.

Транзакции bitcoin группируются в блоки. Каждый блок ссылается на предыдущий через включенный в его заголовок уникальный хэш, идентифицирующий предыдущий блок. За исключением первого блока, который, естественно, ни на что не ссылается.

Цепочку блоков можно представить в виде дерева, начинающегося с начального блока и идущую последовательно. Ветви этого дерева представляют собой истории биткоин транзакций. Ветвь не может содержать двух конфликтных транзакций, однако может быть другая ветка, которая содержит противоречащую транзакцию. Это соответствует ситуации, когда в один момент сгенерировалось 2 разных блока и часть узлов стало майнить от одного блока, а другая часть – от второго. Обычно, такое разногласие разрешается, как только находится следующий блок. Верной веткой считается та, которая включает в себя более длинную цепь последующих блоков.

Рис.1. Дерево начинается снизу, стрелки показывают с какого блока на какой идет ссылка в заголовке блока. (a) Возможный вариант построения дерева. (b) Помеченная ветка недействительна, потому что ее длинна составляет только 3 блока, в то время как существует более длинная ветка. (c) Темная ветка, как и прямая, имеет наибольшую длину, поэтому некоторыми узлами считается действительной. (d) Когда находится новый блок, который ссылается только на один из предыдущих блоков, то какая-то ветка становится длиннее и принимается всеми узлами, как действительная.

Договоримся, что транзакция имеет n подтверждений, если она включена в блок, который является частью действующей цепочки, и существует n блоков, включая данный и все последующие, идущие от него. Считается, что обезопасить транзакцию от double-spending может достаточное число таких подтверждений.

Для проведения успешной атаки double-spending требуются следующие шаги:

1. Выполнить транзакцию, которая атакует прежде осуществлённую оплату.
2. Тайно майнить, используя тот блок, который включает в себя эту последнюю транзакцию.
3. Подождать, пока транзакция, отправляющая деньги продавцу получит достаточно подтверждающих блоков, и продавец передаст свой товар, уверенный, что деньги окончательно присвоены ему.
4. Продолжать майнить тайную альтернативную ветку, пока она не станет больше, чем публичная, после чего ее транслируются в сеть. Поскольку новая ветвь длиннее всех других известных, то она будет считаться действительной, и перевод btc продавцу будет заменен отправкой монет злоумышленнику.

Рис. 2. Осуществление атаки double-spending.

(a) Состояние сети до действий злоумышленника. (b) Ветка слева включает в себя транзакцию отправки btc продавцу. Имеет 2 подтверждения. В результате чего продавец передал свой продукт. В это время у злоумышленника сгенерирован блок, включающий атакующую транзакцию. (c) Если атакующему удается создать цепочку длиннее, то он публикует ее в сеть, и биткоины возвращаются ему.

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

Для моделирования ситуации сделаем несколько упрощающий допущений, которые будем использовать в последующем анализе:

1. Общая скорость майнинга в общей сети и у атакующего остается постоянной. Суммарная скорость майнинга будет H, из которой часть pH относится к честным майнерам, а qH – к злоумышленнику. При этом: p + q = 1. То есть вероятность, что блок найдет честная сеть равна p, а что злоумышленник – q.
2. Сложность майнинга остается постоянной.

Обозначим буквой z = n – m число блоков, в которых честная сеть имеет преимущество перед атакующим. После каждого обнаружения нового блока z меняется, увеличиваясь на 1, если его нашла честная сеть, и, уменьшаясь на 1 - если злоумышленник. Математически это представляет собой цепь Маркова.

Если z достигает значение -1, то атака удается. Если этого никогда не происходит, то атака провалена. Поскольку нас интересует, станет ли когда-нибудь z=-1, и когда это случится, то можно использовать для решения задачи теорию цепей Маркова, где каждый шаг представляет собой факт нахождения блока кем-либо. zi+1 может быть равным либо (zi+ 1) с вероятностью p, либо (zi - 1) с вероятностью q.

Рис. 3. Вероятность обгона. (a) успешная попытка double-spending после 15 обнаруженных блоков. (b) Проваленная попытка атаки: после 20 обнаруженных блоков сеть получила настолько значительное преимущество, что шансы атакующего догнать незначительны.

az- вероятность, что злоумышленник обгонит сеть, при отставании в z блоков. Очевидно, что если z < 0 то az = 1, то есть атака удалась.
az+1 – вероятность обогнать сеть на следующем шаге, когда новый блок был найден честной сетью, что возможно с вероятностью p.
az-1 – вероятность обогнать сеть на следующем шаге, когда новый блок был найден злоумышленником, что возможно с вероятностью q.

Учитывая p + q = 1 и ограничивающие условия, найдем az:

Сразу понятно, что если атакующий владеет более чем половиной мощностей сети bitcoin, то его атака удастся.

Шансы на успех зависят от значения z в момент времени, когда товар передан, а значит уже есть цепочка из n подтверждающих блоков. В своей статье Сатоши рассчитывает среднее число блоков злоумышленника с помощью распределения Пуассона, как nq/p. Мы не будем использовать данное решение, а используем более точную модель m, как отрицательную биномиальную переменную. Функция вероятности от числа успехов отыскания блоков злоумышленником перед тем, как будет найдено n блоков в честной сети:

Гонка начинается с z=n-m-1 (при условии, что один блок был предварительно получен злоумышленником, прежде чем он начал атаку) Отсюда следует, что вероятность осуществления атаки double-spending, когда продающий подождал n подтверждений, равна:

Построим график полученного решения.

Рис.4. Вероятность r успешности атаки, как функция зависимости от соотношения уровня мощностей майнинга у атакующего ко всей суммарной мощности. Разными цветами нарисованы графики для различного числа подтверждающих блоков n. Больше подтверждений уменьшает вероятность успеха атаки. При приближении соотношения мощностей к 50%, вероятность успеха приближается к 100%

Также составим график еще один график:

Рис 5. Зависимость числа подтверждающих блоков от уровня соотношения мощности майнинга атакующего q. Цветами выделены следующие вероятности успешности атаки: 10% - желтый, 1% - фиолетовый и 0,1% - синий.

Например, если мощность сети злоумышленника составляет 10% от общей мощности, то требуется 2 подтверждения, чтобы сделать вероятность атаки меньше 10%, 4 подтверждения, чтобы меньше 1% и 6, чтобы меньше 0,1%.

В таблице ниже представлены значения вероятности успеха атаки в зависимости от q - соотношения мощностей майнеров, принадлежащих злоумышленнику, ко всей мощности сети bitcoin и числа подтверждений n.

Из этой таблицы можно сделать следующие выводы:

• Есть вероятность успеха атаки при любых уровнях мощности атакующего.
• Ожидание как можно большего числа подтверждающих блоков увеличивает вероятность провала атаки.
• Вероятность провала атаки зависит от количества подтверждающих блоков, а не от времени ожидания после осуществления транзакции. Альтернативные биткоину сети, таким образом, могут дать более высокий уровень безопасности сделки, при одинаковом времени ожидания до выдачи товара.
• Никакое количество подтверждений не снизит вероятность успеха до полного 0.

Посчитаем экономический уровень прибыли для атакующего при атаке double-spending:

1. Атака может быть осуществлена против более чем одного продавца. Альтернативные платежи могут быть направлены одновременно против k различных продавцов.
2. От каждого торговца будут приобретаться продукты со средней стоимостью v, которую мы будем считать итоговой стоимостью.
3. Независимо от того, удастся атака или нет, злоумышленник получит товар на сумму kv.
4. Если атака не удастся, и злоумышленник успеет найти j блоков за время попытки, каждый по цене B, все они будут отклонены и злоумышленник потеряет сумму равную jB.

Вероятность провала атаки равна 1 – r (функцию от n и q, найденную ранее). Тогда выгода будет рассчитываться следующим образом:

Для того, чтобы атака была прибыльной, требуется выполнение условия:

Продавец в безопасности до тех пор, пока стоимость товара достаточно невысока, чтобы было экономически невыгодно осуществлять такую атаку. Посчитаем на примере. Пусть j = 20, то есть злоумышленник сгенерировал 20 блоков, прежде чем прекратил попытки генерации. B = 25BTC – награда за один блок. А k = 5. Тогда продавец защищен от атаки ввиду ее нецелосообразности до тех пор, пока выполняется следующее:

Максимальные безопасные суммы сделок в BTC для различных значений числа подтверждающих блоков n и уровней мощности майнинга у злоумышленника представлены в таблице. Таблица основана на рассматриваемом примере. Но это не 100% точные цифры, так как было сделано много допущений при моделировании системы.

Полученные результаты опровергают те мифы, которые существовали ранее, связанные с атакой double-spending, а именно:

1. Данная атака требует более половины всех мощностей сети bitcoin.
2. Ожидание подтверждающих блоков значительно защищает от атаки с большими мощностями майнинга.
3. 6 подтверждающих блоков дают полную защиту от атаки.
4. Важно подождать как можно больше времени после транзакции, не обращая внимания на то, сколько было в это время сгенерировано блоков.