Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARK, основанных на эллиптических кривых, STARK можно рассматривать как SNARK, основанные на хэшах. Основной причиной низкой эффективности STARK в настоящее время является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, булевы значения, счетчики и т.д. Однако для обеспечения безопасности доказательства, основанного на дереве Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область, даже если оригинальное значение само по себе очень мало. Чтобы решить эту проблему, уменьшение размера области стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, ширина кодирования STARKs второго поколения составляет 64 бита, ширина кодирования STARKs третьего поколения составляет 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 в своем интерактивном 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-битные подполя(.
! [Исследование битlayer: анализ принципов и оптимизационное мышление 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 предлагает улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым в каждом месте на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специализируя это значение на 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждать, что U не равно нулю на гиперкубе; Binius правильно обработал эту проблему, даже когда знаменатель равен нулю, ProductCheck Binius продолжает обрабатывать, позволяя расширять до любого значения произведения.
Перестановочная проверка кросс-столбцов: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные ситуации с многочленными перестановками.
Таким образом, Binius улучшил механизм PIOPSumCheck, что повысило гибкость и эффективность протокола, особенно при обработке более сложной верификации многовариантных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только решают ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
10 Лайков
Награда
10
5
Поделиться
комментарий
0/400
ZkSnarker
· 07-29 13:22
ну, технически старки — это просто закуски, но с хешами, лол
Посмотреть ОригиналОтветить0
PebbleHander
· 07-26 15:33
Бэнбу остановился, и кто-то действительно говорит такую жесткую вещь.
Посмотреть ОригиналОтветить0
SmartContractPhobia
· 07-26 15:26
Это снова техническая работа, которая раздражает нас, новичков.
Посмотреть ОригиналОтветить0
LootboxPhobia
· 07-26 15:23
Неплохо, с трехзначного числа снизилось до двухзначного.
Посмотреть ОригиналОтветить0
notSatoshi1971
· 07-26 15:18
Да вы с ума сошли, хотите превзойти snark? Эта оптимизация слишком консервативна.
Binius STARKs: Оптимизация двоичных полей и анализ принципов
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARK, основанных на эллиптических кривых, STARK можно рассматривать как SNARK, основанные на хэшах. Основной причиной низкой эффективности STARK в настоящее время является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, булевы значения, счетчики и т.д. Однако для обеспечения безопасности доказательства, основанного на дереве Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область, даже если оригинальное значение само по себе очень мало. Чтобы решить эту проблему, уменьшение размера области стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, ширина кодирования STARKs второго поколения составляет 64 бита, ширина кодирования STARKs третьего поколения составляет 32 бита, но 32-битная ширина кодирования все еще имеет много неиспользуемого пространства. В отличие от этого, двоичное поле позволяет выполнять операции непосредственно с битами, кодирование компактно и эффективно без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
Таблица 1: Путь разветвления STARKs
| Поколение | Ширина кода | Представляющая система | |------|----------|----------| | 1-е поколение | 252bit | STARK | | 2-е поколение | 64 бит | Plonky2 | | 3-е поколение | 32bit | Mina | | 4-е поколение | 1bit | Binius |
По сравнению с Goldilocks, BabyBear, Mersenne31 и другими новыми исследованиями有限域 последних нескольких лет, исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко применяются в криптографии,典型例子包括:
При использовании меньших полей операция расширения поля становится все более важной для обеспечения безопасности. А бинарное поле, используемое 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-битные подполя(.
! [Исследование битlayer: анализ принципов и оптимизационное мышление 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 предлагает улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым в каждом месте на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специализируя это значение на 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждать, что U не равно нулю на гиперкубе; Binius правильно обработал эту проблему, даже когда знаменатель равен нулю, ProductCheck Binius продолжает обрабатывать, позволяя расширять до любого значения произведения.
Перестановочная проверка кросс-столбцов: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные ситуации с многочленными перестановками.
Таким образом, Binius улучшил механизм PIOPSumCheck, что повысило гибкость и эффективность протокола, особенно при обработке более сложной верификации многовариантных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только решают ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.