Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что в большинстве реальных программ значения достаточно малы. Однако для обеспечения безопасности доказательств, основанных на деревьях Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область. Чтобы решить эту проблему, уменьшение размера области стало ключевой стратегией.
Первое поколение STARKs имеет ширину кодирования 252 бита, второе поколение - 64 бита, третье поколение - 32 бита, но 32-битная ширина кодирования по-прежнему имеет много неиспользуемого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно без какого-либо неиспользуемого пространства, то есть четвертое поколение STARKs.
При использовании меньших полей операции расширения поля становятся все более важными для обеспечения безопасности. Двоичное поле, используемое Binius, полностью зависит от расширения поля для обеспечения своей безопасности и реальной полезности. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в основном поле, что позволяет достичь высокой эффективности в малом поле. Однако проверка случайных точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
Binius предложил инновационное решение для обработки этих двух проблем, реализовав это с помощью двух различных способов представления одних и тех же данных: во-первых, заменив одновариантный полином многовариантным (в частности, многолинейным) полиномом, представляя всю вычислительную траекторию через его значения в "гиперкубах" (hypercubes); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае с STARKs, невозможно, однако гиперкуб можно рассматривать как квадрат (square), на основе которого можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
Binius: HyperPlonk PIOP + Brakedown PCS + бинарная область. В частности, Binius включает в себя пять ключевых технологий для достижения своей эффективности и безопасности:
Артификация на основе башенных бинарных полей (towers of binary fields)
Адаптированы проверки произведения и перестановки HyperPlonk
Новая многолинейная смещение доказательство
Улучшенная версия доказательства поиска Lasso
Малое поле многочленная схема обязательств (Small-Field PCS)
2.1 Ограниченные поля: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, что в значительной степени обусловлено двумя аспектами: эффективными вычислениями и эффективной арифметикой. Двоичная область по своей сути поддерживает высокоэффективные арифметические операции, что делает её идеальным выбором для криптографических приложений, чувствительных к производительности. Кроме того, структура двоичной области поддерживает упрощенный процесс арифметики, то есть операции, выполняемые в двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме.
2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации корректности многочленов и множеств многомерных переменных. Эти основные проверки включают:
Проверка ворот
Проверка перестановок
LookupCheck
МультисетЧек
Проверка продукта
Нузерчек
Суммчек
Пакетная проверка
Binius улучшил следующие 3 аспекта:
Оптимизация ProductCheck
Обработка проблемы деления на ноль
Перекрестная проверка перестановок
2.3 PIOP：новый многолинейный сдвиг аргумента
В протоколе Binius конструкция и обработка виртуальных полиномов являются одной из ключевых технологий и в основном включают два метода:
Упаковка
Оператор сдвига
2.4 PIOP: адаптированная версия аргумента поиска Lasso
Протокол Lasso состоит из трех компонентов:
Виртуальная полиномиальная абстракция большой таблицы
Поиск по маленькой таблице
Множественная проверка
Протокол Binius адаптирует Lasso для операций в бинарной области, вводя мультипликативную версию протокола Lasso.
2.5 PCS：адаптированная версия Brakedown PCS
Основная идея построения BiniusPCS заключается в упаковке. Многочленные обязательства 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, что значительно уменьшает затраты на обязательства.
Вся ценностная концепция Binius заключается в том, что для свидетелей можно использовать минимальные поля степени двойки, поэтому размер поля можно выбирать только в зависимости от необходимости. Binius является совместным проектом "использования аппаратного обеспечения, программного обеспечения и ускоренного протокола Sumcheck на FPGA", который позволяет быстро доказывать с очень низким использованием памяти.
В Binius в значительной степени устранены узкие места обязательств commit Prover, новое узкое место связано с протоколом Sumcheck, в котором возникают проблемы с множественными оценками многочленов и полевым умножением, которые можно эффективно решить с помощью специализированного оборудования. Решение FRI-Binius является вариантом FRI и может предложить очень привлекательный выбор — устранение накладных расходов на встраивание из уровня доказательства поля без резкого увеличения затрат на уровень агрегированных доказательств.
В настоящее время команда Irreducible разрабатывает свой рекурсивный уровень и объявила о сотрудничестве с командой Polygon для создания zkVM на базе Binius; JoltzkVM переходит с Lasso на Binius для улучшения своей рекурсивной производительности; команда Ingonyama реализует версию Binius на FPGA.
Посмотреть Оригинал
На этой странице может содержаться сторонний контент, который предоставляется исключительно в информационных целях (не в качестве заявлений/гарантий) и не должен рассматриваться как поддержка взглядов компании Gate или как финансовый или профессиональный совет. Подробности смотрите в разделе «Отказ от ответственности» .
12 Лайков
Награда
12
6
Поделиться
комментарий
0/400
SilentObserver
· 07-16 18:11
Как так повысилась эффективность?
Посмотреть ОригиналОтветить0
StakeOrRegret
· 07-16 11:52
Это то, о чем я всегда говорил: сколько ресурсов нужно потратить, чтобы эволюционировать в настоящую четвертую генерацию.
Посмотреть ОригиналОтветить0
Ser_This_Is_A_Casino
· 07-16 06:56
Здесь уже быстро перешли к четвертому поколению.
Посмотреть ОригиналОтветить0
AirdropHunterXiao
· 07-15 16:49
Аирдроп内卷了 整天研究这高深的
Посмотреть ОригиналОтветить0
CodeSmellHunter
· 07-15 16:44
старк嗲气666
Посмотреть ОригиналОтветить0
RektRecorder
· 07-15 16:41
Я предпочитаю смотреть на куриные перья и токены, чем на эту кучу эзотерики.
Оптимизация Binius STARKs: бинарная арифметика и многочлены с многими переменными для повышения эффективности
Анализ принципов Binius STARKs и размышления об их оптимизации
1 Введение
Одной из основных причин низкой эффективности STARKs является то, что в большинстве реальных программ значения достаточно малы. Однако для обеспечения безопасности доказательств, основанных на деревьях Меркла, при использовании кодирования Рида-Соломона для расширения данных многие дополнительные избыточные значения занимают всю область. Чтобы решить эту проблему, уменьшение размера области стало ключевой стратегией.
Первое поколение STARKs имеет ширину кодирования 252 бита, второе поколение - 64 бита, третье поколение - 32 бита, но 32-битная ширина кодирования по-прежнему имеет много неиспользуемого пространства. В сравнении, двоичное поле позволяет выполнять операции непосредственно над битами, кодирование компактно и эффективно без какого-либо неиспользуемого пространства, то есть четвертое поколение STARKs.
При использовании меньших полей операции расширения поля становятся все более важными для обеспечения безопасности. Двоичное поле, используемое Binius, полностью зависит от расширения поля для обеспечения своей безопасности и реальной полезности. Большинство многочленов, участвующих в вычислениях Prover, не требуют перехода в расширенное поле и могут работать только в основном поле, что позволяет достичь высокой эффективности в малом поле. Однако проверка случайных точек и вычисления FRI все еще требуют углубления в более широкое расширенное поле для обеспечения необходимой безопасности.
Binius предложил инновационное решение для обработки этих двух проблем, реализовав это с помощью двух различных способов представления одних и тех же данных: во-первых, заменив одновариантный полином многовариантным (в частности, многолинейным) полиномом, представляя всю вычислительную траекторию через его значения в "гиперкубах" (hypercubes); во-вторых, поскольку длина каждого измерения гиперкуба равна 2, стандартное расширение Рида-Соломона, как в случае с STARKs, невозможно, однако гиперкуб можно рассматривать как квадрат (square), на основе которого можно выполнить расширение Рида-Соломона. Этот метод значительно повышает эффективность кодирования и вычислительную производительность при обеспечении безопасности.
! Исследование битlayer: анализ принципов и оптимизационное мышление Binius STARKs
2 Анализ принципов
Binius: HyperPlonk PIOP + Brakedown PCS + бинарная область. В частности, Binius включает в себя пять ключевых технологий для достижения своей эффективности и безопасности:
2.1 Ограниченные поля: арифметика на основе башен двоичных полей
Башенная двоичная область является ключом к реализации быстрого проверяемого вычисления, что в значительной степени обусловлено двумя аспектами: эффективными вычислениями и эффективной арифметикой. Двоичная область по своей сути поддерживает высокоэффективные арифметические операции, что делает её идеальным выбором для криптографических приложений, чувствительных к производительности. Кроме того, структура двоичной области поддерживает упрощенный процесс арифметики, то есть операции, выполняемые в двоичной области, могут быть представлены в компактной и легко проверяемой алгебраической форме.
2.2 PIOP: адаптированная версия HyperPlonk Product и PermutationCheck
Дизайн PIOP в протоколе Binius заимствовал HyperPlonk и использует ряд основных механизмов проверки для верификации корректности многочленов и множеств многомерных переменных. Эти основные проверки включают:
Binius улучшил следующие 3 аспекта:
2.3 PIOP：новый многолинейный сдвиг аргумента
В протоколе Binius конструкция и обработка виртуальных полиномов являются одной из ключевых технологий и в основном включают два метода:
2.4 PIOP: адаптированная версия аргумента поиска Lasso
Протокол Lasso состоит из трех компонентов:
Протокол Binius адаптирует Lasso для операций в бинарной области, вводя мультипликативную версию протокола Lasso.
2.5 PCS：адаптированная версия Brakedown PCS
Основная идея построения BiniusPCS заключается в упаковке. Многочленные обязательства 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
Основные направления оптимизации включают в себя следующие несколько аспектов:
! Исследование Bitlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление
3.3 Sumcheck PIOP оптимизация: основанный на малом поле протокол Sumcheck
Основные точки оптимизации включают:
3.4 PCS Оптимизация: FRI-Binius уменьшает размер доказательства Binius
FRI-Binius реализовал механизм сворачивания FRI в двоичном поле, что привело к 4 аспектам инноваций:
! Исследование Bitlayer: Анализ принципов Биниуса СТАРКСА и оптимизационное мышление
4 Итоги
Вся ценностная концепция Binius заключается в том, что для свидетелей можно использовать минимальные поля степени двойки, поэтому размер поля можно выбирать только в зависимости от необходимости. Binius является совместным проектом "использования аппаратного обеспечения, программного обеспечения и ускоренного протокола Sumcheck на FPGA", который позволяет быстро доказывать с очень низким использованием памяти.
В Binius в значительной степени устранены узкие места обязательств commit Prover, новое узкое место связано с протоколом Sumcheck, в котором возникают проблемы с множественными оценками многочленов и полевым умножением, которые можно эффективно решить с помощью специализированного оборудования. Решение FRI-Binius является вариантом FRI и может предложить очень привлекательный выбор — устранение накладных расходов на встраивание из уровня доказательства поля без резкого увеличения затрат на уровень агрегированных доказательств.
В настоящее время команда Irreducible разрабатывает свой рекурсивный уровень и объявила о сотрудничестве с командой Polygon для создания zkVM на базе Binius; JoltzkVM переходит с Lasso на Binius для улучшения своей рекурсивной производительности; команда Ingonyama реализует версию Binius на FPGA.