Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARKs, основанных на эллиптических кривых, STARKs можно рассматривать как SNARKs, основанные на хэшах. В настоящее время одной из основных причин низкой эффективности STARKs является то, что в большинстве реальных программ числовые значения довольно малы, такие как индексы циклов, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие избыточные значения занимают все поле, даже если исходные значения очень малы. Для решения этой проблемы снижение размера поля становится ключевой стратегией.
Первое поколение кодирования STARKs имеет ширину 252 бита, второе поколение — 64 бита, третье поколение — 32 бита, но 32-битное кодирование все еще имеет много пустого места. В отличие от этого, двоичное поле позволяет напрямую работать с битами, кодирование компактно и эффективно, без потерь, что можно считать четвертым поколением STARKs.
В отличие от обнаруженных в последние годы конечных полей, таких как Goldilocks, BabyBear и Mersenne31, исследования двоичных полей восходят к 1980-м годам. В настоящее время двоичные поля широко применяются в криптографии, таких как поле AES(F28, поле GMAC)F2128, кодирование Рида-Соломона QR-кода(F28 и другие. Протоколы оригинального FRI и zk-STARK, а также хеш-функция Grøstl, прошедшая в финал SHA-3, также основаны на поле F28.
При использовании меньших полей операция расширения становится все более важной для обеспечения безопасности. Двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения безопасности и доступности. Большинство вычислений Prover, связанных с многочленами, требует операций в базовом поле, что обеспечивает высокую эффективность в меньшем поле. Однако проверка случайной точки и вычисления FRI все еще должны проводиться в более широком расширенном поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе двоичных полей существуют две практические проблемы:
При вычислении trace в STARKs размер используемой области должен быть больше степени многочлена.
При коммите Merkle-дерева в STARKs необходимо использовать кодирование Рида-Соломона, размер используемого поля должен быть больше размера, полученного после расширения кодирования.
Binius предложил инновационное решение для решения этих двух проблем:
Использовать многомерный ) многолинейный ( многочлен вместо одномерного многочлена, представляя всю вычислительную траекторию через его значения на "гиперкубе".
Поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае STARKs, невозможно, но гиперкуб можно рассматривать как квадрат, и на основе этого квадрата можно провести расширение Рида-Соломона.
Этот метод значительно повысил эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно включают в себя две части:
Доказательство полиномиального взаимодействия предсказателя информационной теории )PIOP(:
В качестве ядра системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные уравнения. Взаимодействуя с проверяющим, доказчик постепенно отправляет полиномы, позволяя проверяющему проверить правильность вычислений, запрашивая лишь небольшое количество полиномов для оценки результата. Существующие протоколы PIOP включают PLONK PIOP, Spartan PIOP и HyperPlonk PIOP и др.
Многочленное обещание )PCS(:
Используется для доказательства того, выполняется ли полиномиальное равенство, сгенерированное PIOP. PCS — это криптографический инструмент, позволяющий доказателю зафиксировать определенный полином и позже проверить его оценку, скрывая при этом другую информацию о многочлене. Распространенные PCS включают KZG, Bulletproofs, FRI и Brakedown.
В зависимости от требований можно выбирать различные PIOP и PCS, а также сочетать их с подходящими конечными полями или эллиптическими кривыми, чтобы создать доказательные системы с различными свойствами. Например:
Halo2: PLONK PIOP + Bulletproofs PCS + Pasta Curve
Артикуляция на основе башенной двоичной области: составление вычислительной основы, осуществление упрощенных операций в двоичной области
Адаптация проверки произведений и перестановок HyperPlonk: обеспечить эффективную проверку согласованности между переменными и перестановками
Новая многофакторная линейная доказательство: оптимизация эффективности проверки многофакторных отношений на малых областях
Улучшение доказательства поиска Lasso: обеспечение гибкости и безопасности механизма поиска
Малый полиномиальный комитет: реализация эффективной системы доказательства в двоичном поле, сокращение затрат, связанных с большим полем.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Ограниченные поля: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, в основном благодаря эффективным вычислениям и эффективной арифметике. Двоичная область по сути поддерживает высокоэффективные арифметические операции, что делает ее идеальным выбором для чувствительных к производительности криптографических приложений. Структура двоичной области поддерживает упрощенный процесс арифметики, операции, выполняемые на двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме. Эти характеристики в сочетании с возможностью полностью использовать иерархические особенности через башенную структуру, делают двоичную область особенно подходящей для таких масштабируемых систем доказательства, как Binius.
"канонический" обозначает уникальный и прямой способ представления элементов в двоичном поле. Например, в базовом двоичном поле F2 любая строка длиной k может быть напрямую сопоставлена с элементом двоичного поля длины k. Это отличается от простого поля, которое не может предоставить такое каноническое представление в заданном количестве бит. Хотя 32-битное простое поле может быть включено в 32 бита, не каждая 32-битная строка может уникально соответствовать элементу поля, в то время как двоичное поле обладает такой удобной взаимно однозначной соответствием.
В полях простых чисел Fp распространенные методы редукции включают редукцию Барретта, редукцию Монтгомери, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичных полях F2k часто используемые методы редукции включают специальную редукцию (, как AES использует ), редукцию Монтгомери ###, как POLYVAL использует (, и рекурсивную редукцию ), как Tower (.
Статья «Изучение пространства проектирования аппаратных реализаций ECC на простых полях и двоичных полях» указывает, что в двоичных полях не требуется вводить перенос в операциях сложения и умножения, и что возведение в квадрат в двоичных полях очень эффективно, поскольку оно подчиняется упрощенному правилу )X + Y(2 = X2 + Y2.
128-битная строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле, или быть разбита на два 64-битных элемента поля Тау, четыре 32-битных элемента поля Тау, 16 8-битных элементов поля Тау или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, просто преобразование типа битовой строки, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут упаковываться в более крупные элементы поля без дополнительных вычислительных затрат. Протокол 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 улучшил существующий механизм PIOP SumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных многомерных полиномиальных проверок, предоставив более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства, основанных на двоичных полях.
( 2.3 PIOP: новый многомерный сдвиг аргумента------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются одной из ключевых технологий, которые эффективно генерируют и обрабатывают многочлены, производные от входных дескрипторов или других виртуальных многочленов. Вот два ключевых метода:
Упаковка: Этот метод оптимизирует операции, упаковывая меньшие элементы, находящиеся рядом в лексикографическом порядке, в более крупные элементы. Оператор Pack предназначен для блоков размером 2κ и комбинирует их в один элемент в многомерном пространстве. С помощью многолинейного расширения ) Multilinear Extension, MLE (, этот виртуальный многочлен можно эффективно оценивать и обрабатывать, преобразуя функцию t в другой многочлен, что улучшает вычислительную производительность.
Операторы сдвига: операторы сдвига повторно расположают элементы блока на основе заданного смещения o, выполняя циклический сдвиг. Этот метод подходит для блоков размером 2b, каждый блок выполняет сдвиг в зависимости от смещения. Операторы сдвига определяются с помощью функции поддержки, что обеспечивает согласованность и эффективность при обработке виртуальных многочленов. Оценка сложности этой конструкции линейно возрастает с увеличением размера блока, что особенно подходит для обработки больших наборов данных или высокоразмерных сцен в булевом гиперкубе.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP: адаптированная версия аргумента поиска Lasso------применимо к двоичному полю
Протокол Lasso позволяет доказателю зафиксировать вектор a ∈ Fm и доказать, что все его элементы существуют в заранее заданной таблице t ∈ Fn. Lasso раскрывает концепцию "поиска сингулярностей" )lookup singularities( и может применяться к схемам обязательств многочленов с многими линейными переменными. Его эффективность проявляется в следующих двух аспектах:
Эффективность доказательства: для m поисков в таблице размером n доказатель одной лишь необходимо подтвердить m+n элементарных полей. Эти элементарные поля очень малы и находятся в множестве {0,...,m}. В схеме подтверждения, основанной на множественных степеневых вычислениях, вычислительная стоимость доказателя составляет O)m + n### операций в группе( как
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
Binius: Оптимизация и инновации STARKs на основе бинарной области
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
В отличие от SNARKs, основанных на эллиптических кривых, STARKs можно рассматривать как SNARKs, основанные на хэшах. В настоящее время одной из основных причин низкой эффективности STARKs является то, что в большинстве реальных программ числовые значения довольно малы, такие как индексы циклов, логические значения, счетчики и т. д. Однако для обеспечения безопасности доказательства на основе дерева Меркла, при использовании кодирования Рида-Соломона для расширения данных, многие избыточные значения занимают все поле, даже если исходные значения очень малы. Для решения этой проблемы снижение размера поля становится ключевой стратегией.
Первое поколение кодирования STARKs имеет ширину 252 бита, второе поколение — 64 бита, третье поколение — 32 бита, но 32-битное кодирование все еще имеет много пустого места. В отличие от этого, двоичное поле позволяет напрямую работать с битами, кодирование компактно и эффективно, без потерь, что можно считать четвертым поколением STARKs.
В отличие от обнаруженных в последние годы конечных полей, таких как Goldilocks, BabyBear и Mersenne31, исследования двоичных полей восходят к 1980-м годам. В настоящее время двоичные поля широко применяются в криптографии, таких как поле AES(F28, поле GMAC)F2128, кодирование Рида-Соломона QR-кода(F28 и другие. Протоколы оригинального FRI и zk-STARK, а также хеш-функция Grøstl, прошедшая в финал SHA-3, также основаны на поле F28.
При использовании меньших полей операция расширения становится все более важной для обеспечения безопасности. Двоичное поле, используемое Binius, полностью зависит от расширения для обеспечения безопасности и доступности. Большинство вычислений Prover, связанных с многочленами, требует операций в базовом поле, что обеспечивает высокую эффективность в меньшем поле. Однако проверка случайной точки и вычисления FRI все еще должны проводиться в более широком расширенном поле для обеспечения необходимой безопасности.
При построении системы доказательств на основе двоичных полей существуют две практические проблемы:
Binius предложил инновационное решение для решения этих двух проблем:
Этот метод значительно повысил эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно включают в себя две части:
Доказательство полиномиального взаимодействия предсказателя информационной теории )PIOP(: В качестве ядра системы доказательства преобразует входные вычислительные отношения в проверяемые полиномиальные уравнения. Взаимодействуя с проверяющим, доказчик постепенно отправляет полиномы, позволяя проверяющему проверить правильность вычислений, запрашивая лишь небольшое количество полиномов для оценки результата. Существующие протоколы PIOP включают PLONK PIOP, Spartan PIOP и HyperPlonk PIOP и др.
Многочленное обещание )PCS(: Используется для доказательства того, выполняется ли полиномиальное равенство, сгенерированное PIOP. PCS — это криптографический инструмент, позволяющий доказателю зафиксировать определенный полином и позже проверить его оценку, скрывая при этом другую информацию о многочлене. Распространенные PCS включают KZG, Bulletproofs, FRI и Brakedown.
В зависимости от требований можно выбирать различные PIOP и PCS, а также сочетать их с подходящими конечными полями или эллиптическими кривыми, чтобы создать доказательные системы с различными свойствами. Например:
Binius включает пять ключевых технологий:
Артикуляция на основе башенной двоичной области: составление вычислительной основы, осуществление упрощенных операций в двоичной области
Адаптация проверки произведений и перестановок HyperPlonk: обеспечить эффективную проверку согласованности между переменными и перестановками
Новая многофакторная линейная доказательство: оптимизация эффективности проверки многофакторных отношений на малых областях
Улучшение доказательства поиска Lasso: обеспечение гибкости и безопасности механизма поиска
Малый полиномиальный комитет: реализация эффективной системы доказательства в двоичном поле, сокращение затрат, связанных с большим полем.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-1fb9ecbf9b3b2beaec758f3ab686a012.webp(
) 2.1 Ограниченные поля: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, в основном благодаря эффективным вычислениям и эффективной арифметике. Двоичная область по сути поддерживает высокоэффективные арифметические операции, что делает ее идеальным выбором для чувствительных к производительности криптографических приложений. Структура двоичной области поддерживает упрощенный процесс арифметики, операции, выполняемые на двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме. Эти характеристики в сочетании с возможностью полностью использовать иерархические особенности через башенную структуру, делают двоичную область особенно подходящей для таких масштабируемых систем доказательства, как Binius.
"канонический" обозначает уникальный и прямой способ представления элементов в двоичном поле. Например, в базовом двоичном поле F2 любая строка длиной k может быть напрямую сопоставлена с элементом двоичного поля длины k. Это отличается от простого поля, которое не может предоставить такое каноническое представление в заданном количестве бит. Хотя 32-битное простое поле может быть включено в 32 бита, не каждая 32-битная строка может уникально соответствовать элементу поля, в то время как двоичное поле обладает такой удобной взаимно однозначной соответствием.
В полях простых чисел Fp распространенные методы редукции включают редукцию Барретта, редукцию Монтгомери, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичных полях F2k часто используемые методы редукции включают специальную редукцию (, как AES использует ), редукцию Монтгомери ###, как POLYVAL использует (, и рекурсивную редукцию ), как Tower (.
Статья «Изучение пространства проектирования аппаратных реализаций ECC на простых полях и двоичных полях» указывает, что в двоичных полях не требуется вводить перенос в операциях сложения и умножения, и что возведение в квадрат в двоичных полях очень эффективно, поскольку оно подчиняется упрощенному правилу )X + Y(2 = X2 + Y2.
128-битная строка может быть интерпретирована различными способами в контексте двоичного поля. Она может рассматриваться как уникальный элемент в 128-битном двоичном поле, или быть разбита на два 64-битных элемента поля Тау, четыре 32-битных элемента поля Тау, 16 8-битных элементов поля Тау или 128 элементов поля F2. Эта гибкость представления не требует никаких вычислительных затрат, просто преобразование типа битовой строки, что является очень интересным и полезным свойством. В то же время, маленькие элементы поля могут упаковываться в более крупные элементы поля без дополнительных вычислительных затрат. Протокол 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 улучшил существующий механизм PIOP SumCheck, повысив гибкость и эффективность протокола, особенно при обработке более сложных многомерных полиномиальных проверок, предоставив более мощную функциональную поддержку. Эти улучшения не только устраняют ограничения HyperPlonk, но и закладывают основу для будущих систем доказательства, основанных на двоичных полях.
( 2.3 PIOP: новый многомерный сдвиг аргумента------применимо к булеву гиперкубу
В протоколе Binius конструкция и обработка виртуальных многочленов являются одной из ключевых технологий, которые эффективно генерируют и обрабатывают многочлены, производные от входных дескрипторов или других виртуальных многочленов. Вот два ключевых метода:
Упаковка: Этот метод оптимизирует операции, упаковывая меньшие элементы, находящиеся рядом в лексикографическом порядке, в более крупные элементы. Оператор Pack предназначен для блоков размером 2κ и комбинирует их в один элемент в многомерном пространстве. С помощью многолинейного расширения ) Multilinear Extension, MLE (, этот виртуальный многочлен можно эффективно оценивать и обрабатывать, преобразуя функцию t в другой многочлен, что улучшает вычислительную производительность.
Операторы сдвига: операторы сдвига повторно расположают элементы блока на основе заданного смещения o, выполняя циклический сдвиг. Этот метод подходит для блоков размером 2b, каждый блок выполняет сдвиг в зависимости от смещения. Операторы сдвига определяются с помощью функции поддержки, что обеспечивает согласованность и эффективность при обработке виртуальных многочленов. Оценка сложности этой конструкции линейно возрастает с увеличением размера блока, что особенно подходит для обработки больших наборов данных или высокоразмерных сцен в булевом гиперкубе.
![Bitlayer Research: Анализ принципов Binius STARKs и размышления об их оптимизации])https://img-cdn.gateio.im/webp-social/moments-7f96976952fd0f8da0e93ff1042a966d.webp###
( 2.4 PIOP: адаптированная версия аргумента поиска Lasso------применимо к двоичному полю
Протокол Lasso позволяет доказателю зафиксировать вектор a ∈ Fm и доказать, что все его элементы существуют в заранее заданной таблице t ∈ Fn. Lasso раскрывает концепцию "поиска сингулярностей" )lookup singularities( и может применяться к схемам обязательств многочленов с многими линейными переменными. Его эффективность проявляется в следующих двух аспектах: