Построение BARGs: от LWE к масштабируемым доказательствам 15:37
В этой лекции Чжэнчжун Цзинь (Zhengzhong Jin) в рамках курса MIT OpenCourseWare рассматривает глубокие технические аспекты построения сукцинтных неинтерактивных аргументов (SNARGs) для пакетных NP-задач (BARGs) на основе предположения о трудности задач на решетках (LWE). Основная проблема классических BARGs заключается в том, что верификатор вынужден считывать все экземпляры задачи, что приводит к линейной зависимости времени верификации от размера пакета $K$.
Индексные BARGs (Index BARGs) 8:09
Для оптимизации процесса вводится новая концепция — индексный BARG (Index BARG).
- Идея: Вместо того чтобы рассматривать набор неструктурированных экземпляров, мы предполагаем их «равномерность» (uniformity). Это означает, что существует некий универсальный контур $U$, который генерирует $I$-й экземпляр задачи на основе индекса $I$.
- Результат: Верификатор теперь считывает не весь массив данных, а лишь индекс $K$ (представляемый как $\log K$ бит). Это позволяет сократить время верификации до логарифмической зависимости от размера пакета и параметра безопасности $\lambda$.
Для Index BARG на базе LWE доказаны следующие параметры:
- Размер доказательства: $poly \log(K, C, \lambda)$.
- Время верификации: $\log(K, C, \lambda)$.
Рекурсивная стратегия сжатия доказательств 22:24
Ключевым вызовом является сжатие сообщений в протоколе, чтобы размер доказательства не рос линейно с $K$.
- Делегирование: Провайдер не передает верификатору все промежуточные данные (запросы PCP), а вместо этого доказывает, что вычисления были выполнены корректно, используя рекурсивное применение SNARG к самому себе.
- Проблема рекурсии: Если применять это «в лоб», количество экземпляров $K$ остается неизменным, и рекурсия может зациклиться.
- Трюк «2 к 1»: Лектор предлагает объединять каждые два соседних индекса в один, тем самым сокращая количество экземпляров вдвое на каждом этапе рекурсии. При достижении последнего уровня, где остается лишь один экземпляр, провайдер напрямую отправляет свидетель (witness) верификатору.
Роль «быстрой» верификации PCP 56:25
Чтобы избежать роста сложности контура при каждой итерации рекурсии (что привело бы к раздуванию доказательства до размера $K \cdot C$), используется специфический тип PCP с разделением на оффлайн-препроцессинг и онлайн-верификацию.
- Оффлайн-фаза: Зависит от размера контура отношения $C$, но генерирует короткое состояние (state).
- Онлайн-фаза: Очень быстрая, использует только короткое состояние и размер запроса.
Благодаря этому решению, контур $C'$ на каждом этапе рекурсии перестает зависеть от размера основного контура $C$, становясь полилогарифмическим, что и обеспечивает общую эффективность системы.
Безопасность и «полуадаптивная» надежность
Вопрос безопасности в такой схеме осложняется тем, что контур отношения может зависеть от хеш-значений, передаваемых на первом этапе (CRS). Поскольку полная адаптивная надежность труднодостижима, в лекции вводится понятие полуадаптивной надежности (semi-adaptive soundness).
- Суть: Злоумышленник может выбирать контур отношения $C$, но не может выбирать, на каком конкретном индексе $I^*$ пытаться совершить подлог.
- Доказательство: Основано на свойстве связывания (binding) хеш-функции. Если индекс $I^*$ не принадлежит языку задачи, то после рекурсивного сжатия он гарантированно приведет к ложному утверждению на последнем уровне, где провайдер не сможет подделать свидетельство.
В завершение дискуссии было отмечено, что переход от Index BARG к общим BARG остается открытой исследовательской областью, где обсуждаются методы повышения адаптивности за счет использования «сложных рычагов» (complexity leveraging).
