Привет, Хабр! Представляю вашем вниманию перевод статьи Introduction to zk-SNARKs with examples автора Christian Lundkvist.

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

Доказательства с нулевым разглашением

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

Если перейдем к конкретике, представим что у нас есть программа, обозначаемая C, которая принимает два параметра: C(x, w). Параметр x представляет собой публичное значение, а w является секретным значением свидетельства. Программа возвращает логическое значение, то есть или true или false. Цель получить такое публичное значение x, чтобы можно было убедиться в том, что проверяемый знает секретное значение w, такое, что C(x,w) == true.

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

Пример программы

Предположим, что Боб получил хэш H некоторого значения, и он хочет получить доказательство того, что Алиса знает значение s, хэш которого равен H. Обычно Алиса доказывает это, отдавая s Бобу, после чего Боб вычисляет хэш и проверяет, что он равен H.

Однако предположим, что Алиса не хочет раскрывать ценное значение s Бобу, вместо этого она просто хочет доказать, что знает значение s. Для этого она может использовать zk-SNARKs.

Мы можем описать данный сценарий, используя следующую программу, описанную ниже как функция Javascript:

function C(x, w) {
  return ( sha256(w) == x );
}

Другими словами: программа принимает общедоступный хэш x и секретное значение w и возвращает, true если хэш SHA-256 w равен x.

Описав проблему Алисы с помощью функции C(x,w) мы видим, что Алисе нужно создать доказательство того, что она обладает s таким, что C(H, s) == true, не раскрывая значения s. Это общая проблема, которую решают zk-SNARKs.

Определение zk-SNARKs

Generator (C circuit, λ is ️):
(pk, vk) = G(λ, C)
Prover (x pub inp, w sec inp):
π = P(pk, x, w)
Verifier:
V(vk, x, π) == (∃ w s.t. C(x,w))

Определение дано в твитте :)

Zk-SNARKs состоит из трех алгоритмов G, P, V определенных следующим образом:
Генератор ключей G принимает секретный параметр lambda и программу C, и генерирует два публичных ключа: доказательный ключ pk, и ключ проверки vk. Эти ключи являются общедоступными параметрами, которые необходимо создать только один раз для данной программы C.

Доказывающий алгоритм P принимает в качестве входных значений: ключ pk, публичное значение x и секретное значение w. Алгоритм генерирует доказательство prf = P(pk, x, w) того, что доказывающий знает секретное значение w и что секретное значение удовлетворяет программе C.

Проверяющий алгоритм V вычисляет V(vk, x, prf) результатом которого будет true, если доказательство является верным, и false в противном случае. Таким образом, эта функция возвращает true, если проверяющий знает, что секретное значение w удовлетворяет C(x,w) == true.

Обратите внимание на секретный параметр lambda, используемый в генераторе. Этот параметр иногда затрудняет использование zk-SNARKs в реальных приложениях. Причина этого в том, что любой, кто знает этот параметр, может генерировать поддельные доказательства. В частности, при любой программе C и публичном значении x человек, который знает lambda, но не знает секретного w, может создать доказательство fake_prf, на которое алгоритм V(vk, x, fake_prf) вернет true.

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

Zk-SNARKs для нашей примерной программы

Как бы Алиса и Боб использовали zk-SNARKs на практике, чтобы Алиса доказала, что она знает секретное значение в приведенном выше примере?

Прежде всего, как обсуждалось выше, мы будем использовать программу, определяемую следующей функцией:

function C(x, w) {
  return ( sha256(w) == x );
}

Первым шагом Боб запускает генератор G, чтобы создать доказательный ключ pk, и ключ проверки vk. Это делается путем случайного генерирования lambda и использования этого значения в качестве входных данных:

(pk, vk) = G(C, lambda)

Как обсуждалось выше, параметр lambda должен обрабатываться с максимальной осторожностью, так как если Алиса узнает lambda, она сможет создать поддельные доказательства. Далее Боб делится pk и vk с Алисой.

Теперь Алиса будет играть роль доказывающего. Ей нужно доказать, что она знает секретное значение s, хэшем которого является H. Она запускает доказывающий алгоритм, P используя входы pk, H и s, чтобы сгенерировать доказательство prf:
prf = P(pk, H, s)

Далее Алиса представляет доказательство prf Бобу, он выполняет проверяющую функцию V(vk, H, prf), которая вернется true в этом случае, поскольку Алиса действительно знает секретное значение s. Теперь Боб может быть уверен в том, что Алиса знает секретное значение, при этом Алисе не нужно было раскрывать секрет Бобу.

Многоразовые проверки и доказательные ключи

В нашем примере выше zk-SNARKs нельзя использовать, если Боб хочет доказать Алисе, что он знает секретное значение. Это связано с тем, что Алиса не может быть уверенной в том, что Боб не сохранил lambda параметр, и поэтому Боб может подделывать доказательства.

Если программой пользуется множество людей (например Zcash), доверенная независимая группа, отдельно от Алисы и Боба, может запускать генератор и создавать доказательный ключ pk, и ключ проверки vk таким образом, чтобы никто не узнал о параметре lambda.

Любой, кто доверяет этой группе, может использовать эти ключи для будущих взаимодействий.

zk-SNARKs в Эфириуме

Разработчики уже начали интегрировать zk-SNARKs в Ethereum. Как это выглядит? Блоки алгоритма проверки добавляются в Ethereum в виде предварительно скомпилированных контрактов. Используется следующее: генератор запускается вне блокчейна, чтобы создать доказательный ключ и ключ проверки. Любой доказывающий может затем использовать доказательный ключ, чтобы создать доказательство, также вне сети. Затем общий алгоритм проверки может выполняться внутри умного контракта, используя в качестве входных параметров доказательство, ключ проверки и публичное значение. Результат алгоритма проверки затем может быть использован для запуска других действий на блокчейне.

Пример: конфиденциальные транзакции

Вот простой пример того, как zk-SNARKs могут помочь в приватности в Ethereum. Предположим, что у нас есть простой контракт токена. Обычно контракт токена имел бы в своем составе сопоставление адресов с остатками:

mapping (address => uint256) balances;

Мы собираемся сохранить базовое ядро, но заменим балансы на хэш балансов:

mapping (address => bytes32) balanceHashes;

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

Два zk-SNARKs будут использоваться для отправки токенов с одной учетной записи на другую, одно доказательство будет создано отправителем, и одно будет создано получателем.

Обычно в контракте токена для транзакции, размер которой должен быть value, нам необходимо проверить следующее условие:

balances[fromAddress] >= value

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

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

Ниже приведена программа, которую мы будем использовать для отправителя zk-SNARKs, где, как и прежде, x представляет публичное значение и w представляет собой секретное значение.

function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value &&
    sha256(w.value) == x.hashValue &&
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
  )
}

Программа, используемая получателем, приведена ниже:

function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  )
}

Программы проверяют, что баланс отправляющего больше отправляемого значения, а также проверяют соответствие всех хэшей. Доверенное сообщество людей будет генерировать доказательный ключ и ключ проверки для наших ZK-SNARKs, давайте обозначим их: confTxSenderPk, confTxSenderVk, confTxReceiverPkи confTxReceiverVk.

Использование zk-SNARKs в контракте токена будет выглядеть примерно так:

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];

  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

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

Детали

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

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

Введение в zk-SNARKs с примерами (перевод)