Анализ принципов STARKs Binius и размышления по оптимизации
1. Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство значений в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при расширении данных с помощью кодирования Рида-Соломона, многие дополнительные избыточные значения занимают весь диапазон, даже если исходные значения сами по себе очень малы. Чтобы решить эту проблему, снижение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но кодирование шириной 32 бита все еще имеет много неиспользуемого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без случайного неиспользуемого пространства, то есть STARKs четвертого поколения.
По сравнению с ограниченными полями, такими как Goldilocks, BabyBear и Mersenne31, которые были обнаружены в последние годы, исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко используются в криптографии, типичные примеры включают:
Стандарт высокоэффективного шифрования (AES), основанный на поле F2^8
Galois сообщение аутентификации ( GMAC ), основанное на поле F2^128
QR-код, использующий кодирование Рида-Соломона на основе F2^8
Исходные протоколы FRI и zk-STARK, а также хэш-функция Grøstl, вышедшая в финал SHA-3, основанная на поле F2^8, является очень подходящим рекурсивным хэш-алгоритмом.
При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения для гарантии своей безопасности и фактической применимости. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле, а работают только в базовом поле, что позволяет достичь высокой эффективности в малом поле. Тем не менее, случайные проверки точек и вычисления FRI все же требуют глубокого погружения в более крупное расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарного поля существуют две практические проблемы: при расчете представления трассировки в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве дерева Меркла в 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 адаптировал 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 = X^2 + 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 продолжает обрабатывать, что позволяет обобщение на любое значение произведения.
Перестановочная проверка (PermutationCheck) в HyperPlonk не поддерживается; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные варианты многочленов.
Таким образом, Binius улучшил гибкость и эффективность протокола благодаря модификациям существующего механизма PIOPSumCheck, особенно в обработке более сложных проверок многочленов с несколькими переменными, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
( 2.3 PIOP: новый многомерный сдвиг аргумента------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются одной из ключевых технологий, позволяющих эффективно генерировать
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
8 Лайков
Награда
8
5
Репост
Поделиться
комментарий
0/400
AllInDaddy
· 07-27 20:46
А, это Stark оптимизация, я не понимаю.
Посмотреть ОригиналОтветить0
GateUser-e51e87c7
· 07-26 04:42
Технологии вызывают головную боль. Когда будет картинка?
Посмотреть ОригиналОтветить0
VirtualRichDream
· 07-25 03:17
Эффективность — это главный путь!
Посмотреть ОригиналОтветить0
SatoshiChallenger
· 07-25 03:17
Данные снова обманывают для финансирования, 32 бита все еще тратятся?
Посмотреть ОригиналОтветить0
airdrop_whisperer
· 07-25 03:13
32 бита все еще тратят место? Этого ведь недостаточно...
Как Binius использует двоичную область для оптимизации эффективности STARKs: анализ 4 ключевых технологий
Анализ принципов STARKs Binius и размышления по оптимизации
1. Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство значений в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при расширении данных с помощью кодирования Рида-Соломона, многие дополнительные избыточные значения занимают весь диапазон, даже если исходные значения сами по себе очень малы. Чтобы решить эту проблему, снижение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но кодирование шириной 32 бита все еще имеет много неиспользуемого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без случайного неиспользуемого пространства, то есть STARKs четвертого поколения.
| Алгебра | Ширина кодирования | Типичная реализация | |------|----------|----------| | 1-е поколение | 252 бит | StarkWare | | Второе поколение | 64bit | Plonky2 | | 3-е поколение | 32bit | Plonky3 | | 4-е поколение | 1bit | Binius |
По сравнению с ограниченными полями, такими как Goldilocks, BabyBear и Mersenne31, которые были обнаружены в последние годы, исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко используются в криптографии, типичные примеры включают:
При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения для гарантии своей безопасности и фактической применимости. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле, а работают только в базовом поле, что позволяет достичь высокой эффективности в малом поле. Тем не менее, случайные проверки точек и вычисления FRI все же требуют глубокого погружения в более крупное расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарного поля существуют две практические проблемы: при расчете представления трассировки в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве дерева Меркла в 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 адаптировал 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 = X^2 + 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 продолжает обрабатывать, что позволяет обобщение на любое значение произведения.
Перестановочная проверка (PermutationCheck) в HyperPlonk не поддерживается; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные варианты многочленов.
Таким образом, Binius улучшил гибкость и эффективность протокола благодаря модификациям существующего механизма PIOPSumCheck, особенно в обработке более сложных проверок многочленов с несколькими переменными, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
( 2.3 PIOP: новый многомерный сдвиг аргумента------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются одной из ключевых технологий, позволяющих эффективно генерировать