Разгадываем тайны ZK: Системы доказательств. От базовых концепций до продвинутых систем
Мы уже частично рассматривали архитекруту системы доказательств в предыдущей статье. В этой же предлагаю погрузится еще глубже в эту увлекательную тему и поговорить в целом, что же это такое.
Сначала мы начнем с обзора ее основных частей, потом погрузимся в историю и рассмотрим различные модели. Летс гоу! ;)
Что же такое система доказательств?
В информатике доказательство— это формальное демонстрирование того, что определенное утверждение является верным. Доказательства формализуются с использованием так называемых систем доказательств.
Мы можем разделить эти системы на пять основных частей:
1. Формальный язык
Системы доказательств передают утверждения и свойства через формальный язык, который можно рассматривать как точный и стандартизированный синтаксис для записи формул и выражения утверждений. Это включает в себя логические связки, кванторы, переменные и другие символы.
2. Аксиомы
Аксиомы — это базовые истины или предположения, которые принимаются за верные без доказательства. Они служат отправной точкой для построения доказательств.
3. Правила вывода
Правила вывода определяют, как одно утверждение может быть преобразовано в другое, следуя принципам логики.
4. Вывод доказательства
Чтобы вывести доказательство, мы начинаем с аксиом и используем правила вывода для получения новых утверждений из предыдущих утверждений, пока не придем к окончательному утверждению. Эта пошаговая деривация утверждений в конечном итоге приводит нас к нашему окончательному утверждению.
5. Корректность и полнота
Корректность говорит о том, что если утверждение доказано в системе, оно верно. Полнота гарантирует, что если утверждение верно и оно доказуемо в системе. Таким образом, корректность гарантирует, что системы доказательств не дают ложных результатов, а полнота обеспечивает принятие верных утверждений в системе доказательств.
Эволюция систем доказательств
Что ж , с базовым словарем систем доказательств мы разобрались. Теперь давайте рассмотрим, как они изменились за последние 30 лет. Мы воспользуемся классической задачей информатики, задачей раскраски графа, чтобы понять, как человек (то есть доказывающий) мог бы доказать свое решение другому человеку (то есть проверяющему) с использованием каждой системы.
Сначала о самой задаче раскраски графа:
Когда мы присваиваем вершинам графа метки — это называется раскраской графа. Цвета — это целые положительные цифры. Графы нужно раскрашивать так, чтобы соседние вершины имели разные цвета. Еще стоит использовать как можно меньше цветов. Снизу представлены некоторые примеры:
Первый пример на схеме выше не совсем верный, потому что соседним вершинам присваивается один и тот же цвет. Вторая раскраска лучше, так как удовлетворяет правилам, но в ней используется больше цветов, чем нужно. Третья раскраска — правильная. Она удовлетворяет правилам и использует как можно меньше цветов.
В этих графах невозможно использовать меньше трех цветов, так как треугольники содержат три вершины, которые являются соседями.
Теперь давайте смотреть, какими способами мы можем решить данную задачу:
1. Недетерминированное полиномиальное время («NP»)
В первую очередь давайте рассмотрим классическое математическое доказательство, известное как “недетерминированное полиномиальное время” (NP). Если проблема относится к классу NP, это означает, что существует алгоритм или система доказательств полиномиального времени, которые могут проверить, правильно ли эффективное решение. Другими словами, NP определяет набор проблем, для которых существуют эффективные решения, а системы доказательств предоставляют нам структуру для проверки валидности решений для таких проблем.
Но давайте посмотрим это на практике. Как мы создадим доказательство NP для проблемы раскраски графа?
В этом случае доказывающий просто предоставляет потенциальное распределение цветов для графа, а верификатор проверяет его валидность, проверяя все вершины и убеждаясь, что ни две смежные вершины не имеют одинакового цвета. Вот и всё!
2. Интерактивное доказательство (IP)
В 1985 году Голдвейссер и Микали представили революционную идею: «доказывающий» и «проверяющий» могут взаимодействовать для проверки валидности утверждения. Эта идея интерактивного доказательства (IP) оказалась настолько влиятельной, что спустя десятилетия они получили премию Тьюринга.
Работает IP довольно просто. Сначала доказывающий пытается убедить проверяющего в правильности утверждения. Верификатор бросает доказывающему серию «случайных» вопросов. Доказывающий отвечает. Это происходит много раундов, пока верификатор не убеждается, что утверждение доказывающего верно.
Самое важное, что IP позволяет нам использовать вероятностную верификацию. Например, на протяжении многих раундов доказывающий может убедить проверяющего с высокой вероятностью, что он честен. Таким образом, IP является вероятностным, в отличие от классического математического доказательства, которое детерминировано.
Используя взаимодействие и случайность, IP позволяет нам создавать системы доказательств, где у доказывающего есть конфиденциальность. Другими словами, доказывающий может доказать свое утверждение, не раскрывая ничего о самом утверждении (иными словами, это «нулевое разглашение»).
Но как же мы создадим доказательство IP для проблемы раскраски графа?
В этом случае проверяющий начнет со случайного выбора подмножества вершин и попросит доказывающего предоставить цвета, присвоенные этим вершинам. Затем верификатор проверяет правильность цветов, присвоенных выбранным вершинам, и проверяет, что никакие две смежные вершины не имеют одинакового цвета. Проверяющий продолжает выбирать случайный набор вершин и спрашивать у доказывающего их цвета на протяжении нескольких раундов, пока не получит высокую уверенность в том, что доказывающий знает решение.
3. Вероятностные проверяемые доказательства (PCP)
Вероятностное проверяемое доказательство (PCP) является еще одной эволюцией классической системы доказательств NP.
Ключевое отличие? Оно не интерактивно.
В PCP доказательство преобразуется в формат фиксированного размера, называемый “транскриптом доказательства”. Проверяющий может случайным образом запросить небольшое количество бит в транскрипте для проверки доказательства.
Случайный оракул предоставляет PCP возможность случайным образом запрашивать транскрипт доказательства! Таким образом, доказывающий не может предсказать запросы заранее. В случае с PCP, когда мы говорим, что у нас есть доступ к случайному оракулу, это означает, что у нас есть доступ к транскрипту доказательства и источнику случайности, так что проверяющий может получить доступ к случайным частям транскрипта доказательства.
В целом, PCP полезны с педагогической точки зрения, но они не эффективны на практике, потому что доказательства большие, а сложность запросов высока.
С этим разобрались. Ну а как мы создадим доказательство PCP для проблемы раскраски графа?
Доказывающий создает транскрипт доказательства, который кодирует распределение цветов. Верификатор запрашивает вершины графа, используя случайность, предоставленную оракулом, и получает доступ к цвету на этих вершинах через оракул. На основе результатов запросов верификатор может выбрать, принимать ли или не принимать. Обратите внимание, что в этом случае НЕТ взаимодействия. Доказывающий просто создает транскрипт доказательства один раз, и проверяющий использует случайные запросы через оракул для проверки доказательства.
4. Интерактивное оракульное доказательство (IOP)
Следующий исторический этап — это интерактивное оракульное доказательство (IOP), которое является расширением идеи интерактивного доказательства, за исключением того, что оно также включает случайные оракулы (как в PCP). Таким образом, в IOP доказывающий и верификатор взаимодействуют друг с другом и имеют доступ к случайным оракулам. IOP делает интерактивные доказательства более эффективными, используя оракулы для сокращения коммуникации и сложности запросов. Это модель, которую используют современные доказательства с нулевым знанием!
Ну а как мы создадим доказательство IOP для проблемы раскраски графа?
Аналогично PCP, доказывающий создает транскрипт доказательства, который кодирует распределение цветов, и верификатор случайным образом запрашивает вершины графа, используя оракул. Оракул предоставляет верификатору доступ к цвету на запрошенных вершинах. Но вместо того чтобы отправлять весь транскрипт доказательства сразу, как в PCP (что неэффективно), IOP разбивает его и отправляет маленькие части на протяжении нескольких взаимодействий, пока верификатор не убеждается, что доказывающий знает решение.
Что ж, давайте слегка подытожим:
IP = Система доказательств с взаимодействием + случайностью
PCP = Система доказательств со случайностью + доступом к оракулу
IOP = Система доказательств с взаимодействием + случайностью + доступом к оракулу
А теперь идем дальше :)
Система доказательств и криптография — это зкСнарки и зкСтарки
Мы можем разделить zkSNARKs и zkSTARKs на два компонента: информационно-теоретические системы доказательств и криптографические компиляторы.
Информационно-теоретическая система доказательств
Мы узнали о различных системах доказательств в предыдущем разделе. “Информационно-теоретический” относится к способности системы доказательств обеспечивать надежность и полноту даже против противников с неограниченной вычислительной мощностью. Таким образом, информационно-теоретическая система доказательств делает идеализированные предположения, которые трудно применить в реальной жизни. Например, она может предполагать, что проверяющий является доверенным и имеет ограниченный доступ к доказательству.
Поскольку информационно-теоретическая система доказательств не заботится о том, как это предположение управляется в реальном мире, она бесполезна как самостоятельный объект. Однако она может стать полезной, если будет сочетаться с криптографическим компилятором, как — вы увидите далее.
Криптографический компилятор
Криптографический компилятор удаляет идеализированные предположения, которые делает информационно-теоретическая система доказательств. Как? С помощью криптографических примитивов, таких как функция хеширования, устойчивая к столкновениям, случайный оракул или общая билинейная группа.
Выходным результатом является реальная система доказательств, которая является безопасной только при условии наличия доказывающего и/или проверяющего с ограниченной вычислительной мощностью (это предположение делают все криптографические протоколы).
Криптографический компилятор также может предоставить другие желательные свойства информационно-теоретической системе доказательств, такие как устранение взаимодействия, уменьшение сложности коммуникации или добавление функции нулевого знания.
Почему информационно-теоретическая система доказательств и криптографический компилятор разделены?
Если одно бесполезно без другого, то почему они разделены? Ответ — модульность. Сохраняя систему модульной, мы можем анализировать, оптимизировать и реализовывать каждую часть отдельно.
Например, в информационно-теоретической системе доказательств мы можем оптимизировать ее на основе принципов теории информации. Затем мы можем использовать различные криптографические компиляторы на конкретной информационно-теоретической системе доказательств для получения различных реальных систем доказательств, каждая с собственными компромиссами в эффективности, безопасности и предположениях о доверенной настройке.
Более того, информационно-теоретические протоколы служат более чистыми объектами изучения, чем окончательная реальная система доказательств после ее компиляции с использованием криптографического компилятора.
Что ж, вот мы и подошли к концу
Мы рассмотрели много аспектов, начиная с определения пяти элементов систем доказательств и заканчивая различиями систем доказательств на основе их свойств, таких как взаимодействие, случайность или доступ к оракулу.
Оставайтесь любознательными, продолжайте учиться и углубляйтесь в экосистему Aleo — путешествие только начинается. Присоединяйтесь к сообществу здесь:
