Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основная причина низкой эффективности STARKs заключается в том, что большинство чисел в реальных программах небольшие, такие как индексы в цикле 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 адаптировал проверки произведений и перестановок 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 или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
11 Лайков
Награда
11
6
Поделиться
комментарий
0/400
MissedTheBoat
· 13ч назад
Компактность — это король! Парашют!
Посмотреть ОригиналОтветить0
GasBandit
· 08-05 20:35
Как вы подумали об оптимизации стаков?
Посмотреть ОригиналОтветить0
CryptoComedian
· 08-05 20:35
Написание论文 по ширине давления, три поколения написано, но не соответствует стандартам.
Посмотреть ОригиналОтветить0
BlockchainThinkTank
· 08-05 20:23
Мы считаем, что оптимизация zkp все еще находится на ранней стадии, и к таким проектам по повышению эффективности следует относиться с осторожностью.
Посмотреть ОригиналОтветить0
MentalWealthHarvester
· 08-05 20:17
Снова золотая эра моих STARKs. Можно продолжать добычу.
Посмотреть ОригиналОтветить0
LayoffMiner
· 08-05 20:08
Что ты думаешь, газ не снизится, а ты еще так глубокомысленно говоришь.
Новые идеи оптимизации STARKs: Binius способствует развитию двоичных полей
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Основная причина низкой эффективности STARKs заключается в том, что большинство чисел в реальных программах небольшие, такие как индексы в цикле for, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательства на основе дерева Меркла при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают весь диапазон, даже если исходные значения сами по себе очень малы. Для решения этой проблемы снижение размера диапазона стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, ширина кодирования STARKs второго поколения составляет 64 бита, а ширина кодирования STARKs третьего поколения составляет 32 бита, но 32-битная ширина кодирования все еще имеет большое количество неиспользуемого пространства. В сравнении, двоичное поле позволяет выполнять операции напрямую по битам, обеспечивая компактное и эффективное кодирование без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
| Время | STARKs | Ширина кодирования | |------|--------|----------| | 2018 | 1-е поколение | 252bit | | 2021 | Вторая генерация | 64bit | | 2022 | 3-е поколение | 32bit | | 2023 | Четвертое поколение | 1bit |
Таблица 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 адаптировал проверки произведений и перестановок 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-битные подполя ).
! Двоичный домен башни
Рисунок 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 улучшил следующие три аспекта:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на всех точках гиперкуба, и произведение должно равняться определенному значению; Binius упрощает этот процесс проверки, специализируя это значение на 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что приводит к невозможности утверждения о ненулевом значении U в гиперкубе; Binius правильно решил эту проблему, даже в случае деления на ноль, ProductCheck Binius продолжает обработку, что позволяет обобщить на произвольные значения произведения.
Перекрестная проверка перестановки: HyperPlonk не поддерживает эту функцию; Binius поддерживает проверку перестановки между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи排列 многочленов.
Таким образом, Binius улучшил гибкость и эффективность протокола за счет улучшения существующего механизма PIOPSumCheck, особенно при обработке более сложной верификации многочленов с несколькими переменными, предоставляя более мощную функциональную поддержку. Эти улучшения не только решают ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
( 2.3 PIOP: новый многолинейный сдвиг аргумент------применимо к булевому гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются ключевыми.