Анализ принципа Binius STARKs и его оптимизационное мышление

1 Введение

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

Как показано в таблице 1, STARK первого поколения имеют 252 бита, STARK второго поколения — 64 бита, а STARK третьего поколения — 32 бита. В отличие от этого, двоичная область позволяет выполнять операции прямого выравнивания по битам и компактна и эффективна в кодировании без потери места, т.е. STARK 4-го поколения.

Таблица 1: Пути эволюции STARKs

| Функция | СТАРКИ 1-го поколения | СТАРКИ 2-го поколения | СТАРКИ 3-го поколения | 4-е поколение STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Ширина кодирования | 252бит | 64бит | 32бит | 1бит | | Представительные системы | StarkWare | Plonky2 | BabyBear | Binius |

По сравнению с конечными доменами, открытыми в последние годы, такими как Златовласка, BabyBear и Mersenne31, изучение бинарных доменов можно проследить до 80-х годов прошлого века. В настоящее время двоичные домены широко используются в криптографии, типичными примерами являются:

• Advanced Encryption Standard (AES), основанный на доменах F28;

• Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;

• QR-код, использующий кодировку Reed-Solomon на основе F28;

• Оригинальные протоколы FRI и zk-STARK, а также хеш-функция Grøstl, которая попала в финал SHA-3, основана на домене F28 и является хорошо подходящим алгоритмом хеширования для рекурсии.

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

При построении системы доказательств на основе двоичных областей возникают две практические проблемы: при вычислении представления следов в STARK используемый размер области должен быть больше порядка полинома; Когда дерево Меркла обещано в STARKs, оно должно быть закодировано в методе Рида-Соломона, и размер используемого домена должен быть больше, чем размер расширения кодировки.

Биниус предлагает инновационное решение, которое рассматривает эти две проблемы по отдельности и делает это путем представления одних и тех же данных двумя различными способами: во-первых, используя многомерные (в частности, многолинейные) полиномы вместо одномерных многочленов, и представляя всю вычислительную траекторию по ее значению на «гиперкубах»; Во-вторых, поскольку длина каждого измерения гиперкуба равна 2, невозможно сделать стандартное расширение Рида-Соломона, как STARKs, но гиперкуб можно рассматривать как квадрат на основе расширения Рида-Соломона. Этот метод значительно повышает эффективность кодирования и производительность вычислений, обеспечивая при этом безопасность.

2 Анализ принципов

Построение большинства современных систем SNARKs обычно состоит из следующих двух частей:

• Информационно-теоретико-полиномиальное интерактивное доказательство оракула (PIOP) :P IOP в качестве ядра системы доказательства, преобразуя вычислительные отношения входных данных в проверяемые полиномиальные уравнения. Различные протоколы PIOP позволяют проверяющему отправлять полиномы шаг за шагом, взаимодействуя с валидатором, что позволяет валидатору проверять правильность вычислений, запрашивая результаты оценки небольшого числа полиномов. Существующие протоколы PIOP включают PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, все они по-разному обрабатывают полиномиальные выражения, что влияет на производительность и эффективность всей системы SNARK.

• Схема полиномиального обязательства (PCS): Схема полиномиального обязательства используется для доказательства того, является ли истинным полиномиальное уравнение, сгенерированное с помощью PIOP. PCS — это криптографический инструмент, с помощью которого доказывающий может зафиксировать определенный полином и позже проверить результаты оценки этого полинома, скрывая при этом другую информацию о полиноме. К распространенным схемам полиномиальных обязательств относятся KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) и Brakedown. Разные PCS имеют разные сценарии производительности, безопасности и приложений.

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

• Halo2: работает на базе PLONK PIOP в сочетании с Bulletproofs PCS и основан на кривых пасты. Halo2 был разработан с учетом масштабируемости, а также удаления доверенной установки из протокола ZCash.

• Plonky2: Объединяет PLONK PIOP с FRI PCS и основан на домене Златовласки. Plonky2 предназначен для эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать конечной области или эллиптической кривой, используемой для обеспечения правильности, производительности и безопасности системы. Выбор этих комбинаций не только влияет на размер доказательства и эффективность проверки SNARK, но также определяет, может ли система достичь прозрачности без необходимости в доверенных настройках, и может ли она поддерживать расширенные функции, такие как рекурсивные доказательства или агрегированные доказательства.

Binius: HyperPlonk PIOP + Brakedown PCS + Binary Domain. В частности, Binius включает в себя пять ключевых технологий для достижения своей эффективности и безопасности. Прежде всего, арифметика, основанная на башнях двоичных полей, лежит в основе его расчетов, которые могут реализовывать упрощенные операции в двоичных полях. Во-вторых, в своем интерактивном протоколе Oracle Proof Protocol (PIOP) компания Binius адаптировала продукт 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.

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

Как показано на рисунке 1, 128-битная строка: эта строка может быть интерпретирована различными способами в контексте двоичной области. Он может рассматриваться как уникальный элемент в 128-битной двоичной области или может быть разрешен как два 64-битных башенных элемента, четыре 32-битных башенных элемента, 16 8-битных башенных элементов или 128 элементов домена F2. Гибкость этого представления не требует никаких вычислительных затрат, только приведение типов побитовых строк, что является очень интересным и полезным свойством. В то же время небольшие элементы предметной области могут быть упакованы в более крупные элементы предметной области без дополнительных вычислительных затрат. Протокол Binius использует эту функцию для повышения эффективности вычислений. Кроме того, в статье «Об эффективной инверсии в башенных полях характеристики два» исследуется вычислительная сложность операций умножения, квадратуры и инверсии в двоичной области n-битной башни, которая может быть разложена на m-битные подобласти.

2.2 PIOP: адаптированный продукт HyperPlonk и ------ проверки перестановок для двоичных доменов

Схема 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 обрабатывать более сложные полиномиальные перестановки.

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