Microsoft Research показала Magnetar: zkVM в 10–39 раз быстрее аналогов

Microsoft Research представила Magnetar — zero-knowledge virtual machine, которая доказывает выполнение обычных программ на Rust, Go и C. Программа запускается как обычно, а вместе с результатом выдаёт короткое доказательство того, что именно этот код на этих входах дал именно этот выход. Проверка занимает около 12 миллисекунд. На ноутбуке Magnetar обрабатывает 7,2–8,7 млн инструкций процессора в секунду и в среднем в 10–39 раз опережает самые быстрые сопоставимые zkVM. Автор работы — Srinath Setty, старший главный исследователь и руководитель группы в Microsoft Research.

Три проблемы, которые не решались одновременно

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

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

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

Десять лет деталей: из чего собран Magnetar

Magnetar — итог более чем десятилетней работы Microsoft Research. Исследователи шли поэтапно, и каждая работа закрывала свой кусок:

• Spartan (2019) — вернул подход sum-check и сделал его пригодным для программ общего назначения без доверенной настройки; допускает разные криптографические блоки.
• Phalanx (2021) — использует повторяемость, например одинаковый цикл инструкций процессора, и доказывает вычисления примерно на порядок быстрее Spartan. На этой идее построено описание процессора в Magnetar.
• Nova, HyperNova, NeutronNova, Neo и SuperNeo — досрочно останавливают доказательство Spartan и сворачивают частичные результаты, что делает доказательство вычислений любого размера значительно дешевле.
• Brakedown (2021) — быстрая схема обязательств на хеш-функциях; вместе со Spartan дала первый вариант, чья безопасность держится на стандартных хешах.
• Spice, Lasso, Nebula, Twist and Shout — сделали дешёвыми операции с памятью, на которых держится универсальный процессор.
• Jolt — показал, что в сочетании со Spartan можно эффективно доказать выполнение целого процессора.
• Vega — применила эти идеи к цифровой идентичности: факты из государственного документа доказываются менее чем за десятую долю секунды.
• BinarySpartan — перенёс Spartan в бинарные поля, где эффективно выражаются логика процессора и стандартные хеш-функции.
• Ligerito — схема обязательств в стиле Brakedown с заметно более короткими доказательствами.
• Ring switching — позволяет эффективно фиксировать векторы битов.

Скорость и безопасность в цифрах

Magnetar доказывает выполнение RISC-V — открытой архитектуры, для которой есть зрелые компиляторы практически для всех основных языков. Разработчик пишет программу на Rust, Go или C, компилирует и получает доказательство без переписывания в схемы. Бизнес-политика, конвейер данных или интерпретатор виртуальной машины Ethereum — всё это обычные программы.

Ключевые показатели:

• 7,2–8,7 млн инструкций процессора в секунду на ноутбуке;
• 9,5–12,8 млн циклов в секунду в оптимизированной версии, что увеличивает все заявленные ускорения примерно в 1,3 раза;
• в 10–39 раз быстрее в среднем, чем самые быстрые существующие zkVM, на 15 тестовых программах: от криптографического хеширования до переводов токенов в небольшом интерпретаторе EVM;
• более чем в 300 раз быстрее двух других систем на тесте с переводом токенов;
• проверка доказательства около 12 мс.

Безопасность Magnetar опирается на стандартную хеш-функцию вроде SHA-256 или SHA-3. Не нужны эллиптические кривые, решётки, специализированные хеши, доверенная настройка и недоказанные гипотезы о кодах. Хеш-функции изучены лучше всего в криптографии, на них же построены хеш-подписи, которые NIST стандартизировал как консервативный постквантовый вариант. Для Microsoft это ещё и вопрос согласованности с программой Quantum Safe, которая должна перевести продукты на постквантовую криптографию к 2029 году.

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

Где это пригодится на практике

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

Для инженеров важнее другое: порог входа снижается. Если команда уже поддерживает код на Rust, Go или C, ей не нужен специалист по криптографии для написания схем. Остаётся вопрос, какие результаты компании захотят проверять, а не принимать на веру. Microsoft Research приглашает к обсуждению сценариев, а техническая статья с полным описанием дизайна, анализом безопасности и измерениями называется «Magnetar: High-speed post-quantum RV64 zkVM from standard hashes».