Анализ принципов 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 размер используемого поля должен быть больше степени полинома; при обещании дерева Меркла в 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 восьмибитных элементов башенного поля или 128 элементов F2. Эта гибкость представления не требует никаких вычислительных затрат, это всего лишь преобразование типа (typecast) битовой строки, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье «Об эффективном обращении в башенных полях характерного два» рассматривается вычислительная сложность операций умножения, возведения в квадрат и обращения в 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, но и закладывают основу для будущих систем доказательства на основе бинарных полей.

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

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

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

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