[Этот пост изначально был опубликован в Накамото . На основе выступления Эли Бен-Сассона в Сан-Франциско в ноябре 2019 г.]

1. Введение

В течение 3,5 миллиардов лет жизнь на Земле состояла из первобытного бульона из одноклеточных существ. Затем, в мгновение ока, во время так называемого Кембрийского взрыва возникли почти все типы животных, которые мы знаем сегодня.

По аналогии, в настоящее время мы переживаем кембрийский взрыв в области криптографических доказательств вычислительной целостности (CI). В то время как пару лет назад было около 1-3 новых систем в год, скорость выросла настолько, что сегодня мы видим такое же количество ежемесячно, если не еженедельно. А именно, в 2019 году мы узнали о новых конструкциях, таких как Libra , Sonic , SuperSonic , PLONK , SLONK , Halo , Marlin , Fractal , Spartan , Succinct Aurora , и реализациях, таких как OpenZKP , Hodor и GenSTARK.. О, и пока чернила в этом посте сохнут, появляются RedShift и AirAssembly .

Как понять все это чудесное нововведение? Цель этого поста — определить общие знаменатели всех систем CI, реализованных в коде, и обсудить несколько отличительных факторов. Описание будет кратким и намеренно неточным с математической точки зрения. Еще одна важная цель этого поста — объяснить, почему StarkWare помещает все свои фишки с точки зрения науки, техники и продуктов в конкретное подсемейство CI-вселенной, именуемое в дальнейшем симметричными STARK .

Общие предки

Системы проверки CI могут помочь решить две фундаментальные проблемы, с которыми сталкиваются децентрализованные блокчейны (и другие системы): конфиденциальность и масштабируемость. Доказательства с нулевым разглашением (ZKP¹) обеспечивают конфиденциальность , защищая некоторые входные данные вычислений без ущерба для целостности, а кратко проверяемые системы CI обеспечивают масштабируемость , экспоненциально сокращая объем вычислений, необходимых для проверки целостности большого пакета транзакций.

Все системы CI, которые были реализованы в коде, имеют две общие черты: все используют арифметизацию и все обеспечивают «низкую степень соответствия» (LDC) с помощью криптографических средств². Арифметизация — это сокращение вычислительных утверждений, сделанных доказывающим, например:

«Я знаю ключи, которые позволяют мне провести защищенную транзакцию Zcash»

к алгебраическим утверждениям, включающим набор полиномов ограниченной степени, например:

«Я знаю четыре многочлена A(X), B(X), C(X), D(X), каждый степени меньше 1000, для которых выполняется равенство: A(X)*B²(X)-C( X) = (X¹⁰⁰⁰–1)*D(X)».

Соответствие низкой степени означает использование криптографии, чтобы гарантировать, что доказывающая сторона действительно выбирает полиномы низкой степени³ и оценивает эти полиномы в случайно выбранных точках, запрошенных проверяющей стороной. В приведенном выше примере (на который мы продолжим ссылаться в этом посте) хорошее решение LDC гарантирует, что когда пруверу будет задан вопрос об x ₀ , он ответит значениями a ₀ , b ₀ , c ₀ , d ₀ которые являются правильными значениями A, B, C и D на входе x ₀ . Сложность заключается в том, что доказывающий может выбрать A, B, C и D, увидев запрос x ₀ , или может решить ответить произвольным образом a ₀ , b ₀ , c ₀, d ₀ , которые умиротворяют проверяющего и не соответствуют никакой оценке заранее выбранных полиномов низкой степени. Таким образом, вся эта криптография направлена ​​на предотвращение таких векторов атак. (Тривиальное решение, требующее, чтобы доказывающая сторона отправила полные A, B, C и D, не обеспечивает ни масштабируемости, ни конфиденциальности.)

Имея это в виду, CI-версия может быть отображена в соответствии с (i) криптографическими примитивами, используемыми для обеспечения LDC, (ii) конкретными решениями LDC, построенными с этими примитивами, и (iii) типом арифметизации, допускаемой этими вариантами.

2. Размеры сравнения

I. Криптографические предположения

