Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и так далее. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают весь диапазон, даже если исходные значения сами по себе очень малы. Для решения этой проблемы уменьшение размера поля стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования 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 все же требуют глубокого погружения в более крупные расширенные поля, чтобы гарантировать необходимый уровень безопасности.
При построении системы доказательства на основе бинарной области существуют две фактические проблемы: при вычислении представления трассировки в STARKs размер используемой области должен быть больше степени многочлена; при обязательстве Merkle tree в STARKs необходимо выполнять кодирование Рида-Соломона, размер используемой области должен быть больше размера после расширения кодирования.
Binius предложил инновационное решение, которое отдельно обрабатывает эти две проблемы и достигает этого с помощью двух разных способов представления одних и тех же данных: во-первых, с использованием многомерного (, а именно многолинейного ) многочлена вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкутобов равна 2, стандартное расширение Рида-Соломона, как в STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), на основе которого можно провести расширение Рида-Соломона. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно состоит из двух частей:
Информационно-теоретическое полиномиальное интерактивное oracle-доказательство (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 адаптировал проверку переменных и их перестановок в своем интерактивном 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 + Y2.
Как показано на рисунке 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 виртуальный
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
14 Лайков
Награда
14
5
Поделиться
комментарий
0/400
AirdropHunter007
· 18ч назад
Сколько здесь можно заработать?
Посмотреть ОригиналОтветить0
GateUser-3824aa38
· 07-20 17:31
Всего 32 символа, и то много, достаточно закручено.
Посмотреть ОригиналОтветить0
SchroedingerGas
· 07-20 17:30
Газ действительно слишком абстрактен! Кто понимает?
Посмотреть ОригиналОтветить0
WhaleWatcher
· 07-20 17:23
Оптимизация области бык ва, наш круг давно уже нужно изменить.
Посмотреть ОригиналОтветить0
MechanicalMartel
· 07-20 17:08
stark слишком тяжелый, когда он сможет быть быстрее?
Анализ протокола Binius: оптимизация и инновации STARKs в двоичных областях
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и так далее. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают весь диапазон, даже если исходные значения сами по себе очень малы. Для решения этой проблемы уменьшение размера поля стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, ширина кодирования STARKs второго поколения составляет 64 бита, ширина кодирования STARKs третьего поколения составляет 32 бита, однако 32-битная ширина кодирования по-прежнему имеет большое количество неиспользуемого пространства. В сравнении, двоичная область позволяет выполнять операции непосредственно с битами, кодирование компактно и эффективно без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
Таблица 1: Пути дифференциации STARKs
| Алгебра | Ширина кодирования | Представляющая система | |------|----------|----------| | 1-е поколение | 252 бит | StarkWare | | 2-е поколение | 64 бит | Plonky2 | | 3-е поколение | 32bit | Polygon zkEVM | | 4-е поколение | 1бит | Binius |
По сравнению с такими новыми исследованиями конечных полей, как 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 предложил инновационное решение, которое отдельно обрабатывает эти две проблемы и достигает этого с помощью двух разных способов представления одних и тех же данных: во-первых, с использованием многомерного (, а именно многолинейного ) многочлена вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкутобов равна 2, стандартное расширение Рида-Соломона, как в STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), на основе которого можно провести расширение Рида-Соломона. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно состоит из двух частей:
Информационно-теоретическое полиномиальное интерактивное oracle-доказательство (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 адаптировал проверку переменных и их перестановок в своем интерактивном 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 + Y2.
Как показано на рисунке 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 виртуальный