Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
STARKs – это система доказательств на основе хеширования, которая отличается от SNARKs, основанных на эллиптических кривых. Одной из основных причин низкой эффективности STARKs в настоящее время является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Однако, чтобы обеспечить безопасность доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона данные расширяются, и многие дополнительные избыточные значения займут все поле, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы уменьшение размера поля стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но 32-битная ширина кодирования по-прежнему имеет много пустого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактное и эффективное без произвольного пустого пространства, то есть STARKs четвертого поколения.
Таблица 1: Пути эволюции STARKs
| Поколение | Ширина | Особенности |
|------|------|------|
| 1-е поколение | 252 бит | Домен, большое пространство для использования |
| 2-е поколение | 64bit | Среднее поле, большое пространство для отходов |
| 3-е поколение | 32 бит | Маленькая область, все еще есть неиспользуемое пространство |
| 4-е поколение | 1 бит | Бинарная область, без потерь пространства |
В отличие от таких недавно открытых конечных полей, как 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 + Y 2.
Как показано на рисунке 1, строка длиной 128 бит: эта строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или интерпретироваться как два элемента поля длиной 64 бита, четыре элемента поля длиной 32 бита, 16 элементов поля длиной 8 бит или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, это всего лишь преобразование типа строки битов )typecast(, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье «О эффективном обращении в башенных полях характеристики два» рассматривается вычислительная сложность операций умножения, возведения в квадрат и обращения в 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 улучшил следующие 3 аспекта:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был везде ненулевым на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специализируя это значение на 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждать, что U не равно нулю в гиперкубе; Binius правильно обработал эту проблему, и даже в случае, когда знаменатель равен нулю, ProductCheck Binius может продолжать обработку, что позволяет обобщить на любые значения произведения.
Перестановочная проверка межколонок: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многомерных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только решают ограничения HyperPlonk, но и для неопределенных.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
8 Лайков
Награда
8
5
Репост
Поделиться
комментарий
0/400
SelfCustodyIssues
· 07-11 16:18
Эта скорость развития просто жестко снижается.
Посмотреть ОригиналОтветить0
CryptoTarotReader
· 07-11 09:56
Программисты снова начали соревноваться в области. Это необходимо.
Посмотреть ОригиналОтветить0
NFTRegretful
· 07-08 16:51
32 бита недостаточно, трудно справиться.
Посмотреть ОригиналОтветить0
ImpermanentPhilosopher
· 07-08 16:50
Этот прогресс в оптимизации слишком медленный... 32 тоже кажется длинным.
Посмотреть ОригиналОтветить0
BearMarketSurvivor
· 07-08 16:33
32 бита - это слишком много, кто закрутит, тот и проиграет.
Binius двоичный домен STARKs: анализ принципов и инновации в оптимизации
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
STARKs – это система доказательств на основе хеширования, которая отличается от SNARKs, основанных на эллиптических кривых. Одной из основных причин низкой эффективности STARKs в настоящее время является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, логические значения, счетчики и т.д. Однако, чтобы обеспечить безопасность доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона данные расширяются, и многие дополнительные избыточные значения займут все поле, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы уменьшение размера поля стало ключевой стратегией.
Как показано в таблице 1, ширина кодирования STARKs первого поколения составляет 252 бита, второго поколения — 64 бита, третьего поколения — 32 бита, но 32-битная ширина кодирования по-прежнему имеет много пустого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактное и эффективное без произвольного пустого пространства, то есть STARKs четвертого поколения.
Таблица 1: Пути эволюции STARKs
| Поколение | Ширина | Особенности | |------|------|------| | 1-е поколение | 252 бит | Домен, большое пространство для использования | | 2-е поколение | 64bit | Среднее поле, большое пространство для отходов |
| 3-е поколение | 32 бит | Маленькая область, все еще есть неиспользуемое пространство | | 4-е поколение | 1 бит | Бинарная область, без потерь пространства |
В отличие от таких недавно открытых конечных полей, как 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 + Y 2.
Как показано на рисунке 1, строка длиной 128 бит: эта строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или интерпретироваться как два элемента поля длиной 64 бита, четыре элемента поля длиной 32 бита, 16 элементов поля длиной 8 бит или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, это всего лишь преобразование типа строки битов )typecast(, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье «О эффективном обращении в башенных полях характеристики два» рассматривается вычислительная сложность операций умножения, возведения в квадрат и обращения в 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 улучшил следующие 3 аспекта:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был везде ненулевым на гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специализируя это значение на 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать случаи деления на ноль, что привело к невозможности утверждать, что U не равно нулю в гиперкубе; Binius правильно обработал эту проблему, и даже в случае, когда знаменатель равен нулю, ProductCheck Binius может продолжать обработку, что позволяет обобщить на любые значения произведения.
Перестановочная проверка межколонок: HyperPlonk не поддерживает эту функцию; Binius поддерживает перестановочную проверку между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многомерных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только решают ограничения HyperPlonk, но и для неопределенных.