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

1. Введение

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

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

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κ и объединяет их в более крупные.