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

1 Введение

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

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

При построении системы доказательств на основе двоичных полей существуют 2 практические проблемы: при вычислении трассировки в STARKs размер используемого поля должен превышать степень многочлена; при обязательстве Меркле-дерева в 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 акцент делается на масштабируемости и удалении trusted setup из протокола ZCash.

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

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

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

• Упаковка: Этот метод работает путем объединения меньших элементов, находящихся рядом в словарном порядке,