Автор: Justin Drake, исследователь Ethereum Foundation
Перевод: Chopper, Foresight News
31 марта команда Google Quantum AI опубликовала важную работу, посвящённую алгоритму Шора для эллиптических кривых. С технической точки зрения, эта статья является прорывом: эффективность алгоритма была улучшена в 10 раз по сравнению с предыдущими лучшими решениями. Команда выбрала для демонстрации оптимизированных вычислений эллиптическую кривую secp256k1, лежащую в основе подписей Bitcoin и Ethereum, что послужило не только технической демонстрацией, но и тревожным сигналом для индустрии блокчейна.
Однако самое интересное в этой статье лежит не в технической, а в нормативной плоскости. Исследовательская команда не следовала обычной академической процедуре открытой публикации, сохраняя ключевые детали оптимизации в секрете, и использовала доказательства с нулевым разглашением (ZK) лишь для подтверждения существования рабочей оптимизации, не раскрывая никаких технических деталей. В связанном блоге Google упоминается о сотрудничестве с правительственными органами США в ходе проекта. Использование ZK-доказательств для контроля над содержанием академической работы — это беспрецедентный случай в мировой научной истории.
Я, как один из соавторов этой статьи, был свидетелем предыстории и последствий этой ограниченной публикации. Честно говоря, многие детали этого дела вызывают у меня несогласие. Я по-прежнему считаю, что общественность имеет право на получение этой информации, но в силу объективных обстоятельств не могу раскрывать внутренние детали. Однако должен отметить, что команда Google действовала профессионально и скрупулёзно на всём протяжении работы, что заслуживает признания и похвалы.
Намеренный контроль над информацией часто приводит к обратным результатам, и сейчас проявляется «эффект Стрейзанд» (чем больше пытаются скрыть, тем больше внимания это привлекает): ключевой оптимизированный алгоритм, который Google так тщательно охранял, уже был воспроизведён французскими исследователями. Что ещё более неожиданно, был запущен открытый конкурс с участием всего сообщества по взлому алгоритма Шора, и всего через несколько часов после запуска сайта ecdsa.fail был побит мировой рекорд по оптимизации алгоритма Шора.
Алгоритм воспроизведён независимо, открытые конкурсы множатся
Всего через два месяца после публикации статьи Google, французский эксперт в области квантовых технологий Андре Шроттенлохер первым расшифровал эту ключевую логику оптимизации. Его статья под названием «Оптимизированные схемы сложения точек для дискретного логарифмирования на эллиптических кривых» была опубликована сегодня на сайте препринтов 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%.
Для сравнения, официальная позиция США, представленная Агентством национальной безопасности (NSA) и принятая Национальным институтом стандартов и технологий (NIST), указывает на 2035 год как срок, после которого государственным органам США будет запрещено использовать криптосистемы, уязвимые для квантовых атак. В ретроспективе эта оценка серьёзно отстаёт от темпов технологического развития и практически бесполезна. В будущем NIST, скорее всего, будет вынужден значительно перенести этот срок.
Постквантовая миграция: Ethereum планирует завершить её к 2029 году
Хотя к квантовым рискам нужно относиться серьёзно, паниковать не стоит. Поспешное внедрение ещё незрелых постквантовых криптосистем может, наоборот, создать угрозы безопасности. На мой взгляд, 2029 год — это надёжное окно для миграции, примерно три с половиной года от настоящего момента. Google, облачный провайдер Cloudflare и Ethereum Foundation выбрали один и тот же срок.
В настоящее время большая часть моей работы связана с проектом облегчённого обновления Ethereum, направленным на плавный переход всей цепочки Ethereum на постквантовую криптографию. Объём работ огромен: необходимо заменить подписи BLS на уровне консенсуса, обязательства KZG на уровне данных и подписи ECDSA на уровне исполнения. Вся схема обновления построена на основе хеш-криптографии и является полностью выполнимой.
Внутри Ethereum Foundation мы разработали инструмент под названием leanVM, который работает на основе SNARK, использующих хеши. Благодаря выдающейся работе Эмиля, Томаса и других, его производительность полностью обеспечена. С точки зрения безопасности leanVM — это сокровище. Это минималистичная zkVM, разработанная для сквозной формальной верификации и максимальной безопасности. Хотите внести свой вклад? В настоящее время существуют две программы с призовым фондом в 1 миллион долларов. Первая — Proximity Prize: решите давнюю математическую гипотезу в теории кодирования, улучшите SNARK на основе хешей и получите миллион долларов. Вторая — Poseidon Initiative: получите 1 миллион долларов за взлом Poseidon (хэш-функция, дружественная к SNARK).
