ZK-proofs - доказательство с нулевым разглашением

Оглавление:

1. Что такое доказательство с нулевым разглашением?
2. Как работают доказательства с нулевым разглашением?
3. Сфера применения ZK-proofs
4. Можно ли интегрировать ZK-proofs в блокчейн-платформы?
5. Приватность и конфиденциальность
6. Проверка и аудит
7. Масштабируемость
8. Личность и аутентификация
9. Взаимодействие между сетями
10. Недостатки доказательств с нулевым разглашением
11. Типы ZK-proofs
12. Подкласс ZK-доказательств (PoK)
13. Доказательства диапазона
14. Сигма-протоколы
15. Другие алгоритмы

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

Шафи Голдвассер, Сильвио Микали и Чарльз Ракофф впервые представили эту идею в начале 1980-х годов.

Хорошее доказательство с нулевым разглашением должно соответствовать следующим трем критериям:

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

ZK - proofs позволяют доказывающему убедить верификатора в правдивости утверждения, не раскрывая никакой информации о самом утверждении. Доказывающий и верификатор взаимодействуют в нескольких раундах протокола. В конце верификатор удостоверяется в правдивости утверждения, не узнавая никакой дополнительной информации о секрете.

В качестве иллюстрации того, как работают ZK- proofs давайте воспользуемся «задачей трех цветов», также известной как «задача раскраски графа».

Задача

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

Решение с использованием ZK- proofs

Настройка:

Доказывающий и верификатор договариваются об областях и связях графа (карты).

Заявление:

Доказывающий утверждает, что имеет надежную трехцветную раскраску предоставленного графа.

Раунд 1: Обязательство

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

Раунд 2: Вызов

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

Раунд 3: Ответ

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

Итерация:

Раунды 2 и 3 повторяются много раз с использованием различных локаций, выбранных случайным образом. Эта процедура повторяется столько раз, сколько необходимо для установления высокой степени доверия к правдивости утверждения доказывающего.

Вывод:

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

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

Описанное выше пример того, как можно использовать ZK-proofs, чтобы убедить кого-либо в существовании решения, сохраняя при этом суть решения в секрете. Подобное является мощным инструментом для повышения конфиденциальности и безопасности в различных приложениях.

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

Доказательства с нулевым разглашением могут улучшить конфиденциальность транзакций в цифровых валютах центрального банка (CBDC), облегчая частные транзакции и поддерживая анонимность пользователей. Сочетая конфиденциальность и прозрачность транзакций CBDC, ZK-доказательства обеспечивают возможность аудита без раскрытия особенностей транзакции.

ZK-proofs могут быть интегрированы в блокчейн-платформы, и фактически они были успешно реализованы в различных блокчейн-сетях.

ZK-proofs предоставляют мощную технику для повышения эффективности, безопасности и конфиденциальности в системах блокчейн.

При интеграции в блокчейн-платформы ZK-proofs могут служить нескольким целям:

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

Без раскрытия реальных данных или информации ZK-proofs могут использоваться для проверки точности конкретных вычислений или утверждений. Это гарантирует целостность данных и делает возможными эффективные процедуры аудита.

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

Используя ZK-proofs для безопасной проверки личности и аутентификации при защите конфиденциальности пользователей, приложения на основе блокчейна будут более безопасными.

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

ZK-proofs обеспечивают преимущества конфиденциальности и безопасности, но они могут требовать больших вычислительных ресурсов и быть сложными в реализации.

Разработка и проверка ZK-proofs может потребовать значительных физических и вычислительных ресурсов, особенно для более сложных доказательств. Это может привести к увеличению времени обработки транзакций и увеличению вычислительной работы, что может затруднить масштабирование систем блокчейна.

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

ZK-proofs не подходят для всех сфер, поскольку для их правильной реализации требуется специальная подготовка и опыт. Это может помешать их широкому использованию и внедрению во многих областях.

Хотя ZK-proofs обеспечивают полезные функции конфиденциальности и безопасности, их недостатки требуют тщательного изучения и оценки связанных с ними компромиссов до их внедрения в конкретные системы или приложения.

Интерактивные ZK-proofs

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

Пример «Coke-or-Pepsi» представляет собой интерактивный ZKP между доказывающим и верификатором: две стороны должны обмениваться информацией в раундах, при этом информация передается в обоих направлениях по всему протоколу. За пределами домена с нулевым разглашением на практике обычно используются интерактивные протоколы. Например, для аутентификации пользователя с помощью пароля он может запустить интерактивный протокол:

1. Сервер отправляет одноразовый номер клиенту
2. Клиент отвечает серверу H(имя пользователя || пароль || одноразовый номер) для определенной криптографической хеш-функции H.
3. Сервер проверяет допустимость значения, повторно вычисляя то же значение локально.

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

Не интерактивные ZK-proofs

Многие протоколы с нулевым разглашением можно сделать не интерактивными, то есть не интерактивными доказательствами с нулевым разглашением (NIZK). Это означает, что доказывающему нужно только запустить программу, принимающую (f, x, y) в качестве входных данных, и вывести доказательство pi. Любой верификатор с (f, y, pi) может проверить это и убедиться, что доказывающий действительно знает x, не видя его. Рабочий процесс доказательства NIZK напоминает цифровую подпись: подписывающая сторона подписывает общедоступный документ, используя свой закрытый ключ подписи, и создает подпись. Любой верификатор с документом, подписью и ключом проверки может проверить действительность подписи.

Не интерактивные доказательства с нулевым разглашением нашли множество применений в сфере блокчейна из-за их привлекательной возможности передачи: доказывающий, не зная личности верификатора, может создать одно доказательство, которое можно использовать для убеждения любого, кто его получит. NIZK с очень маленькими доказательствами обычно относятся к категории zk-SNARK.

Не интерактивные ZK- proofs подходят для открытых систем, где может быть много верификаторов, заинтересованных в проверке доказательства. В этом случае доказательство нужно вычислить только один раз и дешево проверить многими верификаторами. Однако у таких преимуществ краткого нулевого разглашения имеют некоторые недостатки.

У кратких NIZK часто высокие накладные расходы со стороны доказывающего. Ресурс, необходимый для доказательства функции, на несколько порядков выше, чем тот, который необходим для оценки функции в чистом виде.

Многие NIZK имеют доказательство постоянного размера; в то время как других полилогарифмический размер доказательства.

Надежность означает, что если доказывающая сторона не обладает знаниями или информацией, на которые, как он утверждает, обладает, протокол не должен убеждать проверяющую в обратном. Полнота означает, что если доказывающий обладает знаниями или информацией, протокол должен убедить проверяющего в этом факте. Эти две характеристики необходимы для обеспечения безопасности и точности протоколов PoK.

Доказательства диапазона считались самыми ранними формами проверки обязательств, применяемыми в конфиденциальных транзакциях. Они предоставили человеку способ доказать, что конкретное обязательство является ценностью в заданном диапазоне, при этом утаивая любую информацию о ценности и ее ценности. Например, используя простое доказательство диапазона, вы можете подтвердить, что покойная королева Елизавета родилась после Первой мировой войны и до Второй мировой войны, не раскрывая ее фактический год рождения.

Доказательства диапазона были в основном приняты криптографическими протоколами, повышающими конфиденциальность, и использовались для сокрытия сумм транзакций в таких сетях, как Monero. Стоит отметить, что Monero внедрила еще более эффективную систему проверки диапазона под названием Bulletproofs+. Например, когда вы переводите монеты в блокчейн Monero, Bulletproofs+ доказывает, что ваш платеж является положительным числом, не раскрывая, сколько вы заплатили.

Протоколы Sigma представляют собой трех этапные протоколы для подтверждения знания значений в некотором отношении без раскрытия самих значений. Например, знание дискретного логарифма, т. е. при заданных g и y, доказать знание x в gˣ = y, не раскрывая x.

Протокол Sigma состоит из трех этапов

Обязательство:

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

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

Ответ:

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

Вышеупомянутый протокол является интерактивным протоколом: т.е. доказывающий, и верификатор должны быть в сети и иметь возможность отправлять сообщения для завершения протокола. Но его можно сделать не интерактивным с помощью опции Fiat-Shamir. По сути, это означает, что верификатор не будет отправлять запрос на шаге 2, а будет имитировать вызов, используя хеш-функцию для хеширования чего-то, специфичного для этого выполнения протокола. Одним из возможных кандидатов на это что-то является обязательство на шаге 1 и данные экземпляра. В этом не интерактивном протоколе доказывающий может создать доказательство, а любой верификатор может его проверить.

BP — это тип доказательства диапазона, в котором используются методы проверки с нулевым разглашением, аналогичные используемым zkSNARK и zkSTARK. Они позволяют доказывающей стороне объединять несколько доказательств диапазона для транзакций с несколькими выходами в одно короткое доказательство. Как и zkSTARK, они не требуют первоначальной доверенной церемонии или процедуры установки. Кроме того, они меньше, чем zkSTARK, и обладают значительной эффективностью и безопасностью. Однако проверка BProofs занимает больше времени, чем доказательство zkSNARK.

BProofs привлек внимание из-за преимущества при подтверждении обязательств в конфиденциальных транзакциях. Bulletproofs были приняты блокчейнами конфиденциальности, такими как Monero, которые были открыты в отношении изменений и добились сокращения размера транзакций и комиссий до 80%.

1. PoW (Proof-of-Work)
2. PBFT (Practical Byzantine Fault Tolerance)
3. PoS (Proof of Stake)
4. DPoS (Delegated Proof of Stake)
5. PoB (Proof of Burn)
6. PoC (Proof of Capacity)
7. PoET (Proof-of-Elapsed Time)
8. PoST (Proof-of-Spacetime)