Анализ принципов 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 размер используемого поля должен быть больше степени многочлена; при обязательстве дерева Меркла в 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.

Термин "canonical" относится к уникальному и прямому представлению элементов в двоичном поле. Например, в самом простом двоичном поле F2 любые строки длиной k могут быть напрямую сопоставлены с элементами двоичного поля длиной k. Это отличается от полей с простыми числами, которые не могут предоставить такое стандартное представление в заданной длине. Хотя поле с простым числом длины 32 может содержать элементы в пределах 32 бит, не каждая 32-битная строка может уникально соответствовать элементу поля, тогда как двоичное поле предоставляет удобство такого взаимного сопоставления. В поле с простыми числами Fp распространенные методы редукции включают редукцию Barrett, редукцию Montgomery, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k обычно используются методы редукции, такие как специальные редукции (например, используемые в AES), редукция Montgomery (например, используемая в POLYVAL) и рекурсивная редукция (например, Tower). В статье "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" указывается, что в двоичном поле не требуется вводить перенос при операциях сложения и умножения, а возведение в квадрат в двоичном поле очень эффективно, поскольку оно подчиняется упрощенному правилу (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-битные подполя).

! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs

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

• Упаковка: