Анализ принципов Binius STARKs и размышления об их оптимизации
1. Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т.д. Однако для обеспечения безопасности доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы ключевой стратегией стало уменьшение размера диапазона.
Первое поколение 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 все еще требуют углубления в более широкое расширенное поле для обеспечения необходимого уровня безопасности.
При построении системы доказательств на основе бинарной области существуют две реальные проблемы: при вычислении представления трассы в STARKs размер используемой области должен превышать степень многочлена; при обязательстве Меркле-дерева в 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-битное подполе ).
( 2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck------подходит для бинарного поля
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации правильности многочленов и многомерных множеств. Эти основные проверки включают:
GateCheck: Проверка, соответствуют ли конфиденциальное свидетельство ω и открытый ввод x логическому отношению вычислений C)x,ω###=0, чтобы гарантировать правильную работу схемы.
PermutationCheck: Проверяет, являются ли результаты вычисления двух многомерных многочленов f и g на булевом гиперкубе перестановочным отношением f(x) = f(π)x((, чтобы обеспечить согласованность перестановок между переменными многочлена.
LookupCheck: проверка, находится ли значение многочлена в заданной таблице поиска, т.е. f)Bµ) ⊆ T(Bµ), обеспечивает, что некоторые значения находятся в заданном диапазоне.
MultisetCheck: Проверяет, равны ли два многомерных множества, то есть {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, обеспечивая согласованность между несколькими множествами.
ProductCheck: Проверка, равно ли значение рационального многочлена на булевом гиперкубе какому-либо заявленному значению ∏x∈Hµ f(x) = s, чтобы гарантировать правильность произведения многочленов.
ZeroCheck: Проверка, является ли произвольная точка многочлена с несколькими переменными на булевом гиперкубе нулем ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, для обеспечения распределения нулей многочлена.
SumCheck: Проверка того, равно ли значение суммы многочлена от нескольких переменных заявленному значению ∑x∈Hµ f(x) = s. Это достигается путем преобразования задачи вычисления многочлена от нескольких переменных в задачу вычисления многочлена от одной переменной, что снижает вычислительную сложность для проверяющей стороны. Кроме того, SumCheck позволяет пакетную обработку, вводя случайные числа и конструируя линейные комбинации для реализации пакетной проверки нескольких экземпляров суммы.
BatchCheck: основанный на SumCheck, проверяет правильность вычислений нескольких многочленных много переменных для повышения эффективности протокола.
Несмотря на то, что у Binius и HyperPlonk есть много сходств в дизайне протокола, Binius улучшил следующие 3 аспекта:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на всем гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать ситуацию деления на ноль, что привело к невозможности утверждать, что U не равно нулю на гиперкубе; Binius правильно справился с этой проблемой, и даже в случае деления на ноль, ProductCheck Binius продолжает обрабатывать, позволяя обобщение на любое произведение.
Перестановочная проверка между столбцами: HyperPlonk не имеет этой функции; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многомерных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
( 2.3 PIOP: новый многолинейный сдвиг аргумент------применимо к булеву гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов является одной из ключевых технологий, которая позволяет эффективно генерировать и управлять многочленами, происходящими от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода:
Упаковка: Этот метод проходит
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Binius STARKs: Инновационные приложения и оптимизация производительности в двоичных полях
Анализ принципов Binius STARKs и размышления об их оптимизации
1. Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, такие как индексы в циклах for, логические значения, счетчики и т.д. Однако для обеспечения безопасности доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы ключевой стратегией стало уменьшение размера диапазона.
Первое поколение 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 все еще требуют углубления в более широкое расширенное поле для обеспечения необходимого уровня безопасности.
При построении системы доказательств на основе бинарной области существуют две реальные проблемы: при вычислении представления трассы в STARKs размер используемой области должен превышать степень многочлена; при обязательстве Меркле-дерева в 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-битное подполе ).
( 2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck------подходит для бинарного поля
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации правильности многочленов и многомерных множеств. Эти основные проверки включают:
GateCheck: Проверка, соответствуют ли конфиденциальное свидетельство ω и открытый ввод x логическому отношению вычислений C)x,ω###=0, чтобы гарантировать правильную работу схемы.
PermutationCheck: Проверяет, являются ли результаты вычисления двух многомерных многочленов f и g на булевом гиперкубе перестановочным отношением f(x) = f(π)x((, чтобы обеспечить согласованность перестановок между переменными многочлена.
LookupCheck: проверка, находится ли значение многочлена в заданной таблице поиска, т.е. f)Bµ) ⊆ T(Bµ), обеспечивает, что некоторые значения находятся в заданном диапазоне.
MultisetCheck: Проверяет, равны ли два многомерных множества, то есть {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, обеспечивая согласованность между несколькими множествами.
ProductCheck: Проверка, равно ли значение рационального многочлена на булевом гиперкубе какому-либо заявленному значению ∏x∈Hµ f(x) = s, чтобы гарантировать правильность произведения многочленов.
ZeroCheck: Проверка, является ли произвольная точка многочлена с несколькими переменными на булевом гиперкубе нулем ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, для обеспечения распределения нулей многочлена.
SumCheck: Проверка того, равно ли значение суммы многочлена от нескольких переменных заявленному значению ∑x∈Hµ f(x) = s. Это достигается путем преобразования задачи вычисления многочлена от нескольких переменных в задачу вычисления многочлена от одной переменной, что снижает вычислительную сложность для проверяющей стороны. Кроме того, SumCheck позволяет пакетную обработку, вводя случайные числа и конструируя линейные комбинации для реализации пакетной проверки нескольких экземпляров суммы.
BatchCheck: основанный на SumCheck, проверяет правильность вычислений нескольких многочленных много переменных для повышения эффективности протокола.
Несмотря на то, что у Binius и HyperPlonk есть много сходств в дизайне протокола, Binius улучшил следующие 3 аспекта:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был ненулевым на всем гиперкубе, и произведение должно быть равно определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, тем самым снижая вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог должным образом обработать ситуацию деления на ноль, что привело к невозможности утверждать, что U не равно нулю на гиперкубе; Binius правильно справился с этой проблемой, и даже в случае деления на ноль, ProductCheck Binius продолжает обрабатывать, позволяя обобщение на любое произведение.
Перестановочная проверка между столбцами: HyperPlonk не имеет этой функции; Binius поддерживает перестановочную проверку между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных верификаций многомерных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства на основе двоичных полей.
( 2.3 PIOP: новый многолинейный сдвиг аргумент------применимо к булеву гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов является одной из ключевых технологий, которая позволяет эффективно генерировать и управлять многочленами, происходящими от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода: