Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах достаточно малы, но для обеспечения безопасности доказательства на основе дерева Меркла при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения будут занимать всю область, даже если исходное значение само по себе очень мало. Для решения этой проблемы уменьшение размера области стало ключевой стратегией.
Ширина кодирования 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 адаптировал проверку произведений и перестановок 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-битные подполя).
2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck------подходит для двоичного поля
Дизайн PIOP в протоколе Binius заимствован из HyperPlonk и использует ряд основных механизмов проверки для верификации корректности многочленов и многомерных множеств. Эти основные проверки включают:
GateCheck: проверяет, удовлетворяют ли конфиденциальные доказательства ω и открытый ввод x вычислительным отношениям C(x,ω)=0, чтобы гарантировать правильную работу цепи.
PermutationCheck: Проверка, являются ли результаты вычисления двух многомерных полиномов f и g на булевом гиперкубе отношением перестановки f(x) = f(π(x)), чтобы обеспечить согласованность перестановки между переменными полинома.
LookupCheck: Проверка значений многочлена на наличие в заданной таблице поиска, то есть f(Bµ) ⊆ T(Bµ), чтобы убедиться, что некоторые значения находятся в заданном диапазоне.
MultisetCheck: Проверка на равенство двух многомерных множеств, т.е. {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, гарантируя согласованность между несколькими множествами.
ProductCheck: Проверка того, равно ли значение рационального многочлена на булевом гиперкубе заявленному значению ∏x∈Hµ f(x) = s, чтобы гарантировать правильность произведения многочлена.
ZeroCheck: проверка того, является ли любая точка многочлена с несколькими переменными в булевом гиперкубе нулем ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, для обеспечения распределения нулей многочлена.
SumCheck: Проверка суммы значений многочлена с несколькими переменными на соответствие заявленному значению ∑x∈Hµ f(x) = s. Путем преобразования задачи оценки многочлена с несколькими переменными в задачу оценки одночленного многочлена, снижается вычислительная сложность для проверяющей стороны. Кроме того, SumCheck также позволяет пакетную обработку, вводя случайные числа и создавая линейные комбинации для реализации пакетной проверки нескольких экземпляров суммы.
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κ и комбинирует их в один элемент в многомерном пространстве. Через многолинейное расширение.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Binius инновации: оптимизационное решение STARKs на основе двоичных доменов
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах достаточно малы, но для обеспечения безопасности доказательства на основе дерева Меркла при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения будут занимать всю область, даже если исходное значение само по себе очень мало. Для решения этой проблемы уменьшение размера области стало ключевой стратегией.
Ширина кодирования 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 адаптировал проверку произведений и перестановок 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.
! Исследование бит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 и использует ряд основных механизмов проверки для верификации корректности многочленов и многомерных множеств. Эти основные проверки включают:
GateCheck: проверяет, удовлетворяют ли конфиденциальные доказательства ω и открытый ввод x вычислительным отношениям C(x,ω)=0, чтобы гарантировать правильную работу цепи.
PermutationCheck: Проверка, являются ли результаты вычисления двух многомерных полиномов f и g на булевом гиперкубе отношением перестановки f(x) = f(π(x)), чтобы обеспечить согласованность перестановки между переменными полинома.
LookupCheck: Проверка значений многочлена на наличие в заданной таблице поиска, то есть f(Bµ) ⊆ T(Bµ), чтобы убедиться, что некоторые значения находятся в заданном диапазоне.
MultisetCheck: Проверка на равенство двух многомерных множеств, т.е. {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, гарантируя согласованность между несколькими множествами.
ProductCheck: Проверка того, равно ли значение рационального многочлена на булевом гиперкубе заявленному значению ∏x∈Hµ f(x) = s, чтобы гарантировать правильность произведения многочлена.
ZeroCheck: проверка того, является ли любая точка многочлена с несколькими переменными в булевом гиперкубе нулем ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, для обеспечения распределения нулей многочлена.
SumCheck: Проверка суммы значений многочлена с несколькими переменными на соответствие заявленному значению ∑x∈Hµ f(x) = s. Путем преобразования задачи оценки многочлена с несколькими переменными в задачу оценки одночленного многочлена, снижается вычислительная сложность для проверяющей стороны. Кроме того, SumCheck также позволяет пакетную обработку, вводя случайные числа и создавая линейные комбинации для реализации пакетной проверки нескольких экземпляров суммы.
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 конструкция и обработка виртуальных многочленов является одной из ключевых технологий, которая позволяет эффективно генерировать и оперировать многочленами, производными от входных дескрипторов или других виртуальных многочленов. Вот два ключевых метода: