Анализ принципов 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 включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных двоичных полях (towers of binary fields) арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в двоичных полях. Во-вторых, Binius в своем интерактивном Oracle доказательном протоколе (PIOP) адаптировал проверки произведения и перестановки HyperPlonk, обеспечивая безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое многочленное смещение доказательства, оптимизируя эффективность проверки многочленных отношений на малых полях. В-четвертых, Binius использует улучшенную Lasso проверку поиска, обеспечивая гибкость и мощную безопасность для механизма поиска. Наконец, протокол использует схему обязательств многочленов на малых полях (Small-Field PCS), позволяя ему реализовать эффективную систему доказательств в двоичных полях и снижая затраты, обычно связанные с большими полями.

2.1有限域: на основе арифметики башен двоичных полей

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

где «канонический» относится к уникальному и прямому представлению элемента в двоичной области. Например, в самой простой двоичной области F2 любая k-битная строка может быть отображена непосредственно на k-битный элемент двоичной области. В отличие от поля простых чисел, которое не может обеспечить такое каноническое представление в данной позиции. Хотя 32-разрядное поле простых чисел может содержаться в 32-разрядной системе, не каждая 32-разрядная строка однозначно соответствует элементу предметной области, и двоичные поля имеют удобство такого взаимно-однозначного отображения. В простой области Fp общие методы редукции включают редукцию Барретта, редукцию Монтгомери и специальные методы редукции для конкретных конечных полей, таких как Мерсенна-31 или Златовласка-64. В бинарной области F2k обычно используемые методы редукции включают специальные ( редукции, такие как использование ) в AES, Редукционные ( Монтгомери, такие как 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-битные подполя ).

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 продолжает обрабатывать, что позволяет обобщать на любое произведение.

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

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

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

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

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