Введение 
В последние несколько лет очень популярными стали системы на основе так называемого блокчейна, привлекающие пользователей рядом своих преимуществ: децентрализацией, неизменностью данных, прозрачностью и отсутствием доверенного центра, то есть посредника.
Предоставление таких преимуществ возможно благодаря двум «столпам» блокчейна: асимметричное шифрование и использовать хеш-функции .
Однако из-за развития квантовых вычислений безопасность этих примитивов оказалась под угрозой, поэтому возникает необходимость найти новые подходы к построению блокчейна, который будет устойчив к атакам с использованием квантового компьютера — так называемому постквантовый блокчейн .
В этой статье рассказывается, какие части блокчейна наиболее уязвимы для квантовых компьютерных атак, насколько реальны эти угрозы, какие существуют подходы к построению устойчивого к ним постквантового блокчейна и насколько эти подходы применимы.
Блокчейн-устройство 
Для начала давайте вспомним, что такое блокчейн, чтобы понять, почему он уязвим для атак с использованием квантового компьютера.
По сути, блокчейн — это база данных, состоящая из цепочки блоков, в которой каждый блок хранит хэш предыдущего блока, в результате чего необходимо перестраивать все последующие блоки, чтобы изменить или удалить блок из середины цепочки.
Подсчет каждого блока — вычислительно сложная задача, поэтому пересчет блоков практически невозможен и поэтому блокчейн обладает свойством неизменности данных.
Такой вычислительно сложной задачей может быть, например, поиск хеш-коллизий: нахождение определенного числа доказательство работы (англ.
доказательство работы), при добавлении хеш блока начинается с нескольких нулей.
Эту задачу можно решить только с помощью классического компьютера методом перебора, поэтому среднее время нахождения такого числа растет экспоненциально с увеличением необходимого количества нулей.
Подробнее об этом вы можете прочитать в оригинальная статья С.
Накамото, выдвинувший эту идею.
Блоки состоят из генерируемых пользователями транзакций, которые подписываются ими с использованием асимметричной криптографии.
У каждого пользователя есть два ключа: приватный, известный только этому пользователю, которым он подписывает транзакции, и публичный, известный всем пользователям, с помощью которого любой может проверить подпись.
Например, Биткойн использует алгоритм ECDSA (алгоритм цифровой подписи эллиптической кривой) для подписи транзакций, аналогичный алгоритму DSA (алгоритм цифровой подписи), но определенный в группе точек эллиптической кривой.
Криптографическая стойкость этого алгоритма основана на сложности задачи дискретного логарифмирования, которую можно решить на классическом компьютере за экспоненциальное время относительно размера ключа.
Другой вычислительно сложной проблемой является проблема факторизации больших чисел, на которой основан, например, алгоритм RSA (англ.
Rivest Shamir Adleman), который также обеспечивает криптографическую стойкость цифровой подписи, поскольку основная проблема решается в время, которое экспоненциально зависит от размера ключа.
Таким образом, пока существует эта криптографическая устойчивость, пользователям гарантируется, что никто другой не сможет совершать транзакции от их имени.
Уязвимость квантового компьютера 
Как указано выше, блокчейн опирается на две сложные вычислительные задачи: поиск коллизий хэшей и получение дискретных логарифмов или факторизацию больших чисел.
Обе задачи можно решить на классическом компьютере за экспоненциальное время, так что если выбрана достаточно сложная хеш-функция или достаточно длинный ключ, их можно считать неразрешимыми.
Однако настоящим шоком является то, что существуют алгоритмы, которые позволяют квантовым компьютерам решать эти проблемы на порядки быстрее.
В то время как классический компьютер оперирует битами, которые представлены как ноль или единица, квантовый компьютер оперирует кубитами, которые могут находиться в суперпозиции разных состояний.
Проще говоря, каждое такое состояние может обрабатываться одновременно, в результате чего можно получить значительное ускорение по сравнению с его классическим аналогом.
Далее мы рассмотрим два основных квантовых алгоритма, которые могут поставить под угрозу безопасность обычного блокчейна.
Алгоритм Гровера
Алгоритм Гровера позволяет получить квадратичное ускорение при решении задачи поиска, поэтому его можно использовать для ускорения генерации хешей.
Благодаря этому злоумышленник сможет генерировать ложные блоки на порядки быстрее, чем генерация реальных блоков, тем самым создавая более длинную цепочку блоков, которая будет принята всеми пользователями.
Этот алгоритм также можно использовать для замены существующих блоков в блокчейне, сохраняя при этом их целостность.
Суть алгоритма Гровера состоит в следующем.
Допустим, у нас есть определенная функция 
, корень которого мы и собираемся найти.
Пусть эта функция реализована на классическом компьютере, тогда теоретически представляется возможным реализовать обратимую функцию 
, что равно 
, Если 
является корнем функции 
, И 
- в противном случае.
Эта функция называется оракул , а его обратимость гарантирует, что его можно реализовать на квантовом компьютере, например, с помощью Клапаны Тоффоли .
В этом случае на вход этой функции можно подать более одного значения.
, как при классическом перечислении, а суперпозиция всех возможных значений
, что означает, что вывод представляет собой суперпозицию всех возможных выходных значений оракула.
Далее, используя элементарные квантовые вентили, можно повысить амплитуду вероятности состояния, соответствующего корню оракула.
После определенного количества таких итераций результат измерения даст корень исходной функции
с вероятностью почти равной
.
Ситуация несколько усложняется, когда функция
корней несколько, что соответствует задаче поиска хэш-коллизий, однако даже в этом случае алгоритм Гровера показывает значительное ускорение по сравнению с простым поиском.
Атака на доказательство работы
Несмотря на то, что алгоритм Гровера способен обеспечить квадратичное ускорение при подсчете блоков, атака с его помощью не является критичной для блокчейна, как сказано в Недавний доклад группы канадских и австралийских ученых.
Дело в том, что вычислительная мощность интегральных схем специального назначения (ASIC), находящихся сейчас в руках майнеров, может свести на нет практически любую попытку ускорить майнинг с помощью квантового компьютера.
Не исключено, однако, что дальнейшее развитие квантовых технологий может способствовать тому, что квантовые компьютеры получат серьезное преимущество перед существующими вычислительными мощностями, но это, по мнению авторов работы, произойдет только после широкого распространения квантовых технологий.
компьютеры.
Когда это произойдет, майнеры также смогут их использовать, тем самым исключив возможность доминирования с помощью квантового компьютера.
Кроме того, существуют и другие подходы к генерации блоков, не основанные на вычислительно сложных задачах, а это означает, что основанные на них блокчейны можно считать устойчивыми к атакам доказательства работы.
Самый популярный такой подход, который в настоящее время уже используется, например, в БлэкКоин , является доказательство доли (англ.
Proof of Stake), заключающийся в том, что блоки с большей вероятностью будут генерироваться теми пользователями, которые владеют большей частью средств в блокчейне.
Proof-of-Stake не требует поиска хеш-коллизий, поэтому с этой точки зрения он устойчив к атакам с использованием квантового компьютера.
Однако доказательство доли по-прежнему уязвимо для атак со стороны квантового компьютера, если он способен подделывать цифровые подписи, например, с использованием алгоритма Шора, который обсуждается далее.
В этом случае злоумышленник сможет очень быстро сконцентрировать все средства блокчейна на подконтрольных аккаунтах и получить над ним полный контроль.
Стоит отметить, что цифровые подписи широко распространены и в других областях, которые теперь могут стать уязвимыми для квантового компьютера, поэтому ведутся активные исследования по разработке новых подходов к созданию цифровых подписей, ряд из которых будет рассмотрен далее в этой статье.
Алгоритм Шора
Теперь перейдем к краткому обзору Алгоритм Шора , который способен факторизовать большие числа и выполнять дискретные логарифмы, и делать все это за полиномиальное время, сводя обе эти проблемы к нахождению периода функции.
Благодаря этому сложные вычислительные задачи, лежащие в основе криптографической стойкости алгоритмов создания цифровой подписи, таких как RSA, ECDSA, ECDH, DSA, могут быть решены за разумное время с использованием квантового компьютера достаточной мощности.
Наличие такого квантового компьютера позволит злоумышленнику создавать ложные транзакции, получая тем самым доступ ко всем средствам, хранящимся в блокчейне, поэтому атаки с использованием алгоритма Шора на данный момент считаются наиболее опасными для безопасного функционирования блокчейна.
Постквантовый блокчейн
Требования к постквантовому блокчейну
Прежде чем перейти к обзору различных подходов к созданию цифровой подписи, устойчивой к квантовым атакам, давайте рассмотрим, какие требования предъявляются к постквантовому блокчейну в целом, чтобы в будущем иметь представление о том, какие методы можно использовать, а какие нельзя.
С одной стороны, кажется, что увеличить размер ключей и хеша можно только для того, чтобы отсрочить момент, когда квантовые компьютеры смогут наконец взломать блокчейн, но у такого подхода есть ряд недостатков.
Во-первых, это потребует от устройств большого объема памяти и вычислительных ресурсов, что недопустимо.
в случаях , когда устройствам Интернета вещей необходимо взаимодействовать с блокчейном, так как они часто не обладают большой памятью и мощностью, а, наоборот, должны работать несколько лет на одной батарее.
Во-вторых, увеличение размера хэшей и подписей влечет за собой увеличение размера блокчейна, который необходимо хранить всем пользователям, что может занимать довольно много памяти.
Эта проблема уже возникла в Биткойн , размер блокчейна увеличился на целых 60 ГБ за один год и на момент написания статьи составляет 310 ГБ , а его рост только продолжает увеличиваться и, можно предположить, примерно к 2030 году он превысит 1ТБ.
Конечно, есть вариант использовать так называемый «легкие» кошельки , что позволяет не хранить весь блокчейн, но это снижает надежность системы.
Таким образом, основные требования к постквантовому блокчейну касаются размеров подписей, ключей и хэшей: они не должны быть слишком большими.
Кроме того, постквантовый блокчейн должен иметь достаточно высокую скорость выполнения операций, чтобы обеспечить стабильную работу системы с огромным количеством транзакций в секунду.
Алгоритмы постквантовой цифровой подписи
В настоящее время ведется активная работа по разработке алгоритмов шифрования, в том числе алгоритмов создания цифровой подписи, которые будут устойчивы к атакам с использованием квантового компьютера.Интерес исследователей подогревается тем, что в 2016 году NIST (англ.
National Institute of Standards and Technology) запустил конкурс такие алгоритмы, результаты работы которых будут объявлены к 2022 году.
Ниже мы представляем наиболее известные из предложенных алгоритмов, устойчивых к квантовым атакам.
Начнем рассмотрение с механизмов цифровой подписи.
на основе кода (английский: на основе кода), примером которого является система МакЭлис , предложенный примерно в то же время, что и широко используемый алгоритм RSA, но в то время широко не использовавшийся.
В настоящее время эта система, а также ряд ее усовершенствований, таких как система Нидеррейтер , становятся все более популярными, поскольку устойчивы к атакам алгоритма Шора.
В их основе лежит задача декодирования линейных кодов, которая является NP-полной задачей, но пока неразрешимой на квантовом компьютере.
Несмотря на то, что подписи, созданные с помощью этих методов, имеют относительно небольшой размер и могут быть проверены достаточно быстро, они требуют хранения огромных матриц, выполняющих роль ключей, что, в свою очередь, также увеличивает время генерации подписи, что затрудняет ее использование в блокчейне.
В связи с этим исследуются различные методы сжатия матриц или использование других кодов, например, кодов LDPC (англ.
Low Density Parity Check), особенностью которых является малая плотность проверочной матрицы.
Другим механизмом создания цифровой подписи является так называемый механизм на основе решетки (английский: на основе решетки), что было отдельно выделено в Недавний доклад NIST как наиболее перспективный.
Так называемая сетка можно себе представить себя как набор точек n-мерного пространства с периодической структурой.
В этом случае математической задачей, на которой основана криптографическая стойкость, является, например, задача поиска кратчайшего вектора в этой решетке (проблема кратчайшего вектора) или аналогичная задача поиска ближайшего вектора (проблема ближайшего вектора), и обе Эти задачи имеют огромную вычислительную сложность.
Однако недостатком таких систем является необходимость хранить большие ключи, которые ведет к значительным издержкам зашифрованного текста и делает практически невозможным использование таких систем в блокчейне.
Однако существуют решетчатые системы, основанные на задаче короткое целочисленное решение (англ.
Short Integer Solution), благодаря чему можно уменьшить размер ключа, тем самым позволяя использовать такие системы в блокчейне.
Последний механизм создания цифровой подписи, обсуждаемый в этой статье, — это на основе хеша (англ.
hashbased), безопасность которого основана не на сложности какой-либо математической задачи, а на лежащей в ее основе криптографической хэш-функции.
Подобный подход был предложенный еще в 70-х годах прошлого века в качестве альтернативы алгоритмам RSA и DSA он, однако, не пользовался особым интересом, поскольку накладывает ограничение на количество повторных использований подписей.
Однако сейчас этот подход набирает популярность, поскольку он устойчив к квантовым атакам.
Недостатком данного подхода является то, что генерация ключа занимает достаточно много времени, что затрудняет непригодный для использования в блокчейне.
Заключение В этой статье были рассмотрены атаки с использованием квантового компьютера, для которых блокчейн оказывается уязвим.
Выяснилось, что хотя алгоритм Гровера демонстрирует квадратичное ускорение по сравнению с классическими подходами, атака с его помощью практически не представляет угрозы для существующих систем, основанных на доказательстве работы, не говоря уже о других методах генерации блоков, таких как доказательство выполнения работы.
работа.
из стека.
При этом основной угрозой, которая может свести на нет безопасное функционирование не только блокчейна, но и практически всех цифровых финансовых транзакций, является атака с использованием алгоритма Шора, методы борьбы с которой также были рассмотрены в этой статье.
Кроме того, были рассмотрены требования к квантовому блокчейну, определяющие, какие методы борьбы с той или иной атакой приемлемы, а какие нет. Теги: #информационная безопасность #квантовые вычисления #блокчейн #Распределенные системы #квантовая криптография
-
Биткаса Стартовала!
19 Oct, 24 -
О Команде Ракетчиков, Которые Могут
19 Oct, 24 -
Как Веб-Студии Избежать Споров С Заказчиком
19 Oct, 24 -
Выйди С Моей Головы. Гтд В Разработке
19 Oct, 24 -
Работа Со Сжатием Текстур В Unity3D + Ngui
19 Oct, 24 -
Оригинальная Контекстная Реклама
19 Oct, 24
