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

1 Введение

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

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

Таблица 1: Пути разветвления STARKs

| Алгебра | Ширина кодирования | Представляемая система | |------|----------|----------| | 1-е поколение | 252 бит | StarkWare | | Второе поколение | 64bit | Plonky2 | | 3-е поколение | 32bit | BabyBear | | 4-е поколение | Бинарная область | Binius |

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

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

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

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

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

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

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

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

![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 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,虚