Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Тем не менее, для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область, даже если исходное значение само по себе очень мало. Для решения этой проблемы снижение размера области стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования 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 все еще требуют углубления в более крупное расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарного поля существуют две реальные проблемы: при вычислении представления трассировки в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве Merkle tree в STARKs необходимо выполнить кодирование Рида-Соломона, размер используемого поля должен быть больше размера после расширения кодирования.
Binius предложил инновационное решение для одновременной обработки этих двух проблем, представляя одни и те же данные двумя разными способами: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), на основе которого можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
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 включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных двоичных полях (towers of binary fields) арифметическая структура составляет основу его вычислений, позволяя осуществлять упрощенные операции в двоичных полях. Во-вторых, Binius в своем интерактивном Oracle доказательном протоколе (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-битные подполя ).
Рисунок 1: Башенная бинарная область
( 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: новое многолинейное смещение аргумент------применимо
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
15 Лайков
Награда
15
6
Репост
Поделиться
комментарий
0/400
WhaleWatcher
· 2ч назад
stark усложнил технологии?
Посмотреть ОригиналОтветить0
LightningPacketLoss
· 08-08 03:54
Эта оптимизация слишком неэффективна, 32 бита как этого достаточно?
Посмотреть ОригиналОтветить0
PanicSeller
· 08-08 03:50
Снова оптимизация и сжатие, а всё равно в убытках.
Посмотреть ОригиналОтветить0
MoonBoi42
· 08-08 03:49
Эта вещь оптимизировалась полдня, а не лучше, чем Polaris.
Посмотреть ОригиналОтветить0
DecentralizeMe
· 08-08 03:40
Оптимизировать это дер цветное
Посмотреть ОригиналОтветить0
ApeWithAPlan
· 08-08 03:32
Кодирование с шириной 252 бит до 32 бит все еще слишком медленно, не так ли?
Binius STARKs: Инновации и оптимизация в двоичной области
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Тем не менее, для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область, даже если исходное значение само по себе очень мало. Для решения этой проблемы снижение размера области стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения - 64 бита, третьего поколения - 32 бита, но кодирование шириной 32 бита по-прежнему имеет много неиспользуемого пространства. В сравнении, бинарная область позволяет напрямую работать с битами, кодирование компактно и эффективно без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
Таблица 1: Эволюционные пути STARKs
| Поколение | Ширина кодирования | Представляемая система | |------|----------|----------| | 1-е поколение | 252 бит | StarkWare STARKs | | Второе поколение | 64 бит | Plonky2 | | 3-е поколение | 32 бита | BabyBear | | 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 обычно состоит из двух частей:
Информационно-теоретическое полиномиальное интерактивное оракульное доказательство ( 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) адаптировал проверку произведений и перестановок 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-битные подполя ).
Рисунок 1: Башенная бинарная область
( 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: новое многолинейное смещение аргумент------применимо