a16z запускает Lattice Jolt: доказательства в 3 раза быстрее с постквантовой безопасностью

Автор: a16z crypto

Перевод: Shenchao TechFlow

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

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

• Jolt становится постквантово безопасным.
• Скорость prover и verifier увеличена в 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-битную безопасность на основе этого стандартизированного и хорошо изученного предположения.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На протяжении многих лет внимание сообщества SNARK (и практически все производственные развертывания) было сосредоточено на хэш-основанных SNARK, рассматривая их как путь к постквантовой безопасности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эпоха SNARK наступила.

Данный материал предназначен исключительно для ознакомления и не должен использоваться в качестве юридических, коммерческих, инвестиционных или налоговых рекомендаций. По этим вопросам вам следует проконсультироваться со своим консультантом. Упоминание любых ценных бумаг или цифровых активов носит исключительно иллюстративный характер и не является предложением инвестиционных рекомендаций или предложения услуг инвестиционного консультанта. Кроме того, данный материал не адресован никаким инвесторам или потенциальным инвесторам и не может служить основанием для принятия решения об инвестировании в любой фонд, управляемый a16z. (Предложение об инвестировании в фонды a16z осуществляется исключительно через частное предложение этих фондов, соглашения о подписке и другие сопутствующие документы, которые следует внимательно изучить в полном объеме.) Любые упомянутые, цитируемые или описанные инвестиции или портфельные компании не представляют собой полный перечень инвестиций, осуществляемых инструментами управления a16z, и не гарантируют прибыльность этих инвестиций, а также не гарантируют, что будущие инвестиции будут иметь аналогичные характеристики или результаты. Список инвестиций, сделанных фондами, управляемыми Andreessen Horowitz (за исключением инвестиций, раскрытие которых эмитенты не разрешили a16z публиковать, а также непубличных инвестиций в списочные цифровые активы), доступен по адресу https://a16z.com/investments/.

Представленные на диаграммах данные приведены исключительно в ознакомительных целях и не должны использоваться в качестве основы для принятия каких-либо инвестиционных решений. Прошлые результаты не являются показателем будущих результатов. Данный контент отражает ситуацию на указанную дату. Любые прогнозы, оценки, перспективные заявления, цели, перспективы и/или мнения, выраженные в этих материалах, могут быть изменены в любое время без предварительного уведомления и могут отличаться от или противоречить мнениям других лиц. Более подробную информацию см. на сайте https://a16z.com/disclosures.