Анализ принципов 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 все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.

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

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

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

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

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

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

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

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

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

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