Анализ принципа 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 предложил инновационное решение, которое обрабатывает эти две проблемы по отдельности и реализует представление одних и тех же данных двумя различными способами: во-первых, используя многомерный ) конкретно многолинейный ( многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" )hyper cubes (; во-вторых, поскольку длина каждого измерения гиперкуба равна 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 обычно используемые методы редукции включают редукцию Barrett, редукцию Montgomery, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k общие методы редукции включают специальную редукцию ###, используемую в AES (, редукцию Montgomery ), используемую в POLYVAL (, и рекурсивную редукцию ), такую как Tower (. В статье "Исследование пространства проектирования аппаратных реализаций ECC на полях простых чисел и двоичных полях" отмечается, что в двоичном поле сложение и умножение не требуют переноса, и операция возведения в квадрат в двоичном поле очень эффективна, так как она следует упрощенному правилу )X + Y (2 = X2 + Y 2.

Как показано на рисунке 1, 128-битная строка: эта строка может быть интерпретирована несколькими способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле, или быть разобрана на два элемента 64-битного поля, четыре элемента 32-битного поля, 16 элементов 8-битного поля или 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 внес улучшения в следующих трех аспектах:

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

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

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

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

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

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

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