FROST-GKR: протокол глобальной трассы для пакетного Poseidon2b

Проблема повторяющейся перестановки

Системы доказательств на основе хеш-функций многократно исполняют одну криптографическую перестановку. Входы меняются; константы раундов, нелинейный слой и линейные отображения — нет. Обычная послойная арифметизация часто теряет эту регулярность. Каждая перестановка получает собственные столбцы и собственную последовательность редукций, даже если пятьдесят девять экземпляров выполняют совершенно одинаковое вычисление из шестидесяти шести раундов.

Poseidon2b — исследуемая здесь криптографическая перестановка над бинарным полем. Она преобразует состояние из четырёх слов за шестьдесят шесть фиксированных раундов и многократно используется для хеширования в стеке доказательств ParanO(1)d.

Метод Голдвассер–Калай–Ротблум (GKR) предоставляет аппарат многолинейных продолжений и sumcheck, который сводит большое вычисление к небольшому набору значений в точках, выбранных проверяющей стороной.

FROST-GKR начинает с другого объекта. Каждому независимому исполнению Poseidon2b он отводит один слот, а затем размещает весь пакет в единой булевой области-произведении; двумя другими координатами служат раунд и координата состояния. Вместо спуска по отдельным слоям схемы протокол создаёт криптографическое обязательство к глобальной трассе исполнения и сводит отношения над ней к открытиям тех же зафиксированных столбцов.

Три столбца обязательства

Для B активных исполнений Poseidon2b пусть L = 2^s — дополненное число слотов. Poseidon2b имеет ширину четыре и шестьдесят шесть нелинейных раундов. FROST резервирует 128 позиций раунда и использует четыре координаты состояния (lane), поэтому полная таблица имеет:

Свидетель содержит всего три многолинейных столбца:

• z содержит состояние на входе раунда и строку финального состояния;
• s_in содержит вход активного S-box — нелинейного преобразования подстановки внутри перестановки;
• s_out содержит соответствующий выход S-box.

Обязательства ко всем трём столбцам создаются до того, как проверяющая сторона выбирает случайный вызов для отношения. Публичные селекторы определяют активные слоты, раунды и координаты S-box. Отображение седьмой степени вычисляется непосредственно над GF(2¹²⁸): возведение Фробениуса в квадрат делает x² и x⁴ линейными операциями, тогда как x³ и x⁷ требуют двух общих умножений. Это преимущество реализации; формальная степень протокола sumcheck остаётся равной семи.

Две редукции ограничений

У протокола две алгебраические задачи. Сначала он должен доказать каждое локальное уравнение раунда Poseidon2b. Затем — доказать, что материализованные представления следующего раунда и проекции координат действительно выведены из исходного обязательства.

Протокол zero-check проверяет, обращается ли полиномиальное отношение в ноль во всех точках закодированной области исполнения. Протокол sumcheck последовательно исключает булевы переменные и сводит это глобальное утверждение к небольшому числу значений в точках, выбранных проверяющей стороной. Затем схема полиномиальных обязательств (PCS) связывает итоговые значения со столбцами трассы, зафиксированными до выбора случайных вызовов.

Глобальное отношение

Один протокол zero-check степени девять проверяет S-box, константы раундов, полные и частичные линейные слои и смежность для каждого активного слота. Для дополненного по слотам пакета основной протокол sumcheck имеет n раундов; число активных перестановок влияет только на логарифмический размер координаты слота.

Терминал содержит одну прямую оценку Z и одиннадцать оценок сдвинутых представлений или проекций координат. Эти одиннадцать утверждений нельзя просто считать открытиями S_in, S_out и Z: увеличение двоичного индекса раунда не является аффинным преобразованием многолинейных переменных.

Редукция сдвинутых представлений

Второй протокол sumcheck степени два объединяет одиннадцать линейных функционалов и сводит их к прямым значениям трёх зафиксированных полиномов в новой точке. Итоговый интерфейс открытия остаётся компактным и явным: два утверждения о значениях Z, одно — S_in и одно — S_out. Схема полиномиальных обязательств, поддерживающая многоточечные открытия, может обработать их напрямую; в статье также описан универсальный завершающий слой для пакетирования трёх столбцов.

Что доказывает протокол

Внутреннее отношение удостоверяет корректное исполнение Poseidon2b в каждом активном слоте. Приложению всё ещё необходимо ограничить открытые входные и выходные строки. Оно может зафиксировать публичный вход, приравнять выход одного слота к входу следующего либо связать финальный выход с публичным дайджестом. Эти уравнения конечных точек используют тот же столбец состояния обязательства, поэтому последовательные цепочки, деревья и губчатые конструкции (sponge) компонуются без повторения внутреннего отношения перестановки.

FROST-GKR — слой алгебраической редукции, использующий схему многолинейных полиномиальных обязательств со связывающим свойством. Полный аргумент объединяет внутреннюю редукцию, отношение граничных значений приложения и выбранную PCS; при оценке корректности эти три составляющие учитываются раздельно.

Корректность и точный расчёт

Для трассы с n переменными интерактивная алгебраическая ошибка внутренних редукций ограничена:

В оценённом экземпляре n = 15 и F = GF(2¹²⁸), поэтому до добавления ошибок корректности отношения конечных точек и полиномиального обязательства это слагаемое ниже 2⁻¹¹⁹. Общий вариант транскрипта использует 22n + 18 элементов поля при передаче полных векторов коэффициентов полинома раунда.

Измерение 59 перестановок

Сопровождающая реализация сравнивает FROST-GKR с базовой схемой цепочек произведений, где для каждой перестановки отдельно выполняется собственная последовательность алгебраических редукций. Обе схемы доказывают один и тот же пакет из пятидесяти девяти перестановок Poseidon2b ширины четыре. До измерения времени стенд строит корректные доказательства, проверяет оба протокола, непосредственно сверяет итоговые утверждения о многолинейных продолжениях (MLE) и учитывает каждый элемент поля в алгебраической части доказательства.

В статье приведён отдельный чистый прогон с медианами 1 605,931 мс для прежнего подхода и 150,218 мс для FROST-GKR. Сохранённый результат репозитория фиксирует другую серию из двадцати измерений на Intel Core i7-1365U: 1 495,629 и 142,475 мс соответственно. Обе серии измеряют слой редукции, а не полный краткий аргумент.

Статья и воспроизводимая реализация

FROST-GKR — исследование O(1) Lab. Автор статьи — Andrew Boyle; она содержит полное отношение трассы, теорему композиции, доказательства полноты и интерактивной корректности, точный расчёт транскрипта и эталонное сравнение.

Прочитать полную статью (PDF) или изучить воспроизводимый испытательный стенд.