Анализ принципов 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 все же требуют углубления в более крупные расширенные поля для обеспечения необходимого уровня безопасности.

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

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

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

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

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

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

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

• Упаковка：