# Интерактивные доказательства: от протокола Sum-Check до верификации сложных вычислений Источник: https://www.youtube.com/watch?v=SRY3F9vtJHo Канал: MIT OpenCourseWare Опубликовано: 29.01.2025 --- На лекции в Массачусетском технологическом институте (MIT OpenCourseWare) было представлено глубокое погружение в мир интерактивных доказательств и протокола Sum-Check. Профессор подробно разобрал, как абстрактные криптографические концепции применяются к классическим задачам информатики, таким как #SAT и подсчет треугольников в графах. Особое внимание было уделено переходу к концепции «дважды эффективных» протоколов, которые позволяют оптимизировать вычисления и находят реальное применение в современных блокчейн-системах. ## 🎲 Открытые монеты и сила случайности верификатора [[JUMP:1:05]] В начале занятия лектор провел интерактивный опрос среди аудитории, в шутку попросив всех закрыть глаза, чтобы честно оценить темп подачи материала. Убедившись, что группа довольна скоростью изложения, профессор перешел к разбору важного свойства протокола Sum-Check, которое не было детально освещено ранее. В рамках этого протокола доказывающий (prover) отправляет полиномы низких степеней, в то время как верификатор (verifier) в ответ посылает исключительно случайные элементы поля. Каждый раунд верификатор выбирает случайные биты и открыто передает их доказывающему. Протоколы такого типа называют протоколами с «открытой монетой» (public coin protocols). Это свойство критически важно, поскольку в дальнейшем, с помощью криптографических методов, оно позволяет полностью исключить интерактивность из протокола. Один из студентов поинтересовался, имеет ли смысл использовать случайность на стороне доказывающего. По словам профессора, случайность со стороны доказывающего не добавляет протоколу силы, поскольку все его «монеты» можно заранее зафиксировать. Случайность доказывающего становится необходимой только в протоколах нулевого разглашения (zero knowledge), где главной целью является скрытие информации. В текущем же контексте случайность верификатора имеет первостепенное значение. Доказывающий не должен знать, какую именно точку $t$ выберет верификатор. Если бы доказывающий знал эту точку заранее, он мог бы легко смухлевать, предоставив ложный полином, который случайно совпадает с истинным именно в точке $t$. Таким образом, случайность используется как оружие против потенциально нечестного доказывающего, в то время как верификатор априори считается честным. Профессор подчеркнул, что под «открытой монетой» подразумевается абсолютная прозрачность действий верификатора: он не скрывает свои биты и не сохраняет никакого внутреннего секретного состояния между раундами. Он просто генерирует и отправляет истинно равномерные случайные биты. ## 📦 Геометрическая интерпретация надежности [[JUMP:7:06]] Для лучшего понимания математической строгости протокола была предложена наглядная геометрическая интерпретация его надежности (soundness). Представим себе гиперкуб $H^m$. Доказывающий пытается убедить верификатора в том, что сумма значений низкостепенного полинома во всех точках этого куба равна некоторому значению $\beta$. Если доказывающий пытается обмануть верификатора и исходное утверждение ложно, то вычисленная сумма неизбежно должна быть ошибочной хотя бы на одном из элементов куба. Верификатор не знает, где именно кроется ошибка. Однако благодаря механизмам коррекции ошибок, если утверждение неверно хотя бы в одной точке, оно окажется неверным и в случайной точке расширения поля $t_1$ с высокой степенью вероятности. В ходе протокола верификатор последовательно переходит от одной размерности к другой: * Сначала фиксируется случайная точка $t_1$, и фокус смещается на оставшиеся координаты. * Если утверждение ложно на $t_1$, оно должно быть ложным хотя бы для одного значения следующей координаты $h_2$. * Верификатор снова выбирает случайную точку в расширении поля и с высокой вероятностью обнаруживает ошибку там. Этот процесс напоминает «прыжки» по измерениям — от $t_1, t_2$ к $t_3, t_4$ и так далее, пока верификатор не доберется до финальной случайной точки, где обман доказывающего станет очевидным. ## 🧮 Протокол Sum-Check на службе #SAT [[JUMP:9:30]] Протокол Sum-Check может показаться очень специфическим инструментом, однако он обладает колоссальной общностью. В качестве примера профессор продемонстрировал, как с его помощью можно построить интерактивное доказательство для классической задачи #SAT (Sharp SAT). Суть задачи #SAT заключается в следующем: дана булева формула $\phi$ от $n$ переменных, и необходимо определить точное количество наборов аргументов, удовлетворяющих этой формуле. Сама формула представляет собой бинарное дерево, где внутренние узлы — это логические вентили (И, ИЛИ, НЕ), а листья — переменные $x_i$ или их отрицания. Размер такой формулы определяется количеством ее листьев. Профессор обратил внимание на важное различие между формулой и схемой (circuit): * Формула — это строго бинарное дерево. Если один и тот же промежуточный результат нужен в разных частях формулы, его приходится вычислять заново. * Схема представляет собой произвольный направленный ациклический граф (DAG), что позволяет существенно оптимизировать вычисления, избегая дублирования. Задача #SAT для формул считается крайне сложной. Тем не менее её можно элегантно свести к протоколу Sum-Check с помощью метода арифметизации. Идея заключается в преобразовании логических операций над булевыми значениями (0 и 1) в полиномиальные операции над большим конечным полем $F$. Перевод логических вентилей в арифметические элементы происходит по следующим правилам: 1. Вентиль «И» (AND) от $x$ и $y$ заменяется на умножение: $x \cdot y$. 2. Вентиль «ИЛИ» (OR) трансформируется в выражение: $x + y - x \cdot y$. 3. Вентиль «НЕ» (NOT) превращается в вычитание: $1 - x$. В результате исходная булева формула преобразуется в арифметическую схему $\tilde{\phi}$, которая на булевом кубе $\{0,1\}^n$ ведет себя точно так же, как исходная логическая формула. Задача подсчета числа удовлетворяющих наборов сводится к вычислению суммы значений $\tilde{\phi}$ по всем точкам булева куба и проверке, равна ли эта сумма числу $k$. ## 📐 Анализ степени и сложности вычислений [[JUMP:19:50]] Для успешного применения Sum-Check необходимо гарантировать, что степень полученного полинома не слишком велика. Профессор сформулировал и доказал методом индукции по глубине формулы утверждение: сумма степеней всех переменных в арифметизированном полиноме $\tilde{\phi}$ не превышает размер исходной формулы $s$ (число листьев). Поскольку размер формулы является полиномиальным, степень полинома также остается полиномиальной, что гарантирует эффективность верификатора. Итоговые параметры сложности протокола выглядят следующим образом: * **Количество раундов:** равно числу переменных $n$. * **Сложность верификатора:** составляет $n \cdot s \cdot \text{polylog}(|F|)$. * **Вероятность ошибки (soundness error):** составляет $n \cdot s / |F|$. Чтобы обеспечить высокую надежность, достаточно выбрать конечное поле $F$, размер которого значительно превосходит произведение $n \cdot s$. В ходе дискуссии студенты подняли вопрос о характеристике поля: что делать, если искомое число решений $k$ превышает размер поля? Профессор пояснил, что поле изначально выбирается достаточно большим. Слушатели предложили альтернативный вариант — запуск протокола параллельно над несколькими небольшими полями с последующим применением Китайской теоремы об остатках. По мнению студентов, это позволило бы снизить общую вычислительную сложность и распараллелить процесс. Профессор согласился, что такой подход жизнеспособен. В завершение раздела лектор сравнил #SAT для формул с аналогичной задачей для схем (Sharp Circuit SAT). Для общих схем степень полинома при стандартной арифметизации может оказаться слишком высокой, что требует сложных процедур понижения степени (degree reduction) — именно этот механизм использовал Шамир в своем знаменитом доказательстве равенства классов IP и PSPACE. Для формул же низкая степень обеспечивается автоматически, что делает протокол максимально простым и изящным. ## ⚡ Дважды эффективные доказательства: шаг к реальности [[JUMP:40:07]] До сих пор при рассмотрении интерактивных доказательств классическая теория фокусировалась на том, чтобы верификатор работал за полиномиальное время, в то время как доказывающий мог обладать неограниченной вычислительной мощностью. В рассмотренных ранее протоколах для #SAT доказывающий неизбежно тратит экспоненциальное время ($2^n$), чтобы просто перебрать все варианты. Однако, как резонно заметил профессор, в реальной жизни всесильных доказывающих не существует — любые вычислительные ресурсы ограничены. Это привело к формированию концепции «дважды эффективных интерактивных доказательств» (doubly efficient interactive proofs), где ограничения накладываются на обе стороны. В таком протоколе рассматриваются даже задачи из класса P, которые сами по себе могут быть решены за полиномиальное время (например, за $n^4$). Цель состоит в том, чтобы верификатор тратил существенно меньше времени, чем требуется для прямого решения задачи (например, работал за линейное или квазилинейное время $\tilde{O}(n)$). При этом честный доказывающий не должен нести колоссальных вычислительных накладных расходов: время его работы должно иметь лишь небольшое полиномиальное (а в идеале — линейное) приращение относительно детерминированного времени решения задачи. Подобные протоколы крайне востребованы на практике, например, при масштабировании блокчейн-систем. Профессор сослался на лекционные заметки Джастина Талера (Justin Thaler), где подробно описаны конкретные параметры и практические реализации таких систем. ## 🔺 Поиск треугольников в графах через полиномы [[JUMP:46:14]] Для демонстрации концепции двойной эффективности профессор предложил разобрать задачу из класса P — подсчет точного количества треугольников в заданном графе $G = (V, E)$. В лоб эту задачу можно решить за время $O(n^3)$ (где $n$ — число вершин), просто перебрав все возможные тройки вершин. Цель интерактива — позволить верификатору убедиться в правильности ответа за линейное время, заставив доказывающего выполнить основную работу с минимальным оверхэдом. Для этого граф необходимо представить в виде полинома. Профессор напомнил свой тезис о том, что «все вокруг может стать полиномом». Мы берем матрицу смежности графа и описываем её как функцию $f$, которая принимает пару вершин в бинарном представлении (из пространства $\{0,1\}^{\log n} \times \{0,1\}^{\log n}$) и возвращает 1, если ребро существует, и 0 в противном случае. Тогда число треугольников $k$ можно выразить через следующую сумму по всем тройкам вершин $i, j, k$: $$\frac{1}{6} \sum_{i,j,k} f(i,j) \cdot f(j,k) \cdot f(i,k) = k$$ Множитель $1/6$ необходим, поскольку каждая тройка вершин, образующая треугольник, учитывается во всех шести возможных перестановках. Выражение под суммой уже напоминает структуру протокола Sum-Check, однако здесь все еще нет алгебры поля — функция оперирует сугубо булевыми значениями. При этом размер пространства перебора составляет $2^{3 \log n}$, что эквивалентно полиному от $n$, а значит, доказывающий укладывается в полиномиальное время работы. ## 📐 Теорема о низкостепенном расширении (LDE) [[JUMP:54:09]] Для того чтобы привнести в задачу о треугольниках алгебраическую структуру, используется фундаментальный метод под названием «низкостепенное расширение» (Low-Degree Extension, LDE). Этот метод позволяет преобразовать любую дискретную функцию в уникальный полином низкой степени. Профессор провел аналогию с одномерным случаем, упомянутым на первой лекции в контексте умножения матриц. Там строка матрицы из $n$ элементов интерпретировалась как полином от одной переменной степени $n-1$. Однако в текущей задаче одномерный полином не подходит: его степень оказалась бы равной $n^2$, и верификатор потерял бы свою эффективность. Решением является переход к многомерным полиномам (multivariate polynomials). Теорема о низкостепенном расширении гласит: для любой функции $f: H^m \rightarrow \{0,1\}$ и любого конечного поля $F$, содержащего множество $H$, существует единственное расширение — полином $\tilde{f}: F^m \rightarrow F$, который совпадает с $f$ на исходном гиперкубе $H^m$. При этом степень полинома $\tilde{f}$ по каждой отдельной переменной не превышает $|H| - 1$. Идея заключается в добавлении новых переменных. Вместо того чтобы упаковывать данные в огромную степень одной переменной, мы распределяем их по множеству измерений малого размера. Если соотнести параметры так, чтобы $|H|^m = n$, то в каждом измерении степень полинома составит всего лишь $|H| - 1$ вместо $n-1$. Например, если выбрать размер множества $|H| = \log n$, то степень полинома по каждой переменной будет равна всего лишь $\log n$, что является отличным результатом. Время работы верификатора в таком случае зависит от параметров $m$, $H$ и степени полинома, превращаясь в полилогарифмическую величину, что крайне эффективно. На следующей лекции профессор пообещал детально разобрать доказательство теоремы LDE и продемонстрировать ее финальное применение как для подсчета треугольников, так и для верификации любых вычислительных схем малой глубины.