Привет всем.
Я некоторое время работал в блокчейн‑проекте, который являлся форком проекта Zcash. Проект Zcash — это первопроходец технологии zero knowledge («нулевого знания») в блокчейнах. В блокчейне Zcash поддерживаются приватные транзакции, в которых пользовательские данные (об отправителях, получателях, пересылаемых суммах) скрыты, а технология «нулевого знания» используется для валидации таких транзакций без раскрытия пользовательских данных.
Я пользовался этой технологией как «черным ящиком», но всегда хотел понимать, как она устроена изнутри. Когда я пытался изучать документацию по технологии zk‑SNARK, используемой в Zcash, это потребовало довольно много времени и углубления в математику. Возникла идея написать об этой технологии простым языком и постараться дать ответы на вопросы, которые могут появляться у читателя об этой технологии.
Цель этой статьи — популяризация технологии нулевого знания на примере приватных транзакций в блокчейне Zcash. Я попытаюсь представить эту технологию не как «черный ящик», а хотя бы как «серый ящик». Я не математик, а разработчик и хотя полностью без отсылок к математике рассказать не получится, я постараюсь сделать это на любительском уровне (это будет не доказательная, а иллюстративная математика).
Я считаю технологию «нулевого знания» актуальной сегодня, когда персональные данные регулярно утекают огромными массивами из различных систем. Технология нулевого знания позволила бы получать различные сведения о данных, не раскрывая их самих сторонним сервисам или пользователям. Сегодня известно не очень много примеров, где она используется (блокчейн — это один из немногих примеров).
Полное название технологии, о которой пойдет речь — zk‑SNARK, то есть Zero Knowledge Succint Non‑Interactive Argument of Knowledge. (Мой перевод: «технология нулевого знания с кратким не‑интерактивным аргументом знания», ниже я прокомментирую эти понятия).
Обычно про технологию нулевого знания говорят, что она позволяет установить истинность некоторого заключения, не раскрывая наблюдателю ничего, кроме того, что это заключение истинно. Пример: если у меня есть секретный и публичный ключ электронной подписи, то я могу убедить наблюдателя, что знаю свой секретный ключ, не раскрывая его: я посылаю наблюдателю сообщение, подписанное секретным ключом и открытый ключ: наблюдатель, проверив мою подпись, сможет убедиться, что я владею секретным ключом (это и есть «заключение»), и я не раскрыл его («нулевое знание» для наблюдателя).
Но «нулевое знание», когда есть секретный и открытый ключи — это частный случай. Вот другой пример: если я отправил наблюдателю хеш некоторого сообщения (допустим, что это хеш SHA2 или SHA256), то убедить наблюдателя, что я знаю исходное сообщение, можно, если только раскрыть его и посчитать значение хэша. А мы хотим уметь делать такое, не раскрывая самих исходных данных.
Что такое «приватные транзакции»?
В обычном блокчейне, например Bitcoin, все свойства транзакций открыты: кто угодно может видеть, какое количество монет или токенов некоторый адрес отправил другому адресу. Когда создается новая транзакция Bitcoin, все узлы блокчейна проверяют данную транзакцию на соответствие правилам, прописанным в программном коде Bitcoin, в частности проверяется баланс транзакции: сумма на входах транзакции должна быть больше, чем сумма на выходах.
Но в сети Zcash мы не увидим в самом блокчейне ни сумм, ни адресов приватных транзакций — вместо этого мы видим некие коммитменты («commitment» можно перевести как «поручительство»: тот, кто создал приватную транзакцию, «ручается», что адрес и сумма соответствуют исходным данным. Но далее я буду все‑таки использовать термин «коммитмент»). Коммитмент — это тоже хэш, вычисленный для адреса и суммы в транзакции. Технология zero knowledge позволяет доказать, что пользователь знает свой адрес и сумму в приватной транзакции, но не раскрывать эти данные наблюдателям (валидаторам транзакций).
На рисунке показана упрощенная структура приватных транзакций:
У приватной транзакции есть выходы (в Zcash они называются notes — «ноты»), где указаны адрес и сумму монет, которые может потратить этот адрес. В блокчейне Zcash хранятся не сами ноты, а их коммитменты (обозначены как «cm» на рисунке).
Чтобы потратить монеты на своих нотах, пользователь создает приватную транзакцию, в которой есть исходящие ноты, на которые будут переведены монеты с нот предыдущей транзакции. Новая приватная транзакция должна быть проверена всеми валидаторами сети, прежде чем она будет добавлена в блокчейн. Приватная транзакция содержит доказательство «нулевого знания» («zk‑proof»), которая позволяет валидаторам проверить, что пользователь знает адрес и сумму для своей ноты (то есть, соответствуют коммитменту cm), при этом валидаторы не видят сами значения.
Я постараюсь рассказать, как устроена система доказательств нулевого знания (или «zk‑доказательств») groth16, используемая в ранних версиях Zcash.
Система groth16 довольно изящна и состоит из нескольких этапов:
Первый шаг: разработка системы R1CS
«Коммитмент» — это хэш некоторых исходных данных и вычисляется некоторой компьютерной программой. Наша первая задача — это представить такую программу как схему элементарных операций сложения и умножения (их называют gates, и это похоже на принципиальную схему вычислителей в электронике).
Вообще для проверки zk‑доказательств нам требуется не просто вычисление коммитмента, а проверка того, что исходные данные соответствуют коммитменту. Для этого схема вычислителя конвертируется в массив элементарных проверок (или ограничений) Ai * Bi=Ci (это называется Rank1 Constraint System — R1CS).
Если на вход системе R1CS подать данные, которые мы хотим проверить (адрес и сумму) и публичные данные (коммитмент), то R1CS даст ответ, были ли эти данные исходными для коммитмента.
Заметим, что пока нам приходится раскрывать наши данные, когда мы делаем проверку с помощью R1CS, а наша конечная цель — выполнить проверку, но не раскрывать их исходные данные.
Аппроксимирование R1CS в виде полиномов
Для такой задачи, как проверка коммитментов, у нас получится очень большая система R1CS. Поэтому ее конвертируют в систему полиномов, то есть выражений вида P(x)=a0x0 + a1x1 + a2x2 + … + anxn. Принцип такой конвертации вполне однозначный (интерполяция Лагранжа):
Аргумент x — это целое число и принимает значения порядковых номеров i ограничений Ai * Bi = Ci.
Для каждого ограничения с номером i создаем полином такой, что для x = i выражение Ai Bi = Ci выполняется, а для всех остальных x!= i значение y должно быть 0. Делается это путем добавления множителей, которые обнуляют полином в других точках: (x-0)(x-1)(x-2)…(x‑n).
Все полиномы суммируются, и мы получаем результирующий полином P(x) = A(x) * B(x) — C(x), который включает наши ограничения R1CS, проиндексированные как i = 0...n.
Если P(x) будет равен нулю во всех x = 0...n, то означает, что все ограничения R1CS выполняются успешно. Математическое правило для полиномов позволяет убедиться в этом, если P(x) делится без остатка на универсальный полином‑делитель T(x) = (x-0)(x-1)(x-2)...(x‑n).
Итого: полином P(x) аппроксимирует ограничения R1CS, наши исходные данные соответствуют коммитментам, если деление P(x) / T(x) = H(x) выполняется без остатка.
Добавим, что такое представление ограничений в виде полинома называется Quadratic Arithmetic Program (QAP).
Сокрытие секретных данных
Выше мы получили способ проверки того, что пользователь знает исходные данные для коммитментов, путем операций с полиномами. Есть две проблемы с этим: эти исходные данные «зашиты» в коэффициентах полинома P(x), а значит, все еще являются открытыми. Другая проблема — это то, что такие полиномы могут быть очень большими (например, полином для задачи вычисления коммитментов содержит около 2 млн параметров).
Поэтому в groth16 в системе проверки zk‑доказательств используется не сам полином, а его значение P(s) для случайного аргумента s. Данный аргумент s генерируется при доверенной инсталляции системы. Для данного s получают несколько константных значений путем применения операции сокрытия homomorphic hiding.
Для операции сокрытия используется такая же методика, как в технологии электронной подписи на эллиптических кривых из секретного ключа получают публичный ключ. Есть эллиптическая кривая (точнее, алгебраическая группа), точки на которой получены из точки‑генератора G путем операции Gx. Публичный ключ — это тоже точка на кривой, полученная из секретного ключа (числа d) путем выполнения операции E(d) = Gd (также можно записать как G^d).
При инсталляции groth16 мы вычисляем точки на эллиптической кривой для степенных компонентов полинома для аргумента s, это и есть операция сокрытия данных: E(s0), E(s1), E(s2),…,E(sn). Эти значения мы будем использовать для получения zk‑доказательств.
Вообще системы электронных подписей (и сокрытия данных) существуют только потому, что невозможно за приемлемое время выполнить обратную операцию — получение секретного ключа d из открытого ключа.
В системе groth16 для операции сокрытия используется эллиптическая кривая BLS12-381, которая имеет полезное свойство гомоморфизма: она позволяет для некоторого полинома P(x) вычислить E(P(s)), не зная исходного s, а используя E(s).
После инсталляции важно уничтожить исходный аргумент s (если происходит его утечка, то вся система становится уязвимой: нарушитель мог бы генерировать ложные zk‑доказательства, если бы узнал s).
Далее мы формируем zk‑доказательство как сокрытое значение нашего полинома E(P(s)) путем применения коэффициентов a1, a2,…,an из полинома P(x) = a0s0 + a1s1 + a2s2 + … + ansn (эти коэффициенты как раз и будут секретными данными):
E(P(s)) = E(a0s0 + a1s1 + a2s2 + … + ansn) =
G^(a0s0 + a1s1 + a2s2 + … + ansn) =
G^a0s0 * G^a1s1 * G^a2s2 * … * G^ansn =
E(s0)^a0 * E(s1)^a1 * E(s2)^a2 * … * E(sn)^an
(Напомним, что E(s0),E(s1),E(s2),…E(sn) — это точки на кривой, которые мы сформировали во время инсталляции.) Проверяющая сторона увидит только сокрытое значение полинома для аргумента s (будут скрыты и коэффициенты полинома, то есть исходные секретные данные).
Также для аргумента s мы вычисляем сокрытое значение для полинома‑частного E(H(s)). Для этого мы получаем полином H(x) = P(x) / T(x), где полином T(x) является известным и универсальным для всей системы и равен (x-0)(x-1)(x-2)...(x‑n). Получив полином H(x), мы можем выразить E(H(s)) через имеющиеся сокрытые значения для степенных компонентов E(s), E(s), E(s2),...,E(sn), точно также как мы делали для E(P(s)). Значение E(T(s)) также является известным еще на этапе инсталляции.
Наше zk‑доказательство — это сокрытые значения E(P(s)) и E(H(s)). Имея только их и E(T(s)), проверяющая сторона должна убедиться, что P(s) = H(s) * T(s). Это называют «слепое вычисление» полинома (blind evaluation). Это делает возможным функция «билинейного спаривания» (bilinear pairing) e, поддерживаемая для этой эллиптической кривой. Эта функция позволяет проверить соотношения между аргументами, не видя самих значений: произведение xy равно ab, если выполняется соотношение для спаривания e(E(x), E(y)) = e(E(a), E(b)).
Существует математическое обоснование, что вероятность того, что кто‑либо сможет создать полином P«(s) с другими коэффициентами и который будет успешно проверен, ничтожно мала.»
В итоге мы получили методику (argument of knowledge), как сформировать компактное (succinct) zk‑доказательство и как его проверить. При этом исходные данные не видны проверяющему, так как скрыты путем применения операции homomorphic hiding.
Кстати, почему данная методика считается non‑interactive (неинтерактивной)? Исходно системы нулевого знания были интерактивными, то есть, когда между проверяющей и доказывающей сторонами существовал протокол, позволяющий проверить истинность утверждения на отдельных кейсах. Чем больше таких кейсов, тем выше вероятность того, что утверждение верно. В случае zk‑SNARK такого интерактивного обмена нет: используется всего один случайный аргумент s, подготовленный заранее.
Знаешь ли ты свой полином?
И последний шаг: поскольку в качестве доказательства мы используем не сам полином, а лишь его значение для некоторого аргумента s, да еще и скрытое E(P(s)), проверяющая сторона должна убедиться, что мы знаем исходный полином (а не просто подобрали подходящие точки на кривой). Для проверки этого факта используется математическое утверждение «знание экспоненты» («Knowledge of Exponent Assumption», KEA), которое говорит, что, если мы хотим получить на нашей эллиптической кривой пару точек Y и C, таких что Y = Ca, то мы должны знать значение c, такое что C = Gc (где, напомню, G — точка‑генератор на кривой).
Чтобы применить это утверждение, при доверенной инсталляции groth16 кроме числа s генерируется еще одно случайное число α (альфа), и вычисляются еще один набор степенных компонентов полинома, «сдвинутых» на эту «альфа»: E(αs1), E(αs2),…,E(αsn).
Т.е. если исходно мы получили полином вида y = 2 x3 + 5 x2 + 7 x + 9 и опубликовали его скрытое значение для s как:
E(P(s)) = E(2s3 + 5 s2 + 7 s + 9) = E(s3)2 * E(s2)5 * E(s1)7 * E(s0)9,
то проверяющая сторона может потребовать предоставить «сдвинутое» на α значение:
E(P(αs)) = E(2αs3 + 5 αs2 + 7 αs + 9) = E(αs3)2 * E(αs2)5 * E(αs1)7 * E(αs0)9
То есть, для вычисления E(P(αs)), согласно утверждению KEA, мы должны знать коэффициенты 2, 5, 7 и 9.
Что еще?
Выше мы рассказали о том, как работает технология «нулевого знания», позволяющая убедить проверяющую сторону, что создатель приватной транзакции знает свой адрес и сумму на выходе другой приватной транзакции (с помощью которой ему переслали монеты). Мне следует сделать несколько уточнений для полноты картины приватных транзакций в Zcash.
Нулификаторы. Конечно, одного лишь доказательства, что пользователь знает свой адрес и сумму, недостаточно для того, чтобы разрешить тратить монеты. Необходимо, как в случае с биткоином, еще доказать, что пользователь знает секретный ключ для данного адреса (который вычисляется из секретного ключа).
Поэтому в приватной транзакции еще передаются «нулификаторы» для входящих нот (то есть тех, которые мы тратим и передаем их монеты на выходные ноты). Каждый нулификатор является уникальным для своей ноты и для его создания необходимо знать секретный ключ. При добавлении приватной транзакции в блокчейн нулификаторы публикуются в блокчейне, и входящие ноты становятся потраченными. Публикация нулификаторов не позволяет повторно тратить одну и ту же ноту.
Проверка баланса приватной транзакции. Еще один важный момент: валидаторы не должны допускать в блокчейн транзакции, для которых не соблюдается баланс сумм монет на входе и на выходе (иначе любой мог бы просто добавлять любое количество монет на свои ноты). Но валидаторы не могут видеть реальные суммы монет в приватных транзакциях. Поэтому приватные транзакции содержат еще коммитменты cv для сумм нот. Для этого типа коммитмента (Homomorphic Pedersen Commitment) действует свойство гомоморфизма: cv(sum1) + cv(sum2) = cv(sum1 + sum2). Используя его, валидаторы проверяют равенство сумм на входах и выходах приватных транзакций.
Тогда более полное zk‑доказательство будет звучать так:
«Для публичных коммитметнтов cm и cv и нулификатора nf я знаю адрес и сумму, такие что:
— адрес и сумма соответствуют коммитменту cm,
— эта же сумма соответствует коммитменту cv,
— нулификатор nf однозначно соответствует (идентифицирует) cm,
— нулификатор и адрес порождены из одного и того же секретного ключа.»
При этом сами значения адреса, суммы и секретного ключа остаются секретными.
И есть еще момент, что хорошо бы проинформировать получателя о реальных сумме и адресе в нотах приватной транзакции. Для этого секретные данные ноты (адрес, сумма) присоединяются к транзакции зашифрованными на ключе получателя.
TL;DR
Мы рассмотрели, как устроена система нулевого знания zk‑SNARK в блокчейне: как с помощью zk‑доказательства можно убедиться, что некто знает секретные данные, которые можно проверить с помощью открытых данных, не раскрывая самих секретных данных. Принцип заключается в том, что данные отображаются в другое множество (на эллиптической кривой), где сохраняются математические отношения, существующие между исходными данными.
Кто‑то может спросить, а зачем все это нужно мне, если я не имею никакого отношения к блокчейнам или криптовалюте? Дело в том, что в качестве полинома QAP можно представить самые разные программы.
Пример использования нулевого знания на практике: проверка возраста человека без раскрытия его паспортных данных. Такая программа, использующая zk‑SNARK, уже разработана в Европе https://ageverification.dev/: государственный сервис, проверив документ пользователя, выдает zk‑доказательство, подтверждающее возраст пользователя, которое могут проверять соцсети.
Можно экстраполировать этот подход на гостиницы: я очень не люблю давать сканировать свой паспорт в гостинице, так как совсем не уверен что они надежно хранят персональные данные. Вместо паспорта я бы мог предъявить QR‑код с zk‑доказательством, назвать свое ФИО и показать лицо в видеокамеру. Система zk‑SNARK гостиницы могла бы сверить мою биометрию и ФИО с данными в zk‑доказательстве и убедиться, что паспорт валидный и действительно принадлежит мне. Микрофинансовые организации также могли бы пользоваться данной технологией при выдаче краткосрочных кредитов, без риска утери персональных данных для клиента.
Я думаю, что можно подобный алгоритм можно применять для регистрации пользователей в различных системах, требующих идентификации пользователя по национальному документу, без онлайн‑обращений в государственную систему.
В общем, при сегодняшней тотальной цифровизации технология нулевого знания могла бы помочь повысить приватность и конфиденциальность данных, хранящихся в различных системах и базах данных.
Ссылки:
Описание homomorphic hidings:
https://blog.ethereum.org/2016/12/05/zksnarks‑in‑a‑nutshell
Описание groth16:
https://rareskills.io/post/groth16
Спецификация Zcash:
https://zips.z.cash/protocol/protocol.pdf
Серия статей Виталика Бутерина про zk‑SNARK с подробным изложением математики:
https://vitalik.eth.limo/general/2016/12/10/qap.html
https://vitalik.eth.limo/general/2017/01/14/exploring_ecp.html
https://vitalik.eth.limo/general/2017/02/01/zk_snarks.html
Проект для разработки собственных приложений с zk‑доказательствами на JavaScript:
https://github.com/iden3/snarkjs.git
