[Из песочницы] Введение в zk-SNARK с примерами (перевод)
В этой статье мы постараемся дать обзор zk-SNARK с практической точки зрения. Мы будем рассматривать используемую математику как черный ящик, но попытаемся проявить немного интуиции чтобы понять, как можно использовать данную технологию, и покажем простое приложение, основанное на недавней интеграции zk-SNARK в Ethereum.
Доказательств с нулевым разглашением
Цель доказательств с нулевым разглашением заключается в том, чтобы проверяющий мог удостовериться в том, что проверяемый обладает знанием секретного параметра, называемого свидетельством, удовлетворяющим некоторым отношениям, не раскрывая свидетельство проверяющему или кому-либо еще.
Если перейдем к конкретике, представим что у нас есть программа, обозначаемая C, которая принимает два параметра: C(x, w). Параметр x представляет собой публичное значение, а w является секретным значением свидетельства. Программа возвращает логическое значение, то есть или true или false. Цель получить такое публичное значение x, чтобы можно было убедиться в том, что проверяемый знает секретное значение w, такое, что C(x,w) == true.
Мы специально будем обсуждать неинтерактивные доказательства с нулевым разглашением, а это означает, что само доказательство является блоком данных, которое может быть проверено без какого-либо взаимодействия с проверяемым.
Пример программы
Предположим, что Боб получил хэш H некоторого значения, и он хочет получить доказательство того, что Алиса знает значение s, хэш которого равен H. Обычно Алиса доказывает это, отдавая s Бобу, после чего Боб вычисляет хэш и проверяет, что он равен H.
Однако предположим, что Алиса не хочет раскрывать ценное значение s Бобу, вместо этого она просто хочет доказать, что знает значение s. Для этого она может использовать zk-SNARK.
Мы можем описать данный сценарий, используя следующую программу, описанную ниже как функция 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-SNARK.
Определение zk-SNARK
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-SNARK состоит из трех алгоритмов 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-SNARK в реальных приложениях. Причина этого в том, что любой, кто знает этот параметр, может генерировать поддельные доказательства. В частности, при любой программе C и публичном значении x человек, который знает lambda, но не знает секретного w, может создать доказательство fake_prf, на которое алгоритм V(vk, x, fake_prf) вернет true.
Таким образом, запуск генератора должен являться безопасным процессом, защищенным от того, чтобы кто-то могу узнать или украсть параметр lambda. Это стало причиной чрезвычайно сложной церемонии, проведенной командой Zcash для создания доказательного ключа и ключа проверки, при этом все «токсичные отходы» lambda были уничтожены.
Zk-SNARK для нашей примерной программы
Как бы Алиса и Боб использовали zk-SNARK на практике, чтобы Алиса доказала, что она знает секретное значение в приведенном выше примере?
Прежде всего, как обсуждалось выше, мы будем использовать программу, определяемую следующей функцией:
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-SNARK нельзя использовать, если Боб хочет доказать Алисе, что он знает секретное значение. Это связано с тем, что Алиса не может быть уверенной в том, что Боб не сохранил lambda параметр, и поэтому Боб может подделывать доказательства.
Если программой пользуется множество людей (например Zcash), доверенная независимая группа, отдельно от Алисы и Боба, может запускать генератор и создавать доказательный ключ pk, и ключ проверки vk таким образом, чтобы никто не узнал о параметре lambda.
Любой, кто доверяет этой группе, может использовать эти ключи для будущих взаимодействий.
zk-SNARKs в Эфириуме
Разработчики уже начали интегрировать zk-SNARK в Ethereum. Как это выглядит? Блоки алгоритма проверки добавляются в Ethereum в виде предварительно скомпилированных контрактов. Используется следующее: генератор запускается вне блокчейна, чтобы создать доказательный ключ и ключ проверки. Любой доказывающий может затем использовать доказательный ключ, чтобы создать доказательство, также вне сети. Затем общий алгоритм проверки может выполняться внутри умного контракта, используя в качестве входных параметров доказательство, ключ проверки и публичное значение. Результат алгоритма проверки затем может быть использован для запуска других действий на блокчейне.
Пример: конфиденциальные транзакции
Вот простой пример того, как zk-SNARK могут помочь в приватности в Ethereum. Предположим, что у нас есть простой контракт токена. Обычно контракт токена имел бы в своем составе сопоставление адресов с остатками:
mapping (address => uint256) balances;
Мы собираемся сохранить базовое ядро, но заменим балансы на хэш балансов:
mapping (address => bytes32) balanceHashes;
Мы не собираемся скрывать отправителя или получателя транзакций, но мы сможем скрыть остатки и отправленные суммы. Иногда это называют конфиденциальными транзакциями.
Два zk-SNARK будут использоваться для отправки токенов с одной учетной записи на другую, одно доказательство будет создано отправителем, и одно будет создано получателем.
Обычно в контракте токена для транзакции, размер которой должен быть value, нам необходимо проверить следующее условие:
balances[fromAddress] >= value
Таким образом, нам нужно удостовериться в том, что наши zk-SNARK докажут, что условие выполняется, а также то, что обновленные хэши соответствуют обновленным балансам.
Основная идея заключается в том, что отправитель будет использовать свой начальный баланс и стоимость транзакции в качестве секретных значений, а хэши начального, конечного балансов и стоимости транзакции в качестве публичных значений. Точно так же получатель будет использовать начальный баланс и стоимость транзакции в качестве секретных значений, а хэши начального, конечного балансов и стоимости транзакции в качестве публичных значений.
Ниже приведена программа, которую мы будем использовать для отправителя zk-SNARK, где, как и прежде, 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-SNARK в контракте токена будет выглядеть примерно так:
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 байта данных и кодировать энтропию в части баланса, чтобы предотвратить возможность подбора хэшей для вычисления значений балансов.
- Необходимо решить что делать в случае отправки на неиспользуемый адрес.
- Для отправки отправителю необходимо взаимодействовать с получателем. Можно было бы создать систему, в которой отправитель использует свое доказательство для инициирования транзакции, а получатель может увидеть в блокчейне, что у него есть «ожидающая входящая транзакция», и завершить ее.
Автор: Christian Lundkvist
→ Источник
