1. Введение

В отличие от SNARK, основанных на эллиптических кривых, STARK можно рассматривать как SNARK, основанный на хэшах. Одно из основных проблем, приводящих к текущей неэффективности STARK, заключается в том, что большинство значений в фактических программах относительно небольшие, такие как индексы в циклах, булевые значения и счетчики. Однако, для обеспечения безопасности доказательств на основе дерева Меркла, используется кодирование Рида-Соломона для расширения данных, что приводит к появлению множества избыточных значений, занимающих всю область, даже когда сами исходные значения небольшие. Для решения этой неэффективности уменьшение размера поля стало ключевой стратегией.

Как показано в Таблице 1, у первого поколения STARKs была ширина кодирования 252 бита, у второго поколения - 64 бита, а у третьего поколения - 32 бита. Несмотря на уменьшение ширины кодирования в третьем поколении, остается значительное избыточное пространство. В отличие от этого, бинарные поля позволяют прямую манипуляцию на уровне битов, обеспечивая компактное и эффективное кодирование с минимальными потерями. Эта эффективность реализуется в четвертом поколении STARKs.

Table 1: STARKs Derivation Path

В сравнении с конечными полями, такими как Goldilocks, BabyBear и Mersenne31, которые недавно привлекли внимание, исследования бинарных полей восходят к 1980-м годам. Сегодня бинарные поля широко используются в криптографии, среди заметных примеров:

• Стандарт шифрования Advanced Encryption Standard (AES), основанный на
• 𝐹28
• поле;
• Код аутентификации сообщений Галуа (GMAC), основанный на
• Ф2128
• поле;
• QR-коды, использующие кодирование Рида-Соломона на основе
• Ф28
• поле;
• Оригинальные протоколы FRI и zk-STARK, а также хэш-функция Grøstl, финалист в соревновании SHA-3, которая основана на
• 𝐹28
• поле и хорошо подходит для рекурсивных хэш-алгоритмов.

При использовании меньших полей операции расширения полей становятся все более важными для обеспечения безопасности. Бинарное поле, используемое Binius, полностью основано на расширении полей для гарантии как безопасности, так и практической применимости. Большинство полиномиальных вычислений, выполняемых при операциях доказывателя, не нужно входить в расширенное поле, так как они должны только работать в базовом поле, что обеспечивает высокую эффективность в малом поле. Однако случайные проверки точек и вычисления FRI все равно должны выполняться в большем расширенном поле, чтобы гарантировать необходимый уровень безопасности.

При построении системы доказательств на основе бинарных полей существуют две практические проблемы: во-первых, размер поля, используемого для представления трассы в STARKs, должен быть больше степени полинома. Во-вторых, размер поля, используемого для фиксации дерева Меркля в STARKs, должен быть больше размера после расширения кодирования Рида-Соломона.

Binius - инновационное решение для решения этих двух проблем путем представления одних и тех же данных двумя различными способами: Во-первых, путем использования многомерных (в частности, многолинейных) полиномов вместо одномерных полиномов, представляя всю вычислительную трассу через их оценки на “hypercubes”. Во-вторых, поскольку каждое измерение гиперкуба имеет длину 2, невозможно выполнить стандартные расширения Рида-Соломона, как в STARKs, но гиперкуб можно рассматривать как квадрат, и на основе этого квадрата можно выполнить расширение Рида-Соломона. Этот метод не только обеспечивает безопасность, но и значительно повышает эффективность кодирования и вычислительную производительность.

2. Принципы Binius

Построение большинства современных систем SNARK обычно состоит из следующих двух компонентов:

• Информационно-теоретико-полиномиальное интерактивное доказательство оракула (PIOP): Являясь ядром системы доказательств, PIOP преобразует вычислительные соотношения из входных данных в верифицируемые полиномиальные уравнения. Различные протоколы PIOP позволяют доказывающему отправлять полиномы инкрементно через взаимодействие с верификатором. Это позволяет верификатору подтвердить правильность вычисления, запрашивая только небольшое количество полиномиальных вычислений. Различные протоколы PIOP, такие как PLONK PIOP, Spartan PIOP и HyperPlonk PIOP, по-разному обрабатывают полиномиальные выражения, влияя на производительность и эффективность всей системы SNARK.
• Схема обязательства полиномом (PCS): PCS - криптографический инструмент, используемый для доказательства правильности полиномиальных уравнений, созданных PIOP. Он позволяет доказывающему зафиксировать полином и проверить его оценки, не раскрывая дополнительной информации о полиноме. Распространенными схемами PCS являются KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP) и Brakedown, каждая из которых предлагает отличающиеся характеристики производительности, гарантии безопасности и применимые сценарии.

Выбирая различные схемы PIOPs и PCS и комбинируя их с подходящими конечными полями или эллиптическими кривыми, можно построить системы доказательств с различными свойствами. Например:

• Halo2: Сочетает PLONK PIOP с Bulletproofs PCS и работает на кривой Pasta. Halo2 разработан с учетом масштабируемости и устраняет доверенную настройку, ранее использовавшуюся в протоколе ZCash.
• Plonky2: Сочетает PLONK PIOP с FRI PCS и основан на поле Goldilocks. Plonky2 оптимизирован для эффективной рекурсии.

При проектировании этих систем важна совместимость выбранного PIOP, PCS и конечного поля или эллиптической кривой для обеспечения правильности, производительности и безопасности. Эти комбинации влияют на размер SNARK-доказательства, эффективность верификации и определяют, может ли система достичь прозрачности без доверенной настройки, а также поддерживать расширенные функции, такие как рекурсивные доказательства или агрегация доказательств.

Binius combines HyperPlonk PIOP with Brakedown PCS and operates in a binary field. Specifically, Binius incorporates five key technologies to achieve both efficiency and security:

1. Арифметика на основе башен бинарных полей: это обеспечивает вычислительную основу Binius, позволяющую упрощать операции в бинарном поле.
2. Продукт HyperPlonk и проверки перестановок: Binius адаптирует проверки продукта и перестановок HyperPlonk в своем PIOP, чтобы обеспечить безопасную и эффективную согласованность между переменными и их перестановками.
3. Новый аргумент множественного сдвига: эта оптимизация улучшает проверку множественных отношений внутри малых полей, повышая общую эффективность.
4. Улучшенный аргумент Lasso lookup: Протокол включает более гибкий и безопасный механизм поиска с помощью этого передового аргумента.
5. Схема фиксации полинома малого поля (PCS): Binius использует PCS, созданный для малых полей, что уменьшает накладные расходы, обычно связанные с более крупными полями, и обеспечивает эффективную систему доказательств в двоичном поле.

Благодаря этим инновациям Binius может предложить компактную, высокопроизводительную систему SNARK, оптимизированную для бинарных полей с обеспечением надежной безопасности и масштабируемости.

2.1 Конечные поля: арифметика, основанная на башнях двоичных полей

Башни двоичных полей играют ключевую роль в достижении быстрых и проверяемых вычислений благодаря двум основным факторам: эффективному вычислению и эффективной арифметизации. Двоичные поля по своей сути поддерживают высокоэффективные арифметические операции, что делает их идеальными для криптографических приложений, требующих высокой производительности. Более того, их структура позволяет упрощенный процесс арифметизации, при котором операции, выполняемые в двоичных полях, могут быть представлены в компактных и легко проверяемых алгебраических формах. Эти характеристики, в сочетании с иерархической структурой башен двоичных полей, делают их особенно подходящими для масштабируемых систем доказательств, таких как Binius.

Термин "канонический" относится к уникальному и прямому представлению элементов в бинарном поле. Например, в самом базовом бинарном поле $\mathbb{F}2

,anyk−bitstringможет быть напрямую отображен toak−bitbinaryfieldelement.Это отличается от простых полей, которые не предлагают такого канонического представления с заданным числом битов.Хотя32−битное простое поле может поместиться в пределах 32 бит, обратите внимание, что очень32−битстрокаможет уникально соответствовать элементу поля, тогда как двоичные поля обеспечивают этоодин−к-одномусопоставлению.Inprimeполей

$\ mathbb {F}_p$ , общие методы сокращения включают сокращение Барретта, сокращение Монтгомери, а также специализированные методы сокращения для определенных конечных полей, таких как Мерсенна-31 или Голдилокс-64. В двоичных полях $\ mathbb {F} {2 ^ k}$ общие методы сокращения включают специальное сокращение (как в AES), сокращение Монтгомери (как в POLYVAL) и рекурсивное сокращение (как в полевых башнях). Статья Исследование пространства проектирования аппаратной реализации ECC с использованием простого поля и двоичного поляотмечает, что в двоичных полях не требуется перенос при сложении или умножении, а возведение в квадрат в двоичных полях высокоэффективно благодаря правилу упрощения

(𝑋+𝑌)2=𝑋2+𝑌2

.

Рис. 1. Башни Бинарного поля

Как показано на рисунке 1, 128-битная строка может быть интерпретирована несколькими способами в контексте двоичного поля. Его можно рассматривать как уникальный элемент в 128-битном двоичном поле или как два 64-битных элемента поля башни, четыре 32-разрядных элемента поля башни, шестнадцать 8-битных элементов поля башни или 128 элементов поля башни

Ф2

Эта гибкость представления не влечет за собой вычислительных издержек, поскольку это всего лишь приведение типа битовой строки. Это очень интересное и полезное свойство, поскольку меньшие элементы поля могут быть упакованы в большие элементы поля без дополнительных вычислительных затрат. Протокол Binius использует это свойство для повышения вычислительной эффективности. Кроме того, статья...О эффективной инверсии в башенных полях характеристики два исследует вычислительную сложность умножения, возведения в квадрат и инверсии в

