Перевод Анонимность криптовалют. Доказательства с нулевым разглашением и доказательства zk-SNARK (1/2)

Тема в разделе "Статьи", создана пользователем Mr. Pickles, 23 ноя 2019.

  1. Mr. Pickles

    Команда форума Модератор Редактор

    Регистрация:
    11 сен 2017
    Сообщения:
    556
    Симпатии:
    205
    Даже несмотря на то, что мы уже демонстрировали (например, в нашей второй статье) такую возможность, по-прежнему должно казаться немного непонятным, как же мы можем использовать блокчейн, проводить транзакции при наличии такого большого объёма анонимных составляющих (таких как личность участников, суммы транзакций и так далее). Давайте вернёмся немного назад и подумаем, какой может быть такая система.

    Очевидно, что вы являетесь членом «элитного, эксклюзивного и эксцентрического клуба» (а с чего бы вам ещё заниматься криптовалютами?), где все ваши действия находятся под постоянным наблюдением с использованием высококачественных видеосистем, а вы находитесь в хорошо освещённой комнате с гигантским подиумом. Время от времени на подиум выходит человек, личность которого скрыта плащом, и громко выкрикивает ряд чисел.

    После этого вы и остальные члены клуба дружно киваете и обновляете свой реестр (ваши копии блокчейна), понимая, что какой-то незнакомый вам человек (назовём его/её A) действительно передал некоему также незнакомому вам человеку B сколько-то монет, и в результате:
    1. Никто не знает, кто такие A и B. Возможно, это вообще один и тот же человек.

    2. Все уверены в том, что ни одна монета не была уничтожена или создана из воздуха.

    3. Никому не известна сумма, которая была передана, даже несмотря на то, что все уверены в том, что A не передал B монет больше, чем было у A.
    Это абсурдные условия. В частности, в следующий раз, когда незнакомец выкрикнет набор чисел, что будет соответствовать попытке перевести X монет кому-то другому, люди смогут определить попытку обмана (например, что у них меньше, чем X монет). В этом случае единственное, что узнают остальные члены клуба, так это то, что у незнакомца нет достаточного количества монет! Они не узнают ничего об X или о том количестве монет, которые были у незнакомца!

    Пример, приведённый выше, демонстрирует, что такое участие в системе, основанной на доказательствах с нулевым разглашением или ZKP (Zero-Knowledge Proofs). ZKP являются прекрасной частью теоретической криптографии и очень популярны в криптовалютном сообществе, по большей части благодаря известным вариантам реализации (и акронимам) zk-SNARK (известен благодаря ZCash) и zk-STARK. Вместе с тем в последнее время широкое применение находят и другие системы на базе ZKP, такие как Bulletproofs.

    Что касается нашей темы, эта статья познакомит технического (но не обязательно теоретически подкованного) читателя с основными теоретическими идеями и их связи с аспектом анонимности. Для этого в качестве основного примера (и целью первой части этой статьи) нами будет использована упрощённая версия ZCash.

    1.jpeg
    Посадка закончена. Источник: Wikipedia

    Мы хотим, чтобы читатель понял эти концепции и чем они отличаются друг от друга на уровне, который будет чуть выше «криптографического волшебства». При этом мы оставим слишком сложные технические подробности в «чёрном ящике». Поправки и предложения приветствуются, как обычно.

    Доказательства, доказательства с нулевым разглашением конфиденциальной информации и доказательства zk-SNARK

    Что означает весь этот суп из букв? По сути, это доказательства с дополнительными гарантиями. Доказательство представляет собой некую строку (которая может быть просто последовательностью чисел), позволяющую доказывающей стороне убедить верификатора, что некоторое утверждение является истинным. Требуется соблюдение двух условий:
    1. Полнота. Если утверждение будет истинным, верификатор будет убеждён, что так оно и есть. Достаточно очевидно.

    2. Корректность. Если утверждение будет ложным, в нём будет «сложно» убедить верификатора. Как и в случае с обычным применением теории сложности и криптографии, «сложно» означает «очень низкую вероятность», то есть 10^{-800}. Несмотря на то, что возможность существования «фальшивого доказательства» в контексте денег звучит скверно, тот факт, что сама вероятность столь мала, говорит о достаточно хорошем уровне защиты в условиях реального мира.
    Далее мы называем доказательство доказательством с нулевым разглашением (ZKP), если «верификатор не получает какой-либо дополнительной информации», помимо подтверждения истинности утверждения. Этот по-волшебному звучащий термин формально определяется требованием, которое сводится к тому, что доказательство должно быть неотличимо от доказательства, созданного симулятором; это означает, что «если кто-то, кто не знает ничего, смог бы убедительно смоделировать весь процесс взаимодействия, то вы никаким образом не смогли бы заполучить информацию, просто наблюдая за взаимодействием». Более подробную информацию заинтересованный читатель сможет найти в соответствующей статье на Wikipedia или в посте Мэтью Грина (Matthew Green), но в нашем случае будет достаточно и грубого определения, которое приводится выше, так как симуляторы важны с формальной точки зрения, но не для реализации (то есть, когда вы доказываете что-либо, используя ZKP, вам необязательно создавать для этого симулятор).

    Чтобы понять, почему ZKP могут быть полезны с точки зрения обеспечения анонимности, будет неплохо взглянуть на то, как работают более знакомые нам цифровые подписи. С философской точки зрения (хорошая) цифровая подпись T доказывает утверждение «Мне известен секрет SK, поэтому, когда я запускаю программу Sign(SK,M) по публичному сообщению M, я получаю значение T».

    Задумайтесь на минутку. Если секрет SK был бы известен только Дениз и подразумевается, что без SK получить Sign(SK,M) = T сложно, то если Дениз докажет вышеуказанное утверждение, а затем предоставит свою подпись T к своему сообщению M, таким образом она докажет свою идентичность! Следовательно, цифровую подпись можно считать неинтерактивным доказательством того, что Дениз известен секретный ключ SK. Такая схема подписи станет к тому же и доказательством с нулевым разглашением, если подпись T не будет разглашать никакой информации о секретном ключе SK.

    Это хорошая промежуточная остановка, так как ZKP являются одной из самых крутых теоретических частей классической криптографии. Криптовалютами был популяризирован тип ZKP под названием zk-SNARK. Этот тип ZKP предполагает наличие дополнительных требований (соответствующих дополнительным буквам), которым было бы хорошо следовать криптовалютам. 2 буквы нам уже понятны, осталось ещё 5! Да, нам известно, что P пропала, но мы и до этого доберёмся.
    • Во-первых, S означает succinct (краткий), что указывает на то, что пара вещей должны быть краткими/быстрыми: длина доказательства (так как в случае с криптовалютами пользователям необходимо дублировать данные) и время верификации (из-за децентрализации многим может захотеться самостоятельно верифицировать каждую транзакцию).
    • Во-вторых, N означает non-interactive, то есть подчёркивает свойство неинтерактивности доказательств. В данном случае это важно, поскольку исследователи компьютерной теории часто работают с интерактивными (с нулевым разглашением и другими) доказательствами, когда верификатор может сделать интерактивный запрос доказывающей стороне на этапе верификации. Такие доказательства являются более общими и более простыми для понимания, но они менее подходят для криптовалют по множеству причин. Например, одна из причин заключается в том, что (как с точки зрения масштабируемости, так и из соображений безопасности) мы стараемся избегать необходимости в том, чтобы доказывающая сторона и верификатор одновременно находились онлайн для того, чтобы интерактивно верифицировать доказательство. Ещё одна глубокая философская причина состоит в том, что интерактивные протоколы зависят от верификатора (которым является блокчейн!), использующего некоторую секретную произвольность, которая требуется в силу требований таких протоколов, что представляется невозможным.
    • AR обозначает argument (аргумент), являющийся более слабой формой «доказательства». Техническое отличие состоит в том, что свойство «корректности», о котором мы говорили, когда речь шла о доказательствах, требует, чтобы для доказывающей стороны, обладающей большой вычислительной мощью, было сложно убедить верификатора в ложном утверждении, в то время как системы, основанные на аргументе, требуют, чтобы доказывающей стороне было сложно убедить верификатора в ложном утверждении по полиномиальному времени. На удалённом уровне разница кажется незначительной.
    • И наконец, K обозначает, что наши аргументы касаются знания, то есть knowledge. Это формальный способ сказать то, что мы подразумеваем под утверждениями в форме «Мне известен X» вместо прямых математических выражений, таких как «Y=Z». Формальное определение «аргумента знания» основано на технической концепции экстрактора, который точно указывает, что именно означает для утверждения принять форму «Мне известен X».
    Если кратко, система zk-SNARK, в случае с доказывающей стороной Элис и верификатором Бобом, будет представлять собой следующее:
    • Элис известна часть K (знание);
    • Элис может доказать Бобу, что ей она известна, при помощи N (неинтерактивного) AR (аргумента), по сути, доказательства, после чего Боб будет уверен в том, что Элис известна часть знания, при этом он получит Z (нулевое) K (знание) об этой части;
    • длина аргумента Элис и время, необходимое Бобу для проверки аргумента, являются S (краткими).
    Безусловно, это только требования к zk-SNARK; нами ничего не было сказано о том, как на деле реализуются такие вещи. Когда люди из мира криптовалют говорят SNARK, они обычно имеют в виду какой-то определённый вариант реализации zk-SNARK. Это как в случае с компанией Xerox и ксероксом в значении «ксерокопия». Понятие доказательств SNARK впервые появилось в статье Бен-Сассона (Ben-Sasson), Чиеза (Chiesa), Тромера (Tromer) и Вирца (Virza) (будем всех вместе называть их BCTV), где они использовали алгебру над конечным полем, эллиптические кривые и QAP (квадратичные арифметические программы, которые шифруют отдельные логические элементы в арифметической схеме как арифметические операции между парами полиномов). Если вам, как и нам, хотелось бы глубже погрузиться в математическую суть вопроса, мы рекомендуем вам ознакомиться с трилогией постов Виталика Бутерина (Vitalik Buterin): I, II и III. Кроме того, лично нам кажется, что Pinocchio, предшественники SNARK на базе QAP, реализованные Парно (Parno) и Джентри (Gentry), также весьма полезны для понимания BCTV.

    Для нас наиболее важен тот факт, что BCTV предлагают вариант доказательств zk-SNARK для общих вычислений! А это означает, что мы можем «zk-SNARK-ифицировать» произвольные аргументы, звучащие как «Мне известны некоторые входы X, и если вы произведёте определённый ряд вычислений по X, то получите Y», в результате чего такие утверждения превратятся, например, в ряд чисел. Это очень, очень мощно. При таком результате мы можем создавать последовательности, которые будут доказывать утверждения вроде следующих:
    1. «Мне известен секрет S, поэтому, если я использую хеш-функцию f(S), я получу значение H» (поскольку хеш-функция является простым вычислением).

    2. «Мне известны числа X, Z, при которых X² + Y² = Z² (для некоторого заданного Y)».

    3. «Мне известно число SK, являющееся приватным ключом по крайней мере для одного из UTXO_1 и UTXO_2».
    Таким образом, получатели будут убеждены в истинности этих утверждений, но не узнают ничего из того, что известно вам, после того как вы убедите их!

    Теперь давайте посмотрим, как это «работает» в случае с какой-то гипотетической криптовалютой.

    Что насчёт анонимности криптовалют?

    Теперь мы опишем, как доказательства zk-SNARK могут использоваться со SnarkCoin, гипотетической упрощённой версией Zerocash (протоколом, ведущим к ZCash), для проведения чего-то вроде встреч клуба с нулевым разглашением, как было описано нами во вступлении. Мы убрали некоторые детали, характерные для Zerocoin, такие как различия между «стабильной монетой» и «защищённой монетой», чтобы сфокусироваться на сути идеи.

    В случае с SnarkCoin данные монеты состоят из трёх частей:
    • значение (денежная сумма);
    • серийный номер (идентификатор монеты, который впоследствии гарантирует, что монета не была потрачена дважды);
    • адрес (это публичный ключ, связывающий монету с кем-то при помощи соответствующего приватного ключа, принадлежащего только тому, кто может потратить эту монету).
    Каждая монета имеет обязательство, которое является числом, полученным на основе монеты при помощи некоторой функции (об идее обязательств и раскрытия говорилось в нашем втором посте; основная идея состоит в сложности интерпретации обязательства по одному значению в качестве обязательства по какому-то другому значению, поэтому в нашем случае, если у нас есть обязательство по 30 монетам, по сути, невозможно соврать и вместо этого сказать, что обязательство было по 50 монетам). Когда мы «передаём монету в блокчейн», мы передаём только обязательства по ней, а не данные её значения или серийные номера. Блокчейн SnarkCoin состоит из транзакций, которые формируют его текущее состояние, которое определяется следующим:
    • рядом обязательств, которые играют роль, аналогичную роли UXTO (непотраченных выходов транзакций) в Bitcoin;
    • рядом раскрытых серийных номеров, которые играют роль списка потраченных монет.
    Чтобы описать транзакции SnarkCoin, предположим, что пользователю Элис известны приватные ключи для монет Coin_A и Coin_B, каждая из которых имеет значение, равное 50, и Элис хочет отправить 30 SnarkCoin другому пользователю, Бобу, потратив Coin_A и Coin_B и создав новые монеты Coin_C (со значением 30 для Боба) и Coin_D (со значением 70 для Элис). Она может сделать это, передав в сеть транзакцию Pour(Serial_A, Serial_B, Commit_C, Commit_D), которая будет содержать следующую информацию:
    • серийные номера Serial_A и Serial_B для монет Coin_A и Coin_B;
    • обязательства Commit_C = Commit(Coin_C) и Commit_D = Commit(Coin_D) для монет Coin_C и Coin_D;
    • доказательство zk-SNARK (любого типа, например, BCTV, которое позволит доказать такие утверждения), подтверждающее, что транзакция Pour(Serial_A, Serial_B, Commit_C, Commit_D) является действительной, то есть доказательство zk-SNARK для утверждения «Мне известны данные некоторых монет Coin_A, Coin_B, Coin_C, и Coin_D, а также приватные ключи Key_A и Key_B, таким образом...»
    1. «Приватные ключи Key_A и Key_B являются действительными ключами, соответствующими публичным ключам монет Coin_A и Coin_B». Для валидации приватных ключей просто производится вычисление, и мы можем создать zk-SNARK для вычисления!

    2. «Обязательства Commit(Coin_A) и Commit(Coin_B) есть в реестре». Так как обязательства являются функциями, первая часть является ещё одной вычислительной проверкой для вычисления обязательств. Вторая часть — это просто проверка наличия определённых элементов в некотором множестве, что реализуется довольно просто (в случае с Zerocash это делается путём проверки дерева Меркла).

    3. «Обязательства Commit_C и Commit_D равны Commit(Coin_C) и Commit(Coin_D)». Это противопоставление предыдущей позиции: Commit_C и Commit_D являются публичными, в то время как Commit(Coin_A) и Commit(Coin_B) нет. Мы также не проверяем реестр, так как обязательства Commit_C и Commit_D являются новыми.

    4. «Серийные номера Serial_A и Serial_B старых монет не находятся в списке потраченных монет». Нечто подобное необходимо нам, чтобы гарантировать, что монеты не будут потрачены множество раз.

    5. «значения монет Coin_A, Coin_B, Coin_C и Coin_D не являются отрицательными, а Value(Coin_A) + Value(Coin_B) = Value(Coin_C) + Value(Coin_D)». Эти утверждения гарантируют, что монеты ни создаются, ни уничтожаются.
    Понимание определённых пунктов поможет вам, но основная идея состоит в том, что мы зашифровали желаемое в математические формулировки, а BCTV знают, как превратить эти математические формулировки в доказательства zk-SNARK.

    Все транзакции SnarkCoin будут иметь именно такую форму. Стоит отметить несколько моментов с точки зрения «заливки»:

    1. Серийные номера Serial_A и Serial_B старых монет становятся видимыми, но сами монеты нет. Так происходит, потому что мы хотим, чтобы значения и адреса, соответствующие монетам, оставались приватными, но демонстрация старых серийных номеров гарантирует, что монеты не будут потрачены снова.

    2. Обязательства Commit_C и Commit_D новых монет становятся видимыми (поскольку нам необходимо поместить их в публичный реестр), но, опять же, сами монеты (даже их серийные номера) нет.
    Несмотря на то, что «заливка» позволяет Элис только превратить две монеты в две другие монеты, это строительный блок, который можно комбинировать с целью обработки случайных сложных транзакций, в которых участвует множество людей.

    Если вы хотите изучить проблему подробнее, мы рекомендуем вам посмотреть это видео, в котором Алессандро Чиеза раскрывает основные идеи, стоящие за протоколом Zerocash.

    Что дальше

    Вот мы и получили простую криптовалюту, реализующую наш, как казалось в начале, невозможный трюк. Как только люди начинают передавать монеты (то есть выходят на подиум, выкрикивают ряды чисел, обновляя реестры остальных людей), монеты начинают перемещаться, и никому в клубе не известно ничего, кроме того, сколько монет у них имеется. И если пример SnarkCoin кажется вам недостаточно убедительным, мы оставляем вас со следующими (странными!) свойствами:
    • соглашаясь с последовательностью транзакций, узлы соглашаются с существованием действительного подтверждения владения (ни одна монета не была потрачена дважды, и монеты тратились только владельцами, которым известны их приватные ключи), но ни одному из узлов при этом не известен сам владелец или значения монет;
    • оговорка, касающаяся вышесказанного: как отмечает Алессандро Чиеза, наша упрощённая схема позволяет плательщику узнать того, кто получает платёж, если второй использует монету, созданную плательщиком позднее. Это можно исправить, как в случае с ZCash, но над этим ещё надо поработать;
    • в частности, пользователи даже могут запомнить свои приватные ключи, но они не смогут потратить свои SnarkCoin, если забудут соответствующие серийные номера;
    • для валидации транзакций пользователям необходимо хранить полный набор обязательств, даже по потраченным монетам, так как им неизвестно, какие монеты были потрачены.

    (В целом это не то, о чём мы думали, когда писали вступление. Правда! Источник: VeChain)

    Теперь нам нужно прерваться на какое-то время. Вторая часть статьи, которую мы скоро опубликуем, будет посвящена другим протоколам ZKP, появление которых стало возможным благодаря доказательствам zk-SNARK, а также их сравнению.

    Продолжение следует...

    Мы хотели бы поблагодарить Михали Барац (Mihaly Barasz), Альберта Ни (Albert Ni), Виталика Бутерина и Алессандро Чиеза за их полезные комментарии и помощь, оказанную в ходе написания обеих частей этой статьи.

    Источник: Privacy in Cryptocurrencies: Zero-Knowledge and zk-SNARKs (1/2)

    Перевод:
    Mr. Pickles (@v1docq47)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
    #1 Mr. Pickles, 23 ноя 2019
    Последнее редактирование: 28 ноя 2019
  • О нас

    Наш сайт является одним из уникальных мест, где русскоязычное сообщество Monero может свободно общаться на темы, связанные с этой криптовалютой. Мы стараемся публиковать полезные мануалы и статьи (как собственные, так и переводы с английского) о криптовалюте Monero. Если вы хорошо владеете английским (или можете писать собственные статьи/мануалы) и хотите помочь в переводах и общем развитии Monero для русскоязычной аудитории - свяжитесь с одним из администраторов.