Квантовые атаки на Биткоин: [Часть №1]⁠⁠

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

В целом, результаты исследования говорят о том, что квантовые компьютеры представляют собой серьезную угрозу для криптовалют, и необходимо разрабатывать новые методы защиты, чтобы обеспечить их безопасность в будущем. Также на примере мы рассмотрим процесс компрометации извлечения секретного ключа Nonce значение K из уязвимой RawTX транзакции с помощью процесса машинного обучение BitcoinChatGPT.1

Биткоин, как децентрализованная и защищенная криптографией цифровая валюта, успешно существует с 2008 года, вдохновляя создание множества других криптовалют. Его безопасность обеспечивается механизмом подтверждения работы (proof-of-work) и криптографическими подписями на основе эллиптических кривых. Однако, развитие квантовых компьютеров представляет серьезную угрозу для Биткоина и всей современной криптографии, используемой в интернете и финансовых транзакциях. Исследование показывает, что алгоритм подтверждения работы, используемый в Биткоине, относительно устойчив к квантовым атакам в ближайшие 10 лет благодаря высокой скорости специализированного оборудования для майнинга. Но система цифровых подписей на эллиптических кривых уязвима для алгоритма Шора и может быть взломана уже к 2027 году, что позволит злоумышленникам получать секретные ключи из транзакции Биткоина и приватные ключи из открытых. В качестве решения предлагается использовать альтернативные алгоритмы, такие как Momentum для подтверждения работы, и квантово-устойчивые схемы подписи. В целом, результаты исследования говорят о том, что квантовые компьютеры представляют собой серьезную угрозу для Биткоина, и необходимо разрабатывать новые методы защиты, чтобы обеспечить его безопасность в будущем. Квантовые компьютеры могут взломать Биткоин в течение пяти лет. Это может привести к потере более 3 трлн долларов на криптовалютных и других рынках и вызовет глубокую рецессию.

Основы работы Биткоина и принципы защиты от атак: механизм блокчейна и доказательство работы

В этой части статьи мы постараемся объяснить, как устроен Биткоин, чтобы было проще понять возможные атаки с использованием квантовых компьютеров. Описание дается в общих чертах, так как основные принципы работы похожи и у других криптовалют. Все транзакции записываются в публичный реестр – блокчейн. Транзакции объединяются в блоки, которые считаются произошедшими одновременно и выстраиваются в цепочку. Каждый блок содержит ссылку на предыдущий в виде его хеша. Новые блоки добавляют майнеры, используя механизм «доказательства работы» (Proof-of-Work, PoW). Биткоин использует алгоритм Hashcash. Майнеры ищут подходящий заголовок блока, чтобы его хеш был меньше определенной величины. Заголовок содержит информацию о транзакциях, хеш предыдущего блока, временную метку и случайное число (nonce). Сложность задачи подбирается автоматически, чтобы блок находился примерно за 10 минут. В Биткоине используется двойное хеширование SHA256.

Python-скрипт: DoubleSHA256Hasher.py

import hashlib def double_sha256(data): """ Performs double SHA256 hashing on the input data. """ # First pass of SHA256 hash1 = hashlib.sha256(data).digest() # Second pass of SHA256 hash2 = hashlib.sha256(hash1).digest() return hash2 # Example usage data = b"Example data for double SHA256" # Data must be represented as bytes hashed_data = double_sha256(data) print(hashed_data.hex()) # Output in hexadecimal format

В этом скрипте:

1. Импортируется модуль hashlib.

2. Определяется функция double_sha256, которая принимает данные в байтовом формате2.

3. Внутри функции:

   • Вычисляется хеш SHA256 от входных данных с помощью hashlib.sha256(data).digest(). Метод .digest() возвращает хеш в виде байтовой строки.

   • Затем вычисляется хеш SHA256 от полученного хеша.

   • Функция возвращает второй хеш.

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

