Корректность ParanO(1)d в отраслевых метриках

В сравнении используются четыре специальных понятия. FRI — семейство доказательств малой степени, лежащее в основе перечисленных систем с кодированием. Интерактивное оракульное доказательство (IOP) позволяет проверяющей стороне запрашивать отдельные позиции зафиксированных данных вместо чтения всей таблицы доказательства. Оценка Toy Problem — принятая в отрасли эвристика параметров, зависящая от кодовой скорости, числа запросов и размера поля. Пораундовая корректность доказательства знания (RBR), напротив, ограничивает вероятность неудачи экстрактора на каждом ходе проверяющей стороны; связанная метрика $t/e(t)$ делит работу атаки $t$ на вероятность её успеха $e(t)$. В таблице сопоставляются только значения, полученные в метрике, указанной в соответствующей строке; сами протоколы не объявляются одинаковыми.

Значения ParanO(1)d выведены из параметров рабочей реализации, вычисляются исполняемыми формулами и зафиксированы регрессионными тестами. Каждое сохраняет смысл породившей его метрики: гипотетическая оценка параметров, граница обобщённой RBR-корректности доказательства знания или конечная композиция с учётом работы.

Область и метод

Числа безопасности легко сравнивать, если отбросить их определения. Но такое сравнение теряет смысл. «100 бит», «96 бит» и «128 бит» могут означать гипотетическую оценку запросов, доказанную ошибку интерактивной корректности, ослабленное определение работы на один успех, стойкость хеш-функции или композицию прикладного протокола. Число — последний шаг; сначала задаются модель атаки и редукция.

Исследование отвечает на один воспроизводимый вопрос: какую оценку получает зафиксированная геометрия доказательства ParanO(1)d при тех же классических соглашениях, которые публикуют известные проекты систем доказательств? Четыре величины оцениваются раздельно:

1. оценка параметров при точном применении формулы Plonky2/Toy Problem;
2. оценка работы запросов с фактическим радиусом приёмки и обязательным предварительным перебором (grinding);
3. опирающаяся на теорему граница обобщённой RBR-корректности доказательства знания для базового IOP кошелька;
4. конечные суммы ошибок корректности по полной траектории принятия с явным учётом предварительного перебора.

Результаты не усредняются и не сводятся к одному числу, поскольку отвечают на разные вопросы. В публичном репозитории они представлены разными типами и отдельными разделами вывода.

Параметры рабочей реализации

Входные значения взяты из коммита ParanO(1)d 93b0252317208c20f8a769afb74681aa9389e286. Его идентификатор записан в расчётном проекте. При изменении протокола необходимо явно обновить и привязку к исходному коду, и ожидаемые результаты.

State — аутентифицированный набор текущих непотраченных выходов и счётчиков консенсуса. HistoryStep — рекурсивное доказательство точного перехода блока от родительского State к дочернему. B64 и B255 — два фиксированных класса его вместимости, рассчитанные соответственно на блоки с числом пользовательских страниц транзакций до 64 и до 255. Они проверяют одинаковые правила валидности, но используют области ограничений разного размера.

Геометрия кошелька закреплена в zk_capsule.rs. Минимальное число запросов BaseFold, предварительный перебор и рабочая шкала параметров закреплены в basefold.rs. Независимый расчётный проект содержит только значения, необходимые для вычислений:

pub const PRODUCTION: ProductionParameters = ProductionParameters {
    challenge_field_bits: 128,
    digest_bits: 256,
    wallet_query_count: 64,
    wallet_log_inverse_rate: 5,
    wallet_miss_numerator: 3,
    wallet_miss_denominator: 10,
    wallet_grind_bits: 16,
    max_authorizations_per_block: 255,
    history_query_count: 125,
    history_log_inverse_rate: 2,
    history_grind_bits: 16,
    history_log_message_columns: [18, 19],
};

Дублирование сделано намеренно: любое расхождение приводит к отказу проверки. Указанный коммит — первичный источник, а независимый проект служит для воспроизводимого контроля расчёта. Тесты обнаруживают устаревшие значения и не позволяют расчётной таблице незаметно пережить описываемую ею версию протокола.

Метрика 1. Оценка по исходной формуле Toy Problem

Plonky2 использует известное выражение через кодовую скорость и число запросов, ограниченное размером поля:

где $q$ — число запросов, $\rho$ — кодовая скорость, $g$ — предварительный PoW-перебор (grinding), а $\lambda_F$ — ограничение, задаваемое полем. Реализация в расчётном проекте в точности следует этой формуле:

pub fn literal_toy_problem_score(
    query_count: u32,
    log_inverse_rate: u32,
    grind_bits: u32,
    field_bits: u32,
) -> (f64, f64) {
    let raw = (query_count * log_inverse_rate + grind_bits) as f64;
    (raw, raw.min(field_bits as f64))
}

