01 Августа 2019
Reading time: 7 min
Продолжим нашу серию публикаций о блокчейне и криптовалютах рассказом об одном интересном протоколе, который позволяет одной стороне («доказывающему» или «prover») подтвердить истинность утверждения для другой стороны («верификатора» или «verifier»), не раскрывая при этом содержания этого утверждения.
Самый простой пример, не относящийся к блокчейну: вы хотите доказать кому-то, что решили судоку, не показывая при этом самого решения или даже его части. Как это сделать? Как раз при помощи механизмов, заложенных в протоколе Zero Knowledge Proof. Подробности читайте далее.
Определение
Zero Knowledge Proof (или Zero Knowledge Protocol, ZKP, доказательство с нулевым разглашением) — это криптографический протокол, который позволяет одной стороне (доказывающему) подтвердить истинность утверждения другой стороне (верификатору), не раскрывая никакой дополнительной информации о нем (ни содержания, ни источника и пр.).
В блокчейне это, к примеру, способ аутентификации без обмена паролями, что существенно уменьшает вероятность их кражи. Использование ZKP является гарантией, что в процесс коммуникации не смогут вмешаться третьи лица и каким-либо образом воздействовать на ее безопасность. Несмотря на то, что суть передаваемой информации не раскрывается, проверяющий (верификатор) все равно может убедиться в том, что доказывающий — именно тот человек, за которого себя выдает.
Осторожно, много доказательств!
Говоря еще более простым языком, доказательство с нулевым разглашением позволяет доказать, что доказываемое утверждение верно и доказывающий знает, как именно оно выглядит, но при этом верификатор не получает никакой информации о доказательстве данного утверждения.
Как это работает?
Одним из лучших примеров работы ZKP является так называемая «Пещера нулевого разглашения». Впервые этот пример был описан в известной работе по теме под названием «Как объяснить протокол доказательства с нулевым разглашением вашим детям» авторства Жана-Жака Кискатера.
Перед нами круглая пещера, вот такая:
Перед ней стоят два героя этой истории — Пегги (от англ. Prover) и Виктор (от англ. Verifier). Пегги знает пароль, с помощью которого можно открыть дверь между C и D (в любую сторону). Виктор хочет знать, правда ли девочке известен пароль. Пегги готова это доказать, но не хочет выдавать сам пароль. Чтобы решить проблему, они поступают следующим образом: пока Виктор стоит в точке А, Пегги идет к двери, и после того, как она исчезает из виду (то есть, неизвестно, с какой стороны она зашла в круглую пещеру), Виктор идет в точку В, и кричит оттуда: «Пегги, нужно выйти справа!» или «Пегги, нужно выйти слева!». Если девочка действительно знает пароль, она ни разу не ошибется с выходом, сколько бы раз ее не проверял товарищ. В первый раз вероятность того, что она знает кодовое слово составляет 50%, если же повторить проверку n раз, вероятность будет расти и расти.
Достоверность
Как вы поняли, есть нюанс: в случае с zero knowledge proof верификатор никогда не будет уверен в истинности факта на 100%. Всегда остается вероятность, что свою роль сыграла удача или обман. Эта проблема как раз решается повторением эксперимента как можно большим количеством раз. Шанс, что доказывающий угадывает уменьшается все сильнее: после пяти повторений вероятность обмана составит 1 к 32, после 10 раундов — 1 к 1024, а после 20 раундов — примерно 1 к 1 000 000.
Историческая справка
Концепция доказательства с нулевым разглашением была придумана и разработана учеными Шафи Гольдвассер, Сильвио Микали и Чарльзом Реккофом. Информацию они обнародовали в статье «Знание и сложность интерактивной системы с доказательством» в 1989 году. Как видите, это вовсе не новейшее изобретение, хотя оно и стало популярным в последнее время из-за развития блокчейна.
В статье ученые представили иерархию интерактивных систем с доказательством, основываясь на объёме информации о доказательстве, который необходимо передать от доказывающего до верификатора. Они же предоставили первый пример zero knowledge proof.
Работа над концепцией доказательства с нулевым разглашением в 1993 году принесла им первую премию Гёделя, а в 2012 году Гольдвассер и Микали стали лауреатами премии Тьюринга за создание криптосистемы с вероятностным шифрованием, отмеченная в номинации как новаторская работа, оказавшая существенное влияние на современную криптографию.
Shafira (Shafi) Goldwasser,2012 Turing Award winner.Фото:https://uwaterloo.ca
Свойства ZKP
Протокол zero knowledge proof должен обладать следующими свойствами:
1. Полнота. Если утверждение действительно верно, то доказывающий убедит в этом верификатора с любой предварительно заданной точностью.
2. Корректность. Даже с помощью обмана доказывающий не сможет убедить верификатора, если утверждение не верно, за исключением пренебрежимо малой вероятности (это будет называться «ошибка корректности»). Как мы уже говорили, благодаря повторным проверкам можно добиться желаемого уровня надежности доказательства, однако 100%-ная уверенность недостижима. Именно поэтому доказательство с нулевым разглашением является не математическим доказательством, а детерминированным.
3. Нулевое разглашение. Если утверждение верно, то даже с помощью обмана верификатор не сможет узнать ничего, кроме того факта, что оно верно.
Виды доказательств с нулевым разглашением
Процесс доказательства бывает интерактивный и неинтерактивный. В первом случае верификатор сам опрашивает доказывающего в реальном времени, а вот второй не требует непосредственной коммуникации между верификатором и доказывающим, подлинность утверждения в данном случае можно проверить и постфактум.
Также ZKP можно поделить на две группы, исходя из наличия или отсутствия фазы фиксации подлинности утверждения несколькими верификаторами (это называется доверенная установка с применением булевой функции).
Что касается доверенной установки, то для некоторых протоколов, таких как zk-SNARKs (Zero-Knowledge Succinct Non-Interactive ARgument of Knowledge), о котором мы еще поговорим, это является обязательным условием. В данном случае верификаторы генерируют специальный секрет, который уничтожается сразу после доверенной установки. Если он продолжит свое существование, то данные в Сети можно будет подделать, что делает бессмысленным использование протокола.
Плюсы и минусы ZKP
Плюсы:
- Повышение приватности в публичных блокчейнах и других сетях, повышение их пропускной способности и улучшение масштабируемости;
- Укрепление информационной безопасности (за счет замены неэффективных способов аутентификации и верификации).
Минусы:
- Необходимость в значительных вычислительных мощностях;
- Возможная уязвимость перед квантовыми вычислениями.
Для чего используют доказательство с нулевым разглашением?
В блокчейне zero knowledge proof широко используется, к примеру, для того, чтобы проверить, есть ли у владельца какой-либо криптовалюты достаточные средства для транзакции.
При этом, другие участники сети не узнают, кто этот пользователь и сколько денег у него на счету.
Как мы уже говорили, доказательство с нулевым разглашением можно использовать и для обеспечения безопасности персональных (и других) данных или проведения финансовых операций. Данный протокол может являться инструментом, который обеспечивает верификацию данных, предоставление особого уровня доступа и установление доверенных соединений.
Что такое zk-SNARKs?
Когда мы говорим о ZKP в блокчейне, чаще всего речь идет именно об одной специфической разновидности — протоколах zk-SNARK.
Для начала давайте подробнее разберем его название. «ZK», как вы наверное догадываетесь, означает «zero knowledge». Дальнейшая расшифровка выглядит так:
S — succinct — сжатое;
N — non-interactive — неинтерактивное;
AR — argument +
K — of knowledge — доказательство знания.
Сжатое доказательство — значит достаточно компактное, чтобы его можно было рассчитать за короткий промежуток времени. Неинтерактивное — то есть, протокол не требует от верификатора непосредственного опроса доказывающего.
Есть и минусы, о которых мы уже упоминали — SNARKи требуют больших вычислительных мощностей. К примеру, ресурсов мобильного устройства им зачастую не хватает. Впрочем, эта проблема сейчас находится в стадии решения. Другая проблема — потеря доступа к хэш-функции, на основании которой проверяется подлинность. Протокол позволяет пользователю доказать, что у него есть доступ к определенному секрету, но доказывающий, в свою очередь, должен обеспечивать его сохранность и доступность.
Самый же серьезный недостаток zk-SNARKs — это фаза установки, необходимый этап внедрения протокола в любую задачу. На нем фиксируется подлинность вычисления (circuit), результат которого вы хотите доказать. Кроме того, на этом этапе создается секрет, существование которого допускает публикацию ложных доказательств (fake proofs).
Если вы хотите использовать какой-то circuit публично, то есть более чем с одним верификатором, необходимо иметь «trusted setup». В данном случае секрет будет генерироваться не одним лицом (которое, кстати, обязано его сразу уничтожить), а группой пользователей. Если все участники группы придерживаются правил (то есть удаляют секретные данные), безопасность обмена гарантирована.
Из-за этого ограничения SNARK-протоколы плохо подходят для произвольных Тьюринг-полных смарт-контрактов — каждый новый договор потребует новой установки.
ZKP и криптовалюты
Самой популярной криптовалютой, которая основана на zk-SNARKs, является Zcash. Главная цель ее создателей — сделать все операции полностью анонимными. С одной стороны, владельцы Zcash могут совершать такие же публичные транзакции, как и держатели биткоина, с другой — им доступна опция сокрытия адресов получателя, отправителя и суммы перевода (так называемая shielded transaction).
Нередко Zcash сравнивают с другой криптовалютой, Monero, но эти системы по-разному подходят к вопросам приватности. Фишка Monero — механизм кольцевых подписей (ring signatures), благодаря которым участники транзакции как бы «теряются» среди других владельцев валюты. Рекорд участников такого «миксера» составил 4500 адресов.
Самый известный блокчейн-проект из тех, что предлагают написание смарт-контрактов, Etherium, ранее не уделял особого внимания такому параметру как приватность. Мельчайшие подробности любого смарт-контракта доступны каждому участнику сети.
Etherium -контракты, пользователям которых необходима приватность, могут обеспечить последнюю лишь за счёт off-chain-средств, то есть операций, проведённых за пределами блокчейна. Это привносит в систему риск и человеческий фактор и серьезно осложняет разработку смарт-контрактов.
Metropolis — следующее обновление протокола Etherium. Оно даст возможность программистам, пишущим смарт-контракты, внедрять zk-SNARKи прямо в блокчейне и верифицировать информацию с их помощью. Это позволит сделать некоторые переменные в контрактах приватными. Секретную информацию можно будет хранить не в блокчейне, а у пользователей, которые будут подтверждать, что действуют в рамках правил с помощью zk-SNARKs.
Однако zk-SNARKи не позволяют достигнуть отделённой от пользователя, автономной приватности в Эфириуме. Пока что они полагаются на off-chain-участника для хранения секрета. Без последнего отслеживать секрет будет некому, а все доказательства будут бесполезны.
Читайте также
