Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARK'ов, основанных на эллиптических кривых, STARK'и могут рассматриваться как SNARK'и, основанные на хэшах. В настоящее время одной из основных причин низкой эффективности STARK'ов является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах 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, должен быть больше степени многочлена; при обязательстве 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 использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье "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 в гиперкUBE; Binius правильно обработал эту проблему, даже в случае, когда знаменатель равен нулю, ProductCheck Binius продолжает работать, позволяя обобщение на любое значение произведения.
Перекрестная проверка перестановок: HyperPlonk не имеет этой функции; Binius поддерживает проверку перестановок между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных многомерных полиномиальных проверок, предоставив более мощную функциональную поддержку. Эти улучшения не только устранили ограничения HyperPlonk, но и заложили основу для будущих доказательственных систем на основе двоичных полей.
( 2.3 PIOP: новый аргумент многомерного сдвига------применимо к булевому гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов являются одной из ключевых технологий, позволяющей эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Анализ принципов Binius STARKs: инновации в двоичных полях и оптимизация производительности
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARK'ов, основанных на эллиптических кривых, STARK'и могут рассматриваться как SNARK'и, основанные на хэшах. В настоящее время одной из основных причин низкой эффективности STARK'ов является то, что большинство чисел в реальных программах довольно малы, например, индексы в циклах for, булевы значения, счетчики и т. д. Однако для обеспечения безопасности доказательств, основанных на деревьях Меркла, при использовании кодирования Рида-Соломона для расширения данных много дополнительных избыточных значений занимает всю область, даже если исходное значение само по себе очень маленькое. Для решения этой проблемы уменьшение размера области стало ключевой стратегией.
Первое поколение кодирования STARKs имеет ширину в 252 бита, второе - 64 бита, третье - 32 бита, однако кодировка шириной 32 бита все еще содержит большое количество неиспользуемого пространства. В отличие от этого, двоичное поле позволяет производить операции непосредственно с битами, кодирование компактно и эффективно, без произвольных потерь пространства, что можно считать четвертым поколением STARKs.
В отличие от новых исследований, проведенных в последние годы, таких как Goldilocks, BabyBear, Mersenne31 и других конечных полях, исследования двоичных полей восходят к 80-м годам прошлого века. В настоящее время двоичные поля широко применяются в криптографии,典型例子包括:
При использовании меньших полей операции расширения становятся все более важными для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения своей безопасности и реальной применимости. Большинство многочленов, участвующих в вычислениях Prover, не требуют входа в расширенное поле и могут работать только в базовом поле, что обеспечивает высокую эффективность в малом поле. Тем не менее, случайная проверка точек и вычисления FRI все же требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательства на основе бинарного поля существуют 2 практические проблемы: размер поля, используемого для вычисления представления следа в STARKs, должен быть больше степени многочлена; при обязательстве Merkle tree в STARKs необходимо выполнить кодирование Рида-Соломона, и размер используемого поля должен быть больше размера после расширения кодирования.
Binius предложил инновационное решение, которое обрабатывает эти две проблемы отдельно и реализует это с помощью двух различных способов представления одних и тех же данных: во-первых, используя многомерный (, а именно многолинейный ) многочлен вместо однолинейного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), и на основе этого квадрата производить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, при этом обеспечивая безопасность.
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно состоит из двух частей:
Информационно-теоретическое полиномиальное интерактивное оракульное доказательство (Information-Theoretic Polynomial Interactive Oracle Proof, PIOP): PIOP как основа системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные равенства. Разные протоколы PIOP позволяют доказателю поэтапно отправлять полиномы через взаимодействие с проверяющим, что позволяет проверяющему проверять правильность вычислений, запрашивая лишь небольшое количество оценок полиномов. Существующие протоколы PIOP включают: PLONK PIOP, Spartan PIOP и HyperPlonk PIOP и т.д., каждый из которых по-разному обрабатывает полиномиальные выражения, что, в свою очередь, влияет на производительность и эффективность всей системы SNARK.
Полиномные схемы обязательств ( Polynomial Commitment Scheme, PCS ): Полиномная схема обязательств используется для доказательства того, является ли равенство полиномов, сгенерированных PIOP, истинным. PCS — это криптографический инструмент, с помощью которого доказатель может подтвердить определенный полином и позже проверить результаты его оценки, одновременно скрывая другую информацию о полиноме. Распространенные схемы полиномиальных обязательств включают KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) и Brakedown и т.д. Разные PCS имеют разные характеристики, безопасность и области применения.
В зависимости от конкретных потребностей выбирайте различные PIOP и PCS и комбинируйте с подходящими конечными полями или эллиптическими кривыми, можно создать доказательную систему с различными свойствами. Например:
• Halo2: сочетание PLONK PIOP и Bulletproofs PCS, основанное на кривой Pasta. При разработке Halo2 внимание уделялось масштабируемости и устранению доверительной настройки в протоколе ZCash.
• Plonky2: использует PLONK PIOP в сочетании с FRI PCS и основан на области Goldilocks. Plonky2 предназначен для достижения эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать используемому конечному полю или эллиптической кривой, чтобы обеспечить правильность, производительность и безопасность системы. Выбор этих комбинаций влияет не только на размер доказательства SNARK и эффективность проверки, но также определяет, может ли система достигнуть прозрачности без необходимости в доверенной настройке, может ли она поддерживать такие расширенные функции, как рекурсивные доказательства или агрегированные доказательства.
Binius: HyperPlonk PIOP + Brakedown PCS + бинарные поля. Конкретно, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных бинарных полях (towers of binary fields) арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в бинарном поле. Во-вторых, Binius адаптировал проверки произведений и перестановок 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 использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье "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 в гиперкUBE; Binius правильно обработал эту проблему, даже в случае, когда знаменатель равен нулю, ProductCheck Binius продолжает работать, позволяя обобщение на любое значение произведения.
Перекрестная проверка перестановок: HyperPlonk не имеет этой функции; Binius поддерживает проверку перестановок между несколькими колонками, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных многомерных полиномиальных проверок, предоставив более мощную функциональную поддержку. Эти улучшения не только устранили ограничения HyperPlonk, но и заложили основу для будущих доказательственных систем на основе двоичных полей.
( 2.3 PIOP: новый аргумент многомерного сдвига------применимо к булевому гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов являются одной из ключевых технологий, позволяющей эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов.