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

Привет, Хабр! Представляю вашем вниманию перевод статьи 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:

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

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

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

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 на практике, чтобы Алиса доказала, что она знает секретное значение в приведенном выше примере?

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

Первым шагом Боб запускает генератор G, чтобы создать доказательный ключ pk , и ключ проверки vk . Это делается путем случайного генерирования 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 в Ethereum. Как это выглядит? Блоки алгоритма проверки добавляются в Ethereum в виде предварительно скомпилированных контрактов. Используется следующее: генератор запускается вне блокчейна, чтобы создать доказательный ключ и ключ проверки. Любой доказывающий может затем использовать доказательный ключ, чтобы создать доказательство, также вне сети. Затем общий алгоритм проверки может выполняться внутри умного контракта, используя в качестве входных параметров доказательство, ключ проверки и публичное значение. Результат алгоритма проверки затем может быть использован для запуска других действий на блокчейне.

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

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

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

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

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

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

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

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

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

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

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

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

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