Zero Knowledge Proofs 101
Сергей Прилуцкий - Chief of R&D @ MixBytes
Zero Knowledge Proof — это криптографический протокол, который позволяет доказать истинность утверждения без необходимости раскрывать дополнительную информацию о нем.
Пещера нулевого знания
Представьте, что есть дверь, Алиса и Боб. У Боба либо есть ключ от этой двери, либо нет. Алиса бросает монетку и говорит Бобу идти налево или направо. Если у Боба есть ключ, то он может попробовать открыть дверь и пройти через неё. Понятно, что ему может повезти, но с каждой попыткой вероятность успеха уменьшается. Если мы будем повторять подобные протоколы много раз, Алиса сможет убедиться, что у Боба точно есть ключ.
Этот принцип также применим в компьютерных системах, где предоставлены различные вычислительные задачи, аналогичные передаче ключа. Однако, понимание того, как это работает на практике, всё равно остается не ясным.
Есть еще одна проблема - "верификация". Клиентская машина - браузер взаимодействует с сервером - Яндекс-навигатором, который отправляет задачу клиенту: найти маршрут, используя данные карты. Клиент выполняет вычисления и возвращает данные серверу. Однако серверу не хочется заниматься всеми вычислениями, потому что это требует много ресурсов и дорого. Поэтому сервер хочет переложить часть этой нагрузки на клиентов.
Возникает вопрос: как сервер может доверять результатам, которые вычисляют клиенты? Например, клиенту могут поручить выполнение сложных вычислений, таких как факторизация больших чисел. Клиент может работать над этой задачей часами и сообщить серверу результат - огромное число. Но как сервер может проверить правильность этого числа, не выполняя вычисления снова?
Для решения этой проблемы существует множество "интерактивных" протоколов. Когда клиент выполняет сложную задачу, он периодически отправляет серверу чекпоинты, и сервер может проверить результат. Однако такие схемы требуют постоянного взаимодействия между клиентом и сервером, и это может быть непрактично.
Zk-SNARK
Zk-SNARK — это теоретическая концепция у криптографии, которая позволяет делать доказательства, что вероятность того, что пользователь сможет обмануть систему, путем создания невалидного доказательства, стремиться к нулю.
Пока вычеслительные архитектуры тянут их очень-очень тяжело. Это крайне нагруженные вычисления. Работа zk-команд сейчас заключается в том, чтобы сделать эти протоколы более-менее удобоваримыми, чтобы они работали на компьютерах.
Argument of knowledge
Представьте, что у вас есть какая-то функция. Она принимает несколько аргументов (a, b, c). Внутри она делает какое-то вычисление, наприер, перемножает между собой. Эту функцию называют Pure, потому что она сама в себе и во внешний мир не ходит. Она делает какое-то вычисление и потом возвращает какое-то значение. Это называется input. На входе мы подаём input, а на выходе у нас output.
Argument of knowledge в SNARK означает, что я доказываю факт того, что я знаю такие input (a, b, c), что если их пропустить сквозь вот эту функцию, то у меня получится вот такой-то output.
Если возвращаться к терминологии, Prover - тот, кто доказывает, и Verifier - тот, кто проверяет. Prover берет input, считает функцию, получает результат, к нему прикреплет криптографическое доказательство и отправляет verifier. Verifier проведит setup для того, чтобы убедиться что пруфы работают. Смотрит верно ли доказательство для этой функции и для этого результата. То есть он может только сказать действительно ли этот пруф верный.
Первая ступень криптографии
Сначала была симметричная криптография. Например, блочный шифр AES. У нас есть Алиса и Боб. Они оба знают какой-нибудь секретный ключ и при помощи него зашифровывают информацию и отправляют её. Взяли сообщение, зашифровали, получили шифр, отправили, расшифровали, получили обратно сообщение. В этом случае, секретную информацию знают две стороны.
Вторая ступень криптографии
Затем повилась асимметричная криптография, когда у Алисы есть публичный ключ, у Боба есть публичный ключ, есть секретный ключ Алисы и секретный ключ Боба. Алиса зашифровывает данные своим секретным ключом, отправляет шифр, а Боб расшифровывает публичным ключом Алисы. В таком случае, Алиса должна держать в секрете свой секретный ключ и Боб должен держать в секрете свой секретный ключ. Это нужно для того, чтобы можно было секьюрно меняться информацией и каким-то образом её проверять.
Третья ступень криптографии
Zk — это следующая ступень, потому что теперь нет вообще никаких секретов. В этом случае, есть prover и verifier, у них у обоих есть prover-key для генерирования proof и verify-key для проверки proof. Всё это публично. Все знают какая функция доказывается и всем известно все, кроме input.
Non-Interactive
Это очень важное свойство, которое означает что доказывающий берет input, считает его, получает output вместе с proof и все это, одним пакетом, отправляет verifier, который берет output, proof и все это вычисление заворачивается в один proof. Поэтому это не интерактивно.
Это позволяет отправить публичный ключ и доказательство того, что у вас есть секретный ключ в одной транзакции. Например, если говорить об Ethereum, вы можете отправить человеку адрес вместе с доказательством того, что вы знаете приватный ключ от этого адреса. На первый взгляд может казаться, что это бесполезно, но с другой стороны, если вы не хотите в протоколах принимать какие-то рандоные адреса и сервер не хочет делать несколько обращений, то это может быть очень полезно.
Именно поэтому SNARK прижились в блокчейне. На серверной стороне, то есть на стороне самого блокчейна, ограниченнные ресурсы. Есть контракты, которые мало что умеют и там очень здорово разместить verifier, легкий и маленький проверяющий proof. А prover будут в одну транзакцию закидывать в контракт информацию уже с готовыми выходными данными. Контракт же проверит и если proof верный, то заберёт его.
Succiuct
Эти доказательства являются компактными и позволяют сделать проверку — верификацию алгоритмически легче, чем доказательства. Предположим, наша функция делает что-то за O от N шагов, то есть она делает что-то тысячу раз или миллион раз. Какая-либо система позволяет доказать, что программа выполнила тысячу раз, за O от единицы (O(1)). Таким образом, мы выполнили что-то тысячу раз, а проверить нас можно за константное время. То есть, компактность позволяет доказательства сжимать.
Это самое мощное свойство сейчас. Именно за счет него работают все ZK-L2 решения. Оно позволяет в процессе большого колличества транзакций завернуть все в одну проверку. На L1 весит верификатор, который за константное время проверяет исполнение в L2 большого колличества транзакций.
ZK
По дизайну этих протоколов, zk — это не главное. Например, вы написали какую-либо функцию, взяли 2 числа, самое простое — вернули (ab). Prover взял два числа, например, a=11 и b=3, расчитал на выходе 33. После, сгенерировал к этому доказательство, что он исполнил необходимую функцию и отправил это verifier. Verifier получил число 33 и доказательство. Можно сказать, что zk мы здесь получили на халяву из коробки, потому что эта функция может работать как Zero Knowledge, если a и b будут огромными. Тогда verifier видит их произведение, но ему надо его разложить до множителя, а эта задача для больших чисел довольно серьезная. То есть он не сможет это восстановить.
Ссылки для подробного изучения материала:
Для глубокого понимания темы, рекомендуем просмотреть видео с Сергеем и получить практические знания.