На высоте 30 000 футов самым большим теоретическим фактором, различающим различные системы CI, является то, требуют ли их безопасности симметричные или асимметричные примитивы (см. рис. 1).Типичными симметричными примитивами являются SHA2, Keccak (SHA3) или Blake, и мы предполагаем, что они являются устойчивыми к коллизиям хеш-функциями (CRH), псевдослучайными и ведут себя как случайный оракул.Асимметричные предположения включают такие вещи, как сложность решения задачи дискретного логарифмирования по модулю простого числа, модуля RSA или группы эллиптических кривых, сложность вычисления размера мультипликативной группы кольца RSA и более экзотические варианты таких задач. например, предположение о «знании экспоненты», предположение об «адаптивном корне» и т. д.

Это разделение симметрии/асимметрии между системами КИ имеет много последствий, среди которых:

A. Вычислительная эффективность
Безопасность асимметричных примитивов, реализованных сегодня в коде⁴, требует арифметизации и решения задач LDC в больших алгебраических областях: больших простых полях и больших эллиптических кривых над ними, в которых каждый элемент поля/группы имеет длину в сотни битов, или целочисленные кольца, в которых каждый элемент имеет длину в тысячи битов. Напротив, конструкции, основанные только на симметричных предположениях, арифметизируют и выполняют LDC над любой алгебраической областью (кольцом или конечным полем), которая содержит гладкие⁵ подгруппы, включая очень маленькие двоичные поля и 2-гладкие простые поля (64 бита или меньше), в которых арифметические операции выполняются быстро.

Вывод: симметричные системы непрерывной интеграции могут выполнять арифметические операции в любом поле, что повышает эффективность.

B. Постквантовая безопасность
Все асимметричные примитивы, используемые в настоящее время в CI-вселенной, будут эффективно взломаны квантовым компьютером с достаточно большим состоянием (измеряемым в кубитах), если и когда такой компьютер появится. С другой стороны, симметричные примитивы, вероятно, являются постквантово безопасными (возможно, с большими начальными значениями и состояниями на бит безопасности).

Вывод: только симметричные системы являются постквантово безопасными.

C. Защита будущего
Теория эффекта Линди гласит, что «ожидаемая продолжительность жизни в будущем некоторых долговечных вещей, таких как технология или идея, пропорциональна их нынешнему возрасту». или, говоря простым языком, старые вещи живут дольше, чем новые. В области криптографии это можно перевести как утверждение о том, что системы, основанные на старых, проверенных в боевых условиях примитивах, более безопасны и более перспективны, чем более новые предположения, шины которых меньше изнашиваются (см. рис. 2). С этой точки зрения новые варианты асимметричных предположений, таких как группы неизвестного порядка , общая групповая модель и знание экспонентыпредположения моложе и тянут более легкую экономическую тележку, чем более старые предположения, такие как более стандартные предположения DLP и RSA , которые используются, например, для цифровых подписей, шифрования на основе идентификации и для инициализации SSH. Эти допущения менее перспективны, чем симметричные допущения, такие как существование устойчивой к коллизиям хеш-функции , потому что эти последние допущения (и даже конкретные хеш-функции) являются кирпичом и раствором, используемым для защиты компьютеров, сетей, Интернета и электронной коммерции.

Более того, среди этих предположений существует строгая математическая иерархия. Допущение CRH господствует в этой иерархии, потому что, если это предположение нарушается (это означает, что не может быть найдена безопасная криптографическая хэш-функция), тогда, в частности, предположения RSA и DLP также не нарушаются, поскольку эти предположения подразумевают существование хорошего CRH! Точно так же предположение DLP доминирует над предположением о знании экспоненты (KoE), потому что, если первое предположение (DLP) не выполняется, то последнее (KoE) также не выполняется. Точно так же предположения RSA доминируют над предположением группы неизвестного порядка (GoUO), потому что, если RSA нарушается, GoUO также нарушается.

Вывод: новые асимметричные допущения представляют собой более рискованную основу для финансовой инфраструктуры.

D. Длина аргумента
Все пункты, сделанные выше, отдают предпочтение симметричным конструкциям КИ, а не асимметричным. Но есть одна область, в которой асимметричные конструкции работают лучше. Связанная с ними сложность коммуникации (или длина аргумента) меньше на 1–3 порядка (несмотря на закон Нильсена⁶). Известно, что Groth16 SNARK короче 200 байт при предполагаемом уровне безопасности 128 бит, тогда как все существующие сегодня симметричные конструкции требуют десятков килобайт для того же уровня безопасности. Следует отметить, что не все асимметричные конструкции имеют размер 200 байт. Недавние конструкции улучшают Groth16 за счет (i) устранения необходимости в доверенной настройке (прозрачность) и/или (ii) обработки общих схем (Groth16 требует одну доверенную настройку на схему). Но эти более новые конструкции имеют более длинные аргументы, достигающие размера от полукилобайта (как в случае PLONK) до двузначного числа килобайт, что приближается к длине аргумента симметричных конструкций.