Майнеры добавляют в блок выбранные ими транзакции и получают за это вознаграждение в биткоинах. Когда майнер находит подходящий заголовок, он сообщает об этом сети, и блок добавляется в блокчейн. Проверить правильность решения PoW легко – достаточно один раз вычислить хеш. PoW нужен для того, чтобы один участник не мог подделать блокчейн, например, чтобы потратить одни и те же деньги дважды. Блокчейн может разветвляться, но майнеры должны работать над самой длинной цепочкой. Считается, что транзакция в Биткоине подтверждена, когда после нее добавлено еще 6 блоков. В статье рассматривается, какое преимущество квантовый компьютер может дать при решении PoW и сможет ли он подделывать блокчейн. Также анализируется структура транзакций. Когда Боб хочет отправить биткоины Алисе, Алиса создает пару ключей – приватный и публичный. Публичный ключ хешируется и получается адрес, который Алиса сообщает Бобу. Биткоин использует хеш публичного ключа для экономии места. Для отправки биткоинов Боб указывает транзакции, где он получил биткоины на свои адреса. Сумма полученных биткоинов должна быть не меньше, чем сумма, которую Боб хочет отправить Алисе. Боб подтверждает владение адресами, указывая публичные ключи и подписывая сообщение своим приватным ключом. Выбор использовать хеш публичного ключа вместо самого ключа влияет на безопасность Биткоина от квантовых атак.

Attacks on the Bitcoin Proof-of-Work

По большой части квантовый компьютер может быть эффективнее обычного при майнинге Биткоина, то есть при выполнении Proof-of-Work (PoW) на основе алгоритма hashcash. Квантовый компьютер, использующий алгоритм поиска Гровера, может выполнить PoW, перебрав значительно меньше вариантов хешей, чем классический компьютер. Однако, современные ASIC-майнеры, специализированные на вычислении хешей, работают настолько быстро, что это преимущество квантовых компьютеров нивелируется, учитывая, что скорость работы квантовых компьютеров пока еще относительно невелика. В будущем, если скорость работы квантовых компьютеров удастся увеличить до 100 ГГц, они смогут решать задачу PoW примерно в 100 раз быстрее, чем сейчас. Но это вряд ли произойдет в ближайшие 10 лет. К тому времени и обычные компьютеры станут быстрее, и квантовые технологии получат более широкое распространение, так что ни у кого не будет возможности единолично доминировать в майнинге. Для оценки безопасности блокчейна важно понимать, какой объем вычислительных ресурсов потребуется, чтобы квантовый компьютер мог успешно решать задачу PoW с вероятностью больше 50%.В итоге, хотя квантовые компьютеры и могут ускорить процесс майнинга теоретически, на практике, из-за ограничений текущих технологий, они пока не представляют серьезной угрозы для безопасности Биткоина. Однако, в будущем, с развитием квантовых технологий, эта угроза может стать более реальной, и необходимо разрабатывать соответствующие меры защиты насколько эффективным может быть квантовый компьютер при майнинге Биткоина, с учетом всех технических сложностей и ограничений. Алгоритм Гровера позволяет квантовому компьютеру искать решение (подходящий заголовок блока) гораздо быстрее, чем классическому, но на практике это преимущество сильно нивелируется.

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

Вычисление хеша SHA256 на квантовом компьютере требует преобразования логических операций в обратимые квантовые операции, что увеличивает сложность. Кроме того, квантовым компьютерам необходимо исправлять ошибки, что также требует дополнительных ресурсов и времени. В итоге, скорость майнинга на квантовом компьютере зависит не только от алгоритма Гровера, но и от множества других факторов, таких как тактовая частота, частота ошибок, сложность алгоритмов коррекции ошибок и количество используемых кубитов. В статье вводится понятие «эффективной скорости хеширования» для квантового компьютера (hQC), которая учитывает все эти факторы. Анализ показывает, что при текущем уровне развития технологий квантовые компьютеры значительно уступают специализированным ASIC-майнерам по скорости хеширования. Однако, ожидается, что в будущем квантовые технологии будут развиваться, и их производительность будет расти. В статье приводятся прогнозы на ближайшие 25 лет и оценивается, когда квантовые компьютеры смогут превзойти классические в майнинге Биткоина. Даже если квантовый компьютер не сможет единолично контролировать майнинг, он может быть использован для атак на майнинговые пулы с использованием смарт-контрактов. Небольшое преимущество в скорости хеширования позволит злоумышленникам получать прибыль за счет манипуляций и удержания блоков.

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

