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

1 Введение

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

Первые STARKs имеют ширину кодирования 252 бита, вторые STARKs имеют ширину кодирования 64 бита, третьи STARKs имеют ширину кодирования 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 предложил инновационное решение, которое обрабатывает эти две проблемы отдельно и реализует представление одних и тех же данных двумя различными способами: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" ( hypercubes ); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ( square ) и на основе этого квадрата выполнять расширение Рида-Соломона. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.

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 адаптировала HyperPlonk умножение и проверку перестановок в своем интерактивном протоколе доказательства Oracle (PIOP), обеспечивая безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое многочленное смещение доказательства, оптимизируя эффективность проверки многочленных отношений на малых полях. В-четвертых, 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-битные подполя ).

! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs

( 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µ), ensuring that certain values are within the specified range.

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

• Упаковка: этот метод оптимизирует операции, объединяя меньшие элементы, расположенные рядом в лексикографическом порядке, в более крупные элементы. Оператор Pack работает с блоками размером 2κ и комбинирует их в многомерное пространство.