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

1 Введение

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

Ширина кодирования 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 Принципиальный анализ

Текущая структура большинства систем SNARK обычно включает в себя следующие две части:

• Информационная теория полиномиальных интерактивных оракульных доказательств ( 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 + Y2.

Как показано на рисунке 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 внес улучшения в следующие 3 аспекта:

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

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

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

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

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

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

• Упаковка: этот метод осуществляется путем