𝑛

битовая башня двоичных полей (раскладываемая на

м

-битные подполя).

2.2 PIOP: Адаптированный продукт HyperPlonk и проверка перестановки — подходит для бинарных полей

Дизайн PIOP в протоколе Binius черпает вдохновение из HyperPlonk и включает серию основных проверок для проверки правильности полиномов и многомерных наборов. Эти проверки являются важными для обеспечения целостности вычислений внутри системы доказательств, особенно при работе с бинарными полями. Ключевые проверки включают:

1. gateCheck: Обеспечивает, что приватный свидетель
2. 𝜔
3. и общественный ввод
4. 𝑥
5. удовлетворить отношение работы схемы
6. 𝐶(𝑥,𝜔)=0
7. , проверка правильного выполнения схемы.
8. PermutationCheck: Проверяет результаты оценки двух многопеременных полиномов
9. 𝑓
10. и
11. 𝑔
12. на булевом гиперкубе формируют перестановочное отношение
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , обеспечивая согласованность между переменными полинома.
15. LookupCheck: Проверяет, находится ли вычисление полинома в заданной таблице поиска, т.е.
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. обеспечивая, что определенные значения попадают в указанный диапазон.
18. MultisetCheck: Подтверждает, являются ли два многомерных набора равными, т.е. ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, обеспечивая согласованность между различными наборами.
19. ProductCheck: Обеспечивает, чтобы оценка рационального полинома на булевом гиперкубе равнялась заявленному значению, т.е.,
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , подтверждая правильность многочлена произведения.
22. ZeroCheck: Проверяет, вычисляется ли многочлен нескольких переменных в нуль в любой точке на булевой гиперкубе, т. е.,
23. ∏𝑥∈𝐻𝜇𝑓(𝑥)=0
24. для всех
25. 𝑥∈𝐁𝜇
26. , обеспечивая правильное распределение нулей в полиноме.
27. SumCheck: Подтверждает, равна ли сумма оценок многомерного многочлена заявленному значению, т.е.,
28. ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
29. . Путем сведения оценки многомерных полиномов к оценке одномерных полиномов снижается вычислительная сложность верификатора. SumCheck также позволяет использовать пакетную обработку, которая строит линейные комбинации с использованием случайных чисел для пакетной обработки нескольких экземпляров.
30. BatchCheck: Расширение SumCheck, которое проверяет правильность нескольких оценок многочленов с несколькими переменными, увеличивая эффективность протокола.

Хотя протоколы Binius и HyperPlonk имеют несколько сходств в их конструкциях, Binius вводит следующие ключевые улучшения:

1. Оптимизация ProductCheck: В HyperPlonk для ProductCheck требуется знаменатель
2. 𝑈
3. чтобы быть ненулевым во всем гиперкубе и чтобы произведение соответствовало определенному значению. Binius упрощает эту проверку, устанавливая значение произведения равным 1 и уменьшая общую вычислительную сложность.
4. Решение проблем с нулевым делением: HyperPlonk не решает эффективно проблемы с нулевым делением, что затрудняет обеспечение
5. 𝑈
6. остается ненулевым над гиперкубом. Binius разрешает это, обрабатывая сценарии деления на ноль правильно, позволяя ProductCheck функционировать даже при нулевом знаменателе, позволяя расширяться до произвольных значений продукта.
7. Cross-Column PermutationCheck: HyperPlonk lacks support for cross-column permutation checks. Binius addresses this limitation by introducing support for cross-column PermutationCheck, enabling the protocol to manage more complex polynomial permutations across multiple columns.

Таким образом, Binius улучшает гибкость и эффективность протокола путем улучшения существующего механизма PIOP SumCheck, особенно путем предоставления более сильной функциональности для проверки более сложных многочленов нескольких переменных. Эти улучшения не только решают ограничения HyperPlonk, но и заложить основу для будущих систем, основанных на двоичных полях.

2.3 PIOP: Новый мультинейный аргумент сдвига — применимый к булевому гиперкубу

В протоколе Binius манипуляция и построение виртуальных полиномов играют важную роль в обеспечении эффективной обработки полиномов. Для этих операций используются две основные техники:

• Упаковка: Метод упаковки оптимизирует обработку более мелких элементов, группируя их в более крупные домены. Конкретно, элементы, соседние в лексикографическом порядке, упаковываются в более крупные блоки, обычно размером
• 2𝜅
• . С помощью многолинейного расширения (MLE) упакованные элементы преобразуются в новый виртуальный полином, который затем может быть эффективно оценен и обработан. Этот метод повышает производительность операций на булевом гиперкубе путем перестройки функции
• 𝑡
• вычислительно эффективной формы.
• Оператор сдвига: оператор сдвига переставляет элементы внутри блока, циклически сдвигая их на заданный сдвиг
• o
• . Это изменение применяется к блокам размером
• 2𝑏
• , обеспечивая равномерное смещение всех элементов в блоке в соответствии с предопределенным смещением. Этот оператор особенно полезен при работе с виртуальными полиномами в высокомерных пространствах, поскольку его сложность линейно возрастает с размером блока, что делает его идеальным методом для обработки больших наборов данных или сложных вычислений на булевой гиперкубе.

