Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основной причиной низкой эффективности STARKs является то, что большинство числовых значений в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т. д. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения займут весь диапазон, даже если оригинальное значение само по себе очень мало. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования первого поколения STARKs составляет 252 бита, ширина кодирования второго поколения STARKs составляет 64 бита, а ширина кодирования третьего поколения STARKs составляет 32 бита, но 32-битная ширина кодирования по-прежнему имеет много неиспользуемого пространства. В сравнении с этим, двоичная область позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, т.е. четвертое поколение STARKs.
Таблица 1: Пути разветвления STARKs
В отличие от таких недавних исследований конечных полей, как Goldilocks, BabyBear и Mersenne31, исследования бинарных полей восходят к 80-м годам прошлого века. В настоящее время бинарные поля широко применяются в криптографии,典型例子包括:
Стандарт высокоуровневого шифрования ( AES ), основанный на поле F28;
Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;
QR-код, использующий кодирование Рида-Соломона на основе F28;
Исходные протоколы FRI и zk-STARK, а также хеш-функция Grøstl, которая вошла в финал SHA-3, основанная на поле F28, является очень подходящим рекурсивным хеш-алгоритмом.
При использовании меньших полей операция расширения полей становится все более важной для обеспечения безопасности. А бинарное поле, используемое Binius, полностью зависит от расширения полей для гарантии своей безопасности и практической полезности. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в основном поле, что обеспечивает высокую эффективность в малом поле. Однако случайная проверка точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле, чтобы обеспечить необходимую безопасность.
При построении системы доказательств на основе двоичного поля существуют 2 практические проблемы: при расчете представления следа в STARKs, размер используемого поля должен быть больше, чем степень многочлена; при обязательстве Merkle tree в STARKs необходимо выполнить кодирование Рида-Соломона, размер используемого поля должен быть больше, чем размер после расширения кодирования.
Binius предложил инновационное решение, которое отдельно решает эти две проблемы и представляет одни и те же данные двумя различными способами: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 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 или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
7 Лайков
Награда
7
5
Репост
Поделиться
комментарий
0/400
BlockchainBard
· 14ч назад
STARKs становятся все более экономичными по пространству!
Посмотреть ОригиналОтветить0
StakeHouseDirector
· 14ч назад
Оптимизируйте, оптимизируйте, занимаемое пространство все еще слишком велико!
Посмотреть ОригиналОтветить0
MetaverseLandlord
· 14ч назад
Только и знать, что накапливать технические параметры, у меня от этого голова кружится.
Посмотреть ОригиналОтветить0
WhaleWatcher
· 14ч назад
Каждый день говорят о повышении эффективности, а эффективность все еще не увеличилась?
Посмотреть ОригиналОтветить0
AirdropBuffet
· 15ч назад
Брат, оптимизация такая мощная, жаль, что все равно не обгоняет.
Анализ принципов Binius STARKs: инновационные применения и оптимизация эффективности двоичных полей
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основной причиной низкой эффективности STARKs является то, что большинство числовых значений в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т. д. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения займут весь диапазон, даже если оригинальное значение само по себе очень мало. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования первого поколения STARKs составляет 252 бита, ширина кодирования второго поколения STARKs составляет 64 бита, а ширина кодирования третьего поколения STARKs составляет 32 бита, но 32-битная ширина кодирования по-прежнему имеет много неиспользуемого пространства. В сравнении с этим, двоичная область позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, т.е. четвертое поколение STARKs.
Таблица 1: Пути разветвления STARKs
В отличие от таких недавних исследований конечных полей, как Goldilocks, BabyBear и Mersenne31, исследования бинарных полей восходят к 80-м годам прошлого века. В настоящее время бинарные поля широко применяются в криптографии,典型例子包括:
Стандарт высокоуровневого шифрования ( AES ), основанный на поле F28;
Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;
QR-код, использующий кодирование Рида-Соломона на основе F28;
Исходные протоколы FRI и zk-STARK, а также хеш-функция Grøstl, которая вошла в финал SHA-3, основанная на поле F28, является очень подходящим рекурсивным хеш-алгоритмом.
При использовании меньших полей операция расширения полей становится все более важной для обеспечения безопасности. А бинарное поле, используемое Binius, полностью зависит от расширения полей для гарантии своей безопасности и практической полезности. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в основном поле, что обеспечивает высокую эффективность в малом поле. Однако случайная проверка точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле, чтобы обеспечить необходимую безопасность.
При построении системы доказательств на основе двоичного поля существуют 2 практические проблемы: при расчете представления следа в STARKs, размер используемого поля должен быть больше, чем степень многочлена; при обязательстве Merkle tree в STARKs необходимо выполнить кодирование Рида-Соломона, размер используемого поля должен быть больше, чем размер после расширения кодирования.
Binius предложил инновационное решение, которое отдельно решает эти две проблемы и представляет одни и те же данные двумя различными способами: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 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: новый многомерный сдвиг аргумента------подходит для