Анализ принципов Binius STARKs и размышления об их оптимизации

1 Введение

Одной из основных причин низкой эффективности STARK является то, что большинство чисел в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т.д. Однако для обеспечения безопасности доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если само исходное значение очень мало. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.

Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, ширина кодирования STARKs второго поколения составляет 64 бита, ширина кодирования STARKs третьего поколения составляет 32 бита, но кодирование шириной 32 бита все еще имеет много неиспользуемого пространства. В сравнении, двоичные поля позволяют выполнять операции непосредственно над битами, кодирование компактно и эффективно без произвольных пустот, то есть STARKs четвертого поколения.

Таблица 1: Пути производных STARKs

| Алгебра | Ширина слова | Область | |------|------|------| | 1-е поколение | 252 бит | Пространство простых чисел | | Второе поколение | 64bit | Goldilocks | | 3-е поколение | 32bit | Поле простых чисел | | 4-е поколение | 1 бит | двоичное поле |

По сравнению с Goldilocks, BabyBear, Mersenne31 и другими новыми исследованиями ограниченных полей, исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко применяются в криптографии,典型例子包括:

• Стандарт AES (, основанный на поле F28;

• Galois сообщение аутентификации ) GMAC (, основанный на поле F2128;

• QR-код, использующий кодирование Рида-Соломона на основе F28;

• Исходный протокол FRI и zk-STARK, а также хеш-функция Grøstl, вышедшая в финал SHA-3, основанная на поле F28, является очень подходящим хеш-алгоритмом для рекурсии.

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

При построении системы доказательств на основе бинарного поля возникают 2 практические проблемы: при вычислении трассы в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве Меркле-дерева в STARKs необходимо выполнить кодирование Рида-Соломона, при этом размер используемого поля должен быть больше размера после расширения кодирования.

Binius предложил инновационное решение, которое отдельно решает эти две проблемы и реализует представление одних и тех же данных двумя различными способами: во-первых, используя многомерный ), а именно многолинейный ( многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" ); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае STARKs, не может быть выполнено, но гиперкуб можно рассматривать как квадрат (, основанный на котором можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.

2 Анализ принципа

Текущая конструкция большинства систем SNARK обычно включает в себя следующие две части:

• Информационно-теоретическое полиномиальное интерактивное оракульное доказательство )Information-Theoretic Polynomial Interactive Oracle Proof, PIOP(: PIOP, как основа системы доказательства, преобразует входные вычислительные отношения в проверяемые полиномиальные равенства. Разные протоколы PIOP позволяют доказчику поэтапно отправлять полиномы через взаимодействие с проверяющим, что позволяет проверяющему проверить правильность вычислений, запрашивая лишь небольшое количество результатов оценки полиномов. Существующие протоколы PIOP включают: PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, которые по-разному обрабатывают полиномиальные выражения, что влияет на производительность и эффективность всей системы SNARK.

• Полиномиальная схема обязательств )Polynomial Commitment Scheme, PCS(: Полиномиальная схема обязательств используется для доказательства того, является ли полиномиальное равенство, сгенерированное PIOP, истинным. PCS является криптографическим инструментом, с помощью которого доказатель может заверить определенный многочлен и позднее проверить результаты его оценки, при этом скрывая другую информацию о многочлене. Распространенные схемы полиномиальных обязательств включают KZG, Bulletproofs, FRI)Fast Reed-Solomon IOPP( и Brakedown и т.д. Разные PCS имеют разные характеристики, безопасность и области применения.

В зависимости от конкретных требований выбирайте разные PIOP и PCS и сочетайте их с подходящими конечными полями или эллиптическими кривыми, чтобы создать системы доказательства с различными атрибутами. Например:

• Halo2: сочетание PLONK PIOP и Bulletproofs PCS, основанное на кривой Pasta. При проектировании Halo2 акцент был сделан на масштабируемости и удалении доверенной настройки из протокола ZCash.

• Plonky2: использует сочетание PLONK PIOP и FRI PCS, основанное на поле Goldilocks. Plonky2 создан для достижения эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать используемому конечному полю или эллиптической кривой, чтобы обеспечить правильность, производительность и безопасность системы. Выбор этих комбинаций влияет не только на размер доказательства SNARK и эффективность проверки, но и определяет, сможет ли система реализовать прозрачность без необходимости в доверенной настройке, а также поддерживать расширенные функции, такие как рекурсивные доказательства или агрегированные доказательства.

Binius: HyperPlonk PIOP + Brakedown PCS + двоичное поле. Конкретно, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенном двоичном поле )towers of binary fields( арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в двоичном поле. Во-вторых, в своем интерактивном Oracle доказательном протоколе )PIOP( Binius адаптировал проверку произведений и перестановок HyperPlonk, обеспечивая безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое доказательство многолинейного сдвига, оптимизируя эффективность проверки многолинейных отношений на малых полях. В-четвертых, Binius использует усовершенствованную Lasso проверку поиска, обеспечивая механизму поиска гибкость и мощную безопасность. Наконец, протокол использует схему обязательств по многочленам малого поля )Small-Field PCS(, что позволяет ему реализовать эффективную систему доказательства в двоичном поле и уменьшить затраты, обычно связанные с большими полями.

) 2.1 Ограниченные поля: арифметика на основе башен двоичных полей