Вывод: асимметричные системы, специфичные для схем (Groth16), являются самыми короткими, короче всех асимметричных универсальных систем и всех симметричных систем.

Повторяя приведенные выше выводы:

• Симметричные системы непрерывной интеграции могут выполнять арифметические операции в любом поле, что повышает эффективность.
• Только симметричные системы могут быть постквантово безопасными.
• Новые асимметричные допущения представляют собой более рискованную основу для финансовой инфраструктуры
• Асимметричные системы, специфичные для схемы (Groth16), являются самыми короткими, короче всех асимметричных универсальных систем и всех симметричных систем.

II. Схемы низкого уровня соответствия (LDC)

Существует два основных способа достижения низкой степени соответствия: (i) сокрытие запросов и (ii) схемы фиксации (см. рис. 3). Давайте пройдемся по различиям.

Скрытие запросов
Этот подход (формализованный здесь ) используется SNARK в стиле Zcash, такими как Pinocchio, libSNARK, Groth16, и системами, построенными на них, такими как Zcash Sapling, Ethereum Zokrates и т. д. Чтобы заставить доказывающего ответить правильно, мы используем гомоморфный шифрование , чтобы скрыть или зашифровать x ₀ и предоставить достаточно информации, чтобы доказывающий мог оценить A, B, C и D на x ₀ . На самом деле доказывающему дается последовательность зашифровок степеней x ₀ (т. е. зашифровок x ₀¹ , x ₀² , … x ₀¹⁰⁰⁰), так что доказывающий может оценить любой полином степени 1000, но только полиномы степени не выше 1000. Грубо говоря, система безопасна, так как доказывающий не знает, что такое x ₀ , а этот x ₀ выбирается случайным образом (предварительно), так что если доказывающий попытается обмануть, то с очень высокой вероятностью его разоблачат. Здесь необходима доверенная фаза предварительной обработки для выборки x ₀ и шифрования приведенной выше последовательности степеней (и дополнительной информации), что приводит к доказательному ключу, который, по крайней мере, такой же большой, как схема доказываемого вычисления (есть также ключ подтверждения, который намного короче). После того, как настройка завершена и ключи выпущены, каждое доказательство становится единым, кратким , nна интерактивном аргументе знания (или SNARK, для краткости ) . Обратите внимание, что эта система требует некоторой формы взаимодействия в виде фазы предварительной обработки, которая неизбежна по теоретическим причинам. Обратите также внимание на то, что система непрозрачна, а это означает, что энтропия, используемая для выборки и шифрования x ₀ , не может быть просто общедоступной случайной монетой, потому что любая сторона, которая знает x ₀, может взломать систему и доказать ложность. Таким образом, генерация шифрования x ₀ и его возможностей без раскрытия x ₀ является проблемой безопасности, которая представляет собой потенциальную единую точку отказа.

Схемы
фиксации Этот подход требует, чтобы доказывающая сторона фиксировала набор полиномов низкой степени (A, B, C и D в приведенном выше примере), отправляя верификатору некоторое криптографически созданное сообщение фиксации. Имея на руках это обязательство, верификатор теперь делает выборку и запрашивает доказывающего о случайно выбранном x ₀ , и теперь доказывающий отвечает с помощью a ₀ , b ₀ , c ₀ и d ₀ вместе с дополнительной криптографической информацией, которая убеждает проверяющего в том, что четыре значения, выявленные доказывающим, соответствуют ранее отправленному проверяющему обязательству. Такие схемы, естественно, интерактивны, и многие из них прозрачны .(все сообщения, сгенерированные верификатором, являются просто публичными случайными монетами). Прозрачность позволяет сжать протокол до неинтерактивного с помощью эвристики Фиата-Шамира (которая рассматривает псевдослучайную функцию, такую ​​как SHA 2/3, как случайный оракул, обеспечивающий «общедоступную» случайность), или использовать другие общедоступные источники случайности. как заголовки блоков. Наиболее распространенная схема прозрачных обязательств — через деревья Меркла, и этот метод, вероятно, является постквантово безопасным, но приводит к большой длине аргументов, наблюдаемой во многих симметричных системах (из-за всех путей аутентификации, которые необходимо раскрывать и сопровождать каждый ответ доказывающего). . Это метод, используемый большинством STARK, таких как libSTARK и краткая Aurora, а также системами кратких доказательств, такими как ZKBoo, Ligero, Aurora и Fractal (хотя эти системы не удовлетворяют формальному определению масштабируемости STARK). В частности, STARK, которые мы создаем в StarkWare (например,Альфа-версия StarkDEX и StarkExchange , который мы скоро развернем), подпадают под эту категорию. Можно использовать асимметричные примитивы для построения схем обязательств, например, те, которые основаны на сложности дискретной логарифмической задачи над группами эллиптических кривых (это подход, принятый BulletProofs и Halo), и группы предположения неизвестного порядка (как это сделано DARK и СуперСоник). Использование асимметричных схем обязательств имеет свои плюсы и минусы, упомянутые ранее: более короткие доказательства, но более длительное время вычислений, квантовая восприимчивость, более новые (и менее изученные) предположения и, в некоторых случаях, потеря прозрачности.