Для авторизации кошелька 64 * 5 + 16 = 336. Для каждого класса HistoryStep — 125 * 2 + 16 = 266. Оба результата ограничиваются 128 битами поля GF(2¹²⁸); 256-битный дайджест также имеет классический предел коллизий 128 бит. Поэтому минимальная из отображаемых оценок компонентов равна 128 битам.

Точное название: 128-битная гипотетическая классическая оценка параметров по модели Toy Problem. Она использует модель, основанную на кодовой скорости, и не учитывает конечные исключительные множества.

Метрика 2. Работа запросов с фактическим радиусом

Оценка только по кодовой скорости не учитывает радиус приёмки проверяющего. Поэтому вторая, всё ещё гипотетическая, оценка работы использует фактическую вероятность промаха и обязательный 16-битный предварительный перебор непосредственно перед выбором запросов.

Для авторизации кошелька выбранный радиус списочного декодирования равен $7/10$. Слово за пределами этого радиуса может совпадать не более чем с $3/10$ позиций источника. Вероятность того, что шестьдесят четыре запроса пропустят все расхождения, не превышает $(3/10)^{64}$:

Для HistoryStep расчёт использует кодовую скорость $\rho=1/4$, относительное расстояние $\delta=3/4$, длину домена $n$ и фактический радиус близости

Соответствующая оценка:

И слабейший компонент, и аддитивная композиция дают 100,757887 бита. Результат обозначается как 100,76-битная гипотетическая классическая оценка работы запросов с фактическим радиусом. Она использует радиус рабочей реализации, а не только кодовую скорость; конечные исключительные множества анализируются отдельно ниже.

Метрика 3. Граница обобщённой RBR-корректности доказательства знания — 96,047 бита

Результат для кошелька опирается на теорему. Используется обобщённая RBR-корректность доказательства знания (generalized round-by-round knowledge soundness; корректность доказательства знания по раундам) в смысле Block, Garreta, Tiwari и Zając. Протокол содержит 30 ходов проверяющей стороны. Каждому ходу соответствует граница ошибки $\varepsilon_i$, а скалярная RBR-оценка равна их максимуму:

Это не объединение ошибок по всей траектории принятия. Суммирование границ всех ходов определяло бы другую величину.

Точная геометрия кода Рида–Соломона

Исходный аффинный код имеет длину $n=65\,536$, длину сообщения $K=2\,048$, степень в обозначениях статьи $k=K-1=2\,047$ и выбранный радиус $\gamma=7/10$. Семь двоичных свёрток сохраняют кодовую скорость 1/32 и создают восемь длин кодовых слов от 65 536 до 512.

В расчёте применяется теорема 4.6 Ben-Sasson, Carmon, Haböck, Kopparty и Saraf (BCHKS) с кратностью $m=3$ и $h=m+1/2=7/2$:

Потолок не вычисляется в двоичной плавающей точке. При $S=2^{48}$ и

расчётный проект проверяет целочисленный сертификат

Подстановка в положительные знаменатели даёт консервативную рациональную верхнюю границу

поэтому верхняя граница мощности исключительного множества BCHKS равна $A_\gamma=4\,157\,831\,958$. Фиксированное основное расхождение пакетирования является ненулевым аффинным полиномом по тому же вызову и добавляет не более одного корня:

Почему список кандидатов не добавляет вероятность

Выбранная интерполяция Sudan имеет взвешенную степень 19 660 и третью степень по $Y$. Четыре блока коэффициентов содержат 19 661, 17 614, 15 567 и 13 520 мономов: 66 362 неизвестных при 65 536 однородных ограничениях, то есть положительный запас 826. Ненулевой интерполянт существует, и различных множителей $Y-p(X)$ может быть не более трёх. Та же целочисленная проверка размерности остаётся положительной на каждом свёрнутом слое.

Оракулы bank, companion и mid — три кодированные таблицы, наблюдаемые соответственно на исходном этапе, этапе сопутствующего утверждения и промежуточном этапе свёртки протокола авторизации. Экстрактор полностью декодирует каждую таблицу, повторно кодирует каждого кандидата относительно наблюдаемых значений и проверяет точные отношения авторизации и цепочки свёрток. Каждый список содержит не более трёх элементов, поэтому проверяется не более $3^3=27$ троек кандидатов. Эти 27 проверок — детерминированная работа. Они не прибавляются к вероятности отказа и не умножают её.

Таблица границ для 30 ходов

Фаза A — это одиннадцатираундовый sumcheck, связывающий открытое отношение произведения и суммы с доказательством владельца и публичными данными авторизации. Имена из кода в таблице обозначают точные вызовы Fiat–Shamir; сначала указана их роль в протоколе, поэтому таблицу можно читать без обращения к реализации.

MainGamma — максимальный ход. Полученный скаляр:

Результат — 96,047-битная классическая граница обобщённой RBR-корректности доказательства знания для интерактивного базового IOP кошелька. Полное доказательство содержит лемму выбора кандидатов, индукцию по множеству заведомо проигрышных состояний (doomed set) и разбор каждого хода.

