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

Блокчейн Anoma рассчитывает защищенные транзакции благодаря экранированному пулу с несколькими активами. Каждый блок содержит различную информацию, связанную с переходами состояний, которую могут проверить все пользователи блокчейна. Основная идея проверки текущего состояния блока состоит в перерасчете всех переходов между состояниями, начиная с исходного блока. Основным недостатком этого метода является то, что чем длиннее блокчейн, тем дороже он становится в вычислительном отношении.
В этой статье мы представляем, как можно проверить переходы состояний с помощью доказательства знаний. Представляя эту концепцию на простом примере без использования какой-либо криптографии, в этой статье также описываются различные альтернативы получения конкретных безопасных доказательств с криптографической точки зрения. Впоследствии мы представляем эффективные проверки всей цепочки блоков с использованием рекурсивных доказательств знаний. Подводя итог, приведем сравнение различных доступных конструкций с практической точки зрения.
Простой пример
Доказательства знаний стали очень известными в последние несколько лет. Мы начнем этот раздел с очень простого примера использования колоды карт.

Этот простой пример показывает, что:
- Алиса не раскрывает информацию о своей секретной карте (ни номер, ни масть, т. е. ❤️ или ♦️). Мы говорим, что это доказательство с нулевым разглашением.
- Используя это неоспоримое доказательство, Алиса всегда убеждает Боба. При этом мы говорим, что доказательство обладает свойством полноты.
- Мошенник, выбравший красную карту, не сможет доказать, что он выбрал черную карту. Это называется правдивостью доказательства.
В следующих разделах мы рассматриваем доказательства знания, удовлетворяющие нулевому разглашению. Как конструкция криптографии с открытым ключом, схемы доказательства основаны на сложной математической задаче. Надежность доказательств, которые мы здесь исследуем, основана на задаче дискретного логарифмирования (DLP), реализуемой в двух разных случаях: конечные поля и эллиптические кривые. В следующем разделе мы познакомим вас с необходимыми инструментами для доказательства знаний.правдивость и полнота,
В этой статье мы предполагаем, что читатель знаком с эллиптической кривой и криптографией на основе спаривания, а также с алгеброй конечных полей.
Доказательство знания арифметической схемы
Доказательства знания свидетельствуют об знании решения схемы. Доказательства, которые мы рассматриваем в этой статье, имеют аналогичную структуру:
- Рассмотрим арифметическую схему,
- Переведите схему в термины полиномов (см. следующий раздел «Арифметизация Планка»),
- Примите к полиномам использование схемы обязательств.
В следующих разделах мы рассматриваем арифметические схемы по простому модулю.р. Простым примером может служить знание квадратного корня, т.е. данныхй€Фр, знаниеИкстакой, чтоИкс2"="ймодр.
Арифметизация Планка
В этом разделе мы рассмотрим арифметизацию PLONK. Арифметические схемы по модулю рразлагаются на вентили видадла+дрб+дОс+дМаб+дС"="0, где $a$, и $b$с— это ценности, которые мы не хотим раскрывать. Описанную выше схему извлечения квадратного корня можно записать как0⋅Икс+0⋅Икс+(−1)⋅й+0⋅Икс⋅Икс+0"="0, означающий, чтоИкс2"="й. Другой пример (также относящийся к квадратам) — знание пифагоровой тройки, т.е.(Икс,й,я)удовлетворяющийИкс2+й2+я2. Чтобы преобразовать его в схему PLONK, мы разложим его как
Математическое утверждение | Соответствующие ворота PLONK |
---|---|
ИксиТ1удовлетворитьИкс2"="Т1 | 0⋅Икс+0⋅Икс+(−1)⋅Т1+0⋅Икс⋅Икс+0"="0 |
йиТ2удовлетворитьй2"="Т2 | 0⋅й+0⋅й+(−1)⋅Т2+0⋅й⋅й+0"="0 |
яиТ3удовлетворитья2"="Т3 | 0⋅я+0⋅я+(−1)⋅Т3+0⋅я⋅я+0"="0 |
Т1,Т2иТ3удовлетворитьТ1+Т2"="Т3 | 1⋅Т1+1⋅Т2+(−1)⋅Т3+0⋅Т1⋅Т2+0"="0 |
Эту схему можно переписать, используя следующую таблицу:
Ворота | дл | др | дО | дМ | дС | а | б | с |
---|---|---|---|---|---|---|---|---|
1 | 0 | 0 | −1 | 0 | 0 | Икс | Икс | Икс2 |
2 | 0 | 0 | −1 | 0 | 0 | й | й | й2 |
3 | 0 | 0 | −1 | 0 | 0 | я | я | я2 |
4 | 1 | 1 | −1 | 0 | 0 | Икс2 | й2 | я2 |
Схема также требует дополнительной информации: перваяс-ценность (скажемс1) соответствует последнемуа-ценность (котораяс2) и т. д. В этом примерес1"="а4,с2"="б4ис3"="с4. Эту информацию часто называют «ограничениями копирования». Обратите внимание, что одна из схем доказательства, которые мы рассматриваем ниже, определена с использованием "ultraPLONK" арифметизация, приводящая к оптимизации схем. Для простоты мы рассматриваем только случай схем PLONK.
Из этой схемы арифметизация PLONK создает полиномы, соответствующие схеме, а конструкции доказательства основаны на полиномиальных обязательствах. Мы определим их в следующем разделе.
Полиномиальные обязательства
Арифметизация PLONK приводит к нескольким полиномам, знание которых мы стремимся доказать. Здесь мы кратко напомним, что такое полиномиальная схема обязательств.
A схема фиксации — это криптографический примитив, позволяющий фиксировать к выбранному значению (или выбранному оператору), сохраняя его скрытым от других, с возможностью раскрыть зафиксированное значение позже. В данном контексте значение представляет собой полином ж(Икс)€Фр[Икс], а обязательство соответствует оценкеж(с)для данногос€Фр. Благодаря этому обязательству проверяющий может открыть его, чтобы проверяющий мог убедиться в знанииж, не зная его коэффициентов.
Теперь мы представляем две схемы полиномиальных обязательств, основанные на разных предположениях. В этой работе оно изучалось в более общем контексте, включая обобщение для рекурсивных доказательств. Мы вернемся к этим конструкциям в конце статьи.
Схема обязательств IPA
Первая схема полиномиального обязательства, которую мы представляем, разработана Zcash и в настоящее время называется Halo 2 от его дизайнеров. Основная идея – доказать знание многочлена ж(Икс)путем фиксации значенияж(с)для вызоваспредоставленный проверяющим. Используя криптографию эллиптических кривых, мы можем доказать знаниежбез раскрытия его коэффициентов. Схема основана на аргументе внутреннего продукта (IPA). Ниже мы суммируем различные этапы схемы обязательств:
- Настройка:
Мы рассматриваем эллиптическую кривую Эопределено болееФпс подгруппой (большого простого) порядкар. Мы также рассматриваемград(ж)+1точкиЭ(Фп)порядкар. Безопасность основана на задаче дискретного логарифма эллиптической кривой. На практике эта схема часто используется с использованием кривой Пасты. Одним из основных преимуществ конструкции Halo 2 является отсутствие надежной настройки. - Обязательство:
Обязательство — это точка Э(Фп)вычисляется с помощью скалярного умножения на коэффициенты многочленаж. Также необходим дополнительный случайный скаляр, чтобы стать нулевым разглашением. - Открытие:
Учитывая обязательство, он вычисляет скаляры Фри точкиЭ(Фп)в алгоритме сО(бревно(град(ж)))сложность. - Проверка:
После пересчета значений начального шага он проверяет уравнение на кривой. На этот раз открывающие элементы вычисляются с помощью алгоритма, сложность которого линейна в степени ж.
Для более точного описания этой схемы обязательств мы отсылаем читателя к коду Zcash Rust и нашему Код SageMath.
Чтобы достичь 128-битного уровня безопасности, необходимо выбрать эллиптическую кривую с подгруппой 256-битного простого порядка. Команда Zcash разработала эффективную конструкцию с помощью кривых пасты. С помощью этих кривых бревно2(п),бревно2(р)"="256.
Схема обязательств PB
Эта конструкция опирается на различные предположения безопасности при вычислении пар и была представлена в этой статье. Хотя нам нужна надежная задача дискретного логарифмирования кривой, схема вычисляет билинейное отображение, которое выводит элемент конечного поля Фпк для заданной степени встраиванияк. Безопасность также опирается на дискретный логарифм поФпк∗. Следовательно, для 128-битного уровня безопасности эта схема требует большего простого числа.пчем схема обязательств Halo 2. Для каждой кривой необходим специальный анализ безопасности, чтобы оценить, достигнута ли безопасность. Схема обязательств на основе пар (PB) делится следующим образом:
- Надежная установка:
Для этого мы рассмотрим эллиптическую кривую, удобную для спаривания Эопределено болееФп∗, что означает, что для большого простого числар, всер-точки кручения эффективно коммутативны. С этого момента мы обозначаемг1иг2, две ортогональные подгруппы порядкар.г1иг2обозначают образующие этих циклических групп. Для целого числан>0, третья сторона выбирает секретное целое числоси вычисляет([ся]г1)я"="0ниг2,[с]г2. Доверенную настройку можно вычислить один раз, и с ее помощью можно вычислить несколько доказательств. - Обязательство:
Обязательство соответствует оценке полинома по секретному целому числу с, а затем вычисление скалярного умножения. Используя надежную настройку, обязательство можно выполнить, даже не знаяс. - Открытие:
Несколько дополнительных вычислений соответствуют дополнительным необходимым элементам для проверки. Он вычисляет модульную целочисленную арифметику, а также полиномиальную арифметику. - Доказательство:
Используя билинейность спаривания, проверяющий может проверить уравнение над конечным полем Фпк. Эти вычисления требуют арифметики над кривой (точнее, надг1).
Если вы хотите узнать больше о схеме доказательства PB, обратитесь к Rust-коду этого дизайнера или /span> для дальнейших исследований.код SageMath, объясняющий, как вычислить доказательство «вручную». Мы также предоставляем наш пост
На пути к рекурсивным конструкциям доказательства
Наивным решением проверки всех блоков блокчейна было бы проверять каждый блок отдельно. Как упоминалось ранее, этот подход становится все более дорогим, поскольку блокчейн продолжает расти. Чтобы добиться эффективной проверки, некоторые конструкции позволяют вставить одно доказательство в другое. Это то, что мы называем рекурсивными доказательствами.
Доказательство доказательства
Предположим, что у нас есть две цепиС1иС2мы стремимся предоставить доказательства знания решений (Икс1иИкс2). Другими словами,С1(Икс1)иС2(Икс2)верны. Идея «доказательства доказательства» как следует:
- Вычислить доказательство�1знанийИкс1для схемыС1;
- Создать схемуС1'соответствующий проверке�1;
- Вычислить доказательство�2знаний�1дляС1', вместе сИкс2соответствующийС2.
Таким образом, если проверка�2получится, это значит, чтоС2(Икс2)верно, и что существует�1 проверка первой цепи. Другими словами, мы получаем доказательство обоихИкс1иИкс2используя только одно доказательство.
Основным недостатком этой конструкции является то, что схема, соответствующая проверке, зачастую очень сложна. Например, в схеме доказательства на основе пар проверка включает в себя вычисление пар, и они соответствуют большим схемам.
В общем, мы предпочитаем вычислять доказательства с помощью аккумулятора.
Накопитель доказательств
В этой теме были введены аккумуляторы с целью «накопления»; доказательства. Хотя конструкция Halo 2 обеспечивает такое накопление, идеи были формализованы в этой документе в более широком контексте. Аккумулятор удовлетворяет нескольким свойствам:
- Данныйaccи�, мы можем проверить накопление, т.е. что новый аккумуляторacc'действительно накапливаетсяпявacc.
- Учитывая аккумуляторacc, мы можем проверить все накопленные доказательства, используя один алгоритм проверки.
Используя эту конструкцию, можно вычислить доказательства накопления, ведущие к рекурсивному доказательству. Основное преимущество накопительной конструкции (по сравнению с «доказательством доказательства») состоит в том, что проверка накопления намного проще, чем проверка доказательства.
Две представленные нами схемы адаптируемы, и в обоих случаях мы можем получить аккумулятор:
- В схеме IPA доказательства соответствуют полиномиальным обязательствам, и мы можем накапливать их, вычисляя линейные комбинации как обязательств, так и полиномов. .
- В схеме PB аккумулятор также получается из линейных комбинаций доказательств благодаря билинейности спаривания.
В обоих случаях проверка накоплением соответствует более простой схеме, чем в случае «доказательства доказательства». На практике принято использовать аккумуляторную конструкцию, которой мы уделим внимание в оставшейся части статьи. Возвращаясь кФрсхемыС1иС2, конструкция на основе аккумулятора будет:
- Вычислить доказательство�1знанийИкс1для схемыС1. Доказательство�1соответствует элементам, определенным целыми числами по модулюп, а именноФпэлементы и точки кривой, определенные надФп.
- Накопите это доказательство�1в аккумуляторе (элементыФп).
- Создать схемуС1'что соответствует проверке накопления�1. Проверка накопления часто проще, чем в случае «доказательства доказательства». случай, но соответствует арифметическому модулюпсхема.
- Вычислить доказательство�1'знаний�1дляС1'. Эта схема представляет собойФп-схема, поэтому нам нужно использовать эллиптическую кривую с другой структурой для создания доказательства этой схемы. Точнее, нам нужна эллиптическая кривая с подгруппой порядкапдля того, чтобы соответствовать схеме. В следующих разделах мы рассмотрим, насколько сложно получить такие кривые.
- Накапливать�1'в аккумулятор (определенный во втором базовом поле кривой). Если это новое базовое поле кривойФр, мы можем предоставить доказательствоС2рекурсивно, используя первую кривую.
Как мы видели, выбор кривых очень важен для получения рекурсивного доказательства. Нам нужно иметь возможность проводить доказательства на двух разных кривых.Э1,Э2тесно связаны друг с другом:

В следующем разделе мы подробно рассмотрим требования кЭ1иЭ2для получения рекурсивных доказательств в контексте рекурсивных доказательств IPA и PB.
Циклы кривых
Из двух аккумуляторных конструкций мы получаем рекурсивные доказательства, используя конструкцию со схемами по модулюрип. Это означает, что нам нужны две эллиптические кривые:
- Э1определено болееФп, ирделит порядокЭ1(Фп),
- Э2определено болееФр, ипделит порядокЭ2(Фр).
Это определение легко распространяется на цикл, состоящий из более чем двух кривых, но формальное определение нам не требуется. В зависимости от схемы доказательства кривые, которые мы будем использовать, нуждаются в других свойствах. В большинстве схем, используемых на практике, большая мощность2разделяющийп−1ир−1требуется, чтобы арифметика над конечными полями была эффективной с использованием БПФ.
Вслед за этим рассмотрим три типа циклов кривых:
- Цикл без сопряжения:
Обе кривые не подходят для спаривания, и чтобы получить 128 бит безопасности, необходимо использовать бревно2(п),бревно2(р)≥256<а я=0>. В схеме Halo 2 используются кривые Pasta, цикл без спаривания. Получить такие кривые не так уж и сложно, даже со свойствами эффективности и безопасности. - Полупериод:
Возможно несколько конструкций. Например, эта конструкция обеспечивает цикл с кривой Баррето-Наерига (которая удобна для спаривания) и непарной кривой для (консервативного) 128-битный уровень безопасности (бревно2(п)≥384). Цикл полуспаривания может привести к однослойным рекурсивным доказательствам, а это означает, что мы можем проверить пакет доказательств за один раз. Неясно, как мы могли бы получить эффективное полностью рекурсивное доказательство, используя цикл полуспаривания, в частности, используя сочетание доказательств IPA и PB. - Цикл сопряжения:
Обе кривые удобны для спаривания, а размеры пиддолжен быть больше, чтобы достичь 128-битного уровня безопасности. Это зависит от степени встраивания и структуры простых чисел и требует дальнейшего изучения криптоанализа. В настоящее время основная конструкция использует кривые МНТ-4 и МНТ-6 и требует простых чисел.пирне менее 768 бит.
Рекурсивные доказательства на практике
Теперь мы исследуем рекурсивные доказательства с практической точки зрения с целью сравнения различных конструкций, основанных на доказательствах IPA и PB.
Рекурсивное доказательство IPA
Описанную выше схему доказательства Halo 2 можно адаптировать для получения аккумулятора и, как следствие, рекурсивного доказательства.
- Выбор кривых:
Команда Zcash использует цикл кривых под названием Pallas и Vesta. Две кривые определяются с помощью арифметических операций по модулю 256-битных простых чисел, что на практике обеспечивает высокую эффективность и безопасность. - Размер и стоимость:
Оценка объема доказательств и стоимости проверки зависит от рассматриваемой схемы. Асимптотически Halo 2 достигает определенной логарифмической сложности, но не является полностью лаконичной схемой доказательства (где стоимость проверки не зависит от размера схемы). Для неоптимизированной схемы с 1024 элементами максимальной степени 1 доказательство занимает менее 768 байт, а время проверки составляет менее 78,25 мс. Для конкретной схемы множество оптимизаций могут привести к улучшениям с обеих сторон. - Другие свойства:
Эта схема не основана на предположениях, основанных на спаривании, и не требует надежной настройки.
Рекурсивное доказательство PB
Аккумулятор также можно получить по схеме спаривания, рассмотренной ранее в этой статье.
- Выбор кривых:
Циклы спаривания кривых генерировать сложнее. Чтобы практически получить рекурсивное доказательство, необходимо использовать две кривые МНТ. Точнее, мы ограничены кривыми, определенными по модулю больших простых чисел, чем в случае IPA. Аврора Гиллевич рекомендует здесь 992-битные простые числа для консервативной безопасности, а арифметика над этими кривыми не очень эффективна из-за больших модулей. На данный момент кривые, полученные здесь, не соответствуют эффективному умножению полинома Лагранжа, но кривые с такими свойствами можно найти, проведя немного больше исследований. - Размер и стоимость:
Рекурсивные доказательства на основе спаривания являются краткими в том смысле, что стоимость проверки постоянна и не зависит от размера схемы. Практически проверка стоит примерно 20мс, а доказательства соответствуют 16бревно2(п)биты. Для 128-битного уровня безопасности доказательства хранятся в 1984 байтах с использованием кривых MNT. - Другие свойства:
Одним из недостатков этой конструкции является необходимость доверенной настройки, но конструкция обеспечивает полностью краткую проверку. В зависимости от размера схемы эта конструкция может быть предпочтительнее конструкции Halo 2.
Смешивание рекурсивного доказательства IPA×PB
Другая альтернатива — сочетание доказательств IPA и PB.
- Выбор кривых:
Использование сочетания доказательств IPA и PB позволяет нам найти цикл полуспаривания с более эффективными кривыми. А именно, можно достичь 128-битной безопасности с помощью кривых, определенных для 446-битных простых чисел (одна из них удобна для спаривания, другая нет), используя эту работу. Кривая, удобная для спаривания, представляет собой кривую Баррето-Наэрига (BN), и ее структура очень похожа на кривые BLS12. - Размер и стоимость:
Используя этот цикл полуспаривания, мы можем построить краткие рекурсивные доказательства, выбрав Э1быть кривой BN:

- ПараметрЭ1"="ЭБН, схемыСяпривести к кратким доказательствам�яи аккумулятор, определенный надФп.
- СхемыСя'соответствуют проверке накопления в случае схемы ПБ. Они определяются по модулюпи имеют одинаковый фиксированный размер, что обусловлено краткостью�я.
- ДоказательстваСя'получены с использованием схемы доказательства IPA. По размеру цепейСяфиксировано, мы также получаем ограниченный размер доказательства.
- Наконец, проверка всего рекурсивного доказательства соответствует одной проверке PB и одной проверке IPA со схемами фиксированного размера.
- Другие свойства:
Необходимо дальнейшее исследование, чтобы узнать, являются ли схемы Ся'привести к эффективной проверке кривой IPA. Эта конструкция опирается на доказательство PB и, следовательно, требует надежной настройки. Основным преимуществом по сравнению с другими конструкциями является лаконичность в сочетании с практической эффективностью (подлежит подтверждению). Эта конструкция позволяет эффективно выполнять скалярные умножения методом GLV (кривые имеютдж-инвариант0). Конструкция с использованием кривой BN защищена от атак подгрупп, но проверка безопасности скручивания обходится дороже:ЭБНт"="33⋅409⋅4181358137757019⋅п380иЭ2т"="32⋅13⋅73⋅1634952357132739⋅1881161189879663262061651⋅п301(гдепℓобозначает простое числоℓбиты иЭтквадратичный поворотЭ).
Заключение
В этой статье мы представили три конструкции рекурсивных доказательств, основанных на разных предположениях безопасности, с разными компромиссами между размерами доказательств и стоимостью проверки. В следующей таблице мы суммировали размер и сложности, а для реальных сравнений потребуются конкретные реализации.
Рекурсивное доказательство, основанное на | МПА | ПБ | МПА×ПБ |
---|---|---|---|
Предположение безопасности | ECDLP | ECDLP и сопряжение | ECDLP и сопряжение |
Доверенная установка | нет | да | да |
Простой размер | 256-битный | 992-битный | 446-битный |
Размер (пруф + аккумулятор) | линейный в схеме | ≈4464байты | нужно больше работы |
Стоимость поверки (в размере схемы) | логарифмический | постоянный | постоянный* |
∗ константа размера схемы, но ограничена размером схемы проверки накопления (может быть большой).
Используя наш код SageMath, мы можем сравнивать время всех этих схем, но не самым точным способом, как SageMath недостаточно эффективен. Тем не менее, мы можем сравнить стоимость доказательства по 446-битным кривым и с использованием кривых MNT вместе с текущим доказательством PB, основанным на кривых BLS12-381. Следующие сравнения основаны на нашем коде SageMath и, следовательно, неточны.
- Проверка доказательства на кривой BN-446 происходит медленнее, чем на (нециклируемой) кривой BLS12-381, с коэффициентом 1,72.
- По кривой MNT4-768 стоимость проверки в 1,80 раза превышает стоимость кривой BLS12-381.
- Проверка доказательства по кривой MNT6-768 стоит в 2,10 раза больше, чем проверка по кривой BLS12-381.
- Проверка доказательства на кривой MNT6-992 в данный момент невозможна, так как ни одна кривая (сп−1кратное232) уже создан.
Хотя это кажется более дорогим, рекурсивное доказательство PB кажется практически возможным. Однако другие вычисления могут быть более дорогостоящими: когда алгоритмы включают арифметику по модулю pp, вычисления становятся более дорогими, покапстановится больше. Скалярные умножения, а также полиномиальные оценки будут иметь значительные затраты при использовании более крупных кривых MNT.
Наконец, эти оценки требуют дальнейших исследований для подтверждения наших оценок. В частности, была бы полезна реализация с использованием Rust.
Написано Саймоном Массоном, исследователем криптографии с нулевым разглашением и amp; разработчик протокола в Heliax, команде Anoma.
Если вы заинтересованы в криптографии с нулевым разглашением, передовых криптографических протоколах или инженерных позициях в Rust, ознакомьтесь открытыми вакансиями в Heliax .