2.4 PIOP: Адаптированный аргумент поиска Lasso - применимый к бинарным полям

Протокол Lasso в Binius предлагает высокоэффективный способ доказательства элементов вектора

𝑎∈𝐹𝑚

содержатся в заранее определенной таблице

𝑡∈𝐹𝑛

. Этот аргумент поиска вводит концепцию «Lookup Singularity» и хорошо подходит для многолинейных схем обязательств полиномов. Эффективность Lasso подчеркивается в двух основных аспектах:

• Эффективность доказательств: При проведении
• 𝑚
• поиск в таблице размером
• 𝑛
• , производитель должен только обязаться
• 𝑚+𝑛
• небольшие элементы поля, размер поля выбирается из набора
• 0,…,𝑚
• . В криптографических схемах, основанных на возведении в степень, затраты доказательства составляют
• 𝑂(𝑚+𝑛)
• групповые операции (например, сложение точек на эллиптической кривой). Эта эффективность добавляется к стоимости проверки соответствия многолинейного полинома, вычисленного на булевом гиперкубе, элементу таблицы.
• Нет обязательств по большим столам : Если таблица
• 𝑡
• имеет структуру, Lasso не требует прямого обязательства к таблице, что позволяет обрабатывать очень большие таблицы (например,
• 2128
• и более). Время работы доказателя зависит исключительно от конкретных записей, к которым обращается в таблице. Для любого целочисленного параметра
• 𝑐>1
• , основная стоимость связана с размером доказательства, который растет как
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• Зафиксированные элементы поля. Эти элементы тоже небольшие, взятые из набора
• 0,…,max𝑚,𝑛1/𝑐,𝑞−1
• , где
• 𝑞
• является наибольшим значением вектора
• 𝑎
• .

Протокол Lasso состоит из трех основных компонентов:

1. Виртуальная полиномиальная абстракция больших таблиц: протокол Lasso объединяет виртуальные полиномы, чтобы обеспечить эффективный поиск и операции с большими таблицами, обеспечивая масштабируемость без снижения производительности.
2. Поиск по малой таблице: В основе Lasso лежит поиск по малой таблице, который проверяет, является ли виртуальный полином, вычисленный на булевом гиперкубе, подмножеством оценок другого виртуального полинома. Этот процесс подобен обнаружению в офлайн-памяти и сводится к задаче обнаружения мультимножества.
3. Multiset Check: Протокол также включает виртуальный механизм для выполнения мультимножественных проверок, обеспечивая соответствие или выполнение заранее определенных условий двух наборов элементов.

Протокол Binius адаптирует Lasso для бинарных операций над полями, предполагая, что текущее поле является простым полем большой характеристики (гораздо большей, чем длина столбца, который ищется). Binius вводит мультипликативную версию протокола Lasso, требующую от доказывающего и проверяющего операции увеличения <<счетчика памяти>> протокола не просто на 1, а увеличивающую с помощью мультипликативного генератора в рамках бинарного поля. Однако, эта мультипликативная адаптация вносит дополнительную сложность: в отличие от аддитивного увеличения, мультипликативный генератор не увеличивается во всех случаях, вместо этого имея единичную орбиту на 0, что может представлять вектор атаки. Чтобы смягчить этот потенциальный риск, доказывающий должен привязаться к вектору счетчика чтения, который не равен нулю везде, чтобы обеспечить безопасность протокола.

2.5 PCS: Адаптированный Brakedown PCS—Применимо к малым полям

Основная идея создания схемы коммитмента полиномов (Polynomial Commitment Scheme, PCS) Binius заключается в упаковке. В статье Binius представлены две схемы коммитмента полиномов Brakedown на основе двоичных полей: одна, использующая конкатенированные коды, и другая, использующая кодирование на уровне блока, которое поддерживает автономное использование кодов Рида-Соломона. Вторая схема коммитмента полиномов Brakedown упрощает процесс доказательства и проверки, хотя размер доказательства немного больше, чем у первой; однако это компромисс стоит того, благодаря упрощению и преимуществам реализации, которые она предлагает.

Многочлен обязательства Binius в первую очередь использует обязательство многочлена в малом поле с оценками в расширенном поле, универсальную конструкцию в малом поле и блочное кодирование с использованием техник кодирования Рида-Соломона.

Коммитмент полинома малого поля с расширенной оценкой поля В протоколе Binius коммитменты полиномов выполняются над малым полем

𝐾

, с оценками, проходящими в расширенном поле

𝐿/𝐾

. Этот метод гарантирует, что многолинейный полином

𝑡(𝑋0,…,𝑋ℓ−1)

принадлежит к домену

𝐾[𝑋0,…,𝑋ℓ−1]

, в то время как баллы оценки находятся в более крупном поле

𝐿

. Эта структура обязательств позволяет эффективные запросы в рамках расширенного поля, обеспечивая баланс между безопасностью и вычислительной эффективностью.

Малые Универсальные Строительные Работы Этот строительный проект определяет ключевые параметры, такие как поле

𝐾

, его размерность

ℓ

, и связанный линейный блочный код

𝐶

, обеспечивая одновременно расширенное поле

𝐿

достаточно велико для безопасных оценок. Пользуясь свойствами расширенного поля, Binius достигает надежных обязательств через линейные блочные коды, поддерживая баланс между вычислительной эффективностью и безопасностью.

Кодирование на уровне блока с кодами Рида-Соломона для многочленов, определенных над малыми полями, например, $ \ mathbb {F} 2

,𝑡ℎ𝑒𝐵𝑖𝑛𝑖𝑢𝑠𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙𝑒𝑚𝑝𝑙𝑜𝑦𝑠𝑏𝑙𝑜𝑐𝑘−𝑙𝑒𝑣𝑒𝑙𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑢𝑠𝑖𝑛𝑔𝑅𝑒𝑒𝑑−𝑆𝑜𝑙𝑜𝑚𝑜𝑛𝑐𝑜𝑑𝑒𝑠.𝑇ℎ𝑖𝑠𝑠𝑐ℎ𝑒𝑚𝑒𝑎𝑙𝑙𝑜𝑤𝑠𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑜𝑓𝑠𝑚𝑎𝑙𝑙−𝑓𝑖𝑒𝑙𝑑𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙𝑠𝑏𝑦𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑡ℎ𝑒𝑚𝑟𝑜𝑤−𝑏𝑦−𝑟𝑜𝑤𝑖𝑛𝑡𝑜𝑙𝑎𝑟𝑔𝑒𝑟𝑓𝑖𝑒𝑙𝑑𝑠(𝑠𝑢𝑐ℎ𝑎𝑠

\mathbb{F}{2^{16}}$ ), используя эффективность и свойства максимально удаленного кодирования Рида-Соломона. После кодирования эти строки фиксируются с использованием дерева Меркля, что упрощает операционную сложность фиксации полиномиальных коммитов в малых полях. Этот подход позволяет эффективно обрабатывать полиномы в малых полях без вычислительной нагрузки, обычно связанной с большими полями.

3. Оптимизация Биниуса

Для дальнейшего улучшения производительности Binius включает четыре основных оптимизации:

1. PIOP на основе GKR: протокол GKR (Goldreich-Kalai-Rothblum) используется для замены алгоритма Lasso Lookup в умножении бинарных полей, что значительно сокращает накладные расходы в процессе фиксации.
2. ZeroCheck PIOP Optimization : Эта оптимизация решает баланс между вычислительными затратами доказателя и проверяющего, делая операцию ZeroCheck более эффективной за счет более эффективной распределения нагрузки.
3. Оптимизация Sumcheck PIOP: Оптимизируя процесс малых полей Sumcheck, Binius снижает общую вычислительную нагрузку при работе с малыми полями.
4. Оптимизация PCS: С использованием оптимизации FRI-Binius (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) Binius уменьшает размер доказательства и повышает производительность протокола, улучшая общую эффективность как генерации, так и проверки доказательств.

3.1 GKR-основанный PIOP: Умножение двоичного поля с использованием GKR

В исходном протоколе Binius умножение бинарного поля обрабатывается через схему на основе поиска, которая связывает умножение с линейными операциями сложения на основе количества конечностей в слове. Хотя этот метод оптимизирует бинарное умножение в определенной степени, он все равно вводит вспомогательные обязательства линейно, связанные с количеством конечностей. Приняв подход, основанный на GKR, протокол Binius может значительно сократить количество необходимых обязательств, что приводит к дальнейшему повышению эффективности операций умножения бинарного поля.

Основная идея протокола GKR (Goldwasser-Kalai-Rothblum) заключается в достижении согласия между доказывающим (P) и верификатором (V) по слоистой арифметической схеме на конечном поле

𝐹

. Каждый узел в этой схеме имеет два входа для вычисления необходимой функции. Для уменьшения вычислительной сложности Проверяющего протокол использует протокол SumCheck, который постепенно уменьшает утверждения о значениях выходных ворот схемы до значений ворот более низкого уровня, в конечном итоге упрощая утверждения до заявлений о входах. Таким образом, Проверяющему нужно только проверить правильность входов схемы.

Алгоритм умножения целых чисел на основе GKRв Binius преобразует проверку того, являются ли два 32-битных целых числа

𝐴

и

𝐵

удовлетворять

A⋅B=?C

в проверке, либо

(𝑔𝐴)𝐵=?𝑔𝐶

держит в

𝐹264∗

. Это преобразование в сочетании с протоколом GKR значительно снижает накладные расходы, связанные с полиномиальными обязательствами. По сравнению с предыдущей схемой, основанной на поиске Binius, подход умножения на основе GKR требует только одного вспомогательного обязательства и снижает стоимость SumChecks, что делает алгоритм более эффективным, особенно в тех случаях, когда SumCheck более экономичны, чем дополнительные обязательства. Этот метод становится перспективным решением для минимизации затрат на обязательства по бинарным полям полиномов по мере прогресса оптимизации Binius.

3.2 ZeroCheck PIOP Optimization: Балансировка вычислительных затрат между доказывающим и проверяющим

Статья Некоторые улучшения для PIOP для ZeroCheckпредлагает стратегии балансировки вычислительных затрат между доказывающим (P) и проверяющим (V), с фокусом на снижение передачи данных и вычислительной сложности. Ниже приведены основные техники оптимизации:

• Уменьшение передачи данных Prover

Переложив часть вычислительной нагрузки на Проверяющего, можно минимизировать передачу данных Доказывающего. Например, в раунде

я

, провер отправляет

𝑣𝑖+1(𝑋)

для

𝑋=0,…,𝑑+1

, и Verifier проверяет, является ли

vi=vi+1(0)+vi+1(1)

держится.

Оптимизация: Прувер может избежать отправки

vi+1(1)

, поскольку Проверяющий может вычислить это как

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

В начальном раунде Прувер отправляет

𝑣1(0)=𝑣1(1)=0

, устраняя некоторые расчеты оценки, что уменьшает как вычислительные, так и трансмиссионные издержки до

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• Сокращение количества оценочных точек для доказывающего лица

Во время раунда

я

, Профер должен отправить

𝑣𝑖+1(𝑋)

, рассчитывается как

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Оптимизация: Вместо этого доказатель может отправить

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

