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

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 размер используемого поля должен быть больше степени многочлена; при выполнении обязательств Merkle tree в STARKs необходимо использовать кодирование Рида-Соломона, размер используемого поля должен быть больше размера после расширения кодирования.

Binius предложил инновационное решение, которое отдельно обрабатывает эти две проблемы и реализует одно и то же представление данных двумя разными способами: во-первых, используя многомерные (в частности, многолинейные) полиномы вместо одномерных полиномов, представляя всю вычислительную траекторию через их значения на "гиперкубах"; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в STARKs, невозможно, но гиперкуб можно рассматривать как квадрат, и основанное на этом квадрате расширение Рида-Соломона возможно. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.

2. Анализ принципов

Текущая конструкция большинства систем SNARK обычно включает в себя следующие две части:

• Информационно-теоретическое полиномиальное интерактивное оракул-принятие (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 + Y 2.

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

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

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

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

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

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

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

• Упаковка：