III. Арифметизация

Выбор криптографического предположения и методов LDC также влияет на диапазон возможностей арифметизации тремя заметными способами (см. рис. 4):

A. NP (схемы) и NEXP (программы)
Большинство реализованных систем непрерывной интеграции сводят вычислительные задачи к арифметическим схемам, которые затем преобразуются в набор ограничений (как правило, ограничений R1CS, обсуждаемых ниже). Этот подход позволяет проводить оптимизацию для конкретных цепей, но требует от верификатора или какого-либо объекта, которому он доверяет, выполнения вычислений такого же масштаба, как и проверяемое вычисление (схема). Для многоцелевых схем, таких как схема Zcash Sapling, этой арифметизации достаточно. Но масштабируемые и прозрачные системы (без доверенной установки), такие как libSTARK, лаконичная Aurora и системы, которые создает StarkWare, должны использовать краткое представление вычислений, похожее на общую компьютерную программу и имеющее экспоненциально меньшее описание.чем проверяемый расчет. Два существующих метода для достижения этого — (i) алгебраические промежуточные представления (AIR), используемые системами libSTARK, genSTARK и StarkWare, и (ii) краткие R1CS succinct-Aurora, лучше всего описываются как арифметизация общих компьютерных программ (в отличие от схемы). Эти краткие представления достаточно эффективны, чтобы охватить класс сложности недетерминированного экспоненциального времени (NEXP), который является экспоненциально более выразительным и мощным, чем класс недетерминированного полиномиального времени (NP), описываемого схемами.

B. Размер и тип алфавита
Как указывалось выше, используемые криптографические предположения также в значительной степени определяют, какие алгебраические домены могут служить алфавитом, над которым мы выполняем арифметические операции. Например, если мы используем билинейные пары, то алфавит, который мы будем использовать для арифметизации, представляет собой циклическую группу точек эллиптической кривой, и эта группа должна быть большого простого размера, а это означает, что нам нужно выполнять арифметику над этим полем. Возьмем другой пример: система SuperSonic (в одной из ее версий) использует целые числа RSA, и в этом случае алфавит будет большим простым полем. Напротив, при использовании деревьев Меркла размер алфавита может быть произвольным, что позволяет выполнять арифметику в любой конечной области. Это включает в себя приведенные выше примеры, а также произвольные простые поля, расширения небольших простых полей, таких как двоичные поля.

C. R1CS против общих полиномиальных ограничений
SNARK в стиле Zcash использует билинейные пары по эллиптическим кривым для арифметизации ограничений вычислений. Это конкретное использование ⁷ билинейных пар ограничивает арифметизацию гейтами, которые являются квадратичными Rank - 1 системами ограничений ( R1CS ). Простота и повсеместность R1CS побудили многие другие системы использовать эту форму арифметизации для цепей, даже несмотря на то, что могут использоваться более общие формы ограничений, такие как квадратичные формы произвольного ранга или ограничения более высокой степени.

3. STARK против SNARK

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

STARK

Здесь буква S означает масштабируемость , что означает, что по мере увеличения размера партии n доказывается квазилинейная шкала времени по n и одновременно проверяется полилогарифмическая шкала времени⁸ по n. T в STARK означает прозрачность , что означает, что все сообщения верификатора являются общедоступными случайными монетами (без доверенной настройки). В соответствии с этим определением, если есть какие-либо настройки предварительной обработки, они должны быть краткими (полилогарифмическими) и состоять только из выборки общедоступных случайных монет.

SNARK

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

Глядя на CI-версию (см. рис. 5), можно заметить, что некоторые ее члены являются STARK, другие — SNARK, некоторые — обоими, а третьи — ни тем, ни другим (например, если время проверки хуже, чем полилогарифмически по n). Если вас интересуют приложения для обеспечения конфиденциальности (ZKP), то и ZK-SNARK, и ZK-STARK, и даже системы, которые не обладают ни масштабируемостью STARK, ни (более слабой) краткостью SNARK, могут сослужить хорошую службу; Bulletproofs, используемый Monero, является одним из таких примечательных примеров, в котором время проверки линейно зависит от размера схемы. Когда дело доходит до зрелости кода, у SNARK есть преимущество, потому что есть довольно много хороших библиотек с открытым исходным кодом, на которые можно опираться. Но если вы заинтересованы в приложениях с масштабируемостью (где вам нужно создавать для постоянно растущих размеров пакетов), то мы предлагаем использовать симметричные STARK, потому что на момент написания у них самое быстрое время проверки и гарантия того, что ни одна часть процесса проверки (или настройки системы) не требует времени, превышающего полилогарифмическую обработку. И если вы хотите построить системы с минимальными предположениями о доверии, тогда, опять же, вы хотите использовать симметричный STARK, потому что единственный необходимый ингредиент — это некоторая CRH и источник публичной случайности.

4. Резюме

Нам посчастливилось пережить чудесный кембрийский взрыв вселенной систем доказательства Computational Integrity, и все ставки на то, что распространение систем и инноваций будет продолжаться с возрастающей скоростью. Более того, эта попытка описать расширяющуюся и меняющуюся вселенную КИ, скорее всего, не устаревает, поскольку завтра появятся новые идеи и конструкции. Сказав это, изучая сегодня пространство CI, мы видим, что самая большая разделительная линия проходит между (i) системами, которые требуют асимметричных криптографических предположений, которые приводят к более коротким доказательствам, но требуют больших затрат на доказательство, имеют более новые предположения, которые являются квантово-чувствительными, и многие из которых непрозрачны, и (ii) системы, которые полагаются только на симметричные предположения, что делает их вычислительно эффективными, прозрачными,

Спор о том, какую систему аргументации использовать, далек от завершения. Но в StarkWare мы говорим: для коротких аргументов используйте Groth16/PLONK SNARK. Для всего остального есть симметричные STARK.

Эли Бен-Сассон, StarkWare

Особая благодарность Джастину Дрейку за комментарии к предыдущему черновику.

— — — — — — — — — — — — — —

¹ Термин ZKP часто неправильно используется для обозначения всех систем CI, даже тех, которые формально не являются ZKP. Чтобы избежать этой путаницы, мы используем нечетко определенные термины «криптодоказательства» и «доказательства вычислительной целостности (CI)».

² Вы можете прочитать об арифметизации STARK и соответствии с низкой степенью здесь:

• Арифметизация: блоги [ 1 , 2 ], слайды лекций , видеолекции .
• Низкая степень: запись в блоге (для STARK)

³ Использование одномерных полиномов может быть широко распространено, например, на многомерные полиномы и коды алгебраической геометрии, но для простоты мы придерживаемся простейшего одномерного случая.

⁴ Мы специально исключаем из нашего обсуждения конструкции на основе решетки, потому что они еще не развернуты в коде. Такие конструкции являются асимметричными, а также, вероятно, постквантово безопасными и обычно используют небольшие (простые) поля.

⁵ Поле называется k-гладким, если оно содержит подгруппу (мультипликативную или аддитивную) размера, все простые делители которой не превосходят k. Например, все бинарные поля являются 2-гладкими, поэтому поля размера q, такие как q-1, делятся на большую степень 2.

⁶ Закон Нильсена о пропускной способности Интернета гласит, что пропускная способность пользователей увеличивается на 50% в год. Этот закон соответствует данным с 1983 по 2019 год.

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

⁸ Формально «квазилинейный по n» означает O(n logᴼ⁽¹⁾ n), а «полилогарифмический по n» означает logᴼ⁽¹⁾ n.