где $v_i(X) = v_i’(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\alpha

и

r

,𝑡ℑ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓

v_i(Х)

,𝑟𝑒𝑑𝑢𝑐𝑖𝑛𝑔𝑡ℎ𝑒𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛𝑝𝑜𝑖𝑛𝑡𝑠.𝑇ℎ𝑒𝑖𝑛𝑡𝑒𝑟−𝑟𝑜𝑢𝑛𝑑𝑐ℎ𝑒𝑐𝑘𝑐𝑎𝑛𝑡ℎ𝑒𝑛𝑏𝑒𝑠𝑖𝑚𝑝𝑙𝑖𝑓𝑖𝑒𝑑𝑎𝑠

(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),

тем самым снижая потребности в передаче данных и повышая эффективность.С этими улучшениями общая стоимость составляет примерно

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

𝐹𝑜𝑟

d = 3$, эти оптимизации позволяют снизить стоимость в 5/3 раза.

• Алгебраическая оптимизация интерполяции

Для честного доказателя, полиномиальный

𝐶(𝑥0,…,𝑥𝑛−1)

ноль на

𝐻𝑛

и может быть выражено как

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Где

𝑄𝑖

вычисляется через упорядоченное полиномиальное деление, начиная с

𝑅𝑛=𝐶

. Последовательное деление на

𝑥𝑖(𝑥𝑖−1)

вычисляет

𝑄𝑖

и

𝑅𝑖

, с

𝑅0

представляющий мультилинейное расширение

𝐶

на

𝐻𝑛

, предполагается, что это ноль.

Анализ степеней

QI

. Для

Дж>И

,

𝑄𝑗

остается на том же уровне в

кси

как

𝐶

. Для

𝑗=𝑖

, степень уменьшается на 2 и для

𝑗<𝑖

, степень не превышает 1. Учитывая вектор

𝑟=(𝑟0,…,𝑟𝑖)

,

𝑄𝑗(𝑟,𝑋)

многолинейна для всех

𝑗≤𝑖

. Кроме того,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

является уникальным мультилинейным полиномом, соответствующим

𝐶(𝑟,𝑋)

на

𝐻𝑛−𝑖

. Для любого

𝑋

и

𝑥∈𝐻𝑛−𝑖−1

, это можно представить как

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Таким образом, во время каждого раунда протокола создается новый

𝑄

введена и ее оценка может быть выведена из

𝐶

и предыдущий

𝑄

, позволяющий оптимизировать интерполяцию.

3.3 Оптимизация Sumcheck PIOP: Протокол Sumcheck для малых полей

В протоколе STARKs, реализованном Binius, основным узким местом для доказывающего лица часто является протокол проверки суммы, а не Схема полиномиальных обязательств (PCS), из-за низкой стоимости обязательства.

Рисунок 2. Взаимосвязь между раундом переключения и улучшением фактора

В 2024 году Ingonyama предложилаулучшения для протоколов Sumcheck на основе малых полей, сосредоточившись на алгоритмах 3 и 4. Эти улучшения были внедрены и выложены в открытый доступ здесь. Алгоритм 4 включает алгоритм Карацубы в Алгоритм 3, уменьшая количество умножений в расширенном поле в обмен на большее количество умножений в базовом поле. Такой подход более эффективен, когда умножения в расширенном поле обходятся дороже, чем умножения в базовом поле.

1. Влияние раундов переключения и факторы улучшения Оптимизация протокола Sumcheck для малых полей зависит от выбора оптимального раунда переключения

𝑡

, который отмечает возврат протокола от оптимизированной версии к наивному алгоритму. Эксперименты показывают, что коэффициент улучшения достигает пика в оптимальной точке переключения, а затем следует параболическому тренду. При превышении этой точки эффективность снижается, так как соотношение между умножениями базового поля и поля расширения больше в меньших полях, что требует своевременного возврата к наивному алгоритму.

Для некоторых приложений, таких как Cubic Sumcheck (

𝑑=3

), протокол Sumcheck с малым полем обеспечивает улучшение порядка величины по сравнению с наивным подходом. Например, в базовом поле

𝐺𝐹[2]2. Влияние размера базового поля на производительность. Меньшие базовые поля (например,

, Алгоритм 4 превосходит наивный алгоритм почти в 30 раз.

ГФ[2]

) значительно повысить эффективность оптимизируемого алгоритма за счет большей разницы между затратами на умножение поля расширения и базового поля. Это приводит к более существенному коэффициенту улучшения оптимизированного алгоритма.

1. Оптимизационные выгоды от алгоритма Карацубы Алгоритм Карацубы играет решающую роль в повышении производительности протокола Sumcheck с малым полем. Для базового поля

𝐺𝐹[2]

, алгоритм 4 достигает пиковых коэффициентов улучшения, равных 6 для алгоритма 3 и 30 для алгоритма 4, что указывает на то, что алгоритм 4 в пять раз эффективнее алгоритма 3. Алгоритм Карацубы повышает эффективность выполнения и оптимизирует точку переключения для обоих алгоритмов, при этом оптимальные точки находятся на уровне

𝑡=5

для Алгоритма 3 и

𝑡=8

для Алгоритма 4.

1. Улучшение памяти. Протокол малого поля Sumcheck также повышает эффективность использования памяти. Алгоритм 4 требует

𝑂(𝑑⋅𝑡)

память, в то время как Алгоритм 3 нуждается в

O(2d⋅t)

память. Для

𝑡=8

, алгоритм 4 использует всего 0,26 МБ памяти по сравнению с 67 МБ, требуемыми алгоритмом 3. Это делает Алгоритм 4 особенно подходящим для сред с ограниченным объемом памяти, таких как проверка на стороне клиента с ограниченными ресурсами.

3.4 Оптимизация PCS: FRI-Binius Уменьшение размера доказательства Binius

Одной из основных проблем протокола Binius является относительно большой размер доказательства, который масштабируется с квадратным корнем размера свидетельства на

𝑂(𝑁)

. Это масштабирование квадратного корня ограничивает его конкурентоспособность по сравнению с системами, предлагающими более краткие доказательства. В отличие от полилогарифмических размеров доказательств, достигаемых передовыми системами, такими как Plonky3, с использованием техник, таких как FRI, важно обеспечить по-настоящему «краткие» проверяющие. Оптимизация FRI-Binius направлена на уменьшение размера доказательства Binius и улучшение его общей производительности по сравнению с более эффективными системами.

БумагаПолилогарифмические доказательства для многолинейных над бинарными башнями, известный как FRI-Binius, вводит новый механизм сгибания FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) на основе двоичного поля с четырьмя ключевыми инновациями:

• Выровненные многочлены: Преобразует начальный многолинейный многочлен в основу многочлена с низкой высотой кода (LCH) для оптимизированных вычислений.
• Subspace Vanishing Polynomials: Использует эти полиномы в сочетании с аддитивным NTT (теоретико-числовым преобразованием) для включения БПФ-подобного разложения, оптимизируя операции над полем коэффициентов.
• Алгебраическое упаковочное основание: облегчает эффективную упаковку данных, минимизируя накладные расходы протокола, связанные с встраиванием.
• Ring-Switching SumCheck: новая оптимизация SumCheck с использованием техник переключения кольца для дальнейшего улучшения производительности.

Основной процесс схемы коммитмента многолинейного полинома FRI-Binius (PCS)

Протокол FRI-Binius оптимизирует схемы обязательств многолинейных полиномов (PCS) над бинарным полем, преобразуя исходный многолинейный полином, определенный над бинарным полем

𝐹2

в мультилинейный полином над более крупным полем

𝐾

.

