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

1 Введение

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

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

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 адаптировал проверку переменных и их перестановок в своем интерактивном протоколе 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 элементов поля высоты 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 внес улучшения в следующих трех аспектах:

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

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

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

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

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

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

• Упаковка: этот метод основан на том, что меньшие элементы на соседних позициях в лексикографическом порядке