Анализ принципов 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 все же требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарной области возникают 2 практические проблемы: при вычислении отображения следа в STARKs размер используемой области должен превышать степень полинома; при обязательстве Merkle tree в STARKs необходимо выполнять кодирование Рида-Соломона, при этом размер используемой области должен превышать размер после кодирования.
Binius предложил инновационное решение, которое решает эти две проблемы отдельно и реализует это с помощью двух различных способов представления одинаковых данных: во-первых, используя многомерный (, конкретно многолинейный ) многочлен вместо одномерного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае с STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), на основе которого можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
2 Принципиальная структура
Текущая большая часть систем SNARKs обычно состоит из следующих двух частей:
Информационная теоретическая полиномиальная интерактивная оракульная доказательство ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP как основа системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные равенства. Разные протоколы PIOP позволяют доказателю поэтапно отправлять полиномы через взаимодействие с проверяющим, позволяя проверяющему проверять корректность вычислений, запрашивая небольшое количество результатов оценок полиномов. Существующие протоколы PIOP включают: PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, каждый из которых по-разному обрабатывает полиномиальные выражения, что влияет на производительность и эффективность всей системы SNARK.
Полиномиальная схема обязательств ( Polynomial Commitment Scheme, PCS ): Полиномиальная схема обязательств используется для доказательства того, действительно ли полиномиальное равенство, сгенерированное PIOP, выполняется. PCS является криптографическим инструментом, с помощью которого доказатель может обязаться к какому-либо полиному и позднее проверить результат оценки этого полинома, при этом скрывая другую информацию о полиноме. Общие полиномиальные схемы обязательств включают KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) и Brakedown. Разные PCS имеют различные характеристики, безопасность и области применения.
В зависимости от конкретных требований выбирайте разные PIOP и PCS и сочетайте их с подходящими конечными полями или эллиптическими кривыми, чтобы построить доказательственные системы с различными свойствами. Например:
• Halo2: сочетание PLONK PIOP и Bulletproofs PCS, основанное на кривой Pasta. При проектировании Halo2 акцент сделан на масштабируемость и устранение доверенной настройки из протокола ZCash.
• Plonky2: использует комбинацию PLONK PIOP и FRI PCS, основанную на области Goldilocks. Plonky2 разработан для достижения эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать используемому конечному полю или эллиптической кривой, чтобы гарантировать правильность, производительность и безопасность системы. Эти комбинации не только влияют на размер доказательства SNARK и эффективность его проверки, но и определяют, сможет ли система достичь прозрачности без необходимости в доверенной настройке, а также поддерживать расширенные функции, такие как рекурсивные доказательства или агрегированные доказательства.
Binius: HyperPlonk PIOP + Brakedown PCS + двоичные поля. В частности, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных двоичных полях (towers of binary fields) арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в двоичных полях. Во-вторых, Binius адаптировал проверку произведений и перестановок HyperPlonk в своем интерактивном Oracle доказательном протоколе (PIOP), что обеспечивает безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое многолинейное смещение доказательства, оптимизируя эффективность проверки многолинейных отношений на малых полях. В-четвертых, Binius использует улучшенный Lasso поиск доказательства, предоставляя гибкость и мощную безопасность для механизма поиска. Наконец, протокол использует схему обязательств многочленов на малом поле (Small-Field PCS), что позволяет ему реализовать эффективную систему доказательства на двоичных полях и снижает затраты, обычно связанные с большими полями.
( 2.1 Конечное поле: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, что в основном обусловлено двумя аспектами: эффективными вычислениями и эффективной арифметизацией. Двоичная область по своей сути поддерживает высокоэффективные арифметические операции, что делает ее идеальным выбором для криптографических приложений с высокими требованиями к производительности. Кроме того, структура двоичной области поддерживает упрощенный процесс арифметизации, то есть операции, выполняемые в двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме. Эти характеристики, в сочетании с возможностью эффективно использовать иерархические особенности через башенную структуру, делают двоичную область особенно подходящей для таких масштабируемых систем доказательства, как Binius.
Термин "канонический" относится к уникальному и прямому представлению элементов в двоичном поле. Например, в самом простом двоичном поле F2 любая строка длиной k может быть непосредственно сопоставлена с элементом двоичного поля длины k. Это отличается от полей с простым числом, которые не могут предоставить такое стандартное представление в заданной длине. Хотя поле с простым числом размером 32 бита может содержать в себе 32-битные значения, не каждая 32-битная строка может уникально соответствовать элементу поля, тогда как двоичное поле обладает удобством такого взаимно однозначного соответствия. В полях с простым числом Fp распространенными методами редукции являются редукция Барретта, редукция Монтгомери, а также специальные методы редукции для конкретных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k обычно используемыми методами редукции являются специальные редукции ), как в AES, редукция Монтгомери ###, как в POLYVAL, и рекурсивная редукция (, как в Tower ). В статье "Изучение пространства проектирования аппаратных реализаций ECC на полях с простым числом против двоичных полей" указывается, что в двоичном поле не требуется вводить перенос при операциях сложения и умножения, и что операции возведения в квадрат в двоичном поле очень эффективны, так как они следуют упрощенному правилу (X + Y )2 = X2 + Y2.
Как показано на рисунке 1, строка длиной 128 бит: эта строка может быть интерпретирована несколькими способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть разобрана на два 64-битных элемента башенного поля, четыре 32-битных элемента башенного поля, 16 8-битных элементов башенного поля или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, это всего лишь преобразование типа строки битов (typecast), что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье «On Efficient Inversion in Tower Fields of Characteristic Two» рассматривается вычислительная сложность умножения, возведения в квадрат и нахождения обратных значений в n-битном башенном двоичном поле, разлагаемом на m-битные подполя (.
![Bitlayer Research：Анализ принципов 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 внес улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был всюду ненулевым на гиперкубе, и произведение должно равняться определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, что снижает вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог адекватно обработать ситуацию деления на ноль, что привело к невозможности утверждения о ненулевом значении U в гиперкубе; Binius правильно решил эту проблему, даже в случае, когда знаменатель равен нулю, ProductCheck от Binius продолжает обработку, позволяя обобщение на любое значение произведения.
Перекрестная проверка перестановок: HyperPlonk не поддерживает эту функцию; Binius поддерживает проверку перестановок между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложной верификации многочленов с несколькими переменными, предоставив более мощную функциональную поддержку. Эти улучшения не только решили ограничения HyperPlonk, но и заложили основу для будущих систем доказательства на основе двоичных полей.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: новый многоуровневый сдвиг аргумента------применим к булевому гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов является одной из ключевых технологий, которая позволяет эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода:
Упаковка: Этот метод через
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
11 Лайков
Награда
11
5
Репост
Поделиться
комментарий
0/400
ProxyCollector
· 07-20 15:45
Третье поколение 32 бита уже достаточно расточительно~
Посмотреть ОригиналОтветить0
ZeroRushCaptain
· 07-20 15:41
Эти данные сокращаются быстрее, чем я сократил потери и сбежал.
Посмотреть ОригиналОтветить0
BlindBoxVictim
· 07-20 15:38
Этот кодировщик слишком медленно обрабатывает ширину.
Посмотреть ОригиналОтветить0
AirdropCollector
· 07-20 15:25
Продолжайте на халяву пользоваться этими Аирдроп возможностями
Посмотреть ОригиналОтветить0
LiquidationWatcher
· 07-20 15:22
звучит как дежавю с 2022 года... не позволяйте этим битам обмануть вас, как это сделал кредитный рычаг
Анализ протокола 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 все же требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе бинарной области возникают 2 практические проблемы: при вычислении отображения следа в STARKs размер используемой области должен превышать степень полинома; при обязательстве Merkle tree в STARKs необходимо выполнять кодирование Рида-Соломона, при этом размер используемой области должен превышать размер после кодирования.
Binius предложил инновационное решение, которое решает эти две проблемы отдельно и реализует это с помощью двух различных способов представления одинаковых данных: во-первых, используя многомерный (, конкретно многолинейный ) многочлен вместо одномерного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубах" (; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае с STARKs, невозможно, но гиперкуб можно рассматривать как квадрат ), на основе которого можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
2 Принципиальная структура
Текущая большая часть систем SNARKs обычно состоит из следующих двух частей:
Информационная теоретическая полиномиальная интерактивная оракульная доказательство ( Information-Theoretic Polynomial Interactive Oracle Proof, PIOP ): PIOP как основа системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные равенства. Разные протоколы PIOP позволяют доказателю поэтапно отправлять полиномы через взаимодействие с проверяющим, позволяя проверяющему проверять корректность вычислений, запрашивая небольшое количество результатов оценок полиномов. Существующие протоколы PIOP включают: PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, каждый из которых по-разному обрабатывает полиномиальные выражения, что влияет на производительность и эффективность всей системы SNARK.
Полиномиальная схема обязательств ( Polynomial Commitment Scheme, PCS ): Полиномиальная схема обязательств используется для доказательства того, действительно ли полиномиальное равенство, сгенерированное PIOP, выполняется. PCS является криптографическим инструментом, с помощью которого доказатель может обязаться к какому-либо полиному и позднее проверить результат оценки этого полинома, при этом скрывая другую информацию о полиноме. Общие полиномиальные схемы обязательств включают KZG, Bulletproofs, FRI ( Fast Reed-Solomon IOPP ) и Brakedown. Разные PCS имеют различные характеристики, безопасность и области применения.
В зависимости от конкретных требований выбирайте разные PIOP и PCS и сочетайте их с подходящими конечными полями или эллиптическими кривыми, чтобы построить доказательственные системы с различными свойствами. Например:
• Halo2: сочетание PLONK PIOP и Bulletproofs PCS, основанное на кривой Pasta. При проектировании Halo2 акцент сделан на масштабируемость и устранение доверенной настройки из протокола ZCash.
• Plonky2: использует комбинацию PLONK PIOP и FRI PCS, основанную на области Goldilocks. Plonky2 разработан для достижения эффективной рекурсии. При проектировании этих систем выбранные PIOP и PCS должны соответствовать используемому конечному полю или эллиптической кривой, чтобы гарантировать правильность, производительность и безопасность системы. Эти комбинации не только влияют на размер доказательства SNARK и эффективность его проверки, но и определяют, сможет ли система достичь прозрачности без необходимости в доверенной настройке, а также поддерживать расширенные функции, такие как рекурсивные доказательства или агрегированные доказательства.
Binius: HyperPlonk PIOP + Brakedown PCS + двоичные поля. В частности, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности. Во-первых, основанная на башенных двоичных полях (towers of binary fields) арифметика составляет основу его вычислений, позволяя выполнять упрощенные операции в двоичных полях. Во-вторых, Binius адаптировал проверку произведений и перестановок HyperPlonk в своем интерактивном Oracle доказательном протоколе (PIOP), что обеспечивает безопасную и эффективную проверку согласованности между переменными и их перестановками. В-третьих, протокол вводит новое многолинейное смещение доказательства, оптимизируя эффективность проверки многолинейных отношений на малых полях. В-четвертых, Binius использует улучшенный Lasso поиск доказательства, предоставляя гибкость и мощную безопасность для механизма поиска. Наконец, протокол использует схему обязательств многочленов на малом поле (Small-Field PCS), что позволяет ему реализовать эффективную систему доказательства на двоичных полях и снижает затраты, обычно связанные с большими полями.
( 2.1 Конечное поле: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, что в основном обусловлено двумя аспектами: эффективными вычислениями и эффективной арифметизацией. Двоичная область по своей сути поддерживает высокоэффективные арифметические операции, что делает ее идеальным выбором для криптографических приложений с высокими требованиями к производительности. Кроме того, структура двоичной области поддерживает упрощенный процесс арифметизации, то есть операции, выполняемые в двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме. Эти характеристики, в сочетании с возможностью эффективно использовать иерархические особенности через башенную структуру, делают двоичную область особенно подходящей для таких масштабируемых систем доказательства, как Binius.
Термин "канонический" относится к уникальному и прямому представлению элементов в двоичном поле. Например, в самом простом двоичном поле F2 любая строка длиной k может быть непосредственно сопоставлена с элементом двоичного поля длины k. Это отличается от полей с простым числом, которые не могут предоставить такое стандартное представление в заданной длине. Хотя поле с простым числом размером 32 бита может содержать в себе 32-битные значения, не каждая 32-битная строка может уникально соответствовать элементу поля, тогда как двоичное поле обладает удобством такого взаимно однозначного соответствия. В полях с простым числом Fp распространенными методами редукции являются редукция Барретта, редукция Монтгомери, а также специальные методы редукции для конкретных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k обычно используемыми методами редукции являются специальные редукции ), как в AES, редукция Монтгомери ###, как в POLYVAL, и рекурсивная редукция (, как в Tower ). В статье "Изучение пространства проектирования аппаратных реализаций ECC на полях с простым числом против двоичных полей" указывается, что в двоичном поле не требуется вводить перенос при операциях сложения и умножения, и что операции возведения в квадрат в двоичном поле очень эффективны, так как они следуют упрощенному правилу (X + Y )2 = X2 + Y2.
Как показано на рисунке 1, строка длиной 128 бит: эта строка может быть интерпретирована несколькими способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле или быть разобрана на два 64-битных элемента башенного поля, четыре 32-битных элемента башенного поля, 16 8-битных элементов башенного поля или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, это всего лишь преобразование типа строки битов (typecast), что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут быть упакованы в более крупные элементы поля без дополнительных вычислительных затрат. Протокол Binius использует эту особенность для повышения вычислительной эффективности. Кроме того, в статье «On Efficient Inversion in Tower Fields of Characteristic Two» рассматривается вычислительная сложность умножения, возведения в квадрат и нахождения обратных значений в n-битном башенном двоичном поле, разлагаемом на m-битные подполя (.
![Bitlayer Research：Анализ принципов 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 внес улучшения в следующих трех аспектах:
Оптимизация ProductCheck: в HyperPlonk ProductCheck требует, чтобы знаменатель U был всюду ненулевым на гиперкубе, и произведение должно равняться определенному значению; Binius упрощает этот процесс проверки, специфицируя это значение как 1, что снижает вычислительную сложность.
Обработка проблемы деления на ноль: HyperPlonk не смог адекватно обработать ситуацию деления на ноль, что привело к невозможности утверждения о ненулевом значении U в гиперкубе; Binius правильно решил эту проблему, даже в случае, когда знаменатель равен нулю, ProductCheck от Binius продолжает обработку, позволяя обобщение на любое значение произведения.
Перекрестная проверка перестановок: HyperPlonk не поддерживает эту функцию; Binius поддерживает проверку перестановок между несколькими столбцами, что позволяет Binius обрабатывать более сложные случаи перестановки многочленов.
Таким образом, Binius улучшил существующий механизм PIOPSumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложной верификации многочленов с несколькими переменными, предоставив более мощную функциональную поддержку. Эти улучшения не только решили ограничения HyperPlonk, но и заложили основу для будущих систем доказательства на основе двоичных полей.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.3 PIOP: новый многоуровневый сдвиг аргумента------применим к булевому гиперкубу
В протоколе Binius конструирование и обработка виртуальных многочленов является одной из ключевых технологий, которая позволяет эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов. Ниже приведены два ключевых метода: