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

1. Введение

Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, но для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.

Ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 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, стандартное расширение Рида-Соломона как в 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 + Binary Domain. В частности, Binius включает в себя пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, арифметика, основанная на башне двоичной области (towers двоичной fields) составляет основу ее вычислений, которые могут реализовывать упрощенные операции в двоичной области. Во-вторых, в своем интерактивном протоколе Oracle proof (PIOP) Binius адаптирует продукт 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 + Y2.

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

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

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

! Исследование битlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление

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

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

• Упаковка: этот метод включает упаковку меньших элементов, находящихся рядом в лексикографическом порядке, в более крупные.