Результаты анализа производительности квантовых компьютеров при атаках на блокчейн представлены на рисунке 2. На графике сравнивается мощность хеширования сети Биткоин и одного квантового компьютера в течение следующих 25 лет. Оценки даны в оптимистичном и пессимистичном сценариях. Согласно оптимистичному прогнозу, до 2028 года не будет существовать квантовых компьютеров, достаточно мощных для реализации алгоритма Гровера. Для сравнения, на графике также показана скорость хеширования современных ASIC-устройств.

Описание схемы скорости хеширования ASIC-устройств

Современные ASIC-устройства для майнинга криптовалют на основе алгоритма SHA-256 (например, Bitcoin) работают следующим образом:

1. Предварительная обработка данных: Входные данные дополняются до длины кратной 512 битам.

2. Начальная настройка: Используются предопределенные начальные значения хеша.

3. Обработка в блоках: Данные обрабатываются в 512-битных блоках за 64 раунда.

4. Смешивание и преобразование: Побитовые операции, модульное сложение и сдвиги битов смешивают данные.

Примеры устройств

УстройствоСкорость ХешированияBitmain Antminer S21 ProДо 234 Th/s1Antminer T911,5 Th/s4Cheetah Miner F1Около 24 Th/s6

Эти устройства оптимизированы для максимальной производительности при минимальном энергопотреблении.

Для оценки достижимой производительности рассматриваются сверхпроводящие схемы, которые на сегодняшний день являются самыми быстрыми квантовыми технологиями и имеют хорошие перспективы масштабирования. При максимальной скорости работы элементов и определенных предположениях о частоте ошибок и сложности задачи, эффективная скорость хеширования квантового компьютера составляет 13.8 GH/s, что требует использования 4.4 миллиона физических кубитов. Это в тысячи раз медленнее, чем современные ASIC-устройства, которые достигают скорости 14 TH/s. Причина кроется в низкой скорости работы квантовых элементов и задержках, связанных с созданием отказоустойчивых T-элементов. Ожидается, что в будущем квантовые технологии будут быстро развиваться, и произойдет «квантовая версия закона Мура», которая повлияет на тактовую частоту, точность элементов и количество кубитов. Это позволит оценить мощность квантовых компьютеров в будущем.

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

Очевидно, что квантовым компьютерам потребуется время, чтобы превзойти классические машины в задаче майнинга. Даже когда это произойдет, ни один квантовый компьютер не будет обладать подавляющей мощностью. Однако, даже небольшое преимущество в мощности над другими майнерами может сделать выгодными определенные виды атак, например, на майнинговые пулы, которые используют смарт-контракты. Например, при определенных оптимистичных предположениях, группа из 20 квантовых машин, работающих параллельно, может иметь 0.1% от общей мощности хеширования. Этого достаточно для проведения атак на майнинговые пулы и снижения их прибыли на 10% с минимальными затратами на подкуп.

Attacks on signatures

Биткоин использует для создания подписей Elliptic Curve Digital Signature Algorithm (ECDSA), основанный на кривой secp256k1. Безопасность этой системы опирается на сложность задачи дискретного логарифма на эллиптической кривой (ECDLP). Несмотря на то, что классически эта проблема считается сложной, Питер Шор предложил эффективный квантовый алгоритм для её решения.

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

Последствия для биткоина таковы:

1. (Повторное использование адресов) Чтобы потратить биткоин с адреса, необходимо раскрыть открытый ключ, связанный с этим адресом. Как только открытый ключ раскрывается в присутствии квантового компьютера, адрес больше не является безопасным и поэтому никогда не должен использоваться повторно. Хотя всегда использовать новые адреса — это рекомендуемая практика в Bitcoin, на практике это не всегда соблюдается. Любой адрес, на котором есть биткоины и для которого был раскрыт открытый ключ, является совершенно небезопасным.

2. (Обработанные транзакции) Если транзакция совершена с адреса, с которого раньше не было расходов, и эта транзакция помещена в блокчейн с несколькими следующими за ней блоками, то эта транзакция достаточно защищена от квантовых атак. Закрытый ключ может быть получен из опубликованного открытого ключа, но, поскольку адрес уже был потрачен, это должно быть объединено с обходом хеширования сети для выполнения атаки двойной траты. Как мы видели в разделе III A, даже с квантовым компьютером атака двойной траты маловероятна, если за транзакцией следует много блоков.

3. (Необработанные транзакции) После того, как транзакция была передана в сеть, но до того, как она будет помещена в блокчейн, она подвергается риску квантовой атаки. Если секретный ключ может быть получен из широковещательного открытого ключа до того, как транзакция будет помещена в блокчейн, злоумышленник может использовать этот секретный ключ для трансляции новой транзакции с того же адреса на свой собственный адрес. Если злоумышленник затем гарантирует, что эта новая транзакция будет помещена в блокчейн первой, то он может фактически украсть все биткоины, стоящие за исходным адресом. Мы рассматриваем пункт (3) как наиболее серьезную атаку. Чтобы определить серьезность этой атаки, важно точно оценить, сколько времени потребуется квантовому компьютеру для вычисления ECDLP, и можно ли это сделать за время, близкое к интервалу между блоками.

Мы считаем атаку, описанную в пункте 3 (атака на необработанные транзакции), наиболее опасной. Чтобы оценить её серьёзность, важно понять, сколько времени потребуется квантовому компьютеру для решения задачи дискретного логарифма на эллиптической кривой (ECDLP) и возможно ли это сделать за время, сравнимое с интервалом между созданием блоков в блокчейне. Для поля из n-битного простого числа, согласно последним исследованиям, квантовый компьютер может решить задачу ECDLP, используя 9n + 2log2(n) + 10 логических кубитов и (448log2(n) + 4090)*n^3 вентилей Тоффоли. В биткоине используются 256-битные подписи (n = 256), поэтому число вентилей Тоффоли составляет 1.28 * 10^11, которые можно немного распараллелить до глубины 1.16 * 10^11. Каждый вентиль Тоффоли может быть реализован с использованием небольшой схемы T-вентилей, действующих на 7 кубитах параллельно (включая 4 вспомогательных кубита). Анализируя это, можно оценить ресурсы, необходимые для квантовой атаки на цифровые подписи. Как и в случае майнинга блоков, основное время тратится на дистилляцию «магических состояний» для логических T-вентилей. Время решения ECDLP на квантовом процессоре равно τ = 1.28 * 10^11 * cτ(pg)/s, где cτ зависит только от частоты ошибок вентилей (pg), а s — это тактовая частота. Количество необходимых физических кубитов равно nQ = 2334 * cnQ(pg), где первый множитель — это число логических кубитов, включая 4 вспомогательных логических кубита, а cnQ — это коэффициент пространственных затрат.

На рисунке 3 показана производительность квантового компьютера для атак на цифровые подписи. Используя код поверхности с частотой ошибок физических вентилей pg = 5 * 10^-4, коэффициенты накладных расходов составляют cτ = 291.7 и cnQ = 735.3. В этом случае, при тактовой частоте 66.6 МГц, решение задачи займет 6.49 дней, используя 1.7 * 10^6 физических кубитов. Если же тактовую частоту увеличить до 10 ГГц, а частоту ошибок уменьшить до 10^-5, то подпись можно взломать за 30 минут, используя 485550 кубитов. Последний сценарий делает атаку на необработанные транзакции (пункт 3) вполне возможной и серьезно угрожает безопасности текущей системы Bitcoin. На рисунке 4 представлена оценка времени, необходимого квантовому компьютеру для взлома схемы подписи в зависимости от времени, основанная на определённой модели.

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

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

Мы даем более и менее оптимистичные оценки (красные полосатые линии). Подробно модели описаны в Приложении C. Согласно этой оценке, схема подписи может быть взломана менее чем за 10 минут (600 секунд, черная пунктирная линия) уже в 2027 году

Будущие усовершенствования квантовых атак

Атаки на протокол Биткоин с использованием известных квантовых алгоритмов и схем коррекции ошибок. Хотя некоторые оценки скорости и масштабирования квантовых вычислений могут показаться оптимистичными, важно помнить, что есть несколько путей для улучшения производительности квантовых компьютеров в решении упомянутых проблем. Во-первых, в качестве кода коррекции ошибок здесь рассматривается код поверхности, который требует значительных классических вычислительных затрат для дистилляции состояний, извлечения синдрома ошибок и коррекции. Другие коды, обеспечивающие трансверсальные вентили Клиффорда и не-Клиффорда, могут устранить необходимость в медленной дистилляции состояний. Фактически, замедление из-за классической обработки для извлечения и коррекции синдрома может быть полностью устранено с использованием протокола без измерения, например, [PSBT10], который в недавнем анализе показывает пороговые значения ошибок [CJS16] всего примерно в 5 раз хуже, чем код поверхности с большим количеством измерений. Это может потенциально значительно улучшить общую скорость коррекции ошибок.

Во-вторых, уменьшение количества логических вентилей в квантовых схемах возможно по мере разработки более эффективных передовых методов квантовых вычислений. Например, используя конкретную задачу большого размера (включая реализации оракула), которая была проанализирована в предыдущей работе [SVM+17], было достигнуто прямое сравнение конкретных подсчетов вентилей, полученных с помощью программного пакета Quipper, между старым [HHL09] и новым [CKS15] квантовыми алгоритмами решения линейных систем, показывающее улучшение на несколько порядков.

Учитывая, что квантовые алгоритмы Шора и Гровера были хорошо изучены и тщательно оптимизированы, не следует ожидать такого значительного улучшения, тем не менее, вероятно, возможно некоторое улучшение. В-третьих, различные квантовые алгоритмы могут обеспечить относительное ускорение. Недавняя работа Калиски [Kal17] представляет квантовый алгоритм для задачи дискретного логарифма: найти m, если дано b = a^m, где b — известное целевое значение, а a — известное основание, используя запросы к так называемой подпрограмме «магического ящика», которая вычисляет наиболее значимый бит m. Повторяя запросы, используя продуманно выбранные степени целевого значения, можно вычислить все биты m и решить задачу. Поскольку разные биты решаются один за другим, задача может быть распределена между несколькими квантовыми процессорами. Каждому процессору требуется количество логических кубитов, сопоставимое с решением всей задачи, но общее время будет сокращено за счет распараллеливания. Кроме того, накладные расходы на квантовую коррекцию ошибок, вероятно, уменьшатся, поскольку фазы в квантовом преобразовании Фурье части схемы не должны быть такими точными, как в исходном алгоритме Шора.

Хотя квантовые атаки на Биткоин кажутся сложными, не стоит расслабляться. Существуют способы сделать квантовые компьютеры быстрее и эффективнее в решении этих задач.

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

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

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

Поэтому, даже если сейчас квантовая атака на Биткоин требует огромных ресурсов, с развитием технологий эта угроза будет становиться все более реальной.

КОНТРМЕРЫ: Alternative proofs-of-work

Квантовый компьютер может использовать поиск Гровера для выполнения proof-of-work в Биткоине, используя квадратично меньше хэшей, чем требуется классически. В этом разделе мы исследуем альтернативные proof-of-work, которые могут предложить меньшее квантовое преимущество. Основные свойства, которые мы хотим получить от proof-of-work:

1. (Сложность) Сложность задачи можно регулировать в соответствии с вычислительной мощностью, доступной в сети.

2. (Асимметрия) Гораздо проще проверить, что proof-of-work успешно завершен, чем выполнить proof-of-work.

3. (Отсутствие квантового преимущества) Proof-of-work не может быть выполнен значительно быстрее с помощью квантового компьютера, чем с помощью классического компьютера.

Python-скрипт: QuantumInspiredPoW.py

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

2. поиск Гровера proof_of_work(difficulty): Это основная функция, которая пытается найти nonce, удовлетворяющий требованиям PoW.

   • N = 2**32: Представляет собой пространство поиска nonce. В реальной сети Bitcoin пространство поиска гораздо больше.

   • iterations = int(N**0.5): Ключевая идея, вдохновленная алгоритмом Гровера. Алгоритм Гровера теоретически позволяет найти решение в пространстве поиска размера N за O(sqrt(N)) операций, в отличие от O(N) для полного перебора. Мы пытаемся отразить это, выполняя корень квадратный из N итераций.

   • В цикле мы случайным образом выбираем nonce и проверяем, соответствует ли его хеш требованиям сложности.

3. Обратите внимание, что этот код не является реальной реализацией алгоритма Гровера и не даст никакого ускорения на классическом компьютере. Он просто демонстрирует концепцию использования sqrt(N) итераций.

