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

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 включает в себя пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных бинарных полях (towers of binary fields) арифметика сформировала основу его вычислений, позволяя выполнять упрощенные операции в бинарном поле. Во-вторых, 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 + Y 2.

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

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