В этой лекции профессор Яэль Калай (Yael Kalai) из MIT раскрывает удивительную связь между интерактивными протоколами и вероятностно проверяемыми доказательствами (PCP). Она подробно объясняет, как с помощью развертывания знаменитого протокола GKR можно превратить любое классическое доказательство из класса NP в компактную структуру, проверяемую всего за несколько случайных запросов. Материал знаменует собой важный переход от чистой теории сложности к практической криптографии и вычислительной надежности.
🔍 Что такое вероятностно проверяемые доказательства (PCP)? 2:26
Концепция вероятностно проверяемых доказательств (Probabilistically Checkable Proofs, PCP) переворачивает традиционный взгляд на верификацию. В классическом сценарии класса NP у нас есть утверждение $x$ и свидетельство (witness) $w$, выполняющее роль доказательства. Чтобы проверить такое доказательство, верификатор вынужден прочитать его целиком и прогнать через специальную схему верификации. Идея PCP заключается в том, чтобы трансформировать исходное доказательство в новую структуру (обычно обозначаемую как $\pi$), размер которой может быть больше оригинала, но по-прежнему ограничен полиномом.
Самое поразительное свойство PCP заключается в том, что верификатору не нужно читать доказательство целиком, чтобы убедиться в его подлинности. Вместо этого он выбирает случайные позиции (биты) в доказательстве, запрашивает их значения и применяет локальную схему проверки. Критически важно, что позиции выбираются случайно, и доказывающий (prover) не знает их заранее. Если бы доказывающий знал точки запроса, он мог бы легко сфальсифицировать ответ.
Отвечая на вопрос из аудитории, Яэль Калай уточняет, что PCP эффективны, даже если размер свидетельства $m$ меньше размера утверждения $n$. Профессор также упоминает концепцию «PCP близости» (PCP of proximity), где верификатор не считывает полностью даже само утверждение $x$, а проверяет близость предоставленного оракула к языку. Современная наука дошла до того, что любое свидетельство можно превратить в PCP, требующее от верификатора проверки всего 3 бит для достижения определенного уровня надежности. В рамках лекции рассматривается чуть более простая конструкция с полилогарифмической сложностью запросов.
📊 PCP как класс сложности и свойство неадаптивности 7:47
В теории сложности PCP формализуется как класс языков, обладающих определенными параметрами эффективности. Класс обозначается как $PCP[c, s, r, q]$, где:
- $c$ — параметр полноты (completeness);
- $s$ — параметр надежности (soundness);
- $r$ — количество используемых случайных бит;
- $q$ — количество запросов к оракулу.
Верификатор представляет собой вероятностную полиномиальную машину Тьюринга с доступом к оракулу. Свойство полноты гарантирует, что для любого верного утверждения существует доказательство $\pi$, которое верификатор примет с вероятностью не менее $c$ (в рассматриваемых системах $c = 1$). Надежность гарантирует, что если утверждение ложно, то никакой обманщик не сможет составить такое доказательство $\pi^*$, которое верификатор примет с вероятностью выше $s$ (обычно целевое значение $s = 1/2$).
Важнейшей характеристикой верификатора в большинстве современных PCP-систем является неадаптивность (non-adaptivity). Неадаптивный верификатор работает в два этапа:
- На основе входного слова $x$ и случайных бит он сразу вычисляет все $q$ позиций в доказательстве, которые планирует проверить;
- Он отправляет запросы к оракулу, получает ответы и на их основе принимает решение.
Адаптивный верификатор мог бы выбирать вторую точку запроса на основе того, что он прочитал в первой, однако неадаптивность крайне важна для криптографических приложений, включая построение лаконичных аргументов (succinct arguments). Профессор Калай подчеркивает, что распределение запросов при этом зависит исключительно от длины входа $n$, но не от конкретного значения $x$.
🛠️ Развертывание протокола GKR для построения PCP 24:34
Основная теорема лекции гласит: для любого языка из класса NP можно построить PCP-систему с полнотой 1, надежностью 1/2, а также полилогарифмической сложностью случайных бит и запросов. Профессор Калай раскрывает секрет: студенты уже знают, как это сделать, поскольку конструкция представляет собой полностью «распакованный» интерактивный протокол GKR.
Для демонстрации выбирается NP-полная задача 3SAT. Схема верификации для 3SAT имеет небольшую (полилогарифмическую) глубину, что критично для GKR, где коммуникационная сложность растет вместе с глубиной схемы. Любой язык из NP можно свести к 3SAT с веером входа (fan-in) равным 2, что дает глубину порядка $O(\log n)$. Такая схема является однородной по логарифмической памяти (logspace uniform), а ее вентили сложения ($add$) и умножения ($mult$) эффективно вычислимы в виде многочленов.
При воссоздании протокола GKR для PCP выполняются следующие шаги:
- Берется свидетельство $w$ (выполняющий набор для 3SAT);
- Схема верификации разбивается по слоям. Для каждого слоя $i$ вычисляются значения всех проводов (размера $s$);
- Индексы проводов кодируются в $m$-мерном кубе над некоторым множеством $H$, так что $H^m = s$;
- Строится низкостепенное продолжение (low-degree extension, LDE) для каждого слоя $V_i \to \tilde{V}_i$ над полем $F$, содержащим $H$.
Яэль Калай обращает внимание на тонкую инженерию параметров. Если бы мы использовали привычное бинарное кодирование ($H = {0, 1}$ и $m = \log s$), размер поля $F$ для обеспечения надежности пришлось бы увеличивать настолько, что размер пространства $F^m$ стал бы суперполиномиальным. Чтобы сохранить полиномиальный размер доказательства, параметры выбираются иначе: $H \approx \log s$, а $m \approx \log s / \log \log s$. Тогда размер поля $F$ остается полилогарифмическим, а $F^m$ — строго полиномиальным от $s$.
🌳 Как устроено оракульное дерево PCP 38:52
В интерактивном протоколе GKR верификатор последовательно запускает протоколы Sumcheck от выходного слоя к входному. Но в системе PCP нет живого доказывающего. Решение заключается в том, чтобы «записать на небесах» (в оракул) абсолютно все возможные ответы доказывающего на любые случайные вызовы верификатора.
Структура PCP-доказательства $\pi$ включает в себя:
- Таблицы значений низкостепенных продолжений $\tilde{V}_i(z)$ для каждого слоя $i$ и для всех возможных точек $z \in F^m$;
- Полные деревья промежуточных протоколов Sumcheck для каждого слоя $i$ и каждой точки $z$.
Поскольку Sumcheck выполняется по $3m$ переменным (для вентилей $add$ и $mult$), верификатор в интерактивной среде генерирует случайный вектор $(r_1, r_2, \dots, r_{3m})$. В PCP-доказательство закладываются все частичные трассировки (transcripts) для любых подмножеств случайных вызовов. Для каждого фиксированного $r_1$ записывается ответ доказывающего, для каждой пары $(r_1, r_2)$ — следующий ответ и так далее.
Хотя это выглядит как гигантское экспоненциальное дерево, за счет малой глубины и грамотного подбора параметров его итоговый размер составляет всего порядка $|F|^{3m}$, что является полиномом от $s$. Верификатор PCP просто симулирует общение с GKR-доказывающим: считывает значение на выходе (ожидая 1), делает полилогарифмическое число случайных запросов к деревьям Sumcheck и сверяет их концы с соответствующими точками на слое ниже. На самом нижнем уровне (входной слой) верификатор самостоятельно вычисляет значение LDE для известного ему утверждения $x$ и считывает предоставленное доказывающим LDE для свидетельства $w$.
🛡️ Анализ надежности и дискуссия о случайности 1:06:00
Надежность полученной конструкции напрямую зависит от размера поля $F$. В рамках одного протокола Sumcheck по $3m$ переменным вероятность обмана составляет $3m \cdot \frac{|H|}{|F|}$. Поскольку верификатор проверяет цепочку из $2d$ последовательных протоколов Sumcheck (где $d$ — глубина схемы), общая ошибка надежности оценивается через неравенство Буля (union bound) как $2d \cdot 3m \cdot \frac{|H|}{|F|}$. Чтобы удержать эту вероятность ниже $1/2$, достаточно выбрать размер поля $|F| > 12d \cdot m \cdot |H|$, что легко укладывается в полилогарифмические рамки.
Во время лекции разворачивается глубокая дискуссия, когда один из студентов предлагает оптимизировать случайность: «Можно ли использовать одни и те же случайные биты во всех раундах, чтобы избавиться от фактора $d$?».
По мнению профессора Калай, в классическом протоколе GKR это привело бы к катастрофе, так как адаптивный доказывающий мгновенно узнал бы случайность последующих раундов из первого ответа и смог бы выстроить стратегию обмана. Однако студент возражает, указывая на то, что в PCP руки доказывающего «связаны» статичным оракулом — он не может менять свои ответы на ходу. Другие участники дискуссии добавляют, что доказывающий, зная о корреляции случайности заранее, все равно может спроектировать структуру дерева так, чтобы использовать это повторение себе во благо.
Яэль Калай признает эту дискуссию чрезвычайно интересной и полушутя благодарит студентов за отличную идею для задачи в следующем домашнем задании (P-set). В завершение лекции она напоминает о критически важном элементе, который необходимо добавить к верификатору: тесте на низкую степень (low-degree test) для входного слоя свидетельства $V_0$. В исходном GKR верификатор сам держал в руках вход и строил LDE, здесь же оракул может подсунуть многочлен произвольно высокой степени, поэтому прямая проверка его структуры обязательна.
