a16z представила Lattice Jolt: доказательства в 3 раза быстрее и защита от квантовых атак

Автор: a16z crypto

Перевод: Deep Tide TechFlow

Введение от Deep Tide: zkVM часто критикуют за «слишком медленное доказательство и слишком большой размер». На этот раз a16z заменила эллиптические кривые решёточной криптографией, что напрямую ускорило доказательства в 3 раза и уменьшило их размер до менее 100 КБ. Это единственное постквантовое решение, которое по скорости превосходит традиционные схемы на эллиптических кривых, и оно напрямую влияет на стоимость проверки на блокчейне и приложения, требующие конфиденциальности.

Сегодня мы официально выпускаем Lattice Jolt — новейшую версию нашей zkVM с открытым исходным кодом (виртуальной машины с нулевым разглашением). Jolt и раньше была самой быстрой и простой zkVM, и её архитектура не изменилась. Но базовая криптография заменена: вместо эллиптических кривых теперь используется решёточная криптография. Это одно изменение даёт сразу три преимущества:

• Jolt становится постквантово-безопасной.
• Скорость работы прувера и верификатора возрастает в 2–3 раза.
• Lattice Jolt имеет самые короткие доказательства среди всех постквантовых zkVM: сейчас менее 100 КБ, и в дальнейшем их можно ещё сжимать. Доказательства нужно публиковать на блокчейне и передавать между сетями, поэтому чем меньше доказательство, тем ниже стоимость проверки.

Эти свойства охватывают все сценарии использования zkVM. Один и тот же прувер может доказывать миллиарды циклов CPU на GPU и доказывать миллионы циклов на смартфоне. В обоих случаях разработчики пишут обычные программы, а не схемы, требующие специальных знаний. Именно поэтому мы называем Jolt «универсальным SNARK».

Но более важная история — это значение Lattice Jolt для проектирования и внедрения SNARK. Почти все постквантовые SNARK, которые уже используются в промышленной эксплуатации, основаны на хешах. Lattice Jolt доказывает, что SNARK на решётках могут быть быстрее и компактнее. Цифровые подписи проходят аналогичную трансформацию: хеш-схемы — консервативный выбор, но именно решёточные схемы массово внедряются в мире. Мы ожидаем, что SNARK пойдут по тому же пути, и во второй половине этой статьи объясним почему.

Замена эллиптических кривых решётками

Предыдущая схема полиномиальных обязательств Jolt называлась Dory и была единственным компонентом системы, зависящим от криптографии на эллиптических кривых. Lattice Jolt заменяет Dory на Akita — совершенно новую схему полиномиальных обязательств, основанную на решёточном предположении Module-SIS. Lattice Jolt опирается на это стандартное и хорошо изученное предположение, обеспечивая полную 128-битную безопасность.

Module-SIS и его родственное предположение Module-LWE принадлежат к одному семейству, на которое мигрирует мировая цифровая инфраструктура. Эти предположения лежат в основе не только стандарта цифровой подписи ML-DSA, но и стандарта установления ключей ML-KEM, который уже является самым широко развёрнутым постквантовым примитивом в мире.

Разработку и реализацию Akita возглавили исследователи и инженеры LayerZero при участии исследователей из Университета Карнеги-Меллона, Университета Южной Калифорнии, а также наших инженерных и исследовательских команд в a16z crypto.

Почему Lattice Jolt быстрее

Lattice Jolt не только постквантово-безопасна, но и быстрее заменённой версии на эллиптических кривых.

Ускорение в основном объясняется простой причиной. Эллиптические кривые вынуждают Jolt работать в 256-битном поле, тогда как решёточная криптография достигает того же уровня безопасности в 128-битном поле. Основная работа прувера Jolt — умножение элементов поля (по сути, умножение очень больших чисел), поэтому уменьшение размера чисел вдвое делает каждое умножение в несколько раз быстрее.

Jolt с Dory уже была быстрой: наше последнее обновление производительности показало, что Jolt доказывает около 700 000 циклов RISC-V (RV64IMAC) в секунду на ноутбуке, а последующие оптимизации подняли версию Jolt на кривых выше 1 миллиона циклов в секунду.

Lattice Jolt на той же машине доказывает более 2 миллионов циклов в секунду.