Proof-of-work Биткоина выполняет пункты (1) и (2), но мы хотели бы найти альтернативный proof-of-work, который лучше справляется с (3). Аналогичные соображения были исследованы авторами, пытающимися найти proof-of-work, которые вместо (3) ищут proof-of-work, которые не могут быть ускорены ASIC. Подход к этому заключается в рассмотрении proof-of-work, интенсивно использующих память. Было предложено несколько интересных кандидатов, таких как Momentum [Lar14], основанный на поиске коллизий в хеш-функции, Cuckoo Cycle [Tro15], основанный на поиске подграфов постоянного размера в случайном графе, и Equihash [BK17], основанный на обобщенной задаче о днях рождения. Это также хорошие кандидаты для более квантово-устойчивого proof-of-work.Все эти схемы основаны на proof-of-work в стиле hashcash и используют следующий шаблон. Пусть h1 : {0, 1} ∗ → {0, 1} n — криптографически безопасная хеш-функция, а H = h1(header) — хеш заголовка блока. Цель состоит в том, чтобы найти nonce x такой, что h1(H k x) ≤ t и P(H, x) для некоторого предиката P.

Тот факт, что заголовок и nonce должны удовлетворять предикату P, означает, что лучший алгоритм больше не будет просто последовательно перебирать nonce x. Наличие proof-of-work в такой форме также гарантирует, что параметр t все еще может быть выбран для изменения сложности. Далее мы проанализируем этот шаблон для proof-of-work Momentum, так как это можно связать с известными квантовыми нижними границами. Для proof-of-work Momentum пусть h2 : {0, 1} ∗ → {0, 1} — другая хеш-функция с n ≤. В исходном предложении Momentum h1 может быть принята как SHA-256, а h2 как хеш-функция, интенсивно использующая память, но это менее важно для нашего обсуждения. Proof-of-work состоит в том, чтобы найти H, a, b такие, что h1(H k a k b) ≤ t и h2(H k a) = h2(H k b) и a, b ≤ 2 `. (1)Сначала давайте исследуем время выполнения для решения этого proof-of-work, предполагая, что хеш-функции h1, h2 могут быть оценены за единицу времени. Взяв подмножество S ⊂ {0, 1} и оценивая h2(H k a) для всех a ∈ S, мы ожидаем найти около |S| 2/2 многих коллизий. Заметим, что, используя соответствующую структуру данных, эти коллизии можно найти за время около |S|. Один из алгоритмов тогда выглядит следующим образом. Для каждого H мы оцениваем h2 на подмножестве S и находим около |S| 2/2  многих пар a, b таких, что h2(H k a) = h2(H k b).

Для каждой коллизии мы затем проверяем h1(H k a k b) ≤ t. В ожидании нам придется выполнить этот второй тест 2n/t много раз. Таким образом, количество H, которые нам придется попробовать, составляет около m = max{1, 2 n+ t|S| 2 }, так как мы должны попробовать хотя бы один H. Поскольку для каждого H мы тратим время |S|, общее время выполнения составляет m|S|. Мы видим, что оно наименьшее, когда |S| = q 2 n+ t , то есть когда m = 1, и мы просто пробуем один H. Это оптимальное время выполнения тогда составляет T = q 2 n+ t , и для его достижения мы должны использовать память, равную времени выполнения, что может быть непомерно дорого. Для некоторой меньшей памяти |S| < q 2 n+ t время выполнения будет 2 n++1 t|S| .Теперь давайте посмотрим на время выполнения на квантовом компьютере. На квантовом компьютере мы можем сделать следующее. Назовем H хорошим, если существуют a, b ∈ S такие, что h1(H k a k b) ≤ t и h2(H k a) = h2(H k b). Проверка того, является ли H хорошим, требует поиска коллизии и, следовательно, требует, по крайней мере, |S| 2/3 времени согласно квантовой нижней границе запросов Ааронсона и Ши [AS04].

.... Продолжение статьи во второй части

Данный материал создан для портала CRYPTO DEEP TECH для обеспечения финансовой безопасности данных и криптографии на эллиптических кривых secp256k1 против слабых подписей ECDSA в криптовалюте BITCOIN. Создатели программного обеспечения не несут ответственность за использование материалов.

Исходный код

Google Colab

BitcoinChatGPT

Blockchain Folbit Leaks

Dockeyhunt Deep Learning

Telegram: https://t.me/cryptodeeptech

Видеоматериал: https://youtu.be/p62orC7WDUE

Video tutorial: https://dzen.ru/video/watch/67c3e91abbfa683a745a0aea

Источник: https://cryptodeeptool.ru/quantum-attacks-on-bitcoin