let rbr = wallet_generalized_rbr_metrics();
assert_eq!(rbr.source_correlated_agreement_bad_coins, 4_157_831_958);
assert_eq!(rbr.gamma_affine_batch_bad_coins, 1);
assert_eq!(rbr.max_restoration_triples_checked, 27);
assert_eq!(rbr.bad_coin_numerator, 4_157_831_959);
close(rbr.generalized_rbr_bits, 96.046_815_693_930_09, 1e-12);

Метрика 4. Конечные оценки корректности по траектории принятия

Обобщённая RBR-корректность и обычная корректность по полной траектории принятия (accepting-path soundness) — разные свойства. Для второго конечные члены ошибки сначала складываются и только затем преобразуются через $-\log_2$. Предварительный перебор транскрипта сам по себе не уменьшает все слагаемые ошибки корректности.

Для одной авторизации кошелька:

что даёт 95,049176 бита. Для HistoryStep:

Для одного фиксированного недействительного блока с одним недействительным доказательством авторизации и одним недействительным HistoryStep консервативная аддитивная оценка без учёта предварительного перебора составляет 84,756737 бита на подделку.

Как учитывается предварительный перебор

16-битный предварительный перебор выполняется непосредственно перед выбором запросов. Если применить его только к последующему члену запросов, не затрагивая несвязанные исключения над конечным полем, для фиксированного недействительного блока получается 95,021747 бита. В расчётном проекте это ближайшая величина ParanO(1)d к ослабленному соглашению об учёте работы, использованному в сравнении с ethSTARK.

Отдельная однократная модель допускает до 255 независимо атакуемых доказательств кошелька в одном блоке:

Объединение событий даёт 84,490657 бита без учёта предварительного перебора и 87,054734 бита, если он применяется только к члену запросов. Это не показатель работы на одну подделку. В определении $t/e(t)$ создание 255 независимых попыток само требует соответствующей работы; вычитание $\log_2(255)$ после учёта всех попыток может дважды учесть одну и ту же кратность. Корректная многоцелевая оценка Fiat–Shamir требует единого глобального бюджета работы противника или запросов к оракулу.

fixed_invalid_block_finite_no_grind_bits:
    union_probability_bits(&[
        wallet.finite_no_grind_bits,
        limiting_history_finite_no_grind_bits,
    ]),

fixed_invalid_block_query_grind_only_bits:
    union_probability_bits(&[
        wallet.finite_query_grind_only_bits,
        limiting_history_finite_query_grind_only_bits,
    ]),

Воспроизводимый расчёт

Расчёт опубликован как небольшой независимый Rust-репозиторий, а не встроен в узел. Он не участвует в консенсусе и не меняет ни одного параметра сети. Его задача — сделать формулы проверяемыми, исполняемыми и чувствительными к изменению параметров.

git clone https://github.com/ignotusnemo/parano1d-soundness.git
cd parano1d-soundness

cargo run --release
cargo test --release
cargo clippy --all-targets --release -- -D warnings
RUSTDOCFLAGS='-D warnings' cargo doc --release --no-deps

Тесты закрепляют исходную версию кода, значения по формуле Toy Problem, оба класса HistoryStep, сертификат квадратного корня в масштабе 2⁴⁸, все восемь границ BCHKS, сертификат интерполяции со списком размера три, точную 30-ходовую таблицу RBR и каждую конечную композицию. В частности, один регрессионный тест утверждает, что 27 троек кандидатов относятся к детерминированной работе экстрактора и не должны входить в числитель ошибки.

Интерпретация результатов

Опубликованные значения предназначены для сопоставления одинаковых сущностей внутри названных метрик:

• 128 бит — гипотетическая классическая оценка параметров по модели Toy Problem.
• 100,76 бита — гипотетическая классическая оценка работы запросов с фактическим радиусом.
• 96,047 бита — опирающаяся на теорему классическая граница обобщённой RBR-корректности доказательства знания для интерактивного базового IOP кошелька.
• 95,022 бита — конечная композиция для фиксированного недействительного блока с учётом работы по заявленному правилу предварительного перебора.

Эти определения соответствуют сравнительной таблице в начале статьи и сохраняются в исполняемом выводе. Каждое значение используется только в пределах явно названной метрики.

Первоисточники

• Ignotus Nemo, ParanO(1)d soundness.
• Авторизация кошелька: обобщённая RBR-граница 96,047 бита.
• Заявление Plonky2 о безопасности и его буквальный расчёт параметров.
• Калькулятор корректности RISC Zero.
• StarkWare, Safe and Sound: A Deep Dive into STARK Security.
• Block, Garreta, Tiwari и Zając, Fiat–Shamir Security of FRI and Related SNARKs.
• Block и Tiwari, On the Concrete Security of Non-interactive FRI.
• Block, Garreta, Tiwari и Zając, On Soundness Notions for Interactive Oracle Proofs.
• Ben-Sasson, Carmon, Haböck, Kopparty и Saraf, On Proximity Gaps for Reed–Solomon Codes.

Ignotus Nemo