Большую часть последних шести месяцев мы потратили не только на разработку Akita и интеграцию её в Jolt, но и полностью переписали кодовую базу Jolt. Jolt и раньше неплохо работала на GPU, но эта переработка сделала реализацию для GPU проще в разработке и оптимизации.

Первым достижением является реализация Apple Metal, которая дала огромное ускорение на оборудовании Apple. (Metal — это фреймворк Apple для выполнения кода на встроенных GPU таких устройств, как MacBook и iPhone.)

• Lattice Jolt с ускорением на GPU доказывает более 10 миллионов циклов RV64IMAC в секунду на MacBook.
• Чисто CPU-версия Lattice Jolt на той же машине доказывает более 2 миллионов циклов в секунду.
• Даже версия Jolt на кривых теперь достигает около 4 миллионов циклов в секунду на MacBook с Metal.

Иными словами, один релиз поднял производительность Jolt на MacBook с примерно 1 миллиона циклов в секунду (версия на кривых, только CPU) до более чем 10 миллионов циклов в секунду (решёточная версия с Metal).

Посмотрим на эти цифры в контексте: четыре года назад, когда мы впервые оценивали накладные расходы SNARK-прувера, доказательство вычисления было в миллионы раз дороже, чем его прямое выполнение. Lattice Jolt снизила эти накладные расходы примерно до десяти тысяч раз. Это ещё не предел — остаётся пространство для оптимизации как на инженерном, так и на протокольном уровне.

Размер доказательства так же важен, как и скорость прувера. При размере менее 100 КБ доказательства Lattice Jolt намного меньше, чем у других постквантовых zkVM, где размеры варьируются от более чем 200 КБ до примерно 600 КБ и более.

Переход на решётки также улучшил и без того отличное использование памяти Jolt: потребление памяти прувером снизилось с примерно 300 байт на цикл до 200 байт. Это означает, что можно доказывать миллионы циклов RISC-V на смартфоне.

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

Почему решётки, а не хеши

В течение многих лет внимание сообщества SNARK (и практически все промышленные развёртывания) было сосредоточено на SNARK на основе хешей как пути к постквантовой безопасности.

Но также существовала постоянная линия исследований решёточных SNARK и решёточных обязательств, включающая LaBRADOR, Greyhound, LatticeFold, SuperNeo и прямого предшественника Akita — Hachi. Lattice Jolt опирается на эти исследования, внедряя слой решёточных обязательств в высокопроизводительную архитектуру zkVM и доказывая, что решёточные SNARK не имеют равных по скорости и компактности.

Это не должно удивлять. Как уже говорилось, та же модель уже произошла в цифровых подписях.

Криптографы конструировали подписи на основе многих предположений. Хеш-подписи обычно считаются самым консервативным выбором: их предположения безопасности просты и стары. Но мир в основном переходит на решёточные подписи, потому что они короче и быстрее:

• Подписи ML-DSA имеют размер порядка нескольких КБ.
• Стандартизированная NIST хеш-альтернатива SLH-DSA в несколько раз больше.
• Для шифрования и обмена ключами ситуация ещё яснее: хеш-вариантов просто нет (доказано, что это невозможно), и постквантовое внедрение в подавляющем большинстве основано на решётках. ML-KEM (основной стандарт установления ключей, утверждённый NIST в 2024 году) уже развёрнут по умолчанию в основных браузерах и приложениях для обмена сообщениями и используется в огромном количестве TLS-соединений в интернете.

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

Здесь стоит прояснить одно заблуждение: хеш-снарки часто называют консервативным постквантовым выбором, потому что «они полагаются только на хеш-функции». Это верно только в том случае, если используемая хеш-функция неалгебраическая.

Сегодня большинство развёрнутых SNARK на основе хешей полагаются на дружественные к SNARK алгебраические хеш-конструкции (например, Poseidon), чтобы дёшево доказывать корректность вычисления хеша. Это особенно важно для рекурсии (здесь рекурсия означает доказательство того, что у вас есть действительное доказательство SNARK). Такие конструкции имеют больше структуры, чем стандартные хеш-функции, и их криптоанализ ещё незрел.

Короче говоря, мы не уверены в безопасности алгебраических хеш-функций. Тем не менее сегодня они широко используются в производственных SNARK-системах. (Впрочем, есть и обнадёживающий сигнал: Ethereum Foundation недавно объявила об отказе от их использования.)

