В лекции Массачусетского технологического института (MIT OpenCourseWare) представлена долгожданная конструкция лаконичных неинтерактивных аргументов знания (SNARG). Профессор подробно объясняет, как связать два мощных криптографических примитива: пакетные аргументы (BARG) и локально извлекаемые хеш-функции. Этот метод позволяет доказывать корректность масштабных вычислений без раскрытия лишних данных и с минимальными затратами времени на проверку со стороны верификатора.
📦 Пакетные аргументы (BARG) как фундамент системы 1:08
Профессор начинает финальное занятие курса с угощения студентов печеньем, чтобы подсластить сложную тему, и сразу переходит к повторению ключевых криптографических понятий. Главная цель текущей лекции — собрать воедино полноценную структуру криптографического доказательства SNARG. Основой для этого служат пакетные аргументы, или BARG (Batch Arguments), предназначенные для одновременного доказательства того, что множество различных инстансов принадлежат к одному NP-языку.
Конструкция BARG для NP-языка состоит из трех основных алгоритмов:
- Gen (генерация параметров): принимает на вход параметр безопасности $\lambda$ (в унарной системе счисления для обеспечения полиномиального времени работы), а также количество инстансов $k$ и длину каждого инстанса $n$ в бинарном виде. В результате работы алгоритм выдает общую строку параметров (CRS) за время, пропорциональное полилогу от $k$ и $n$.
- Prover (доказывающий): принимает CRS, набор из $k$ инстансов вместе с их секретными свидетельствами (witnesses) и формирует лаконичное доказательство $\pi$.
- Verifier (проверяющий): принимает CRS, инстансы и доказательство, после чего выдает вердикт — принять или отклонить (1 или 0).
Критически важным свойством BARG является его лаконичность: размер доказательства $\pi$ должен зависеть от количества задач $k$ лишь логарифмически — $\text{poly}(\lambda, \log k)$. Профессор подчеркивает, что криптографы допускают полиномиальную зависимость размера доказательства от длины одного свидетельства, но оно ни в коем случае не должно линейно расти вместе с увеличением числа инстансов $k$.
🛡️ Проблема полуадаптивной надежности 5:32
В вопросах вычислительной надежности (soundness) криптографических протоколов принципиальное значение имеет момент, когда именно потенциальный злоумышленник выбирает ложные утверждения. Если выбор происходит до того, как он увидит CRS, надежность называют неадаптивной; если после — адаптивной. Профессор отмечает, что идеальной целью криптографии является защита от полностью адаптивного противника, способного подстраиваться под параметры системы.
Однако на практике в базовой схеме BARG удается гарантировать лишь промежуточный вариант — полуадаптивную надежность (semi-adaptive soundness). В этой модели злоумышленник может выбирать сами инстансы адаптивно, но позицию (индекс $i$), на которой он планирует смухлевать и подсунуть ложное утверждение, он обязан зафиксировать до ознакомления с CRS. Вероятность того, что прувер сможет успешно обмануть верификатора на этой конкретной позиции, должна быть пренебрежимо малой (negligible). Злоумышленник при этом может делать все что угодно с остальными позициями в пакете, но факт обмана на зафиксированном индексе $i$ гарантированно аннулирует доказательство.
По мнению профессора, прямая трансформация такой полуадаптивной схемы в полностью адаптивную через банальное угадывание индекса (с вероятностью успеха $1/k$) сталкивается с серьезными аналитическими трудностями. Проблема заключается в том, что при изменении CRS в процессе доказательства безопасности противник может незаметно изменить точку обмана (например, сдвинуться на другой индекс), тем самым уходя от криптографической ловушки. Ситуация усложняется тем, что для стороннего наблюдателя математически крайне трудно эффективно определить, является ли конкретный инстанс истинным или ложным.
🔑 Локально извлекаемый хеш: второй элемент пазла 14:44
Вторым незаменимым компонентом для построения SNARG является семейство локально извлекаемых хеш-функций, также известных в академической литературе как SSB-хеш (Somewhere Statistically Binding). Этот примитив позволяет сжать длинную строку данных в компактное значение, сохранив при этом жесткую математическую привязку к конкретному биту исходного текста.
Полный математический аппарат SSB-хеша включает в себя пять алгоритмов, работающих за полиномиальное время:
- Gen (генерация ключа): принимает параметр безопасности, длину входного текста $n$ (не превышающую $2^\lambda$) и целевой индекс $i$, генерируя публичный ключ хеширования и секретный трапдор (trapdoor).
- Eval (вычисление): принимает ключ и $n$-битную строку, возвращая компактное значение хеша $v$.
- Open (открытие): позволяет пруверу сформировать локальное доказательство (открытие) $\rho_j$ для любого конкретного бита под произвольным индексом $j$.
- Ver (верификация): дает возможность верификатору проверить корректность открытого бита на позиции $j$, используя лишь компактный хеш, индекс и доказательство.
- Extract (извлечение): позволяет с помощью секретного трапдора гарантированно извлечь исходный $i$-й бит прямо из значения хеша.
🔒 Три столпа безопасности SSB-хеша 18:26
Безопасность системы опирается на три фундаментальных свойства. Первое — полнота (completeness): при честном выполнении протокола верификатор всегда принимает доказательство открытия, а алгоритм извлечения выдает абсолютно точный бит.
Второе свойство — скрытие индекса (index hiding). Ключ хеширования устроен так, что внешнему наблюдателю невозможно определить, на какой именно индекс $i$ была настроена извлекаемость при генерации ключа. Ключи, созданные для разных индексов, вычислительно неотличимы друг от друга.
Третье свойство — статистическая привязка (somewhere statistical binding). На целевом индексе $i$ даже всесильный противник с неограниченными вычислительными ресурсами неспособен создать такое значение хеша, которое можно было бы одновременно успешно открыть и как 0, и как 1. Профессор уточняет, что для подавляющего большинства генерируемых ключей математически просто не существует тройки из значения хеша и двух конфликтующих доказательств открытия. Благодаря скрытию индекса, жесткая статистическая привязка на одной позиции автоматически гарантирует вычислительную привязку на всех остальных позициях схемы для любого полиномиального противника.
Эту криптографическую схему можно успешно масштабировать. Путем параллельного повторения алгоритма генерации ключей $l$ раз криптографы получают хеш, обладающий свойством извлекаемости сразу для $l$ различных позиций. При этом раскрытие трапдоров для части позиций оставляет остальные индексы полностью скрытыми и защищенными от компрометации.
🛠️ Архитектура гомоморфного шифрования и подводные камни 42:16
Разбирая внутреннее устройство локально извлекаемого хеша, профессор описывает метод его реализации на базе полностью гомоморфного шифрования (FHE). Естественная, но ошибочная на первый взгляд идея заключается в том, чтобы заложить в ключ хеширования побитовое шифрование целевого индекса, а затем построить дерево Меркла, где каждый узел является результатом гомоморфного вычисления. Программа под капотом должна выбирать левого или правого потомка в зависимости от зашифрованного бита индекса, последовательно поднимая выбранное значение к корню дерева.
Однако такая наивная схема не обеспечивает необходимую статистическую привязку. Главная опасность кроется в действиях вредоносного прувера, который может подать на вход «мусорные» данные — некорректные биты, которые вообще не являются валидными шифртекстами FHE и не поддаются дешифровке. Он может использовать эти дефектные блоки для создания ложных доказательств открытия в двух разных направлениях.
Для обхода этой уязвимости криптографическую архитектуру приходится существенно усложнять. Вместо одного публичного ключа шифрования используется цепочка из множества ключей, соответствующих уровням дерева вычислений. Внутри защищенного гомоморфного «ящика» на каждом уровне дерева происходит принудительная расшифровка предыдущего шифртекста с помощью секретного ключа предыдущего уровня и его последующая чистая перешифровка следующим ключом.
По словам профессора, даже если один из промежуточных элементов дерева окажется поврежденным или вредоносным, индуктивный метод построения гарантирует, что на самом пути локального открытия все шифртексты будут математически корректными и расшифруются правильно. Верификатор выполняет те же самые гомоморфные проверки, полностью лишая злоумышленника шанса на фальсификацию. Поскольку глубина вычислений в данном дереве строго ограничена, криптографам удается избежать тяжелых допущений о циклической безопасности (circular security) алгоритмов шифрования, обходясь без дорогостоящей процедуры бутстрапинга.
🚀 Финальная сборка: Объединение BARG и SSB в структуру SNARG 1:02:42
Достигнув кульминации курса, профессор представляет итоговую схему SNARG, которая изящно объединяет изученные элементы. Задача состоит в том, чтобы неинтерактивно доказать верификатору, что для некоторого входа $x$ логическая схема вычислений $C_x$ выдает истинное значение (единицу).
Процесс генерации доказательства SNARG выглядит следующим образом:
- Шаг 1: Доказывающий (прувер) полностью просчитывает значения абсолютно всех внутренних проводов (wires) логической схемы вычислений для заданного входа и свидетельства.
- Шаг 2: Все полученные значения проводов упаковываются и сжимаются в единое компактное значение с помощью локально извлекаемого SSB-хеша.
- Шаг 3: Прувер задействует пакетный аргумент (BARG) для одновременного подтверждения того, что каждый логический вентиль (gate) в схеме работает корректно, а финальный выходной провод равен единице.
В рамках BARG-доказательства для каждого вентиля проверяется валидность открытия двух входных проводов и одного выходного провода относительно общего хеша. Свидетельством для пакетного доказательства выступает кортеж, подтверждающий, что значения проводов соответствуют логике конкретного вентиля (например, логическому «И») и успешно проходят верификацию хеша.
⚡ Секрет экстремальной эффективности верификатора 1:24:20
Главная ценность получившейся конструкции SNARG заключается в феноменальной скорости проверки доказательства верификатором. Количество вентилей в сложных вычислениях $k$ может быть огромным. Если бы верификатору приходилось проверять каждый из них вручную, свойство лаконичности было бы полностью утрачено.
Спасением служит использование так называемых индексируемых языков (index languages). Поскольку структура проверяемой логической схемы регулярна и известна заранее, все $k$ инстансов пакетного аргумента имеют строгое и компактное математическое описание. Верификатору не нужно читать гигантский список задач — его время работы зависит лишь от компактного размера самого входа $x$ и полилогарифмически растет от общего размера вычислений $\text{polylog}(k)$.
Профессор резюмирует, что благодаря такому подходу размер доказательства и затраты на его верификацию остаются минимальными. Это знаменует собой успешное завершение долгого теоретического пути к построению полноценных лаконичных неинтерактивных аргументов знания.
