FROST-GKR

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

FROST расшифровывается как Frobenius Reduction over Shifted Tables. Протокол сводит проверку всего пакета перестановок ширины четыре к открытиям трёх многолинейных полиномов.

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

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

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

FROST-GKR объединяет все вычисления в один объект. Номер перестановки, номер раунда и координата состояния становятся осями одного булева домена. Трасса сначала фиксируется обязательствами, после чего все глобальные отношения сводятся к открытиям тех же полиномов.

Одна трасса, три столбца

Пусть B обозначает число вычислений Poseidon2b, а 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_in и S_out. Схема с открытием в нескольких точках может проверить их напрямую. Для общего случая статья задаёт терминальное объединение, которое оставляет по одному утверждению на каждый из трёх столбцов.

Почему бинарное поле даёт выигрыш

Отношение FROST-GKR определено над GF(2^128). В поле характеристики 2 возведение в квадрат по Фробениусу линейно:

(a + b)^2 = a^2 + b^2.

Поэтому прямой S-box можно вычислить как x^3 = x^2 * x и x^7 = x^4 * x^3. Значения x^2 и x^4 получаются возведением в квадрат, так что остаются только два обычных умножения в поле. Это ускоряет реализацию, но не меняет формальную степень: S-box имеет степень семь, а глобальное отношение с селекторами имеет степень девять по каждой переменной.

Как задаётся топология вычисления

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

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

FROST-GKR один раз доказывает корректность всех вычислений Poseidon2b в пакете. Граничные уравнения определяют, как эти вычисления соединены в приложении. Связывание значений гарантирует, что внутреннее и прикладное отношения используют одну и ту же трассу.

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

Если многолинейное обязательство обладает связыванием значений, а интерактивные вызовы выбираются независимо, ошибка алгебраической корректности ограничена выражением

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

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

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

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

Метрика	Product chain	FROST-GKR	Выигрыш
Sumcheck для ограничений	472	2	в 236,00 раза меньше
Раунды этих sumcheck	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. Код собран в режиме release с оптимизацией под этот процессор. После трёх прогревов получено 20 чередующихся измерений. Размер транскрипта рассчитан по несжатым элементам поля. Открытия полиномиальных обязательств и служебные байты сериализации не включены ни в одну сторону сравнения. Поэтому таблица показывает стоимость именно той редукции, которую заменяет FROST-GKR.

Роль в Parano1d

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

Трасса Poseidon2b и отношение FROST-GKR остаются над GF(2^128). В штатном стеке вызовы Fiat-Shamir, терминальные утверждения и аутентификация рекурсивных регионов перенесены в GF(2^256). Расширенное поле окружает FROST-GKR на уровне интеграции и не меняет три столбца свидетеля, отношение степени девять или результаты эксперимента над GF(2^128).

FROST-GKR является самостоятельным воспроизводимым результатом и рабочей частью архитектуры доказательств Parano1d. Это исследование Parano1d Lab.