FROST-GKR включает номер вычисления, раунд и координату состояния в одну булеву область произведения. Один zerocheck степени девять доказывает корректность всех раундов Poseidon2b одновременно. Затем sumcheck степени два связывает представления со сдвигом с тремя столбцами, зафиксированными обязательствами. В эталонном примере с 59 вычислениями перестановки число вызовов sumcheck для проверки ограничений сокращается с 472 до 2, алгебраический транскрипт с 287 712 до 5 568 байт, время доказывающей стороны в 10,69 раза, а проверяющей стороны в 14,80 раза. Отношения начальных и конечных состояний используют ту же трассу для цепочек, деревьев, губчатых конструкций и вычисления состояния Parano1d.
Одна и та же перестановка снова и снова
В системах доказательств на основе хешей одна и та же криптографическая перестановка вычисляется снова и снова. Меняются входы, но S-box, раундовые константы и линейные преобразования остаются прежними. При послойной арифметизации эта регулярность теряется: каждое вычисление Poseidon2b получает собственные столбцы и собственную последовательность алгебраических редукций.
Для Parano1d эта задача была архитектурной. Авторизация кошелька, аутентификация Merkle, вычисление состояния, транскрипты и рекурсивная проверка используют Poseidon2b. Если каждый вызов представлять отдельной алгебраической схемой, слой хеширования растёт вместе с графом протокола и в итоге начинает определять стоимость всего доказательства.
Эталонная нагрузка из статьи FROST-GKR показывает эту границу на конкретных числах. Она содержит 59 вычислений Poseidon2b ширины четыре. Базовая конструкция на основе цепочек произведений требует восемь вызовов sumcheck для проверки ограничений на каждое вычисление, всего 472. FROST-GKR ставит задачу иначе: описать перестановку один раз, а номер её вычисления сделать ещё одной координатой данных.
Результатом стала одна глобальная трасса, зафиксированная обязательством. Номер вычисления, раунд и координата состояния входят в одну булеву область произведения. После двух структурных протоколов sumcheck остаются четыре утверждения о значениях в точках. Затем их объединение даёт по одному конечному утверждению для каждого зафиксированного столбца.
FROST-GKR устранил 470 из 472 вызовов sumcheck для проверки ограничений в эталонной нагрузке. Проверка повторяющейся перестановки превратилась в единый алгебраический модуль с линейным временем работы. Именно это позволило построить остальную архитектуру доказательств Parano1d в практических пределах: новая топология хеширования больше не требует ещё одной копии внутреннего доказательства Poseidon2b.
Все вычисления в трёх столбцах
Пусть B обозначает число реальных вычислений, а L = 2s ≥ B число слотов после дополнения. Poseidon2b имеет четыре координаты состояния и 66 нелинейных раундов. FROST-GKR резервирует 128 позиций раунда, поэтому ячейка трассы индексируется как
Полная область содержит n = s + 9 переменных и N = 2n = 512L ячеек. Зафиксированный свидетель состоит всего из трёх многолинейных столбцов:
stateсодержит состояние на входе каждого раунда и конечную строку состояния;s_inсодержит входы всех активных S-boxx^7;s_outсодержит соответствующие выходы S-box.
Публичные селекторы отмечают реальные слоты, активные раунды и координаты, к которым применяется S-box. Реализация выводит селектор sigma из фиксированного расписания раундов. При вычислении sumcheck эта таблица может храниться в памяти, но она не является четвёртым столбцом свидетеля и для неё не создаётся отдельное обязательство. Поэтому три столбца свидетеля представляют и полные раунды, где нелинейны все четыре координаты, и частичные раунды, где нелинейна только нулевая координата. В Parano1d доказывающая сторона фиксирует эти столбцы обязательствами до выбора проверочных значений. Воспроизводимый сравнительный эксперимент останавливается на тех же конечных многолинейных утверждениях и проверяет их напрямую.
Почему протокол называется FROST
FROST расшифровывается как Frobenius Reduction over Shifted Tables. Обе части названия обозначают ключевые элементы конструкции.
В двоичном поле возведение в квадрат по Фробениусу линейно:
Прямой S-box Poseidon2b можно вычислить как x³ = x²·x и x⁷ = x⁴·x³. Значения x² и x⁴ получаются возведением в квадрат, поэтому остаются только два умножения в поле. При этом протокол сохраняет прямое отношение степени семь и не раскладывает каждый S-box в цепочку вспомогательных слоёв схемы.
Таблицы со сдвигом решают вторую трудность. Уравнение раунда читает состояние в раунде r и состояние в раунде r + 1. Увеличение семибитного номера раунда не является аффинным преобразованием многолинейных переменных. Поэтому значение таблицы со сдвигом нельзя просто объявить открытием исходного столбца в преобразованной точке. FROST-GKR доказывает эту связь отдельно.
Как две редукции доказывают все вычисления
1. Одно глобальное отношение
Единый zerocheck степени девять проверяет каждую активную ячейку Poseidon2b. Он охватывает отношение x^7, раундовые константы, полные и частичные линейные слои и связь соседних состояний. Sumcheck исключает булевы переменные по одной. Число раундов равно n, поэтому рост числа вычислений влияет на глубину протокола только через логарифмическую координату слота.
В конце этой редукции остаются одно прямое значение state и одиннадцать значений представлений со сдвигом раунда или проекцией координаты. Они точно описывают связи в глобальном отношении.
2. Возврат каждого представления к обязательству
Второй sumcheck степени два объединяет одиннадцать производных значений и доказывает, что они являются правильными линейными функционалами исходных трёх столбцов. Протокол возвращается к прямым значениям state, s_in и s_out в новой точке, выбранной проверяющей стороной.
После двух редукций остаются четыре утверждения о значениях в точках: два для state, одно для s_in и одно для s_out. Три протокола объединения значений степени два дают по одному конечному утверждению для каждого зафиксированного столбца. Схема полиномиальных обязательств открывает те же столбцы. Производная таблица, выбранная доказывающей стороной, нигде не подменяет исходную зафиксированную трассу.
Обычный GKR спускается по слоям схемы. FROST-GKR сохраняет единую зафиксированную трассу вычисления как постоянный объект и сводит к её открытиям все глобальные отношения.
Poseidon2b доказывается один раз, а топология задаётся граничными условиями
Внутреннее отношение доказывает корректность Poseidon2b в каждом реальном слоте. Столбец state содержит входную и выходную строки каждого слота. Отдельное отношение начальных и конечных состояний определяет смысл этих вычислений:
- фиксирует вход и выход независимого вызова хеширования;
- приравнивает выход одного слота ко входу следующего для последовательной цепочки;
- соединяет выходы дочерних узлов со входом родительского узла в дереве Merkle;
- соединяет состояния поглощения и выдачи для губчатой конструкции или транскрипта;
- связывает конечные точки с авторизацией кошелька, состоянием или данными рекурсивной проверки.
Семантика перестановки доказывается один раз для всех вычислений. При изменении прикладного графа меняются только уравнения начальных и конечных состояний. Поэтому один протокол покрывает цепочки, деревья и независимые хеши, не создавая заново внутреннее доказательство Poseidon2b для каждой топологии.
Конкретный выигрыш
Воспроизводимый эксперимент сравнивает FROST-GKR с базовой конструкцией, которая доказывает каждую перестановку отдельной цепочкой произведений. Обе реализации доказывают одну последовательность из 59 перестановок Poseidon2b над одним полем и используют один канал транскрипта. До измерений тестовый стенд создаёт и проверяет оба честных доказательства, напрямую сверяет конечные многолинейные значения и проверяет точный размер алгебраического транскрипта.
| Показатель | Отдельная цепочка для каждой перестановки | 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 раза быстрее |
Размеры относятся к элементам поля в алгебраической редукции. Сериализация, открытия схемы полиномиальных обязательств и пути аутентификации Merkle не входят ни в один столбец. Сравнение изолирует именно ту часть системы доказательств, которую заменяет FROST-GKR.
Почему выигрыш сохраняется при росте числа вычислений
При фиксированных ширине и расписании раундов Poseidon2b работа доказывающей стороны составляет O(N) операций в поле, а зафиксированный свидетель содержит 3N элементов. Две структурные редукции используют 2n раундов sumcheck. Удвоение дополненного числа слотов добавляет одну булеву переменную и два раунда редукции, но не дублирует протокол.
При объединении конечных утверждений полный алгебраический транскрипт содержит 22n + 18 элементов поля до открытий обязательств и сериализации. Проверяющая сторона выполняет логарифмическую редукцию вместо повторного вычисления каждого раунда каждой перестановки.
Содержание теоремы
Для схемы многолинейных обязательств со связывающим свойством относительно значений и независимо выбранных интерактивных вызовов внутренняя алгебраическая ошибка ограничена величиной
Для рассмотренного в статье случая с 15 переменными над GF(2128) этот член меньше 2−119 до добавления ошибок отношения конечных точек и схемы полиномиальных обязательств. Теорема устанавливает семантику перестановки, полноту, композицию топологии и полный перечень событий ошибки для обеих редукций.
Роль FROST-GKR в Parano1d
FROST-GKR появился внутри системы доказательств Parano1d и остаётся общей редукцией для повторяющихся вычислений Poseidon2b. Штатная реализация использует те же три зафиксированных столбца свидетеля, а публичное расписание селекторов независимо выводят доказывающая и проверяющая стороны. Хеширование тела транзакции, аутентификация Merkle, фиксированные полевые хеши и рекурсивная проверка применяют эту редукцию к своим трассам и связывают прикладные утверждения с их начальными и конечными состояниями. FRI-Binius/BaseFold открывает полученные многолинейные утверждения без доверенной установки.
Следующий инженерный шаг, который объединил девять рекурсивных областей аутентификации в один упорядоченный проход, описан в статье «Один глобальный проход Poseidon вместо девяти проходов рекурсивного верификатора».
Статья и воспроизводимый эксперимент
Статья FROST-GKR содержит полное отношение трассы, теорему композиции, доказательства полноты и интерактивной корректности, а также точный расчёт транскрипта. Отдельный репозиторий воспроизводит прямое сравнение для 59 перестановок.
FROST-GKR представляет собой исследование Parano1d Lab и штатный компонент архитектуры доказательств Parano1d.