Автор: Джастин Дрейк, исследователь Фонда Ethereum
Перевод: Chopper, Foresight News
31 марта команда Google Quantum AI опубликовала знаковую работу по алгоритму Шора для эллиптических кривых. С технической точки зрения, эта статья представляет собой серьёзный прорыв: эффективность алгоритма повысилась в целых 10 раз по сравнению с предыдущими лучшими решениями. Команда выбрала для демонстрации оптимизации эллиптическую кривую secp256k1, лежащую в основе подписей Bitcoin и Ethereum, что является не только технической демонстрацией, но и тревожным звонком для индустрии блокчейна.
Однако самое интригующее в этой статье заключается не в технике, а в правилах отрасли. Исследовательская группа не следовала обычной академической практике открытой публикации, а держала ключевые детали оптимизации в секрете, используя только доказательства с нулевым разглашением (ZK) для подтверждения действенности оптимизации, не раскрывая никаких технических деталей. В связанном блоге Google упоминается, что в ходе проекта велось взаимодействие с правительственными учреждениями США. Реализация контроля над академическим содержанием с помощью доказательств с нулевым разглашением — беспрецедентный случай в мировой академической истории.
Как один из соавторов этой статьи, я был свидетелем причин и следствий этого ограниченного релиза. Откровенно говоря, во многих деталях этого дела мне трудно согласиться. Я всегда считал, что общественность имеет право знать эту информацию, но в силу объективных обстоятельств не могу раскрывать внутренние детали. Однако необходимо подчеркнуть, что команда Google на протяжении всего процесса действовала профессионально и достойно похвалы.
Намеренный контроль над информацией часто даёт обратный эффект, и сейчас разворачивается "эффект Стрейзанд" (чем больше стараются скрыть, тем больше внимания привлекают): ключевой алгоритм оптимизации, который Google так тщательно охранял, уже был воспроизведён французскими исследователями. Ещё более неожиданно то, что был официально запущен общедоступный конкурс с открытым исходным кодом по взлому алгоритма Шора, и веб-сайт ecdsa.fail побил мировой рекорд по оптимизации алгоритма Шора всего через несколько часов после запуска.
Алгоритм воспроизведён независимо, открытые общественные конкурсы множатся
Всего через два месяца после публикации статьи Google французский эксперт в области квантовых технологий Андре Шроттенлохер первым расшифровал эту ключевую логику оптимизации. Статья под названием "Оптимизированные схемы сложения точек для логарифмов эллиптических кривых" (Optimized Point Addition Circuits for Elliptic Curve Discrete Logarithms) была официально опубликована сегодня на сайте препринтов arXiv. Поздравляю Андре, он опередил ведущих учёных, работающих над этой темой. Также сегодня Крейг Гидни, авторитет в области оптимизации алгоритма Шора, сообщил, что из-за требований контроля он держал эту идею оптимизации при себе целый год, не имея возможности опубликовать её.
Хотя исследование Андре воспроизвело основную структуру, оно не охватило некоторые тонкие возможности оптимизации, присутствующие в оригинальной версии Google и последующих итерациях. В алгоритме Шора по-прежнему скрыт огромный потенциал для оптимизации, что и является целью конкурса ecdsa.fail. Ранее использовавшаяся для проверки ZK-доказательств программа верификации была повторно использована для автоматического отбора эффективных схем оптимизации. В настоящее время разработчики по всему миру продолжают вносить улучшения в детали. По меркам, использующим произведение количества логических кубитов и количества вентилей Тоффоли, эффективность всей схемы повысилась на 8,4% по сравнению с оригинальной версией Google.
Количество участников этого исследовательского бума превзошло все ожидания в отрасли, и это не только ведущие учёные. За последние несколько недель множество любителей, вдохновлённых идеей самостоятельных исследований, предложенной Карпати (ведущим мировым учёным в области ИИ, сооснователем OpenAI), использовали искусственный интеллект для итеративной оптимизации алгоритма Шора. Иронично, что программа верификации, изначально созданная для ZK-доказательств, как раз подошла в качестве системы оценки вознаграждения для итераций ИИ. Эта новая модель исследований имеет чрезвычайно низкий порог входа, и даже непрофессионалы, включая одного подростка, представили высококачественные решения по оптимизации.
В игру вступает технология нейтральных атомов, в отрасли прогнозируют наступление Квантового дня (Q-Day) до 2032 года
История на этом не заканчивается. В тот же день, что и статья Google, стартап в области приватности Oratomic опубликовал свою собственную исследовательскую статью по алгоритму Шора, которая сразу же возглавила список самых популярных на академическом сайте scirate.com.
Вывод Oratomic ошеломляет: на основе логической оптимизации от Google, в сочетании с собственной оптимизацией физической архитектуры на нейтральных атомах, для запуска алгоритма Шора и взлома криптографии secp256k1 потребуется всего десять тысяч физических кубитов — это значение настолько низкое, что оно переворачивает представления отрасли.
Когда я впервые увидел статью Oratomic, я ничего не знал о технологии нейтральных атомов. Из любопытства я потратил сотни часов на углублённое изучение, просмотрел множество образовательных видео в сети, взял интервью у нескольких отраслевых экспертов. Итоговый вывод: технология квантовых вычислений на нейтральных атомах действительно жизнеспособна и перспективна для реализации. Недавнее создание Google лаборатории квантовых вычислений на нейтральных атомах, отойдя от предыдущей стратегии, сфокусированной только на сверхпроводящих кубитах, является лучшим доказательством. Если вы следите за Квантовым днём (Q-Day) — моментом, когда квантовый компьютер взломает коммерческую криптографию, — нельзя игнорировать направление нейтральных атомов.
Интересно, что обе важные статьи, и от Google, и от Oratomic, полностью избегают упоминания о фактическом влиянии их результатов на Q-Day, не давая никаких прогнозов по срокам. Но основная цель белошляпочного криптоанализа как раз заключается в оценке сроков квантового взлома и помощи отрасли в заблаговременном планировании, так что такое молчание особенно ненормально.
Следуя логике статьи Скотта Ааронсона от 29 апреля и основываясь на известной мне публичной информации и неразглашаемых засекреченных данных, я даю следующую оценку: вероятность наступления Q-Day до 2032 года составляет 50%, вероятность реализации до 2030 года — 10%.
Для сравнения, официальная позиция США, представленная Агентством национальной безопасности (АНБ) и принятая Национальным институтом стандартов и технологий (NIST), устанавливает срок в 2035 год, когда правительственным учреждениям США будет запрещено продолжать использовать криптосистемы, уязвимые для квантовых атак. Оглядываясь назад, эта оценка серьёзно отстаёт от темпов технологического развития и практически бесполезна. Вероятно, в будущем NIST будет вынужден значительно перенести крайний срок вперёд.
Переход к постквантовой криптографии: Ethereum планирует завершить к 2029 году
Хотя квантовым рискам нужно уделять внимание, паниковать не стоит. Поспешное внедрение ещё не созревших постквантовых криптосистем может, наоборот, создать угрозы безопасности. На мой взгляд, 2029 год — это безопасное окно для миграции, примерно в трёх с половиной годах от настоящего момента. Google, облачный провайдер Cloudflare и Фонд Ethereum выбрали один и тот же временной ориентир.
В настоящее время большая часть моей работы связана с проектом лёгкого обновления Ethereum и продвижением плавного перевода всей цепочки Ethereum на постквантовую криптографию. Объём работ огромен: подписи BLS на уровне консенсуса, обязательства KZG на уровне данных и подписи ECDSA на уровне исполнения — всё требует замены. Вся схема обновления построена на основе хэш-криптографической системы и достаточно реализуема.
Внутри Фонда Ethereum мы разработали инструмент под названием leanVM, работающий на основе SNARK с хэшированием. Благодаря отличной работе Эмиля, Томаса и других, его производительность полностью обеспечена. С точки зрения безопасности leanVM — настоящая жемчужина. Это минималистичный zkVM, разработанный специально для сквозной формальной верификации и высочайшего уровня безопасности. Хотите внести свой вклад? В настоящее время существует две программы с призовым фондом в 1 миллион долларов. Первая — Proximity Prize: решите давнюю математическую гипотезу в теории кодирования, улучшите SNARK на основе хэширования и получите миллион долларов. Вторая — Poseidon Initiative: получите 1 миллион долларов за взлом Poseidon (дружественной к SNARK хэш-функции).