Башенная бинарная область является ключом к реализации быстрого проверяемого вычисления, что в основном связано с двумя аспектами: эффективными вычислениями и эффективной арифметизацией. Бинарная область по сути поддерживает высокоэффективные арифметические операции, что делает ее идеальным выбором для криптографических приложений, чувствительных к производительности. Кроме того, структура бинарной области поддерживает упрощенный процесс арифметизации, то есть операции, выполняемые в бинарной области, могут быть представлены в компактной и легко проверяемой алгебраической форме. Эти характеристики, вместе с возможностью полностью использовать ее иерархические характеристики через башенную структуру, делают бинарную область особенно подходящей для таких масштабируемых систем доказательств, как Binius.

Термин "канонический" относится к уникальному и прямому представлению элементов в бинарном поле. Например, в самом простом бинарном поле F2 любая строка длиной k может быть напрямую сопоставлена с элементом бинарного поля длиной k. Это отличается от простого поля, которое не может предоставить такое стандартное представление в заданной длине. Хотя 32-битное простое поле может быть включено в 32 бита, не каждая 32-битная строка может уникально соответствовать элементу поля, тогда как бинарное поле обладает удобством такого взаимно однозначного отображения. В простом поле Fp распространенные методы сокращения включают сокращение Барретта, сокращение Монтгомери, а также специальные методы сокращения для конкретных конечных полей, таких как Mersenne-31 или Goldilocks-64. В бинарном поле F2k часто используемые методы сокращения включают специальные сокращения (, такие как использование в AES ), сокращение Монтгомери ###, используемое в POLYVAL (, и рекурсивное сокращение ), такое как Tower (. Статья "Исследование пространства проектирования ECC-аппаратных реализаций простого поля против бинарного поля" указывает, что в бинарном поле при операциях сложения и умножения не требуется вводить перенос, и возведение в квадрат в бинарном поле очень эффективно, так как оно следует упрощенному правилу )X + Y (2 = X2 + Y 2.

Как показано на рисунке 1, строка длиной 128 бит: эту строку можно интерпретировать различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть интерпретирована как два элемента 64-битного башенного поля, четыре элемента 32-битного башенного поля, 16 элементов 8-битного башенного поля или 128 элементов поля F2. Эта гибкость представления не требует дополнительных вычислительных затрат, это просто преобразование типа строки битов )typecast(, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, статья «On Efficient Inversion in Tower Fields of Characteristic Two» рассматривает вычислительную сложность операций умножения, возведения в квадрат и инверсии для ), разлагаемого на m-битные подполя ( в n-битном башенном двоичном поле.

! [Двоичный домен башни])https://img-cdn.gateio.im/webp-social/moments-a5d031be4711f29ef910057f4e44a118.webp(

Рисунок 1: Башенная двоичная область

) 2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck------применимо к двоичным полям

Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных проверочных механизмов для верификации корректности многочленов и множеств с несколькими переменными. Эти основные проверки включают:

1. GateCheck: проверка, удовлетворяют ли конфиденциальные свидетельства ω и открытый ввод x вычислительным отношениям C(x,ω)=0, чтобы гарантировать правильную работу цепи.

2. PermutationCheck: Проверка, являются ли результаты вычислений двух многомерных многочленов f и g на булевом гиперкубе перестановочным отношением f###x( = f)π(x)(, чтобы обеспечить согласованность перестановок между переменными многочлена.

3. LookupCheck: проверка того, находится ли значение многочлена в заданной таблице поиска, то есть f(Bµ) ⊆ T)Bµ(, чтобы гарантировать, что некоторые значения находятся в указанном диапазоне.

4. MultisetCheck: Проверяет, равны ли два многомерных множества, то есть {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, чтобы обеспечить согласованность между несколькими множествами.

5. ProductCheck: Проверка того, равно ли значение многочлена с рациональными коэффициентами на булевом гиперкубе заявленному значению ∏x∈Hµ f)x( = s, чтобы гарантировать корректность произведения многочлена.

6. ZeroCheck: проверить, является ли любая точка многочлена с несколькими переменными на булевом гиперкубе нулем ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, чтобы обеспечить распределение нулей многочлена.

7. SumCheck: Проверка того, совпадает ли сумма значений многочлена с несколькими переменными с заявленным значением ∑x∈Hµ f)x( = s. Это достигается путем преобразования задачи оценки многочлена с несколькими переменными в задачу оценки многочлена с одной переменной, что снижает вычислительную сложность для проверяющей стороны. Кроме того, SumCheck также позволяет пакетную обработку, вводя случайные числа для построения линейной комбинации, что позволяет обрабатывать несколько экземпляров проверки суммы.

8. BatchCheck: основанный на SumCheck, проверяет правильность вычисления нескольких многомерных многочленов для повышения эффективности протокола.

Несмотря на то, что у Binius и HyperPlonk есть много схожего в дизайне протокола, Binius улучшил следующие 3 аспекта:

• Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым в гиперкубе, и произведение должно равняться определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, тем самым снижая вычислительную сложность.

• Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждения о том, что U ненулевое в гиперкубе; Binius правильно справился с этой проблемой, даже когда знаменатель равен нулю, ProductCheck Binius продолжает обрабатывать, что позволяет обобщение на любое произведение.

• Перестановочная проверка по столбцам: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановок многочленов.

Таким образом, Binius улучшил механизм PIOPSumCheck, что повысило гибкость и эффективность протокола, особенно при обработке более сложных верификаций многомерных многочленов, предоставив более мощную функциональную поддержку. Эти улучшения не только решили ограничения HyperPlonk, но и заложили основу для будущих систем доказательства на основе бинарных полей.

) 2.3 PIOP: новый аргумент многообразного сдвига------подходит для булева гиперкуба

В протоколе Binius конструкция и обработка виртуальных многочленов являются ключевыми.