Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах относительно малы, например, индексы в циклах for, булевы значения, счетчики и т.д. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы снижения размера диапазона стало ключевой стратегией.
Ширина кодирования STARKs первого поколения составляет 252 бит, второго поколения — 64 бита, третьего поколения — 32 бита, но 32-битная ширина кодирования все еще имеет много неиспользуемого пространства. В этом отношении двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
По сравнению с ограниченными полями, обнаруженными в недавних исследованиях, такими как Goldilocks, BabyBear, Mersenne31 и др., исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко применяются в криптографии, типичные примеры включают:
Стандарт высокозащищенного шифрования (AES), основанный на поле F28;
Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;
QR-код, использующий кодирование Рида-Соломона на основе F28;
Исходный протокол FRI и zk-STARK, а также хеш-функция Grøstl, вышедшая в финал SHA-3, основанная на поле F28, является очень подходящим рекурсивным хеш-алгоритмом.
При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения своей безопасности и практической применимости. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в базовом поле, что обеспечивает высокую эффективность в малых полях. Тем не менее, проверка случайных точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарной области существует 2 практические проблемы: при вычислении представления трассы в STARKs, используемый размер области должен быть больше степени многочлена; при обязательстве Меркле-дерева в STARKs необходимо выполнить кодирование Рида-Соломона, используемый размер области должен быть больше размера после расширения кодирования.
Binius предложил инновационное решение, которое отдельно обрабатывает две проблемы и реализует их двумя разными способами, представляя одни и те же данные: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" ( hypercubes ); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, невозможно провести стандартное расширение Рида-Соломона, как это делается в STARKs, но гиперкуб можно рассматривать как квадрат ( square ), на основе которого можно провести расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
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-битные подполя ).
( 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 продолжает обрабатывать, что позволяет обобщить на любые значения произведения.
Кросс-колонка PermutationCheck: HyperPlonk не имеет этой функции; Binius поддерживает проверку перестановок между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановок многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных много переменных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательств на основе бинарных полей.
( 2.3 PIOP: новый многоуровневый сдвиг аргумента------применимо к булевому гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются ключевыми технологиями, которые позволяют эффективно генерировать и обрабатывать многочлены, производные от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода:
Упаковка: Этот метод заключается в том, что
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Инновации Binius: бинарная область помогает оптимизировать STARKs для эффективного сжатия арифметических цепей
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах относительно малы, например, индексы в циклах for, булевы значения, счетчики и т.д. Однако, чтобы обеспечить безопасность доказательств на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие дополнительные избыточные значения занимают весь диапазон, даже если оригинальные значения сами по себе очень малы. Для решения этой проблемы снижения размера диапазона стало ключевой стратегией.
Ширина кодирования STARKs первого поколения составляет 252 бит, второго поколения — 64 бита, третьего поколения — 32 бита, но 32-битная ширина кодирования все еще имеет много неиспользуемого пространства. В этом отношении двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно, без произвольного неиспользуемого пространства, то есть STARKs четвертого поколения.
По сравнению с ограниченными полями, обнаруженными в недавних исследованиях, такими как Goldilocks, BabyBear, Mersenne31 и др., исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко применяются в криптографии, типичные примеры включают:
Стандарт высокозащищенного шифрования (AES), основанный на поле F28;
Galois сообщение аутентификации ( GMAC ), основанное на поле F2128;
QR-код, использующий кодирование Рида-Соломона на основе F28;
Исходный протокол FRI и zk-STARK, а также хеш-функция Grøstl, вышедшая в финал SHA-3, основанная на поле F28, является очень подходящим рекурсивным хеш-алгоритмом.
При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения своей безопасности и практической применимости. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в базовом поле, что обеспечивает высокую эффективность в малых полях. Тем не менее, проверка случайных точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарной области существует 2 практические проблемы: при вычислении представления трассы в STARKs, используемый размер области должен быть больше степени многочлена; при обязательстве Меркле-дерева в STARKs необходимо выполнить кодирование Рида-Соломона, используемый размер области должен быть больше размера после расширения кодирования.
Binius предложил инновационное решение, которое отдельно обрабатывает две проблемы и реализует их двумя разными способами, представляя одни и те же данные: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" ( hypercubes ); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, невозможно провести стандартное расширение Рида-Соломона, как это делается в STARKs, но гиперкуб можно рассматривать как квадрат ( square ), на основе которого можно провести расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
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
( 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 продолжает обрабатывать, что позволяет обобщить на любые значения произведения.
Кросс-колонка PermutationCheck: HyperPlonk не имеет этой функции; Binius поддерживает проверку перестановок между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановок многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных много переменных многочленов, предоставляя более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательств на основе бинарных полей.
( 2.3 PIOP: новый многоуровневый сдвиг аргумента------применимо к булевому гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются ключевыми технологиями, которые позволяют эффективно генерировать и обрабатывать многочлены, производные от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода: