Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, множество дополнительных избыточных значений занимает целую область, даже если сами исходные значения очень малы. Для решения этой проблемы ключевой стратегией стало уменьшение размера области.
Ширина кодирования 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 все еще требуют углубления в более широкое расширенное поле, чтобы гарантировать необходимый уровень безопасности.
При построении системы доказательств на основе бинарного поля существуют 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 адаптировал проверку произведений и перестановок 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-битные подполя).
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 внес улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смогла должным образом обработать случаи деления на ноль, что привело к невозможности утверждения о ненулевом значении U в гиперкубе; Binius правильно справился с этой проблемой, и даже в случае деления на ноль, ProductCheck Binius продолжает работать, позволяя обобщение на любое значение произведения.
Перестановочная проверка между столбцами: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многочленов с несколькими переменными, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательств на основе двоичных полей.
2.3 PIOP: новый аргумент мультиленейного сдвига------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных полиномов являются одной из ключевых технологий, позволяющей эффективно генерировать и обрабатывать полиномы, производные от входных дескрипторов или других виртуальных полиномов. Вот два ключевых метода:
Упаковка：
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
9 Лайков
Награда
9
3
Поделиться
комментарий
0/400
BlindBoxVictim
· 21ч назад
32bit? Приятель, лучше использовать бумагу и ручку.
Посмотреть ОригиналОтветить0
AirdropworkerZhang
· 21ч назад
Все еще боремся за место? Я просто хочу занести деньги.
Binius: Новый эффективный STARKs на основе двоичных доменов
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, множество дополнительных избыточных значений занимает целую область, даже если сами исходные значения очень малы. Для решения этой проблемы ключевой стратегией стало уменьшение размера области.
Ширина кодирования 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 все еще требуют углубления в более широкое расширенное поле, чтобы гарантировать необходимый уровень безопасности.
При построении системы доказательств на основе бинарного поля существуют 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 адаптировал проверку произведений и перестановок 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-битные подполя).
! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs
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 внес улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смогла должным образом обработать случаи деления на ноль, что привело к невозможности утверждения о ненулевом значении U в гиперкубе; Binius правильно справился с этой проблемой, и даже в случае деления на ноль, ProductCheck Binius продолжает работать, позволяя обобщение на любое значение произведения.
Перестановочная проверка между столбцами: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многочленов с несколькими переменными, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательств на основе двоичных полей.
2.3 PIOP: новый аргумент мультиленейного сдвига------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных полиномов являются одной из ключевых технологий, позволяющей эффективно генерировать и обрабатывать полиномы, производные от входных дескрипторов или других виртуальных полиномов. Вот два ключевых метода: