Как проблема перебора может разбить биткоин

Биткоин, как считают многие крипто-энтузиасты и крипто-евангелисты, — это неприкосновенная система, которую нельзя разрушить и разбить. Но ученые-информатики не до конца согласны с этим утверждением, ведь если решится одна из семи задач тысячелетия по программированию, то биткоин… Что станет с главной цифровой монетой после доказательства P=NP?

Почему это уравнение так важно для криптографии

Вопрос проблемы перебора, или вопрос о равенстве классов сложности P и NP, где P — это задачи более простого уровня, а NP — трудного, уже более трех десятилетий волнует всех исследователей, которые занимаются теорией вычислительной сложности. В этом разделе теории алгоритмов изучаются такие общие ресурсы, как время (сколько нужно сделать шагов) и память (ее объем для выполнения задачи), поэтому проблема равенства P=NP заключается в вопросе о том, что если ответ на какой-то вопрос можно довольно быстро проверить в рамках полиномиального времени (класс Р), то правда ли, что ответ на этот вопрос можно довольно быстро найти. Будет ли это значить, что решение задачи проверить не легче, чем отыскать его? Если кто-то даст правильный ответ на эту задачу тысячелетия, то он изменит цифровой мир, ведь в теории все алгоритмические задачи, в том числе связанные с крипто-индустрией, будут решаться гораздо быстрее, чем сейчас, и получит $1 миллион от американского Математического института Клэя. Например, к задачам NP относится вскрытие шифра. Сегодня ее можно решить только с помощью перебора всех возможных комбинаций и подбора нужного кода. И если это уравнение не равно, то сохранится асимметрия, на которой основывается биткоин.

Нарушить асимметрии — значит разрушить биткоин

Вся крипто-система состоит из алгоритмической и вычислительной асимметрий, ведь именно они обеспечивают желаемую децентрализацию сети. Следовательно, чтобы разрушить биткоин или альткоины, нужно разбить эти асимметрии. Асимметрия представляет собой нарушение и несоответствие одной стороны другой и не выполняет функцию симметрии f(x)=f(-x) вдоль оси y. Это имеет прямое отношение к цифровому миру, так как он основан на производственных элементах доверия, которые устанавливаются с помощью криптографии с открытым ключом — асимметричная криптография (алгоритмическая асимметрия) и доказательства работы, алгоритм Proof-of-Work (вычислительная асимметрия).

Асимметричная криптография представляет из себя систему шифрования и электронной подписи, при которой открытый ключ передается доступному для наблюдения каналу, она возникает в момент, когда уровень усилий для решения проблемы значительно превышает действия для проверки решения задачи. Например, если вычислять дискриминант квадратного уравнения x^2+2x+3=0, то в ответе будет два решения, где x=1 и x=-3, после получения этих данных можно подставить числа в уравнение и убедиться, что все сделано правильно. То есть в данном случае вначале проще проверить решение, а потом и саму проблему. В более сложном математическом алгоритме нельзя так просто взять и подставить полученные числа.

Дигитализация подразумевает создание защищенной электронной системы блокировки и ключа в транзакциях биткоина и других монет, которые основаны на алгоритме консенсуса Proof-of-Work. Безопасная цифровая система блокировки  создает тот желаемый результат, к которому стремится вся индустрия — защищенность сети. Без этого бы не существовал биткоин, а блокчейн был бы очередной ненадежной системой.

Криптография с открытым ключом используется в биткоине для подписи и защиты массива непотраченных выходов UTXO (Unspent Transaction Output), ведь проверить совпадение открытого ключа с секретным, зная только открытый ключ, практически невозможно. Чтобы разбить ассиметричный алгоритм цифровой подписи эллиптической кривой ECDSA (Elliptic Curve Digital Signature Algorithm), нужны миллиарды лет и самое мощное вычислительное оборудование. Поэтому можно с уверенностью сказать, что человеческие временные масштабы не позволят алгоритмической ассиметрии разрушить биткоин. Так как уровень усилия для решения проблемы высокий, а для проверки решения — низкий. Но не стоит забывать, что криптография с открытым ключом основана на односторонних функциях, которые не имеют научных доказательств.

Односторонние функции в биткоине

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

Удивительно, но существование односторонних функций до сих пор не доказано. Потому что если предполагаемая функция f —односторонняя, то найти ее будет почти невозможно по определению, но довольно легко проверить с помощью вычисления f. Из этого следует, что P ≠ NP. Однако никто не может доказать и понять, влечет ли за собой P ≠ NP существование односторонних функций. Их наличие в блокчейн-системах является важным условием для стойкости многих криптографических схем.

В учебнике «Криптография» программиста-исследователя Найджела Смарта сказано, что односторонняя функция сохраняет свою длину в том случае, если битовая длина значения функции равна битовой длине аргумента. Если эта длина значения постоянно равна любой длине аргумента, то ее называют хэш-функцией, которая используется для хранения паролей. То есть ни один посторонний пользователь не должен иметь возможности в вычислительном отношении по элементу Y из множества значений хэш-функции подобрать такой x, при котором h(x)=Y. Хэш-функция является претендентом на название односторонней функции, но на данный момент исследователи до конца не уверены в этом.

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

Получается, что односторонность необходима для исключения фабрикации сообщения. Биткоин требует, чтобы вычисляемая хэш-функция была меньше специального параметра, для этого необходим неоднократный пересчет с подбором произвольных значений дополнительного параметра. Это и есть майнинг, на решение одной функции которого уходит около 10 минут. Криптографические хэш-функции, такие как SHA-256, вычисляются быстро, без трудностей с точки зрения теории сложности вычислений, а для проверки корректности уже созданного блока необходимо однократное вычисление хэша.

Вычислительная асимметрия направлена на предотвращение атак double-spending и непрерывности блоков в сети биткоина — Proof-of-Work. Для решения необходимо успешно выполнить задачу и вывести одноразовое значение nonce. В данном случае уровень усилий при решении головоломки большой, а уровень усилий для проверки низкий, поэтому вновь создается асимметрия, которая затрудняет процесс и делает его дороже.

Если докажут, что P=NP…

Ученые пытаются найти ответ на равенство классов P и NP еще с 80-х годов, когда Стивен Кук и Леонид Левин независимо друг от друга подняли этот вопрос.

Исследователь из Технического университета Эйндховена ради забавы ведет дневник, куда записывает все неудачные попытки доказательств этого вопроса. В начале нулевых, как показал опрос 100 ученых, 61 математик был уверен, что эти классы неравны. 9 человек предположили, что равны, 22 исследователя затруднились ответить, 8 посчитали, что гипотеза невыводима из текущей системы аксиом, поэтому не может быть доказана или опровергнута.

На данный момент, так как нет доказательств, P не равно NP, ведь иначе бы хакеры уже давно использовали это уравнение в своих помыслах. Так как сейчас подобрать нужный шифр к системе биткоина можно с помощью долгого анализа всех возможных вариантов. При равенстве двух показателей из вычисления алгоритмов исчезнут асимметрии (доказательство по алгоритму консенсуса Proof-of-Work точно), о котором говорилось выше, протоколы станут проще в тысячи раз, а значит, безопасность биткоина и остальных подобных монет будет разрушена, интернет станет «проходным двором», считает профессор математики из Имперского колледжа в Лондоне Кевин Баззард и многие другие его коллеги, которые изучают данный вопрос.

«Если P=NP, то мы одним махом потеряем весь цифровой мир в привычном понимании. Без асимметрии потеряется биткоин. Его не станет, потому что шифр к разгадке больших секретных паролей будет найден. Уровни решения нивелируются, они станут одинаковыми, ведь алгоритмы будут вычислять даже самые трудные задачи», — говорит Баззард.

Таким образом, если докажут, что P=NP, то безопасность биткоина разрушится.