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

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

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

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

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

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

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