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

При построении системы доказательств на основе двоичных полей существуют 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 адаптировал HyperPlonk умножение и проверку перестановки в своем интерактивном протоколе доказательства оракулов (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.

! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs

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

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