Мы уже говорили о ZK и rollups в одном из уроков по Solidity, который можно посмотреть вот тут:
Но как вообще объяснить идею ZK для тех, кто только входит в эту область? Есть два хороших примера, которые мы сегодня рассмотрим. В первую очередь важно понять основную суть ZK.
Мы (prover) доказываем некому проверяющему наблюдателю (verifier), истинность некоторого утверждения. Часто за этим стоит секретная информация (witness), но само утверждение не обязано сводиться только к “я знаю секрет”. При этом саму информацию мы не разглашаем.
В классических интерактивных примерах такое доказательство убедительно именно для проверяющего, участвовавшего в протоколе. В современных неинтерактивных ZK-доказательствах ситуация другая: proof можно передавать и проверять отдельно. Казалось бы, разве это возможно?
Эта запись также доступна в канале Telegram “DEV: Рубиновые тона”, а обсудить же эту тему можно в нашем чате Telegram.
Три основных свойства Zero knowledge
Прежде, чем перейти к примерам, давайте для полноты картины выпишем три основные свойства ZKP:
- Completeness (полнота): честный prover убедит честного verifier’а, если утверждение истинно.
- Soundness (корректность против обмана): мошенник не сможет убедить verifier’а в ложном утверждении; во всяком случае, вероятность этого чрезвычайна мала.
- Zero-knowledge (нулевое разглашение): verifier не узнаёт ничего сверх истинности утверждения.
Пещера Али Бабы
Первый пример связан с так называемой пещерой Али Бабы (только самого героя там нет — видимо, ушёл по делам). Эта пещера круговая, в неё есть всего один незапертый вход, однако в диаметрально противоположной от входа точке (то есть с другой стороны, которую от входа невозможно увидеть) находится волшебная дверь, перегораживающая путь. Вот тут можно посмотреть простую схему.
Очевидно, что если пещера круговая, то войдя в неё можно пойти либо по часовой стрелке (путь А), либо против часовой (путь Б). Однако если вы не знаете стоп-слова секретного слова, которое открывает волшебную дверь, то не сможете совершить полный круг. Короче, пойдя по пути А вы не сможете в итоге выйти со стороны пути Б и наоборот. Теперь вопрос: как Элис может доказать Бобу, что она знает секретное слово для открытия двери, при этом не разглашая само слово?
Можно сделать следующее. Боб остаётся недалеко от входа в пещеру, но отворачивается и действий Элис пока не видит. Элис же заходит в пещеру и произвольно выбирает либо путь А, либо путь Б. Когда она доходит до волшебной двери, Боб идёт к выходу и останавливается. Он не знает, как пошла Элис и не видит с какой стороны от двери она стоит. Далее он просто даёт команду либо “выходи со стороны А”, либо “выходи со стороны Б”.
Ясное дело, что если Элис зашла со стороны А и её просят оттуда же выйти, то открывать ей дверь не нужно вовсе: она просто вернётся обратно той же дорогой. Но вот чтобы выйти со стороны Б, ей по-любому придётся открыть дверь. Ну, а если она не знает секретного слова, то эксперимент окажется провален. Если же мы проделаем этот эксперимент раз 30, и если Элис слова не знает, то вероятность провала будет чрезвычайно большой (увеличивается с каждым новым повторением), ведь она каждый раз идёт по случайному пути, а Боб каждый раз называет случайный выход. Если же после 20-30 раза провала не последовало, то почти наверняка слово Элис известно (вероятность, что ей просто повезло, будет уже в духе “1 к миллиарду”), хотя она всё так же его не раскрыла.
Почему бы наблюдающему просто не подойти ко входу?
Может возникнуть довольно логичный вопрос: а зачем вообще Боб сначала отворачивается, не зная, куда пошла Элис, а потом даёт ей команду? Он же может просто наблюдать за экспериментом с самого начала: увидеть, что Элис пошла по пути А, а затем убедиться, что она вышла со стороны Б. Это ведь тоже докажет, что она знает секретное слово! В общем, да, докажет, но с важной оговоркой.
В нашем интерактивном примере смысл zero knowledge не только в том, что Боб убеждается в знании Элис, но и в том, что при этом он не узнаёт само секретное слово. Повторения нужны, чтобы снизить шанс обмана: если Элис слова не знает, ей придётся угадывать, с какой стороны Боб попросит её выйти. А свойство zero-knowledge состоит в том, что даже после множества таких проверок Боб узнаёт только один факт: Элис, похоже, действительно может открыть дверь.
Есть и другой нюанс. Если Боб с самого начала видит, куда пошла Элис, а потом снимает на камеру, как она выходит с другой стороны, такая запись уже может выглядеть как самостоятельное доказательство для кого-то ещё. То есть Элис теряет контроль над тем, кого именно она убеждает.
В классической интерактивной версии Боб видит только результат отдельного раунда: он сам дал случайную команду и увидел, что Элис смогла её выполнить. Но для третьей стороны запись такого процесса сама по себе не очень ценна. Всегда можно спросить: а вдруг Боб и Элис заранее договорились, какие команды будут звучать? Или как-то сфабриковали такую запись?
Грубо говоря, в этом примере доказательство убедительно именно для Боба, который лично участвовал в проверке и сам выбирал случайные команды. А запись эксперимента не становится таким же сильным доказательством для посторонних, потому что похожую запись можно было бы подготовить заранее.
Здесь речь именно об интерактивном примере. В современных неинтерактивных ZK-доказательствах всё устроено иначе: proof как раз можно передавать третьим лицам, и они смогут проверить его самостоятельно.
Цветные шарики
Рассмотрим и другой пример, на этот раз с двумя шариками: красным и синим. Предположим, что Боб не умеет различать красный и синий цвета, а Элис умеет. Таким образом, для Боба эти шарики кажутся абсолютно одинаковыми, а для Элис - нет. Она хочет доказать Бобу, что умеет различать цвета и что эти два шарика разные, но при этом не сообщая, какой из них синий, а какой — красный.
Чтобы это проверить, Боб берёт в каждую руку по шарику и прячет их за спиной. Он имеет право поменять шарики местами (то есть переложить из левой руки в правую и наоборот), но Элис стоит прямо перед Бобом и этих манипуляций не видит. Затем Боб показывает шарик в правой руке, а Элис подмечает про себя его цвет. Боб снова прячет шарик за спину, после чего может вновь поменять их местами по желанию, либо не менять вовсе. Он вновь показывает шарик в правой руке и спрашивает Элис: “Я показываю тот же шарик или другой?”. Боб не знает цвета шарика, но он ведь знает, менял ли он их за спиной. Следовательно, он понимает тот же это шарик или нет.
Элис же не сможет с уверенностью сказать тот же ли это шарик или другой, если не умеет различать цвета или если оба шарика просто-напросто неотличимы для неё (например, оба серые). В этом случае она будет вынуждена отвечать наобум. Как только она ошибётся, эксперимент будет провален. Таким образом, если мы проведём этот эксперимент 20-30 раз, и Боб будет каждый раз показывать случайный шарик, то, давая случайные ответы, Элис почти наверняка ошибётся. Если же все 30 раз ей удалось правильно идентифицировать шарик (тот же или другой), она с очень высокой вероятностью может отличить один от другого, но опять же она не сообщает, где какой.