a16z запускає Lattice Jolt: докази на 3x швидше з постквантовою безпекою

Автор: a16z crypto

Переклад: Shenchao TechFlow

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

Сьогодні ми офіційно запускаємо Lattice Jolt — останню версію нашого відкритого zkVM (нульових знань віртуальної машини). Jolt і раніше був найшвидшим і найпростішим zkVM, і його архітектура не змінилася. Але нижчий рівень криптографії було замінено: замість еліптичних кривих використовується решіткова криптографія. Ця зміна одночасно призводить до трьох результатів:

• Jolt стає постквантово безпечним.
• Швидкість prover та verifier збільшена в 2–3 рази.
• Lattice Jolt став найкоротшим доказом серед усіх постквантових zkVM: зараз менше 100 КБ, і ще можна стиснути. Оскільки докази потрібно записувати в ланцюжок і передавати між мережами, менший розмір доказу означає нижчі витрати на перевірку.

Ці функції охоплюють усі сценарії використання zkVM. Один і той самий prover може обробляти мільярди 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) за секунду на ноутбуці, а подальші оптимізації перевищили межу в 1 мільйон циклів за секунду для версії Jolt з кривою.

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 prover, створення доказу для обчислення коштувало в мільйони разів дорожче, ніж безпосереднє виконання цього обчислення. Lattice Jolt знизив ці витрати до приблизно десяти тисяч разів. Це ще не кінець — усі ще залишається простір для оптимізації на рівні інженерії та протоколу.

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

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

Незабаром буде опубліковано супутню статтю, яка додасть Lattice Jolt властивість нульового знання — необхідну для застосунків приватності.

Протягом багатьох років увага спільноти SNARK (і майже всі виробничі розгортання) була зосереджена на хеш-орієнтованих SNARK, як на шляху до післяквантової безпеки.

Також завжди існувала постійна лінія досліджень у сфері Lattice SNARK та Lattice commitments, що охоплювала LaBRADOR, Greyhound, LatticeFold, SuperNeo та прямого попередника Akita — Hachi. Lattice Jolt базується на цих дослідженнях, впроваджуючи шар Lattice commitments у архітектуру високопродуктивного 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) можна відновити за допомогою стандартних технологій).

Іронічно, деякі системи, які позиціонуються як «консервативні» післяквантові рішення, насправді залежать від алгебраїчних хеш-функцій, спекулятивних меж proximity-gap та цільового рівня безпеки нижче 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.