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

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

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

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