Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, но для обеспечения безопасности доказательства на основе дерева Меркла при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область. Для решения этой проблемы снижение размера области стало ключевой стратегией.
Первое поколение STARKs имеет ширину кодирования 252 бита, второе поколение - 64 бита, третье поколение - 32 бита, но при этом ширина кодирования в 32 бита все еще имеет большое количество неиспользуемого пространства. По сравнению с этим, двоичное поле позволяет напрямую оперировать битами, кодирование компактно и эффективно, без каких-либо неиспользуемых пространств, то есть четвертое поколение STARKs.
При использовании меньших полей операция расширения полей становится все более важной для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения полей для обеспечения своей безопасности и фактической работоспособности. Большинство многочленов, участвующих в вычислениях Prover, не требуют расширения полей и могут работать только в базовом поле, что обеспечивает высокую эффективность в небольшом поле. Тем не менее, случайная проверка точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимого уровня безопасности.
При построении системы доказательств на основе бинарного поля существуют 2 практические проблемы: при вычислении представления следа в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве Меркле-дерева в STARKs требуется выполнить кодирование Рида-Соломона, размер используемого поля должен превышать размер после расширения кодирования.
Binius предложил инновационное решение, которое отдельно обрабатывает эти две проблемы и реализует их, представляя одни и те же данные двумя различными способами: во-первых, используя многомерные (в частности, многолинейные) многочлены вместо однообразных многочленов, представляя всю вычислительную траекторию через их значения на "гиперкубах"; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае STARKs, невозможно, но гиперкуб можно рассматривать как квадрат и на основе этого квадрата выполнять расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно состоят из двух частей:
Binius: HyperPlonk PIOP + Brakedown PCS + 二进制域。Конкретно, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности:
Арифметика на основе башенной двоичной области
Адаптированная версия проверки произведения и замены HyperPlonk
Новая многолинейная доказательная теория
Улучшенная версия Lasso поиска доказательства
Схема обязательств маломасштабного многочлена
2.1 Конечные поля: арифметика на основе башен двоичных полей
Тау-образное двоичное поле является ключом к реализации быстрого проверяемого вычисления, в основном благодаря двум аспектам: эффективным вычислениям и эффективной арифметизации. Двоичное поле по своей сути поддерживает высокоэффективные арифметические операции, что делает его идеальным выбором для криптографических приложений с высокими требованиями к производительности. Кроме того, структура двоичного поля поддерживает упрощенный процесс арифметизации, то есть операции, выполняемые в двоичном поле, могут быть представлены в компактной и легко проверяемой алгебраической форме.
В области простых чисел Fp распространены методы редукции, такие как редукция Барретта, редукция Монтгомери, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k обычно используются такие методы редукции, как специальные редукции (например, используемые в AES), редукция Монтгомери (например, используемая в POLYVAL) и рекурсивная редукция (например, Tower).
Бинарное поле не требует переноса в операциях сложения и умножения, а возведение в квадрат в бинарном поле очень эффективно, поскольку оно подчиняется упрощенному правилу (X + Y )2 = X2 + Y 2.
2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации правильности многочленов и множеств переменных. Эти основные проверки включают в себя:
Проверка ворот
Проверка перестановок
LookupCheck
МультисетЧек
Проверка продукта
Нузерчек
Суммчек
Пакетная проверка
Binius внес ряд улучшений по сравнению с HyperPlonk:
Оптимизация ProductCheck
Обработка проблемы деления на ноль
Перекрестная проверка перестановок
2.3 PIOP: новый многоуровневый сдвиг аргумента
В протоколе Binius конструирование и обработка виртуальных многочленов являются одной из ключевых технологий, способной эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов. Вот два ключевых метода:
Упаковка
Операторы сдвига
2.4 PIOP：адаптированная версия аргумента поиска Lasso
Протокол Lasso позволяет стороне доказательства обязаться к вектору a ∈ Fm и доказать, что все его элементы существуют в заранее заданной таблице t ∈ Fn. Протокол Lasso состоит из трех компонентов:
Виртуальная полиномиальная абстракция большой таблицы
Поиск по малой таблице
Множественная проверка
Протокол Binius адаптирует Lasso для операций в двоичной области, вводя мультипликативную версию протокола Lasso.
2.5 PCS：адаптированная версия Brakedown PCS
Основная идея построения BiniusPCS — это упаковка. В статье Binius представлены две схемы многочленов с обязательствами Brakedown на основе двоичных полей:
Используйте конкатенированный код для инстанцирования
Используя технологию кодирования на уровне блоков, поддерживает отдельное использование кодов Рида-Соломона.
Binius многочленные обязательства в основном используют следующие технологии:
Малые многочленные обязательства и оценка расширенных областей
Малый универсальный конструктив
Блочное кодирование и код Рида-Соломона
3 Оптимизация мыслительного процесса
Для дальнейшего повышения производительности протокола Binius в статье предложены четыре ключевых момента оптимизации:
PIOP на основе GKR: для операции умножения в двоичной области
Оптимизация ZeroCheck PIOP: балансировка вычислительных затрат между Prover и Verifier
Оптимизация Sumcheck PIOP: оптимизация для малых областей Sumcheck
Оптимизация PCS: оптимизация через FRI-Binius
3.1 GKR-based PIOP：Бинарное умножение в области на основе GKR
Алгоритм умножения целых чисел на основе GKR, преобразует "проверку двух 32-битных целых чисел A и B, удовлетворяющих A·B =? C" в "проверку, выполняется ли (gA)B =? gC", значительно снижая затраты на обязательства с помощью протокола GKR.
3.2 Оптимизация ZeroCheck PIOP: Балансировка вычислительных затрат между Prover и Verifier
Статья «Некоторые улучшения PIOP для ZeroCheck» предлагает несколько оптимизаций для распределения рабочей нагрузки между стороной доказательства (P) и стороной проверки (V), чтобы сбалансировать затраты. Основные оптимизации включают:
Уменьшение передачи данных со стороны подтверждающего лица
Уменьшить количество оценочных точек для доказателей
Алгебраическая интерполяция оптимизации
3.3 Оптимизация Sumcheck PIOP: Протокол Sumcheck на основе малых полей
Ingonyama представил улучшения для протокола Sumcheck на основе малых областей в 2024 году и опубликовал исходный код. Основные оптимизации включают:
Влияние и факторы улучшения переключения раундов
Влияние размера области на производительность
Оптимизация алгоритма Карацубы
Повышение эффективности памяти
3.4 PCS Оптимизация: FRI-Binius уменьшает размер доказательства Binius
Статья «Polylogarithmic Proofs for Multilinears over Binary Towers», сокращенно FRI-Binius, реализует механизм свертки FRI над двоичными полями и приносит 4 аспекта инноваций:
Упрощенный многочлен
Полиномы исчезновения подпространства
Алгебраическая база упакована
Обмен суммы SumCheck
С помощью FRI-Binius можно уменьшить размер доказательства Binius на порядок.
4 Подведение итогов
Binius является совместным проектом, использующим "аппаратное обеспечение, программное обеспечение и ускоренный протокол Sumcheck на FPGA", который может быстро доказывать с очень низким использованием памяти. В Binius практически полностью устранена бутылочная горлышко обязательств Prover, новое узкое место связано с протоколом Sumcheck, и многие проблемы, такие как оценка многочленов и умножение в поле, могут быть эффективно решены с помощью специализированного оборудования.
FRI-Binius решение, являющееся вариантом FRI, предлагает очень привлекательный выбор — устранить накладные расходы на внедрение из слоя доказательства области, не вызывая резкого увеличения затрат на слой агрегативного доказательства. В настоящее время команда Irreducible разрабатывает свой рекурсивный слой и объявила о сотрудничестве с командой Polygon для создания zkVM на основе Binius; JoltzkVM переходит с Lasso на Binius для улучшения своей рекурсивной производительности; команда Ingonyama реализует версию Binius на FPGA.
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
26 Лайков
Награда
26
8
Репост
Поделиться
комментарий
0/400
AirdropF5Bro
· 19ч назад
Ох, какой у нас расклад по starknet!
Посмотреть ОригиналОтветить0
¯\_(ツ)_/¯
· 08-12 16:41
Эта оптимизация слишком сильная, от 252 до двоичного кода.
Посмотреть ОригиналОтветить0
SerumSquirter
· 08-10 20:16
Эффективность все выше, а область все меньше.
Посмотреть ОригиналОтветить0
GateUser-afe07a92
· 08-10 09:35
Так скучно, следующий.
Посмотреть ОригиналОтветить0
ForkTongue
· 08-10 09:20
Написано очень хорошо, но профессионал не понял...
Посмотреть ОригиналОтветить0
NullWhisperer
· 08-10 09:16
хм... оптимизация бинарных полей кажется теоретически элегантной, но давайте поговорим о крайних случаях в операциях над расширенными полями...
Посмотреть ОригиналОтветить0
HalfBuddhaMoney
· 08-10 09:15
Как давно не переводил нулевую ширину? На этот раз объясню четко.
Посмотреть ОригиналОтветить0
NonFungibleDegen
· 08-10 09:08
сер это резкое вещество основано на... двоичные = число растет, наконец-то какой-то реальный альфа, а не это копирование меркл-дерева
Анализ принципов Binius STARKs: Оптимизация двоичного поля и эффективные многочленные обязательства
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что большинство чисел в реальных программах довольно малы, но для обеспечения безопасности доказательства на основе дерева Меркла при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область. Для решения этой проблемы снижение размера области стало ключевой стратегией.
Первое поколение STARKs имеет ширину кодирования 252 бита, второе поколение - 64 бита, третье поколение - 32 бита, но при этом ширина кодирования в 32 бита все еще имеет большое количество неиспользуемого пространства. По сравнению с этим, двоичное поле позволяет напрямую оперировать битами, кодирование компактно и эффективно, без каких-либо неиспользуемых пространств, то есть четвертое поколение STARKs.
При использовании меньших полей операция расширения полей становится все более важной для обеспечения безопасности. А двоичное поле, используемое Binius, полностью зависит от расширения полей для обеспечения своей безопасности и фактической работоспособности. Большинство многочленов, участвующих в вычислениях Prover, не требуют расширения полей и могут работать только в базовом поле, что обеспечивает высокую эффективность в небольшом поле. Тем не менее, случайная проверка точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимого уровня безопасности.
При построении системы доказательств на основе бинарного поля существуют 2 практические проблемы: при вычислении представления следа в STARKs размер используемого поля должен быть больше степени многочлена; при обязательстве Меркле-дерева в STARKs требуется выполнить кодирование Рида-Соломона, размер используемого поля должен превышать размер после расширения кодирования.
Binius предложил инновационное решение, которое отдельно обрабатывает эти две проблемы и реализует их, представляя одни и те же данные двумя различными способами: во-первых, используя многомерные (в частности, многолинейные) многочлены вместо однообразных многочленов, представляя всю вычислительную траекторию через их значения на "гиперкубах"; во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае STARKs, невозможно, но гиперкуб можно рассматривать как квадрат и на основе этого квадрата выполнять расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность, обеспечивая при этом безопасность.
2 Принципиальный анализ
В настоящее время большинство систем SNARKs обычно состоят из двух частей:
Binius: HyperPlonk PIOP + Brakedown PCS + 二进制域。Конкретно, Binius включает пять ключевых технологий для достижения своей эффективности и безопасности:
2.1 Конечные поля: арифметика на основе башен двоичных полей
Тау-образное двоичное поле является ключом к реализации быстрого проверяемого вычисления, в основном благодаря двум аспектам: эффективным вычислениям и эффективной арифметизации. Двоичное поле по своей сути поддерживает высокоэффективные арифметические операции, что делает его идеальным выбором для криптографических приложений с высокими требованиями к производительности. Кроме того, структура двоичного поля поддерживает упрощенный процесс арифметизации, то есть операции, выполняемые в двоичном поле, могут быть представлены в компактной и легко проверяемой алгебраической форме.
В области простых чисел Fp распространены методы редукции, такие как редукция Барретта, редукция Монтгомери, а также специальные методы редукции для определенных конечных полей, таких как Mersenne-31 или Goldilocks-64. В двоичном поле F2k обычно используются такие методы редукции, как специальные редукции (например, используемые в AES), редукция Монтгомери (например, используемая в POLYVAL) и рекурсивная редукция (например, Tower).
Бинарное поле не требует переноса в операциях сложения и умножения, а возведение в квадрат в бинарном поле очень эффективно, поскольку оно подчиняется упрощенному правилу (X + Y )2 = X2 + Y 2.
2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации правильности многочленов и множеств переменных. Эти основные проверки включают в себя:
Binius внес ряд улучшений по сравнению с HyperPlonk:
2.3 PIOP: новый многоуровневый сдвиг аргумента
В протоколе Binius конструирование и обработка виртуальных многочленов являются одной из ключевых технологий, способной эффективно генерировать и управлять многочленами, производными от входных дескрипторов или других виртуальных многочленов. Вот два ключевых метода:
2.4 PIOP：адаптированная версия аргумента поиска Lasso
Протокол Lasso позволяет стороне доказательства обязаться к вектору a ∈ Fm и доказать, что все его элементы существуют в заранее заданной таблице t ∈ Fn. Протокол Lasso состоит из трех компонентов:
Протокол Binius адаптирует Lasso для операций в двоичной области, вводя мультипликативную версию протокола Lasso.
2.5 PCS：адаптированная версия Brakedown PCS
Основная идея построения BiniusPCS — это упаковка. В статье Binius представлены две схемы многочленов с обязательствами Brakedown на основе двоичных полей:
Binius многочленные обязательства в основном используют следующие технологии:
3 Оптимизация мыслительного процесса
Для дальнейшего повышения производительности протокола Binius в статье предложены четыре ключевых момента оптимизации:
3.1 GKR-based PIOP：Бинарное умножение в области на основе GKR
Алгоритм умножения целых чисел на основе GKR, преобразует "проверку двух 32-битных целых чисел A и B, удовлетворяющих A·B =? C" в "проверку, выполняется ли (gA)B =? gC", значительно снижая затраты на обязательства с помощью протокола GKR.
! Исследование битlayer: анализ принципов Биниуса СТАРКСА и оптимизационное мышление
3.2 Оптимизация ZeroCheck PIOP: Балансировка вычислительных затрат между Prover и Verifier
Статья «Некоторые улучшения PIOP для ZeroCheck» предлагает несколько оптимизаций для распределения рабочей нагрузки между стороной доказательства (P) и стороной проверки (V), чтобы сбалансировать затраты. Основные оптимизации включают:
3.3 Оптимизация Sumcheck PIOP: Протокол Sumcheck на основе малых полей
Ingonyama представил улучшения для протокола Sumcheck на основе малых областей в 2024 году и опубликовал исходный код. Основные оптимизации включают:
3.4 PCS Оптимизация: FRI-Binius уменьшает размер доказательства Binius
Статья «Polylogarithmic Proofs for Multilinears over Binary Towers», сокращенно FRI-Binius, реализует механизм свертки FRI над двоичными полями и приносит 4 аспекта инноваций:
С помощью FRI-Binius можно уменьшить размер доказательства Binius на порядок.
4 Подведение итогов
Binius является совместным проектом, использующим "аппаратное обеспечение, программное обеспечение и ускоренный протокол Sumcheck на FPGA", который может быстро доказывать с очень низким использованием памяти. В Binius практически полностью устранена бутылочная горлышко обязательств Prover, новое узкое место связано с протоколом Sumcheck, и многие проблемы, такие как оценка многочленов и умножение в поле, могут быть эффективно решены с помощью специализированного оборудования.
FRI-Binius решение, являющееся вариантом FRI, предлагает очень привлекательный выбор — устранить накладные расходы на внедрение из слоя доказательства области, не вызывая резкого увеличения затрат на слой агрегативного доказательства. В настоящее время команда Irreducible разрабатывает свой рекурсивный слой и объявила о сотрудничестве с командой Polygon для создания zkVM на основе Binius; JoltzkVM переходит с Lasso на Binius для улучшения своей рекурсивной производительности; команда Ingonyama реализует версию Binius на FPGA.