В рамках курса лекций от MIT OpenCourseWare профессор подробно разбирает вторую часть темы дважды эффективных интерактивных доказательств (Doubly Efficient Interactive Proofs). В центре внимания находится оптимизация знаменитого протокола GKR, которая позволяет избежать экспоненциального роста числа проверок при переходе между слоями арифметической схемы. Благодаря изящному решению проводить параллельные проверки с использованием одинаковой случайности верификатора, протокол сохраняет высокую эффективность и надежность.
📋 Административные вопросы и подведение итогов 0:13
В начале занятия профессор делает небольшое административное объявление, касающееся листа записи для конспектирования лекций (Scribd). Все доступные места были распределены крайне быстро. Профессор предлагает студентам, которые слушают курс ради зачетов, но не успели записаться, подойти после лекции для оценки точного количества участников. В качестве альтернативы предлагается вести конспекты совместно с кем-то или взять на себя другие задачи в рамках учебного процесса.
Перед тем как перейти к разбору перехода от одного утверждения к двум, профессор возвращается к вопросам, заданным во время перерыва, чтобы прояснить общую картину происходящего.
В рамках рассматриваемой модели доказывающий (prover) утверждает, что на определенном слое $i$ значение в заданной точке расширения равно $V_i^$. На самом деле доказывающий заявляет, что $V_i^$ является суммой огромного многочлена от многих переменных. Для верификации этого утверждения используется стандартный интерактивный протокол сумма-проверка (sum-check protocol), где проверяемой величиной выступает заявленное значение $V_i^*$.
⚙️ Протокол сумма-проверка как «черный ящик» 2:13
Для понимания дальнейших шагов нет необходимости детально помнить устройство протокола сумма-проверка, его можно рассматривать как «черный ящик». В ходе этого протокола доказывающий постоянно отправляет одномерные полиномы низкой степени, а верификатор выполняет их проверку. Важно отметить, что на протяжении всего процесса сумма-проверки верификатор лишь отправляет случайные элементы поля и выполняет базовые вычисления. Верификатору не нужно знать, как устроен весь гигантский многочлен $f$.
Единственный момент, когда верификатору действительно необходимо сопоставить значения, — это финальная проверка равенства многочлена в случайной точке некоторому элементу поля, полученному в результате протокола.
В теоретической модели предполагалось, что верификатор имеет доступ к Оракулу для этого многочлена, однако в реальности у него нет доступа к этой огромной вычислительной структуре. Более того, верификатор не способен самостоятельно вычислить низкостепенное расширение (low-degree extension) для слоя, находящегося уровнем ниже.
Чтобы решить эту проблему, протокол усложняется: теперь доказывающий сам должен предоставить верификатору два необходимых значения для следующего слоя вычислений.
Если доказывающий попытается смошенничать и предоставить неверные значения, то с крайне высокой вероятностью он будет пойман благодаря математическим свойствам надежности (soundness) протокола сумма-проверки. Если же доказывающий предоставит честные значения, верификатор вычислит правильную функцию, заметит подлог на предыдущем шаге и отклонит доказательство. Таким образом, чтобы иметь шанс на успех, доказывающий вынужден давать ложные ответы. В итоге одно исходное утверждение на слое $i$ редуцируется к двум ложным утверждениям на слое $i+1$.
💡 Парадокс ветвления и идея Лизы: параллельные проверки 6:23
Редукция одного утверждения к двум создает серьезную проблему: при последовательном переходе по слоям количество проверяемых утверждений начнет лавинообразно расти — от двух к четырем, затем к восьми и так далее. Это привело бы к экспоненциальному взрыву сложности.
Профессор отмечает, что в оригинальной статье GKR использовался достаточно сложный промежуточный протокол для обратного сведения двух утверждений к одному. Однако существует гораздо более простое решение, которое профессор сначала ошибочно приписывает Рейчел, но аудитория вовремя поправляет лектора: автором этой элегантной идеи является Лиза.
Суть идеи Лизы заключается в том, чтобы вообще не пытаться сводить два утверждения к одному, а продолжить работу с двумя претензиями. Количество проверок не будет расти дальше и зафиксируется на двойке на каждом последующем слое.
Для этого верификатор запускает два протокола сумма-проверки параллельно для двух разных функций. Основной трюк состоит в использовании одной и той же случайности (verifier randomness) для обеих параллельных проверок.
В результате применения одинаковых случайных элементов поля в самом конце протокола верификатору требуется проверить значения двух функций в одних и тех же случайных точках. Все, что теперь требуется от доказывающего для помощи верификатору, — это предоставить значения многочлена в этих зафиксированных точках. Мы начали с двух значений и закончили двумя значениями, избавившись от экспоненциального расширения.
Таким образом, протокол GKR представляет собой последовательность из пар параллельных сумма-проверок, выполняемых для каждого из слоев арифметической схемы. Крайне важно, чтобы эти проверки на каждом слое выполнялись строго параллельно, а не последовательно. Если запускать их по очереди, доказывающий узнает случайные монеты верификатора заранее и сможет успешно сфальсифицировать результаты.
📊 Анализ сложности протокола GKR 20:45
Профессор переходит к математическому анализу сложности оптимизированного протокола. Полнота (completeness) протокола тривиально следует из свойств базовой сумма-проверки: если все вычисления честны, верификатор примет доказательство.
Параметры сложности выглядят следующим образом:
- Коммуникационная сложность: Поскольку мы имеем $d$ слоев схемы и на каждом выполняем пару параллельных сумма-проверок, общая коммуникация зависит от количества переменных $m$ и степени полинома. Объем передаваемых данных оценивается как $d \times \text{polylog } s$, где $s$ — размер схемы.
- Время работы верификатора: Верификатор тратит время, эквивалентное коммуникационной сложности, выполняя отправку случайных чисел и простейшие проверки константного числа элементов поля на каждом шаге.
- Время работы доказывающего: Доказывающий выполняет работу по вычислению полиномов низкой степени. Время его работы полиномиально зависит от размера схемы ($\text{poly } s$), и глубина схемы $d$ не оказывает на него критического негативного влияния.
🛡️ Доказательство надежности (Soundness) 24:40
Анализ надежности строится от противного. Предположим, что существует нечестный доказывающий, который может успешно обмануть верификатора с некоторой вероятностью $\epsilon$. Поскольку в самом начале (на выходном слое) он предоставляет ложное утверждение, а в самом конце (на входном слое) верификатор проверяет данные самостоятельно и принимает только правду, должен существовать хотя бы один слой, на котором произошло «чудо»: ложное утверждение превратилось в истинное.
Для формализации этого вводится обозначение «плохого события» $B_i$. Это событие, при котором на раунде $i-1$ хотя бы одно из двух утверждений доказывающего было ложным, но на раунде $i$ оба утверждения после раунда сумма-проверки внезапно оказались истинными.
Поскольку общая вероятность обмана равна $\epsilon$, по неравенству Буля (union bound) вероятность того, что произойдет хотя бы одно из плохих событий от первого до последнего слоя, должна быть не меньше $\epsilon$. Каждое событие $B_i$ разделяется на два подслучая: когда ложным было первое утверждение ($B_{i,1}$) или второе ($B_{i,2}$). Успешный переход от лжи к правде внутри одного раунда означает, что доказывающий смог обмануть базовый протокол сумма-проверки.
Вероятность обмана в одиночном протоколе сумма-проверки крайне мала и ограничена величиной порядка $\log^2 s / |F|$, где $|F|$ — размер конечного поля. Таким образом, выбирая достаточно большое поле $F$, мы можем сделать общую вероятность ошибки $\epsilon$ пренебрежимо малой.
Профессор отдельно подчеркивает, что использование одной и той же случайности для двух параллельных проверок не несет в себе опасности. Благодаря методу union bound корреляция между проверками не нарушает общую строгую оценку надежности протокола.
🏁 Финальный этап: входной слой и структура схемы 38:29
Когда протокол достигает самого нижнего, входного слоя схемы, верификатору больше не нужно запрашивать данные у провера. Ему требуется лишь самостоятельно вычислить значения низкостепенного расширения для фактических входных данных $x_1, \dots, x_n$ в двух финальных точках.
Поскольку размер входа $n$ существенно меньше общего размера вычислительной схемы $s$, верификатор может выполнить это вычисление за квазилинейное время относительно $n$. Если для выравнивания структуры схемы требуются фиктивные переменные (padding), их значения просто приравниваются к нулю, что значительно упрощает нотацию и вычисления.
В конце лекции студент Лео задает вопрос о жесткости ограничения на коэффициент ветвления (fan-in), равный двум, который заложен в формулу логических вентилей. Профессор поясняет, что двойка обусловлена тем, что каждый вентиль в рассматриваемой модели имеет строго двух «детей» (входы).
Лео предполагает, что можно использовать вентили с большим числом входов при меньшей общей глубине схемы, проводя больше параллельных сумма-проверок. Профессор полностью соглашается с этим наблюдением: в числе 2 нет никакой магии. Можно строить схемы с более широким ветвлением, при условии, что оно не превышает полилогарифмическую величину, иначе резко возрастет коммуникационная сложность протокола.
