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

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

  1. Mr. Pickles

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

    Регистрация:
    11 сен 2017
    Сообщения:
    556
    Симпатии:
    205
    Несмотря на то, что доказательства zk-SNARK обладают замечательными свойствами, которые мы только что обсудили, всё-таки остаётся ряд вопросов, связанных с их применением с криптовалютами:
    • Время создания доказательства и необходимый объём памяти относительно велики в случае с доказательствами zk-SNARK, используемыми ZCash, что влечёт собой вычислительные затраты при проведении транзакций. Эта проблема была частично решена в последней версии Sapling, и ситуация, возможно, будет улучшаться по мере дальнейшей разработки.
    • Несмотря на то, что отличительным свойством доказательств zk-SNARK является «краткость», всё же их размер остаётся не нулевым, и наличие таких доказательств делает транзакции длиннее, чем у Bitcoin. И это проблема, поскольку соответствующий набор обязательств должен сохраняться каждым узлом навсегда, так как пользователям неизвестно, какие из обязательств были потрачены.
    • Версия доказательств zk-SNARK, предложенная BCTV и используемая ZCash, требует «доверенных настроек», при которых генерируется и уничтожается некоторый начальный случайный секрет. Если случайный выбор получится взломать, злоумышленник сможет сгенерировать доказательства zk-SNARK для недействительных утверждений, разрушая таким образом целостность системы. Первые доверенные настройки были сгенерированы ZCash при помощи радиоактивных отходов в октябре 2016 в ходе церемонии с привлечением 6 участников, а обновление доверенной настройки состоялось в апреле 2018 путём многостороннего вычисления, в которое было вовлечено уже 88 участников.
    В то время как над преодолением этих сложностей уже работают разработчики ZCash, существуют и другие подходы, реализуемые другими криптовалютными проектами, которые заключаются в расширении простых доказательств zk-SNARK или их замене. В настоящее время эти подходы находятся на этапе разработки, и мы кратко опишем несколько из них.

    Доказательства zk-STARK: исключение доверенных настроек и потенциальная возможность масштабирования

    1.jpg

    Ничего не разглашающий Старк

    В работе, написанной Бен-Сассоном (Ben-Sasson), Бентовым (Bentov), Хорешем (Horesh) и Рябцевым (Riabzev) (обозначим их для краткости как BBHR), была предложена альтернатива доказательствам zk-SNARK под названием zk-STARK, предполагающая отсутствие доверенных настроек. Как и в случае с вариантом zk-SNARK BCTV, доказательства zk-STARK являются любой системой, соответствующей списку определённых свойств, но термин часто используется для обозначения определённого варианта реализации, предложенного BBHR, и при сравнении мы будем использовать именно этот вариант.

    Доказательства zk-STARK являются системой, соответствующей требованиям zk-SNARK, но с 2 отличиями:
    • S обозначает scalable (масштабируемые), а не succinct (краткие). Согласно этому требованию время доказательства и верификации должно быть эффективным, при этом требование к верификатору эквивалентно требованию, применяемому в случае с доказательствами zk-SNARK;
    • T обозначает transparent (прозрачные), и это является наиболее важным отличием этого варианта реализации от zk-SNARK, так как означает отсутствие случайного секрета, необходимого для обеспечения безопасности протокола, а также отсутствие необходимости в доверенных настройках.
    Из-за своей схожести с доказательствами zk-SNARK доказательства zk-STARK часто рассматриваются в качестве их «прямой» замены при решении различных криптографических задач. В частности, наше описание SnarkCoin, которое приводится выше, не сильно бы изменилось, замени мы доказательства zk-SNARK на zk-STARK в каждом случае, но это позволило бы нам усовершенствовать монету до версии StarkCoin (официальная монета Stark Industries!). Такое усовершенствование повлекло бы за собой несколько изменений:
    • Помимо очевидного преимущества, связанного с устранением доверенных настроек, вариант zk-STARK, предлагаемый BBHR, как считается, обеспечил бы большую устойчивость к атакам с применением квантовых компьютеров, в то время как вариант zk-SNARK от BCTV, равно как и многие другие криптографические техники (например, обязательства Педерсена, о которых говорилось во втором посте), не обладают таким свойством, так как опираются на сложность задачи вычисления дискретного логарифма (DLP) на эллиптических кривых и/или в конечных полях. Это делает StarkCoin более безопасной с точки зрения постквантовой криптографии.
    • Несмотря на то, что доказательства zk-STARK являются асимптотически масштабируемыми, константы имеют значение, что известно каждому, работающему в рамках «теории реального мира». К сожалению, на практике размер доказательств, предложенных BBHR, примерно в 1000 раз больше, чем вариант BCTV в случае с одними и теми же утверждениями, что делает их непрактичными для применения в настоящее время. Это область активных исследований, проводимых Starkware и другими, и исследователи верят в то, что ситуацию можно значительно улучшить.
    С точки зрения реализации доказательства zk-STARK, предложенные BBHR, строятся на совершенно других математических основах, включая код Рида-Соломона. Мы рекомендуем заинтересованному читателю ознакомиться с соответствующей трилогией (не путать с трилогией по доказательствам zk-SNARK!) руководств (I, II, III), написанных Виталиком Бутериным.

    Рекурсивные доказательства (zk)-SNARK: сжатие состояния блокчейна

    Несмотря на то, что доказательства zk-SNARK, в случае с ZCash, создают необходимость в том, чтобы каждое обязательство сохранялось в блокчейне навсегда, расширение этого вида доказательств под названием рекурсивные доказательства SNARK, представленное в работах, написанных Битански (Bitansky), Канети (Canetti), Чиеза (Chiesa) и Тромером (Tromer) (BCCT), а также Бен-Сассоном, Чиеза, Тромером и Вирца (Virza) (BCTV), является технологией, позволяющей значительно сократить размер состояния. Эта технология может использоваться с применением или без применения аспекта нулевого разглашения zk-SNARK, а это означает, что она применима как к анонимным, так и не анонимным криптовалютам. В настоящее время технология применяется (без компонента нулевого разглашения) в Coda с целью сжатия состояния блокчейна.

    Ключевая идея заключается в создании метода составления доказательств SNARK. На высшем уровне состояние блокчейна включает в себя корень Меркла R для текущего множества балансов S и доказательства P, которое подтверждает, что «существует такое множество транзакций T и множество балансов S, что
    • S создаётся путём применения транзакций в T к состоянию генезиса
    • Validate(T) = True
    • Merklize(S) = R
    В частности, текущее множество балансов S не является частью общего состояния блокчейна; вместо отслеживания множества балансов пользователю придётся сохранить как эти балансы, так и путь Меркла к корню R. Чтобы провести транзакцию в этой системе, начиная с состояния (R, P), пользователю понадобится передавать в сеть транзакцию, состоящую из корня Меркла R' для нового множества балансов S' и доказательства P_diff, подтверждающего, что «существует такое множество транзакций T и множество балансов S и S', что
    • S' создаётся путём применения транзакций в T к S
    • Validate(T) = True
    • Merkelize(S) = R
    • Merkelize(S’) = R'
    Затем такая транзакция может использоваться для обновления состояния блокчейна путём назначения P' = Compose(P, P_diff; R), где Compose использует P и P_diff, чтобы сгенерировать доказательство, подтверждающее, что «существуют такие доказательства P_1 и P_2, множества балансов S_1 и S_2 и такой промежуточный корень Меркла R_1, что
    • Merkelize(S_1) = R_1
    • Merkelize(S_2) = R'
    • P_1 является действительным доказательством того, что «существует такое множество транзакций T_1, что S_1 создаётся путём применения транзакций в T_1 к состоянию генезиса»
    • P_2 является действительным доказательством того, что «существует множество транзакций T_2, берущих S_1 по S_2»
    Эта волшебная операция Compose является предметом сложных технологий, описанных в работах BCCT и BCTV и включающих в себя верификацию SNARK внутри SNARK, но, как это происходит, вам объяснят уже сами авторы.

    Ключевой момент состоит в том, что размер выходящего доказательства P' не зависит от количества транзакций в истории блокчейна, а это значит, что общее состояние блокчейна не увеличивается по мере его использования. Это напоминает свойство Mimblewimble, о котором говорилось в предыдущем посте, и оно способствует тому, что доказательства SNARK, скорее, обеспечивают целостность данных, а не анонимность.

    Bulletproofs: оптимизированные показатели специализированных утверждений

    В целом, существует компромисс между эффективностью и универсальностью доказательств с нулевым разглашением. Так же как схемы ASIC производятся с целью оптимизации выполнения узкоспециальных вычислений, так и инструменты доказательства с нулевым разглашением могут быть оптимизированы так, чтобы они приватизировали узкоспециальный тип вычислений. Примером может служить Bulletproofs, общая система доказательства с нулевым разглашением (технически это аргумент, согласно нашему описанию, которое мы приводили в первой части этой статьи), демонстрирующая довольно хорошие показатели с точки зрения доказательств диапазона, описанных в работе Бюнца (Bünz), Бутля (Bootle), Бонеха (Boneh), Поэлстра (Poelstra), Вуйля (Wuille) и Максвелла (Maxwell).

    Доказательства диапазона служат для подтверждения утверждений в форме «Мне известно, что значение X находится в пределах от 0 до MAX_INT», где MAX_INT = 2^N-1 для некоторого N. Они могут использоваться с криптовалютами, если вспомнить, какой вид утверждений нам было нужно доказать (с нулевым разглашением) в случае с SnarkCoin. Например, чтобы доказать, что у меня есть достаточное количество денег M, чтобы потратить Y монет SnarkCoin, мне бы пришлось бы доказать, что (M-Y) > 0, а для этого нужно доказать, что «(M – Y) находится в пределах от 0 до MAX_INT».

    Доказательства Bulletproofs используют немного прикладной математики. Нам хотелось бы выделить одну из многих забавных идей, использующую в целом полезные хитрости:
    1. Что означает, что X находится в пределах от 0 до 2^N-1? Это означает, что X можно записать как N 0/1 бит. Таким образом, мы можем представить X как N-мерный вектор A_L, разряды которого находятся в (самом большом!) диапазоне {0, 1, ... p-1} для некоторого числа p. Затем доказывающая сторона даёт обязательство по A_L (опять же, используя концепцию обязательств), используя некоторое обязательство (Педерсена) Commit_X = Commit(A_L). После этого цель состоит в доказательстве утверждения «Мне известен некоторый A_L, в котором все разряды равны 0 или 1, что удовлетворяет условию обязательства Педерсена». В этой статье мы сфокусируем наше внимание на первой части (проверке разрядов) и проигнорируем обязательства Педерсена.

    2. Как нам зашифровать эту проверку разрядов? Ответом служит комбинация скалярного произведения (которое мы запишем как <X,Y>) и адамарова произведения (которое мы запишем как h(X,Y)), где оба произведения являются функциями по паре векторов. Утверждение, согласно которому «все разряды A_L равны 0 или 1», эквивалентно логической функции И из 3 утверждений: <A_L, (2^{N-1}, ..., 2^0)> = X (заметьте, что это означает для A_L быть векторным произведением X), <A_R = A_L — (1,1,...1)> и h(A_L, A_R) = (0,...,0). Таким образом, мы сократили проверку разрядов до условий по векторным операциям.

    3. Теперь мы «отходим» и переписываем три вышеуказанных утверждения следующим образом: <A,B> = v, <C, D> = 0, <E,F> = 0, где A, B, C, D, E, F являются просто функциями, включающими A_L, A_R и некоторые вспомогательные переменные (в частности, A = A_L, B = (2^{N-1}, ... 2^0) и так далее).

    4. Преимущество такой формы состоит в том, что доказывающая сторона может доказать, что все эти три утверждения являются действительными одновременно, взяв случайное значение z(in {0,1,…p-1}) и доказав, что <A,B>z^2 + <E,F>z + <C,D> = z^2v.
    Если вернуться назад, то видно, что в результате мы изменили логическое И и N утверждений (касательно того, что каждое значение в векторе равно 0 или 1), объединив их в одно алгебраическое утверждение, касающееся некоторых векторов, что делает решение задачи как концептуально, так и практически проще. Получается, что мы можем использовать некоторые маскирующие элементы для проверки этого утверждения с нулевым разглашением. Таким образом, мы получаем аргумент с нулевым разглашением.

    Когда дело касается доказательств диапазона, Bulletproofs обеспечивают гораздо более короткие доказательства, чем в случае с предыдущими методами, и они уже были реализованы в Monero. С другой стороны, их общая реализация представляется гораздо более сложным полем компромиссов, что подробно описано здесь, и это делает сравнение этого вида доказательств с zk-SNARK или zk-STARK менее понятным.

    Заключение

    Различные инкарнации доказательств с нулевым разглашением, такие как zk-SNARK и zk-STARK, являются превосходными итеративными разработками на базе классических криптовалютных технологий, нашедшими себе применение в самом сердце теории криптовалют. Их до конца не раскрытый потенциал применения доказательств с нулевым разглашением в отношении общих утверждений даёт нам надежду на то, что дальнейшая разработка откроет невероятные новые возможности.

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

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

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

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