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

1 Введение

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

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

В отличие от Goldilocks, BabyBear, Mersenne31 и других ограниченных полей, обнаруженных в последние годы, исследование бинарных полей восходит к 80-м годам прошлого века. В настоящее время бинарные поля широко используются в криптографии, типичные примеры включают:

• Стандарт высокоскоростного шифрования (AES), основанный на поле F28;

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

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

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

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

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

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

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

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

• Информационно-теоретическое полиномиальное интерактивное оракульное доказательство ( 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) арифметика составляет основу его расчетов, позволяя выполнять упрощенные операции в двоичных полях. Во-вторых, Binius в своем интерактивном Oracle доказательном протоколе (PIOP) адаптировал 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 + Y2.

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

( 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 снижает вычислительную сложность для проверяющей стороны. Кроме того, SumCheck также позволяет пакетную обработку, вводя случайные числа для построения линейных комбинаций и реализации пакетной проверки нескольких экземпляров суммы.

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

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

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

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

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

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

! Исследование битlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление

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

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

• Упаковка: этот метод через