Привет! Представляю вашем вниманию перевод статьи 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 байта данных и кодировать энтропию в части баланса, чтобы предотвратить возможность подбора хэшей для вычисления значений балансов.
- Необходимо решить что делать в случае отправки на неиспользуемый адрес.
- Для отправки отправителю необходимо взаимодействовать с получателем. Можно было бы создать систему, в которой отправитель использует свое доказательство для инициирования транзакции, а получатель может увидеть в блокчейне, что у него есть «ожидающая входящая транзакция», и завершить ее.
Автор: AgentRX