Независимый набор из синих вершин — иллюстрация к одной из подзадач биткойн-майнинга

Биткойн предоставляет ученым широчайшее поле для исследований. Для исследования вопросов, связанных с технологией блокчейна, приходится пользоваться множеством понятий из разных областей математики, computer science, экономики и других наук. Недавно эта многогранность биткойна в очередной раз подтвердилась: выяснилось, что быть идеальным майнером с математической точки зрения невероятно сложно.

В теории оптимизации подробно описан класс NP — класс задач, для решения которых, как предполагается, не существует эффективного (полиномиального) алгоритма. Здесь мы не говорим о широко известной задаче нахождения такого блока, что его хэш меньше заданной величины. Эта задача сложна по своей природе. Но перед тем, как начать что-либо хэшировать, майнер должен выбрать транзакции, которые войдут в блок. Оказывается, что эта задача содержит две оптимизационные подзадачи, обе из которых принадлежат классу NP!

В любой момент времени в биткойн-сети содержится множество транзакций, которые еще не были включены в блок. Майнеры могут включать или не включать транзакции в блок по своему усмотрению, предполагая, что они корректны по форме, ссылаются только на уже опубликованные (возможно, в этом же блоке) транзакции и не конфликтуют с ранее подтвержденными транзакциями. Каждая транзакция содержит комиссию. Размер блока не может превышать 1 мегабайт. Задача майнера — подобрать набор транзакций для блока, максимизируя сумму комиссий. Эта задача содержит две оптимизационные задачи.

Задача о ранце

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

Эта задача полностью эквивалентна широко известной «задаче о ранце». Задача о ранце формулируется так: пусть имеется ранец определенной вместимости и набор предметов, каждый из которых имеет два параметра — вес и ценность. Задача заключается в том, чтобы собрать ранец с максимальной ценностью предметов внутри, соблюдая при этом ограничение на вес ранца. В терминологии биткойна «ранец» — это блок, «вес» — это размер транзакции, «цена» — размер комиссии, а «вместимость ранца» — максимальный размер блока (на данный момент 1 мегабайт).

Задача о ранце хорошо изучена. Нахождение оптимального решения для нее принадлежит классу NP, а поиск ответа на вопрос, существует ли решение с суммарным вознаграждением, превышающим данное, является NP-полной задачей (то есть может быть сведена к другой задаче из класса NP полиномиальным алгоритмом). Следовательно, то же самое верно и для задачи составления биткойн-блока, даже без учета возможных конфликтов между транзакциями.

Задача о независимом множестве

Транзакции могут зависеть друг от друга или конфликтовать.

Рассмотрим сначала конфликты: некоторые транзакции не могут быть включены в один блок из-за запрета двойной траты. Упростим задачу, считая размер блока неограниченным и предполагая, что все транзакции включают одну и ту же комиссию. Если транзакции B и B’ в качестве входов используют один и тот же выход транзакции A, только одна из транзакций B и B’ может быть включена в блок. Предполагая это единственным ограничением на формирование блока, мы можем изобразить множество доступных транзакций в виде графа, где две транзакции соединены ребром, если они конфликтуют. Задача майнера — выделить максимальное подмножество вершин (транзакций), чтобы никакие две вершины из этого подмножества не были соединены ребром (не конфликтовали).

Это не что иное как хорошо изученная задача о независимом множестве! Следовательно, задача поиска оптимального решения принадлежит классу NP, а ответ на вопрос, существует ли решение с суммарной комиссией выше заданного уровня, является NP-полной задачей.

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

Кроме того, нам придется добавить на граф дополнительные ребра (конфликты): ведь если B зависит от A, а A конфликтует с A’, тогда B также конфликтует с A’. Для каждой транзакции B мы должны добавить в граф все транзакции, конфликтующие с транзакциями, от которых зависит B. Такая трансформация может быть проведена за полиномиальное время; для вершин модифицированного графа мы можем искать максимальное подмножество без конфликтов, решая задачу о независимом множестве. Задача принадлежит классу NP даже без учета размера транзакций и величины комиссии, а только лишь из-за наличия конфликтов.

Проблема на практике?

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

Но играет ли это роль на практике? Многие задачи в теории являются NP-сложными, но с практической точки зрения зачастую довольно просто найти достаточно хорошую аппроксимацию решения. Неясно, насколько сложной является задача нахождения «достаточно хорошего» биткойн-блока. Попытки двойной траты встречаются относительно редко, так же как и попытки включения в один блок транзакции и ее непосредственного предка. Так что проблема поиска независимого множества на практике не так сложна.

Что же касается «задачи о ранце» в формировании блока, то на практике она не очевидна. Биткойн-блоки обычно собираются из пула в тысячи или даже десятки тысяч транзакций, размер и комиссии у которых могут существенно различаться.

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

Помимо всего прочего, если майнеры будут использовать сложные алгоритмы для составления блока, существует возможность DoS-атак, при которых злоумышленники транслировали бы в сеть специальным образом составленные транзакции, требующие значительных вычислительных ресурсов при оценке целесообразности включения их в блок.

NP-сложные задачи майнинга — еще один пример того, как биткойн объединяет множество разделов математики и информатики. Поэтому он представляет и еще долго будет представлять огромный интерес для исследователей в этих областях.

По материалам Freedom to Tinker

Categories: Майнинг, Образование, Теория, Технологии