# Лектор MIT объясняет создание PCP на базе протокола GKR Источник: https://www.youtube.com/watch?v=L8PXcZ2ExiU Канал: MIT OpenCourseWare Опубликовано: 29.01.2025 --- В современной теоретической информатике существует концепция, которая на первый взгляд кажется невозможной: проверка корректности сложнейшего математического доказательства без необходимости читать его целиком. В рамках курса MIT OpenCourseWare лектор Яэль Калай (Yael Kalai) раскрывает архитектуру вероятностно проверяемых доказательств (PCP), демонстрируя, как с помощью протокола GKR можно превратить громоздкие вычисления в компактные и легко проверяемые структуры. ## 🧩 Сущность PCP: Доказательства, которые не нужно читать целиком [[JUMP:02:26]] Вероятностно проверяемые доказательства (Probabilistically Checkable Proofs, PCP) — это радикальный пересмотр классического понятия доказательства в классе NP. В стандартном сценарии верификатор должен прочитать всё свидетельство (witness) целиком, чтобы убедиться в его истинности. PCP предлагает иной подход: преобразовать исходное доказательство в новую, возможно, более длинную строку, которую можно проверить, изучив лишь несколько случайных битов. Основные характеристики концепции PCP: * **Размер доказательства:** Оно может быть полиномиально больше оригинала. Если исходное свидетельство имеет размер $m$, то PCP-версия будет иметь размер $poly(n, m)$. * **Локальная проверка:** Верификатору не нужно сканировать весь массив данных. Он делает запросы (queries) к конкретным случайным позициям в доказательстве. * **Случайность:** Выбор позиций для проверки должен быть случайным. Яэль Калай подчеркивает: если бы провэр (доказывающий) заранее знал, какие биты будут проверяться, он мог бы легко сфальсифицировать ответ. * **Эффективность:** Современные достижения позволяют свести проверку любого доказательства всего к 3 битам, при этом сохраняется высокая вероятность обнаружения ошибки. В лекции обсуждается также расширение — PCP близости (PCP of Proximity). В этом случае верификатор не читает даже все входные данные $x$, а лишь гарантирует, что вход находится «близко» к какому-то значению из языка. --- ## 📊 Математическая формализация: Классы и параметры PCP [[JUMP:07:47]] Класс сложности PCP определяется набором параметров, которые описывают ресурсы верификатора. Математически это записывается как $PCP[c, s, r, q]$, где: 1. **Полнота ($c$):** Вероятность того, что верное утверждение будет принято (обычно $c = 1$). 2. **Надежность ($s$):** Максимальная вероятность того, что верификатор примет ложное утверждение. Цель — свести $s$ к минимуму (например, $1/2$). 3. **Случайность ($r$):** Количество случайных битов, используемых верификатором. 4. **Запросы ($q$):** Количество обращений к оракулу доказательства. Яэль Калай акцентирует внимание на **неадаптивности** верификатора: он выбирает все индексы для запросов сразу, до того как увидит содержимое оракула. Это свойство критически важно для создания лаконичных аргументов (succinct arguments) в криптографии. По словам лектора, хотя адаптивные верификаторы теоретически возможны, большинство известных конструкций PCP придерживаются неадаптивной схемы. --- ## 🧬 Построение PCP через протокол GKR [[JUMP:24:47]] Центральная часть лекции посвящена «развертыванию» протокола GKR для создания PCP. Основная идея заключается в том, чтобы взять интерактивный протокол и превратить его в статичное доказательство, записав все возможные ответы провэра в оракул. ### Подготовительный этап: 3SAT и арифметизация Для построения используется задача 3SAT, как NP-полная база. Схема верификации для 3SAT имеет малую глубину (polylog $n$), что идеально подходит для GKR, где сложность коммуникации растет вместе с глубиной схемы. ### Структура оракула в PCP Чтобы превратить интерактивный GKR в PCP, провэр должен заранее выложить в открытый доступ следующие данные: * **Расширения низкой степени (LDE):** Для каждого слоя схемы $i$ провэр вычисляет значения всех гейтов и записывает их расширение $V_i \tilde{}$ над полем $F$. * **Дерево всех ответов (Sumcheck Transcripts):** Поскольку верификатор в GKR посылает случайные сообщения, PCP-провэр должен записать свои ответы для *всех возможных* вариантов случайности верификатора. Это выглядит как экспоненциальное дерево, но благодаря правильному подбору параметров (параметр $m$ выбирается как $log \ n / log \ log \ n$), общее количество записей остается полиномиальным. --- ## 🧐 Анализ надежности и сложности [[JUMP:56:31]] Процесс верификации в такой системе сводится к тому, что верификатор «имитирует» сессию GKR, используя случайность для выбора пути в дереве ответов, хранящемся в PCP. **Обеспечение надежности (Soundness):** По мнению лектора, для того чтобы обмануть систему, провэру нужно успешно сжульничать хотя бы в одном из протоколов Sumcheck. Общая ошибка надежности оценивается через объединение (union bound) всех этапов и составляет примерно: $$2d \cdot \frac{3m \cdot |H|}{|F|}$$ где $d$ — глубина схемы, $m$ — количество переменных, а $|F|$ — размер поля. Чтобы надежность была не хуже $1/2$, размер поля $F$ должен быть значительно больше произведения этих параметров. **Почему PCP не «раздувается» до бесконечности?** Хотя верификатор использует много битов случайности (polylog $s$), размер PCP остается полиномиальным. Это происходит благодаря свойству «отсутствия памяти» в GKR: провэру не нужно помнить всю историю запросов, достаточно знать текущий слой и значения $V_i \tilde{}$. --- ## 🔐 Переход к криптографическим аргументам [[JUMP:01:20]] В завершающей части лекции Яэль Калай обозначает переход от информационно-теоретических доказательств к криптографическим «аргументам» (Interactive Arguments). * **Информационная надежность:** Гарантирует, что даже всемогущий провэр не сможет обмануть верификатора (это очень жесткое ограничение). * **Вычислительная надежность (Computational Soundness):** Мы предполагаем, что провэр ограничен в вычислительных ресурсах. Это позволяет обойти многие теоретические барьеры и строить более эффективные протоколы. Именно на этом стыке PCP и криптографии рождаются современные системы с нулевым разглашением и лаконичные доказательства, используемые в блокчейнах и защищенных вычислениях.