Анализ принципов 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 необходимо выполнять кодирование Рида-Соломона, размер поля должен быть больше размера после кодирования.

Биниус предлагает инновационное решение, которое рассматривает эти две проблемы по отдельности и делает это путем представления одних и тех же данных двумя различными способами: во-первых, используя многомерные (в частности, многолинейные) полиномы вместо одномерных многочленов, и представляя всю вычислительную траекторию по ее значению на «гиперкубах»; Во-вторых, поскольку длина каждого измерения гиперкуба равна 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 + 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 улучшил следующие 3 аспекта:

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

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

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

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

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

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

• Упаковка: Этот метод работает путем объединения меньших элементов, находящихся на соседних позициях в словарном порядке.