FROST-GKR

FROST-GKR — исследование Parano1d Lab: глобальный протокол с криптографически зафиксированной трассой для пакетного исполнения Poseidon2b над GF(2^128).

Название расшифровывается как Frobenius Reduction over Shifted Tables. Протокол сводит целый пакет исполнений Poseidon2b с четырьмя компонентами состояния к открытиям трёх многолинейных полиномов, зафиксированных криптографическими обязательствами.

Прочитать статью · Открыть публикацию Parano1d Lab · Изучить эталонную реализацию

Задача повторяющихся вычислений

Системы доказательств на основе хешей многократно вычисляют одну и ту же перестановку. Входы меняются, но константы раундов, S-box и линейные отображения остаются прежними. Если представлять каждое исполнение отдельной схемой, для каждой перестановки потребуются отдельные столбцы и sumcheck-протоколы с одной и той же структурой.

FROST-GKR рассматривает весь пакет как один объект. Слот перестановки, раунд и компонента состояния Poseidon2b становятся координатами единого булева произведения. Основным объектом служит трасса исполнения, зафиксированная криптографическим обязательством (committed execution trace), а глобальные отношения сводятся непосредственно к открытиям того же обязательства.

Одна зафиксированная трасса

Для B активных перестановок берётся дополненное число слотов L = 2^s >= B. Poseidon2b имеет четыре компонента состояния и 66 нелинейных раундов. FROST-GKR резервирует 128 позиций раунда и получает булев домен

(slot, round, lane) in {0,1}^s x {0,1}^7 x {0,1}^2.

У домена n = s + 9 переменных и N = 2^n = 512L ячеек. Свидетель состоит всего из трёх колонок:

Колонка	Смысл
`z`	Состояние Poseidon2b на входе каждого раунда, включая конечную строку
`s_in`	Вход каждого активного S-box `x^7`
`s_out`	Выход каждого активного S-box `x^7`

Доказывающая сторона фиксирует эти столбцы до получения любого случайного запроса отношения. Публичные селекторы отмечают активные слоты, активные раунды и компоненты S-box.

Две структурные редукции

Одно отношение охватывает весь пакет перестановок:

Этап	Раунды	Степень	Результат
Криптографическое обязательство	—	—	Фиксирует три полинома свидетеля
Глобальное отношение	`n`	9	Сводит все активные уравнения раундов к 12 значениям полиномов
Сведение сдвигов	`n`	2	Возвращает 11 производных утверждений к трём исходным столбцам
Общее терминальное пакетирование	`3n`	2	Даёт по одному утверждению об открытии для каждого зафиксированного столбца

Глобальная проверка тождества нулю (zero-check) охватывает S-box, константы раундов, полные и частичные линейные слои и смежность раундов. На выходе остаются значения исходных столбцов и производных представлений со сдвигом раунда и проекцией компоненты.

Инкремент двоичного индекса раунда не является аффинным преобразованием переменных многолинейного продолжения. Поэтому FROST-GKR явно доказывает представления со сдвигом. Один протокол sumcheck степени два объединяет все 11 производных значений и возвращает их к прямым утверждениям о S_in, S_out и Z в новой точке.

После обоих сведений остаются четыре утверждения о значениях в точках: два для Z и по одному для каждого столбца S-box. Схема полиномиальных обязательств с непосредственным открытием в нескольких точках может открыть их напрямую; для общего случая в статье также задано терминальное пакетирование трёх столбцов.

Зачем нужно бинарное поле

Протокол работает над GF(2^128). В поле характеристики 2 возведение в квадрат по Фробениусу линейно, причём

x^7 = x^4 * x^3, где x^3 = x^2 * x.

Реализация может вычислять прямой S-box двумя обычными умножениями в поле и специализированными возведениями в квадрат. Это преимущество реализации: формальная степень sumcheck остаётся равной семи, а замаскированное глобальное отношение имеет степень девять по каждой переменной.

Композиция по граничным значениям

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

независимые вызовы хеша;
последовательные цепочки перестановок;
деревья Merkle;
губчатые конструкции;
графы переходов состояния.

Это интерфейс интеграции. FROST-GKR один раз подтверждает корректность всех исполнений Poseidon2b в пакете, а граничное отношение соединяет подтверждённые слоты в граф приложения. Свойство связывания значений не позволяет двум отношениям использовать разные трассы.

Корректность и стоимость

При многолинейном полиномиальном обязательстве со связыванием значений и независимо выбранных интерактивных запросах ошибка алгебраической корректности общего протокола не превышает

\varepsilon_{\mathrm{alg}} \le \frac{18n+14}{\lvert\mathbb{F}\rvert}.

Для рассмотренного в статье экземпляра с 15 переменными над $\mathbb{F}=\mathrm{GF}(2^{128})$ это меньше $2^{-119}$ до учёта ошибок корректности граничного отношения и полиномиального обязательства. В статье приведён полный перечень событий, приводящих к ошибке корректности, для основной проверки тождества нулю, сведения сдвигов и терминального пакетирования.

При фиксированных ширине и расписании Poseidon2b работа доказывающей стороны составляет $O(N)$ операций поля, а зафиксированный свидетель содержит $3N$ элементов. Два структурных сведения ограничений используют $2n$ раундов sumcheck. При полных векторах коэффициентов раунда и общем терминальном пакетировании алгебраический транскрипт содержит $22n+18$ элементов поля до открытий и служебного обрамления.

Результаты эталонной реализации

Опубликованная реализация сравнивает FROST-GKR с сохранённым сведением product-chain для каждой перестановки. Обе реализации работают с одной последовательной нагрузкой из 59 перестановок, одним полем, одной нативной перестановкой и одним каналом транскрипта.

Метрика	Product chain	FROST-GKR	Изменение
Протоколы sumcheck для ограничений	472	2	в 236,00 раза меньше
Раунды ограничений	4 248	30	в 141,60 раза меньше
Все раунды sumcheck	4 263	75	в 56,84 раза меньше
Алгебраический транскрипт	287 712 Б	5 568 Б	в 51,67 раза меньше
Медиана сведения, доказывающая сторона	1 605,931 мс	150,218 мс	в 10,69 раза быстрее
Медиана сведения, проверяющая сторона	984,269 мс	66,499 мс	в 14,80 раза быстрее

Измерения выполнены на Intel Core i7-1365U в релизном режиме с кодом, оптимизированным для процессора, после трёх прогревов и по 20 чередующимся измерениям. Размер транскрипта указан для несжатых элементов поля. Открытия полиномиального обязательства и служебное обрамление сериализации не входят ни в один столбец: сравнение изолирует именно описанное в статье сведение.

Роль в Parano1d

Исследование появилось при разработке системы доказательств Parano1d. Протокол выполняет пакетную редукцию Poseidon2b в общем бинарном стеке доказательств. Прикладные отношения связывают зафиксированные граничные значения с авторизацией кошелька, вычислениями Merkle и State, а слой FRI-Binius/BaseFold завершает проверку полученных многолинейных утверждений без доверенной настройки.

Поэтому FROST-GKR одновременно является самостоятельным результатом исследования и конкретной частью архитектуры доказательств Parano1d. Автор статьи — Andrew Boyle; FROST-GKR — исследование Parano1d Lab.