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

1. Введение

В отличие от SNARKs, основанных на эллиптических кривых, STARKs можно рассматривать как SNARKs на основе хеширования. Основная причина низкой эффективности 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. Анализ принципов

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

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

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

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

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

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

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

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

• Упаковка：Этот метод работает путем объединения меньших значений на соседних позициях в словаре.