Алгебраические хеши — не единственное скрытое предположение в развёрнутых SNARK на основе хешей: многие системы исторически использовали спекулятивные границы proximity-gap для установки конкретного уровня безопасности вместо полностью доказанных границ. Некоторые из этих границ, считавшиеся самыми сильными, позже оказались неверными.

Даже если избежать этих спекуляций, целевой уровень безопасности хеш-снарков обычно ниже 128 бит, потому что полная 128-битная безопасность влечёт значительные накладные расходы на производительность. Почему? Хеш-снарки не могут достичь 128-битной безопасности в 128-битном поле, поскольку их ошибка достоверности масштабируется как n/|F|, где n — примерно размер доказываемого утверждения, а |F| — размер поля. Поэтому доказательство утверждения на миллиард шагов в 128-битном поле теряет около 30 бит безопасности, опускаясь ниже 100 бит. В отличие от этого, ошибка достоверности Lattice Jolt масштабируется как log(n)/|F|, сохраняя почти полную 128-битную безопасность в том же поле (небольшую потерю log(n) можно восстановить стандартными методами).

Ирония в том, что некоторые системы, рекламируемые как «консервативный» постквантовый выбор, на самом деле одновременно полагаются на алгебраические хеш-функции, спекулятивные границы proximity-gap и целевой уровень безопасности ниже 128 бит. Поэтому, хотя SNARK на основе хешей — важное направление, они не являются автоматически тем низкорисковым вариантом, каким их многие считают.

Один Jolt, три основы: кривые, решётки и хеши

Мы всегда считали, что Jolt не должен быть привязан к единственной криптографической основе. У нас должны быть зрелые и высокопроизводительные SNARK на основе кривых, хешей и решёток. Разные предположения и характеристики производительности подойдут для разных сценариев.

Но если ориентироваться на цифровые подписи, решёточные SNARK станут самым широко развёрнутым постквантовым выбором.

Jolt находится в необычайно выгодном положении в этом переходе. Изначальная конструкция Jolt использовала свойства эллиптических кривых, особенно полезные для обязательств, включая быстрые обязательства для разреженных векторов. Решёточные обязательства обладают тем же свойством: когда большинство элементов вектора равны нулю или малы, стоимость обязательства для вектора низкая, а Jolt почти всегда работает именно с такими векторами. Это свойство позволило нам заменить Dory на Akita, сохранив остальную часть Jolt без изменений.

Мы создадим версию Jolt на основе хешей. Но по сравнению с Jolt на кривых и решётках хеш-версия будет хуже по пространственной эффективности, иметь более крупные доказательства и страдать от различных сложностей. Это связано с тем, что самые перспективные SNARK на основе хешей работают в двоичных полях. Такая система счисления удобна для доказательства вычисления хеша, но не соответствует способу арифметики CPU. Это несоответствие делает доказательство обычного умножения CPU дорогим. Тем не менее экосистема должна иметь zkVM для каждого основного семейства предположений, как и в случае цифровых подписей.

Универсальный SNARK

Lattice Jolt одновременно удовлетворяет все потребности разработчиков в zkVM: постквантовость, прозрачность, скорость, компактность и эффективность по памяти. Она переносит линию исследований решёточных SNARK от LaBRADOR до Hachi в производственную zkVM, не отказываясь ни от одного из преимуществ, которые изначально сделали Jolt быстрой.

Наша цель — не только открыть исходный код самой производительной zkVM для всеобщего использования, но и значительно снизить необходимость ручной настройки SNARK под конкретные приложения. Для этого не требуется, чтобы Jolt была такой же быстрой, как вручную настроенные пруверы. Это недостижимая цель, всё равно что требовать от CPU сравниться со специализированными ASIC в каждой задаче. Достаточно, чтобы Jolt была достаточно быстрой для приемлемого пользовательского опыта.

Для «маленьких» утверждений, связанных с доказательствами на стороне клиента (где сегодня доминируют вручную оптимизированные схемы), ключевой критерий — генерировать доказательство на смартфоне примерно за одну секунду. Jolt уже близка к этому, и в работе находится множество ускоряющих решений.

Эра решёточных SNARK наступила.