Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основная причина низкой эффективности STARKs заключается в том, что большинство значений в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т. д. Однако, чтобы обеспечить безопасность доказательства, основанного на дереве Меркла, при использовании кодирования Рида-Соломона для расширения данных, множество дополнительных избыточных значений занимает весь диапазон, даже если само исходное значение очень мало. Чтобы решить эту проблему, уменьшение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но кодирование шириной 32 бита все еще имеет значительное количество неиспользуемого пространства. В сравнении с этим, двоичные поля позволяют выполнять операции непосредственно с битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
Таблица 1: Пути преобразования STARKs
| Порядок | Ширина | Описание |
|------|------|------|
| 1-е поколение | 252 бит | основано на поле больших простых чисел |
| Второе поколение | 64 бит | Область Goldilocks |
| 3-е поколение | 32 бита | Домен Babybear |
| 4-е поколение | 1 бит | двоичная область |
По сравнению с такими новыми исследованиями, как 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, стандартное расширение Reed-Solomon, как в случае с STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ( square ), на основе которого можно провести расширение Reed-Solomon. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
2 Анализ принципов
Текущая конструкция большинства систем SNARK включает в себя обычно две части:
Информационно-теоретическое полиномиальное интерактивное оракульное доказательство ( 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 адаптировал 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 + Y2.
Как показано на рисунке 1, 128-битная строка: эта строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть интерпретирована как два 64-битных элемента в башенном поле, четыре 32-битных элемента в башенном поле, 16 8-битных элементов в башенном поле или 128 элементов в поле F2. Эта гибкость представления не требует вычислительных затрат, это просто преобразование типа строки битов (typecast), что является очень интересным и полезным свойством. В то же время, небольшие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, статья «On Efficient Inversion in Tower Fields of Characteristic Two» исследует вычислительную сложность операций умножения, возведения в квадрат и нахождения обратного элемента в n-битном башенном двоичном поле, которое может быть разложено на m-битные подполя (.
![Bitlayer Research: Анализ принципов Binius STARKs и его оптимизационные размышления])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
5 Лайков
Награда
5
4
Репост
Поделиться
комментарий
0/400
AllTalkLongTrader
· 7ч назад
Кто это вообще понимает? Кроме star ничего не понял.
Посмотреть ОригиналОтветить0
MerkleDreamer
· 7ч назад
Широкая позиция снизилась, наконец-то уменьшили потери.
Binius STARKs новое достижение: оптимизация двоичных полей и эффективная система доказательств
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основная причина низкой эффективности STARKs заключается в том, что большинство значений в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т. д. Однако, чтобы обеспечить безопасность доказательства, основанного на дереве Меркла, при использовании кодирования Рида-Соломона для расширения данных, множество дополнительных избыточных значений занимает весь диапазон, даже если само исходное значение очень мало. Чтобы решить эту проблему, уменьшение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но кодирование шириной 32 бита все еще имеет значительное количество неиспользуемого пространства. В сравнении с этим, двоичные поля позволяют выполнять операции непосредственно с битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
Таблица 1: Пути преобразования STARKs
| Порядок | Ширина | Описание | |------|------|------| | 1-е поколение | 252 бит | основано на поле больших простых чисел | | Второе поколение | 64 бит | Область Goldilocks | | 3-е поколение | 32 бита | Домен Babybear | | 4-е поколение | 1 бит | двоичная область |
По сравнению с такими новыми исследованиями, как 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, стандартное расширение Reed-Solomon, как в случае с STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ( square ), на основе которого можно провести расширение Reed-Solomon. Этот метод значительно увеличивает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
2 Анализ принципов
Текущая конструкция большинства систем SNARK включает в себя обычно две части:
Информационно-теоретическое полиномиальное интерактивное оракульное доказательство ( 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 адаптировал 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 + Y2.
Как показано на рисунке 1, 128-битная строка: эта строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть интерпретирована как два 64-битных элемента в башенном поле, четыре 32-битных элемента в башенном поле, 16 8-битных элементов в башенном поле или 128 элементов в поле F2. Эта гибкость представления не требует вычислительных затрат, это просто преобразование типа строки битов (typecast), что является очень интересным и полезным свойством. В то же время, небольшие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, статья «On Efficient Inversion in Tower Fields of Characteristic Two» исследует вычислительную сложность операций умножения, возведения в квадрат и нахождения обратного элемента в n-битном башенном двоичном поле, которое может быть разложено на m-битные подполя (.
![Bitlayer Research: Анализ принципов Binius STARKs и его оптимизационные размышления])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
) 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 виртуальные множественные