Виталик Бутерин: Как технология zk-SNARKs защищает конфиденциальность?

zk-SNARKs - это мощный криптографический инструмент, который становится все более необходимой частью приложений, основанных как на блокчейне, так и не на блокчейне. Их сложность очевидна как в понимании того, как они функционируют, так и в том, как их можно эффективно использовать. В этой статье рассматривается, как zk-SNARK адаптируются к современным приложениям, приводятся примеры того, чего они могут и не могут достичь, и предлагаются общие рекомендации о том, когда zk-SNARK подходят для конкретных приложений. Особое внимание будет уделено их роли в обеспечении конфиденциальности.

Что такое zk-SNARK?

Представьте, что у Вас есть публичный вход x, частный вход w и (публичная) функция f(x,w) → {True,False}, которая проверяет входы. С помощью zk-SNARKов можно доказать, что они знают w, такое, что для заданных f и x, f(x,w) = True, и все это без раскрытия того, что на самом деле представляет собой w. Более того, верификаторы могут проверить подлинность доказательства гораздо быстрее, чем они могли бы вычислить f(x,w), даже если бы знали w.

Это наделяет zk-SNARK двумя атрибутами: конфиденциальностью и масштабируемостью. Как уже говорилось, наши примеры в этой статье будут в основном посвящены аспекту конфиденциальности.

Доказательство членства

Предположим, у Вас есть кошелек Ethereum, и Вы хотите доказать, что этот кошелек зарегистрирован в системе доказательства человечности, не раскрывая, кто на самом деле является зарегистрированным человеком. Эта функция может быть математически описана как:

Приватный вход (w): Ваш адрес A, закрытый ключ Вашего адреса k

Публичный вход (x): набор адресов всех проверенных профилей доказательства человечности {H1…Hn}

Проверочная функция f(x,w):

Интерпретируйте w как пару (A, σ), а x как правильный список профилей {H1…Hn}

Убедитесь, что A - один из адресов в {H1…Hn}

Подтвердите privtoaddr(k) = A

Если обе проверки пройдены, верните True. Если хоть один из них не сработал, верните False.

Доказатель генерирует свой адрес A и связанный с ним ключ k, предоставляя w=(A,k) в качестве частного входа для f. Они получают из цепочки публичный вход, который представляет собой текущий набор проверенных профилей доказательства человечности {H1…Hn}. Затем они запускают алгоритм доказательства zk-SNARK, который (при условии, что входные данные верны) выдает доказательство. Это доказательство отправляется верификатору вместе с высотой блока, из которого он извлек список проверенных профилей.

Верификатор также читает цепочку, получая список {H1…Hn} с заданной провером высоты, и проверяет доказательство. Если проверка прошла успешно, верификатор считает, что доказатель обладает проверенным профилем доказательства человечности.

Прежде чем перейти к более сложным примерам, я настоятельно рекомендую полностью разобраться в приведенном выше примере.

Повышение эффективности доказательств членства

Один из недостатков вышеупомянутой системы доказательства заключается в том, что проверяющий должен знать весь набор профилей {H1…Hn}, что требует O(n) времени для "ввода" этого набора в механизм zk-SNARK. Эту проблему можно решить, используя корень Merkle, охватывающий все профили, в качестве публичного входа (потенциально это может быть только корень государства). Мы добавляем еще один частный вход, доказательство Меркла M, подтверждающее, что счет A проверяющего находится в соответствующей части дерева.

Совсем недавно появилась более эффективная альтернатива доказательствам Меркла для доказательств принадлежности к ZK - это Caulk. В будущем некоторые из этих вариантов использования могут перейти к решениям, подобным Caulk.

ZK-SNARKs и монеты

Такие проекты, как Zcash и Tornado.cash, позволяют нам обладать валютами, защищающими конфиденциальность. Теперь можно подумать, что они могли бы использовать упомянутые "человеческие доказательства ZK", но дело не в доказательстве доступа к доказательствам человеческого профиля; дело в доказательстве доступа к монетам. Здесь кроется проблема: мы должны одновременно решать проблемы конфиденциальности и двойных расходов. То есть, мы не должны тратить одну и ту же монету дважды.

Вот как мы решаем эту проблему: Каждый, кто владеет монетой, имеет личный секрет "s". Они локально вычисляют "лист" L=hash(s,1), который публикуется в цепочке, становясь частью состояния, N=hash(s,2), которое мы называем нуллификатором. Состояние хранится в дереве Меркла.

Чтобы потратить монету, отправитель должен предъявить ZK-SNARK, где:

• Открытые входы включают нуллификатор N, текущий или недавний корень Меркла R и новый лист L' (предназначенный для получателя, у которого есть секрет s', переданный отправителю в виде L'=hash(s',1)).

• Частные данные включают в себя секрет s, лист L и ветвь Меркла M.

Функция проверки проверяет:

• M - правильная ветвь Меркла, доказывающая, что L - лист дерева, уходящий корнями в R, где R - корень Меркла текущего состояния.

• hash(s,1)=L и hash(s,2)=N.

Транзакция содержит нуллификатор N и новый лист L'. На самом деле мы ничего не доказываем о L', но она "подмешивается" в доказательство, чтобы предотвратить ее изменение третьими лицами во время транзакции. Чтобы подтвердить транзакцию, цепочка проверяет ZK-SNARK и проверяет, не использовался ли N в предыдущих транзакциях. В случае успеха N добавляется к набору потраченных нуллификаторов, делая его снова непригодным для использования. L' добавляется в дерево Меркла.

Используя ZK-SNARK, мы связываем два значения: L (появляется на цепочке, когда монета отчеканена) и N (появляется, когда монета потрачена), не раскрывая, какое L связано с каким N. Связь между L и N заметна только тогда, когда Вы знаете секрет s, который их генерирует. Каждая отчеканенная монета может быть использована один раз (поскольку для каждой L существует только одна действительная N), но конкретная монета, используемая в любой момент времени, остается скрытой.

Это очень важный момент, который необходимо понять. Многие механизмы, которые мы опишем ниже, основаны на этом, хотя и с разными целями.

Монеты с произвольным балансом

Вышесказанное можно легко распространить на монеты с произвольным балансом. Мы сохраняем концепцию "монеты", но каждая монета имеет (личный) баланс. Простой способ добиться этого - чтобы каждая монета имела цепочку хранения, не только с листом L, но и с зашифрованным балансом. Каждая транзакция будет потреблять две монеты и создавать две новые, добавляя в состояние две пары (лист, зашифрованный баланс). ZK-SNARK также проверяет, что сумма входных остатков равна сумме выходных остатков, и оба выходных остатка неотрицательны.

ZK Антиотказ в обслуживании

Интригующее средство защиты от DOS: Представьте, что у Вас есть некая идентификация в цепи, которую не так-то просто создать; это может быть профиль, защищенный от человеческих действий, или 32 валидатора ETH, или просто аккаунт с ненулевым балансом ETH. Мы можем создать более устойчивую к DOS одноранговую сеть, принимая только те сообщения, которые подтверждают наличие профиля у отправителя. Каждому профилю будет разрешено до 1000 сообщений в час. Если отправитель обманывает, его профиль удаляется из списка. Но как обеспечить конфиденциальность?

Сначала о настройках: пусть k будет закрытым ключом пользователя, а A=privtoaddr(k) - соответствующим адресом. Список действительных адресов является публичным (например, в реестре цепочек). Пока что это отражает пример с человеческой защитой: Вы должны доказать, что владеете закрытым ключом к какому-либо адресу, не раскрывая при этом, к какому именно. Но нам нужно не только доказательство того, что Вы в списке. Нам нужен протокол, который позволит Вам доказать, что Вы находитесь в списке, но при этом ограничит Ваши доказательства.

Мы разделим время на периоды: каждый длится 3,6 секунды (получается 1000 периодов в час). Наша цель - позволить каждому пользователю отправлять только одно сообщение за период; если он отправит два за один период, его поймают. Чтобы учесть случайные всплески, они могут использовать последние периоды. Таким образом, если у пользователя есть 500 неиспользованных периодов, он может отправить 500 сообщений за один раз.

Протокол

Давайте начнем с базовой версии с использованием нуллификаторов. Пользователь генерирует нуллификатор (N = \text{hash}(k, e)), где (k) - его ключ, а (e) - номер эпохи, а затем публикует его с сообщением (m). Затем ZK-SNARK запутает (\text{hash}(m)). В этом процессе ничего о (m) не проверяется, что привязывает доказательство к одному сообщению. Если пользователь свяжет два доказательства с двумя разными сообщениями, используя один и тот же нуллификатор, он рискует быть пойманным.

Теперь мы переходим к более сложной версии. В этом сценарии последующий протокол раскрывает их закрытый ключ, а не просто подтверждает, что кто-то дважды использовал одну и ту же эпоху. Наша ключевая техника основана на принципе "две точки определяют линию". Раскрытие одной точки на линии мало что дает, но раскрытие двух точек раскрывает всю линию.

Для каждой эпохи (e) мы выбираем линию (L_e(x) = \text{hash}(k, e) \times x + k). Наклон линии равен (\text{hash}(k, e)), а y-интерцепт - (k), и оба эти значения неизвестны. Чтобы получить сертификат для сообщения (m), отправитель предоставляет (y = L_e(\text{hash}(m)) = \text{hash}(k, e) \times \text{hash}(m) + k), а также ZK-SNARK доказательство того, что вычисление (y) является точным.

Подводя итог, можно сказать, что ZK-SNARK заключается в следующем:

Общественные ресурсы:

• ({A_1…A_n}): Список действительных учетных записей

• (M): Сообщение, подтверждаемое сертификатом

• (E): номер эпохи для сертификата

• (Y): Оценка линейной функции

Частный вход:

• (K): Ваш закрытый ключ

Функция верификации:

• Проверьте, существует ли (\text{privtoaddr}(k)) в ({A_1…A_n}).

• Подтверждение (y = \text{hash}(k, e) \times \text{hash}(m) + k)

Но что, если кто-то использует эпоху дважды? Они покажут два значения (m_1) и (m_2) вместе со значениями их сертификатов (y_1 = \text{hash}(k, e) \times \text{hash}(m_1) + k) и (y_2 = \text{hash}(k, e) \times \text{hash}(m_2) + k). Затем мы можем использовать эти две точки для восстановления линии и, соответственно, y-intercept, который является закрытым ключом.

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

Жизнеспособная внецепочечная анонимная система защиты от запрета на обслуживание, подходящая для одноранговых сетей на основе блокчейна, чат-приложений и подобных систем, не требует доказательств работы. Проект RLN в основном ориентирован на эту концепцию, хотя и с небольшими изменениями (а именно, в нем используются как нуллификаторы, так и техника двухточечной линии, что упрощает обнаружение случаев повторного использования эпохи).

Отрицательная репутация ZK

Представьте себе создание 0chan - онлайнового форума, подобного 4chan, который предлагает полную анонимность (у Вас даже нет постоянных имен), но с системой репутации для продвижения более качественного контента. Такая система могла бы иметь управляющую DAO, которая отмечала бы сообщения, нарушающие правила системы, вводя механизм трех ударов.

Система репутации может работать как с положительной, так и с отрицательной репутацией; однако для учета отрицательной репутации требуется дополнительная инфраструктура. Это требует, чтобы пользователи включали в свои доказательства все данные о репутации, даже если они отрицательные. Мы в первую очередь сосредоточимся на этом сложном варианте использования, подобном тому, который стремится реализовать Unirep Social.

Связанные посты: Базовые знания

Любой может разместить сообщение, передав сообщение по цепочке, содержащей сообщение, сопровождаемое ZK-SNARK. Этот ZK-SNARK служит доказательством того, что (i) Вы обладаете уникальной внешней идентификацией, которая дает Вам разрешение на создание учетной записи, или (ii) Вы ранее публиковали определенные сообщения. В частности, ZK-SNARK функционирует следующим образом:

Общественные ресурсы:

• Нуллификатор, N

• Самый последний корень состояния блокчейна, R

• Содержимое поста ("подмешивается" в доказательство, чтобы привязать его к посту, без каких-либо вычислений над ним)

Частные входы:

• Ваш закрытый ключ, k

• Внешний идентификатор (адрес A) или нуллификатор Nprev, использованный в предыдущем сообщении

• Доказательство Меркла, M, что цепочка содержит A или Nprev

• Первое сообщение, которое Вы опубликовали, используя эту учетную запись.

Функция верификации:

1. Подтвердите, что M является правильной ветвью Меркла, доказав, что (A или Nprev, в зависимости от того, что предоставлено) является листом дерева с корнем R.

2. Проверьте N = enc(i, k), где enc - это функция шифрования (например, AES).

3. Если i=0, проверьте A=privtoaddr(k), в противном случае проверьте Nprev=enc(i-1,k).

Помимо проверки доказательства, цепочка также проверяет (i) что R действительно является корнем из последнего состояния, и (ii) что нуллификатор N не использовался ранее. До этого момента она напоминала ранее описанные монеты, сохраняющие конфиденциальность, но мы добавили процесс "чеканки" новых аккаунтов и убрали возможность "отправлять" Ваш аккаунт на разные ключи. Вместо этого все нуллификаторы генерируются с использованием оригинального ключа. Мы используем кодировку, чтобы сделать нуллификатор обратимым. Если у Вас есть ключ k, Вы можете расшифровать любой конкретный нуллификатор на цепочке; если результатом будет правильный индекс, а не случайная белиберда (например, мы можем просто проверить dec(N) < 2^64), Вы будете знать, что нуллификатор был сгенерирован с помощью ключа k.

Добавление репутации:

В этой схеме репутация находится в цепи и является явной. В некоторых смарт-контрактах есть метод AddReputation, который принимает на вход нуллификатор, выпущенный вместе с сообщением, и количество единиц репутации, которые нужно добавить или вычесть.

Мы расширили данные, хранящиеся в цепочке, для каждого поста. Вместо того чтобы хранить только нуллификатор N, мы храним {N, h¯, u¯}, где:

• h¯ = hash(h, r), где h представляет собой высоту блока корня состояния, на который ссылается доказательство.

• u¯ = hash(u, r), где u - оценка репутации аккаунта (начинается с 0 для новых аккаунтов).

R здесь - случайная величина, добавляемая для того, чтобы h и u не были найдены с помощью грубой силы. В криптографических терминах добавление R делает хэш скрытым обязательством.

Предположим, что пост использует корень R и хранит {N, h¯, u¯}. В своем доказательстве он ссылается на предыдущий пост, в котором хранятся данные {Nprev, h¯prev, u¯prev}. Доказательство поста также должно пройти через все записи репутации, опубликованные между hprev и h. Для каждого нуллификатора N функция проверки расшифровывает N, используя ключ пользователя k. Если расшифровка выдает правильный индекс, применяется обновление репутации. Если сумма всех обновлений репутации равна δ, то это доказывает, что u = uprev + δ.

Если мы хотим ввести правило "три удара - и Вы выбываете", ZK-SNARK также обеспечит u > -3. Если нам нужно правило, по которому пост с репутацией ≥ 100 получает специальный тег "пост с высокой репутацией", это тоже можно сделать.

Чтобы повысить масштабируемость этой системы, мы можем разделить ее на два типа сообщений: Сообщения и RCA. Сообщение будет не по теме, хотя оно требует указания на RCA, сделанное за последнюю неделю. RCA будут цепочкой, проходящей через все обновления репутации с момента предыдущего RCA издателя. Таким образом, нагрузка на цепочку снижается до одной транзакции на одно сообщение в неделю, плюс одна транзакция на каждое сообщение о репутации.

Обеспечение подотчетности централизованных сторон

Иногда возникает необходимость разработать систему с централизованным "оператором". Причины могут быть разными: иногда это связано с масштабируемостью, а иногда - с конфиденциальностью, особенно с конфиденциальностью данных, хранящихся у оператора. Например, система голосования MACI, устойчивая к принуждению, требует, чтобы избиратели подавали свои голоса по цепочке, зашифрованные ключом, находящимся у централизованного оператора. Этот оператор расшифровывает все голоса в цепи, подсчитывает их и выводит на экран окончательный результат. Они используют ZK-SNARK, чтобы доказать, что все, что они сделали, было точным. Эта дополнительная сложность очень важна для обеспечения надежной конфиденциальности (известной как принудительное сопротивление): пользователи не смогут никому доказать, как они голосовали, даже если бы захотели. Благодаря блокчейну и ZK-SNARK наш уровень доверия к оператору остается минимальным. Вредоносные операторы могут нарушить принудительное сопротивление, но поскольку голоса публикуются в блокчейне, они не смогут обмануть, подвергнув голоса цензуре. И поскольку они должны предоставить ZK-SNARK, они не могут обмануть, неправильно подсчитав результаты.

Комбинирование ZK-SNARK с MPC

Более продвинутое применение ZK-SNARK - это вычисления, где требуется доказательство, при этом входные данные распределены между двумя или более сторонами, и мы не хотим, чтобы какая-либо сторона узнала о входных данных других. В двухстороннем сценарии гарбированные схемы могут удовлетворять требованиям конфиденциальности; для N сторон можно использовать более сложные протоколы многосторонних вычислений. ZK-SNARK могут быть интегрированы с этими протоколами для верифицируемых многосторонних вычислений. Это позволяет создавать продвинутые репутационные системы, позволяющие нескольким участникам выполнять совместные вычисления на своих частных исходных данных. Математика для эффективного достижения этой цели все еще находится на ранней стадии.

Что мы не можем сделать частным?

ZK-SNARKs очень эффективен при создании систем, в которых пользователи имеют частные состояния. Однако он не может поддерживать состояние приватности, о котором никто не знает. Чтобы информация была доказана, проверяющий должен знать ее в открытом виде. Uniswap - пример того, что трудно приватизировать. В Uniswap есть центральная логическая "сущность" - счет поставщика ликвидности, который никому не принадлежит, и все транзакции Uniswap происходят с этим счетом. Вы не можете скрыть состояние этого счета, поскольку для доказательства кому-то нужно хранить это состояние в открытом виде, и каждая транзакция потребует его активного участия. Вы можете использовать запутанные схемы ZK-SNARK для создания централизованной, безопасной, приватной версии Uniswap, но неясно, перевесят ли преимущества затраты. Возможно, это даже не даст никаких реальных преимуществ: контракты должны информировать пользователей о ценах на активы, а сдвиги цен на каждый блок могут раскрыть активность сделок. Блокчейн может глобализировать государственную информацию, а ZK-SNARK - приватизировать ее, но не существует надежного метода, позволяющего глобализировать и приватизировать государственную информацию одновременно.

Соедините примитивы вместе

В разделах выше мы рассмотрели примеры инструментов, которые мощны сами по себе, но также могут служить строительными блоками для других приложений. Нуллификаторы, жизненно важные для валют, теперь снова появляются в других случаях использования. Техника "принудительного связывания", использованная в разделе о негативной репутации, имеет широкое применение. Он очень эффективен для многих приложений, где "профиль" пользователя меняется со временем сложным образом, и Вы хотите заставить пользователей следовать системным правилам, сохраняя при этом конфиденциальность. Пользователям даже можно поручить представить свое внутреннее "состояние" с помощью полного частного дерева Меркла. Упомянутый инструмент "пул обязательств" может быть создан с помощью ZK-SNARK. Если некоторые приложения не могут полноценно функционировать в сети и требуют централизованного оператора, те же самые методы могут заставить оператора быть честным. ZK-SNARK - это мощный инструмент, сочетающий в себе преимущества подотчетности и конфиденциальности. Хотя у них есть свои ограничения, в некоторых случаях продуманный дизайн приложений позволяет обойти эти ограничения. Я надеюсь, что в ближайшие годы мы увидим больше приложений, использующих ZK-SNARK, и в конечном итоге создадим приложения, объединяющие ZK-SNARK с другими формами шифрования.

Отказ от ответственности：

1. Эта статья перепечатана с сайта[Foresightnews]. Все авторские права принадлежат оригинальному автору[Джейкоб Ко]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Предупреждение об ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.