1. Фаза обязательства В фазе обязательства происходит преобразование
2. ℓ
3. -переменный мультилинейный многочлен (над $\mathbb{F}2
4. Интокоммитментфорапакед
5. \ell’
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. (\mathbb{F}{2^{128}}$ ). Этот процесс сокращает количество коэффициентов в 128 раз, что позволяет более эффективно генерировать доказательства.
8. Фаза оценки. В этой фазе проверяющий и подтверждающий выполняют
9. ℓ′
10. раунды протокола переключения кольцевого кросс-проверки SumCheck в сочетании с интерактивными оракульными доказательствами близости (IOPP). Ключевые детали включают в себя:
    • Доказательства открытия FRI: они составляют основную часть размера доказательства и обрабатываются аналогично стандартным доказательствам FRI над большими полями.
    • Стоимость проверки суммы Prover: Сравнима с затратами на выполнение SumCheck в большом поле.
    • FRI-стоимость верификатора: Соответствует стандартным FRI-затратам, наблюдаемым в реализациях для больших полей.
    • Операции верификатора: верификатор получает 128 элементов от
    • 𝐹2128
    • и выполняет 128 дополнительных умножений, что позволяет эффективную проверку.

Преимущества FRI-Binius

Применяя этот метод, Binius способен уменьшить размер своих доказательств на порядок, что приближает его к производительности современных криптографических систем, сохраняя совместимость с бинарными полями. Метод свертки FRI, оптимизированный для бинарных полей, в сочетании с алгебраической упаковкой и оптимизациями SumCheck, помогает Binius генерировать более компактные доказательства без ущерба для эффективности верификации.

Это преобразование является значительным шагом к улучшению размера доказательства в Binius, обеспечивая его большую конкурентоспособность с другими передовыми системами, особенно теми, которые сосредоточены на полилогарифмическом размере доказательств.

Таблица 2: Сравнение размеров доказательств Binius и FRI-Binius

Таблица 3: Сравнение Plonky3 FRI и FRI-Binius

4. Заключение

Вся ценность Binius заключается в его способности использовать наименьший размер поля в степени двух для следящих серверов, выбирая размер поля по мере необходимости. Binius — это схема совместного проектирования для «аппаратного, программного обеспечения и протоколов Sumcheck с ускорением FPGA», обеспечивающая быструю проверку при очень низком использовании памяти.

Системы доказательств, такие как Halo2 и Plonky3, включают четыре ключевых вычислительно интенсивных шага: генерация данных свидетельства, фиксация данных свидетельства, выполнение аргумента исчезновения и генерация открывающего доказательства.

Например, с функцией хеширования Keccak в Plonky3 и функцией хеширования Grøstl в Binius вычислительное распределение для этих четырех ключевых шагов иллюстрируется на рисунке 3.

Рисунок 3. Меньшие затраты на фиксацию

Это сравнение показывает, что Binius в основном устраняет узкое место в обязательстве доказателя. Новое узкое место - протокол Sumcheck, где проблемы, такие как многочисленные вычисления полинома и умножения в поле, могут быть эффективно решены специализированным оборудованием.

Схема FRI-Binius, вариант FRI, предлагает высокоэффективный вариант, устраняя накладные расходы на встраивание из слоя доказательства поля без значительного увеличения стоимости в агрегированном слое доказательства.

В настоящее время команда Irreducible разрабатывает свой рекурсивный слой иобъявлено о партнерстве с командой Polygon для создания zkVM на основе Binius; тем Jolt zkVM переходит с Lasso на Binius для повышения рекурсивной производительности; и Команда Ingonyama реализует FPGA-версию Binius.

Ссылки

1. 2024.04 Binius Краткие аргументы о башнях двоичных полей
2. 2024.07 Пт-Биниус Полилогарифмические доказательства для мультилинейных функций над двоичными башнями
3. Умножение целых чисел в Binius: подход на основе GKR в 2024.08 году
4. 2024.06 zkStudyClub - FRI-Binius: Полилогарифмические доказательства для многолинейных функций над двоичными башнями
5. 2024.04 ZK11: Binius: аппаратно оптимизированный SNARK - Джим Позен
6. Эпизод 303: Погружение в Биниус с Ульветанной, декабрь 2023 года
7. 2024.09 Проектирование высокопроизводительных zkVMs
8. 2024.07 Sumcheck и Open-Binius
9. 2024.04 Binius: высокоэффективные доказательства над бинарными полями
10. 2023.12 SNARK на бинарных полях: Binius - Часть 1
11. 2024.06 SNARKs на бинарных полях: Binius - Часть 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, система zk-proof для ZKEVMs

Отказ от ответственности:

1. Эта статья перепечатана с [bitlayer]. Все авторские права принадлежат автору оригинала [Линделл]. Если у вас есть возражения к этой перепечатке, пожалуйста, свяжитесь с Gate Learnкоманда, и они оперативно справятся с этим.
2. Ответственность за отказ: Взгляды и мнения, выраженные в этой статье, являются исключительно мнениями автора и не являются инвестиционными советами.
3. Переводом статьи на другие языки занимается команда gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.