zk-SNARKs

zk-SNARKs (от англ. Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) — это криптографический протокол, позволяющий одной стороне (доказывающему) убедить другую сторону (проверяющего) в истинности некоторого утверждения, не раскрывая при этом никакой дополнительной информации, кроме самого факта истинности. Ключевые свойства zk-SNARKs: доказательство является кратким (succinct) — его размер и время проверки значительно меньше, чем объём вычислений, необходимых для проверки утверждения напрямую; неинтерактивным (non-interactive) — для передачи доказательства достаточно одного сообщения от доказывающего к проверяющему; и с нулевым разглашением (zero-knowledge) — проверяющий не узнаёт никаких деталей, кроме самого факта, что утверждение верно. Протоколы zk-SNARKs находят широкое применение в системах на основе блокчейна, в частности, в криптовалюте Zcash, а также в верификации вычислений и обеспечении конфиденциальности данных.

История

Концепция доказательств с нулевым разглашением была впервые предложена в 1985 году Шафи Гольдвассером, Сильвио Микали и Чарльзом Ракоффом. Однако ранние протоколы требовали множества раундов взаимодействия между доказывающим и проверяющим, что делало их неэффективными для практического применения.

Развитие неинтерактивных доказательств с нулевым разглашением началось в конце 1990-х — начале 2000-х годов. В 2010 году были предложены первые практические схемы zk-SNARKs, в частности, в работе «Pinocchio: Nearly Practical Verifiable Computation» (2013) Брайана Парно, Джона Хауэлла, Шармилы Гангули и Карла Гантера. Эта схема позволила верифицировать произвольные вычисления, представленные в виде арифметических схем, за время, пропорциональное размеру входных данных, а не сложности самих вычислений.

Значительный прорыв произошёл в 2014 году, когда компания Zerocoin Electric Coin Company (ныне Electric Coin Company) реализовала протокол zk-SNARKs в криптовалюте Zcash, что позволило скрывать отправителя, получателя и сумму транзакции, сохраняя при этом возможность проверки корректности транзакции. В 2017 году была предложена улучшенная схема Groth16, которая стала стандартом для многих приложений благодаря своей эффективности и простоте.

Принцип работы

Протокол zk-SNARKs основан на преобразовании проверяемого утверждения в арифметическую схему — математическое представление вычислений в виде набора уравнений над конечным полем. Затем эта схема преобразуется в систему полиномиальных ограничений, называемую QAP (Quadratic Arithmetic Program) или R1CS (Rank-1 Constraint System). Доказывающий, зная секретные входные данные (свидетеля), вычисляет набор полиномов, которые удовлетворяют этим ограничениям, и формирует краткое доказательство. Проверяющий, используя открытый ключ (common reference string, CRS), может проверить доказательство, выполнив несколько простых операций с полиномами.

Ключевым элементом является фаза доверенной настройки (trusted setup), в ходе которой генерируются секретные параметры (так называемые «токсичные отходы»), которые должны быть уничтожены после создания CRS. Если эти параметры будут скомпрометированы, злоумышленник сможет подделывать доказательства. Существуют протоколы, такие как BCTV и Sonic, которые позволяют проводить настройку без доверия к одной стороне (например, с помощью мультипартийных вычислений).

Классификация

Существует несколько разновидностей zk-SNARKs, различающихся по способу настройки, эффективности и требованиям к доверию:

• Схемы с доверенной настройкой (trusted setup) — например, Groth16, Pinocchio. Требуют одноразовой генерации CRS, которая может быть проведена с участием нескольких сторон. После генерации CRS может использоваться для неограниченного числа доказательств.
• Схемы с прозрачной настройкой (transparent setup) — например, STARKs (Scalable Transparent ARguments of Knowledge), PLONK (Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge). Не требуют доверенной настройки; CRS генерируется случайным образом и не содержит секретных параметров. STARKs, в отличие от zk-SNARKs, не используют эллиптические кривые и устойчивы к квантовым атакам, но имеют больший размер доказательств.
• Схемы с обновляемой настройкой (updatable setup) — например, PLONK, Marlin. Позволяют добавлять новых участников в процесс настройки без необходимости перезапуска всей процедуры.

Применение

Криптовалюты и блокчейн

Наиболее известное применение zk-SNARKs — криптовалюта Zcash, где протокол используется для создания полностью конфиденциальных транзакций. Другие проекты, такие как Ethereum, внедряют zk-SNARKs для масштабирования (например, в решениях второго уровня, таких как zk-Rollups) и для обеспечения конфиденциальности смарт-контрактов.

Верификация вычислений

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

Аутентификация и идентификация

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

Конфиденциальность данных

В системах, где требуется доказать соответствие некоторым критериям (например, возраст, наличие диплома, кредитная история) без раскрытия самих данных, zk-SNARKs позволяют построить доказательства, которые проверяются без доступа к исходным данным.

Критика и ограничения

Основные недостатки zk-SNARKs включают:

• Зависимость от доверенной настройки. Для схем с доверенной настройкой требуется, чтобы участники фазы настройки не сговорились и уничтожили секретные параметры. Компрометация этих параметров делает возможной подделку доказательств.
• Вычислительная сложность генерации доказательства. Генерация доказательства для сложных вычислений может требовать значительных вычислительных ресурсов и времени, что ограничивает применение на мобильных устройствах.
• Размер доказательства. Хотя доказательства zk-SNARKs являются краткими (обычно несколько сотен байт), для некоторых приложений (например, STARKs) размер может быть больше.
• Необходимость в арифметизации. Любое утверждение должно быть представлено в виде арифметической схемы, что может быть сложно для некоторых типов вычислений.

Интересные факты

• Термин «zk-SNARK» был введён в 2012 году в работе Эли Бен-Сассона, Алессандро Кьеза, Эрана Тромера и Мадхара Венкатасвами.
• В 2018 году исследователи из Массачусетского технологического института (MIT) представили протокол zk-STARK, который не требует доверенной настройки и устойчив к квантовым атакам.
• В 2021 году в Ethereum был реализован протокол EIP-1559, который не использует zk-SNARKs, но в сети активно развиваются решения второго уровня на основе zk-Rollups, такие как zkSync и StarkNet.
• В России исследования в области доказательств с нулевым разглашением ведутся в ряде научных центров, включая Математический институт им. В. А. Стеклова РАН и Московский государственный университет.

Источники

• Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014). Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture.
• Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013). Pinocchio: Nearly Practical Verifiable Computation.
• Groth, J. (2016). On the Size of Pairing-Based Non-interactive Arguments.
• Zcash Protocol Specification. (2016). Electric Coin Company.
• Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post-quantum secure computational integrity.