Как квантовый компьютер может быть использован для кражи ваших биткоинов за "9 минут"

Часть 1 этой серии объясняла, что такое квантовые компьютеры. Это не просто более быстрые версии обычных компьютеров, а принципиально другой тип машины, которая использует странные правила физики, применимые только на атомном и субатомном уровнях.

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

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

Одностороннее преобразование

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

Представьте себе это как одностороннюю карту. Начните с известной точки на кривой, с которой все согласны, называемой генераторной точкой G (как показано на диаграмме ниже). Сделайте определенное количество шагов по траектории, определенной математикой кривой. Количество шагов - это ваш приватный ключ. Точка, в которой вы оказываетесь на кривой, - это ваш публичный ключ (точка K на диаграмме). Любой может проверить, что вы оказались именно в этой точке. Никто не может понять, сколько шагов вам потребовалось, чтобы туда добраться.

Технически это записывается как K = k × G, где k - ваш приватный ключ, а K - ваш публичный ключ. "Умножение" - это не обычное умножение, а геометрическая операция, при которой точка многократно добавляется к самой себе вдоль кривой. Результат попадает в, казалось бы, случайное место, которое может быть получено только вашим конкретным числом k.

Ключевое свойство заключается в том, что движение вперед - это просто, а движение назад практически невозможно для классических компьютеров. Если вы знаете k и G, вычисление K занимает миллисекунды. Если вы знаете K и G и хотите узнать k, вы решаете задачу, которую математики называют задачей дискретного логарифмирования на эллиптических кривых.

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

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

Алгоритм Шора открывает возможность движения в обе стороны

В 1994 году математик Питер Шор разработал квантовый алгоритм, который позволяет обойти этот "замок".

Алгоритм Шора эффективно решает задачу дискретного логарифмирования. Та же математика, которая заняла бы у классического компьютера больше времени, чем существует Вселенная, алгоритм Шора выполняет за то, что математики называют полиномиальным временем, то есть сложность медленно возрастает с увеличением чисел, а не взрывообразно.

Интуиция того, как это работает, связана с тремя квантовыми свойствами, упомянутыми в первой части этой серии.

Алгоритму необходимо найти ваш приватный ключ k, зная ваш публичный ключ K и генераторную точку G. Он преобразует это в задачу нахождения периода функции. Представьте себе функцию, которая принимает число в качестве входных данных и возвращает точку на эллиптической кривой.

Когда вы подаете ей последовательные числа, 1, 2, 3, 4, выходные данные в конечном итоге повторяются в цикле. Длина этого цикла называется периодом, и как только вы узнаете, как часто функция повторяется, математика задачи дискретного логарифмирования раскрывается за один шаг. Приватный ключ вычисляется почти мгновенно.

Нахождение этого периода функции — это именно то, для чего созданы квантовые компьютеры. Алгоритм помещает свой входной регистр в состояние суперпозиции (или, в квантовой механике, частица существует в нескольких местах одновременно), представляя все возможные значения одновременно. Он применяет функцию ко всем этим значениям одновременно.

Затем он применяет квантовую операцию, называемую преобразованием Фурье, которая приводит к тому, что количество неверных ответов взаимно уничтожаются, а правильные ответы усиливаются.

Когда вы измеряете результат, появляется период. Из этого периода обычная математика вычисляет k. Это ваш приватный ключ, и, следовательно, ваши монеты.

[Изображение: https://cnews24.ru/uploads/7ff/7ffcb9988cb5ee8cf19ab4a8c4d9a4d734aa7ff8.jpg]

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

Почему биткоин все еще работает сегодня

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

Создание такой машины пока не представляется возможным, но всегда был вопрос о том, насколько "большим" должен быть этот объем.

Предыдущие оценки говорили о миллионах физических кубитов. Статья Google, опубликованная в начале апреля ее подразделением Quantum AI с участием исследователя Ethereum Foundation Джастина Дрейка и криптографа Стэнфордского университета Дэна Бонеха, сократила это число до менее чем 500 000.

Это примерно в 20 раз меньше, чем предыдущие оценки.

Команда разработала две квантовые схемы, реализующие алгоритм Шора для конкретной эллиптической кривой, используемой в биткоине. Одна схема использует примерно 1200 логических кубитов и 90 миллионов логических вентилей Toffoli. Другая использует примерно 1450 логических кубитов и 70 миллионов логических вентилей Toffoli.

Ворота Тоффоли — это тип ворот, которые воздействуют на три кубита: два управляющих кубита, которые влияют на состояние третьего, целевого кубита. Представьте это как три выключателя (кубита) и специальную лампочку (целевой кубит), которая загорается только в том случае, если два определенных выключателя включены одновременно.

Поскольку кубиты постоянно теряют свое квантовое состояние, как объяснялось в части 1, вам нужны сотни избыточных кубитов, проверяющих работу друг друга, чтобы поддерживать один надежный логический кубит. Большая часть квантового компьютера существует просто для того, чтобы обнаруживать ошибки самого компьютера, прежде чем они испортят вычисления. Приблизительное соотношение 400 к 1 между физическими и логическими кубитами отражает то, насколько большая часть машины является инфраструктурой для самоконтроля.

Девятиминутный интервал

В статье Google не только сократили количество кубитов. Они представили практический сценарий атаки, который меняет представление об угрозе.

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

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

Google оценивает, что вторая половина занимает около девяти минут.

Среднее время подтверждения блока в Bitcoin составляет 10 минут. Это означает, что если пользователь отправляет транзакцию, и его открытый ключ виден в mempool, у квантового атакующего есть примерно девять минут, чтобы получить закрытый ключ и отправить конкурирующую транзакцию, которая перенаправит средства.

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

Это атака на mempool. Она вызывает тревогу, но требует квантового компьютера, которого еще не существует.

Однако более серьезная проблема заключается в 6,9 миллионах биткоинов (примерно в одной трети от общего объема), которые хранятся в кошельках, где открытый ключ уже был навсегда опубликован в блокчейне. Эти монеты уязвимы для "статической" атаки, которая не требует гонки со временем. Атакующий может тратить столько времени, сколько ему нужно.

[Изображение: https://cnews24.ru/uploads/70a/70aa15e32ccf14ea48b1a0ec912944014f09cb74.jpg]

Квантовый компьютер, выполняющий алгоритм Шора, может преобразовать биткоин-открытый ключ в закрытый ключ, который контролирует монеты. Для монет, переданных после Taproot (обновления конфиденциальности в Bitcoin, которое было запущено в ноябре 2021 года), открытый ключ уже виден. Для монет в старых адресах открытый ключ скрыт до тех пор, пока вы его не используете, после чего у вас есть примерно девять минут, прежде чем атакующий догонит.

Что это означает на практике, какие 6,9 миллиона биткоинов уже находятся в открытом доступе, что изменил Taproot и как быстро развивается аппаратное обеспечение, будет рассмотрено в следующей и заключительной части этой серии.