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