Привет, Хабр! Меня зовут Сергей Прилуцкий, я руковожу отделом исследований компании MixBytes. Мы занимаемся аудитами безопасности смарт-контрактов и исследованиями в области блокчейн-технологий. В числе прочего занимаемся и направлением zero-knowledge. Эта статья подготовлена по мотивам моего доклада на Highload про zkSNARKs. Это одна из самых горячих тем в современной криптографии. Они используются для обеспечения приватности и масштабируемости в децентрализованных системах. Поговорим, как масштабировать криптографические системы, какие проблемы существуют у снарк-алгоритмов и зачем они нужны.

Что такое zkSNARKs и как это работает

zkSNARKs — это общее название большого семейства алгоритмов и математических концепций для построения так называемых proof-систем. zkSNARKs и их модификациями занимаются ведущие криптографы топовых университетов мира. Курсы по proof-системам можно найти в Стэнфорде, MIT, Беркли. Появляются такие программы и в российских университетах. Эта технология переживает бум развития. На её базе уже запущены десятки реальных проектов, отвечающих за реальные средства пользователей, и разрабатываются сотни новых проектов. Всё потому, что за последние пару лет появилось много значимых работ, которые позволили применять эту технологию на существующем железе. Раньше для её работы требовались слишком большие объёмы вычислений. Сейчас алгоритмы zkSNARKs уже имплементированы во многих готовых движках и библиотеках. Их можно использовать в продакшене. Конечно, если вы не боитесь использовать новейшую криптографию, которая отличается от общепринятой.

Итак, zkSNARKs:

  • доказывают корректное исполнение некоторого вычисления;

  • позволяют проводить вычисления на секретных данных;

  • позволяют масштабировать вычисления;

  • позволяют строить trustless сервисы.

Если объяснять на пальцах, то SNARK позволяет доказать, что вы взяли некоторые inputs, исполнили какой-то конкретный код и получили output. К полученному output прикрепляется proof — доказательство корректного исполнения кода, который может быть проверен за очень короткое время. Существенно меньшее, чем заняло само вычисление. Исторически корни этих алгоритмов уходят к задачам для суперкомпьютеров. Это когда небольшой компьютер, который поставил задачу большому суперкомпьютеру на вычисление, должен был убедиться, что вычисление выполнено верно, но при этом не производить вычисление самостоятельно. Где-то в 90-х годах и появились первые примеры этих алгоритмов. Но тогда они были очень тяжеловесными, и только в наши годы их удалось применить для решения повседневных задач. Да ещё и добавить к ним свойство zero-knowledge, чтобы доказывать вычисления над секретными input-ами.

Сегодня zkSNARKs в основном используются для двух больших задач:

Масштабируемость: proofs, произведённые такими алгоритмами, позволяют доказать процессинг большого числа данных при помощи короткого доказательства. Это позволяет строить двухуровневые схемы, где сервера более низкого уровня проводят вычисления, процессят тысячи транзакций, а потом отдают готовые результаты серверам на уровень выше с коротким доказательством. В результате серверы делают минимальное число проверок и не требуют дублирования процессинга.

Zero-knowledge: эти же алгоритмы позволяют доказать, что output корректно получен из некоторого секретного input-а. Таким образом, убедить проверяющего, что доказывающий владеет корректными данными, которые никуда не отправляются: ни в открытом, ни в зашифрованном виде.

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

Основная схема работы zkSNARKs

Пускай, у нас есть некоторый фиксированный публичный алгоритм вычисления output из input, некоторая функция output=func(input). Например, input — это число, а output — это его факториал. Или input — это некоторая строка, а output — её криптографический хэш. И две роли — доказывающий и проверяющий (prover и verifier).

Setup: изначально и prover, и verifier, и вообще кто угодно проводят процедуру setup, связанную с кодом, который мы хотим использовать. Setup генерирует специальный набор чисел, который будет использоваться prover-ами, чтобы доказывать исполнение этого кода (proving_key) verifier-ами и проверять доказательства исполнения (verifying_key) 

Prover берёт свой секретный input и вычисляет output. Вычисление выполняется с использованием proving_key. Таким образом, помимо самого результата (output) алгоритм генерирует доказательство (proof) корректности вычисления. Это относительно короткий набор чисел, который «связан» с полученным output. Затем prover отправляет output + proof проверяющему (verifier).

Verifier получает (output + proof) и с помощью verifying_key проверяет полученный proof. Если результат — true, то он верит, что Prover получил данный output, строго следуя алгоритму, который был использован на стадии Setup. Заметим, что input при этом может не раскрываться.

Чтобы криптографически доказывать исполнение некоторой программы, она должна быть преобразована в специальный вид, так называемый арифметический контур (arithmetic circuit). Он представляет собой нечто похожее на логическую плату с большим количеством арифметических gates. Также как наши программы при исполнении процессором превращаются в огромное число очень простых низкоуровневых инструкций. Точно также при превращении кода в arithmetic circuit, его логика превращается в набор простейших gates, каждый из которых выполняет самые примитивные операции (умножение и сложение). Процесс превращения программы в такой контур называется арифметизацией. Именно поэтому на картинке я нарисовал arithmetic circuit как печатную плату. 

Общая схема работы proof-системы на базе zkSNARKs

Вот общая схема работы proof-системы на базе zkSNARKs:

(1): мы написали функцию, которая вычисляет output. Чтобы всё работало, функция должна быть детерминистической, то есть не выполнять никаких внешних взаимодействий и быть достаточно компактной, чтобы её можно было арифметизировать.

(2): эта функция переводится в arithmetic circuit. Как и у печатной платы, внутри circuit есть гейты и сигналы, которые бегут между гейтами. Выходы одних гейтов заводятся на входы других. Проводя аналогию, доказательство корректности исполнения нашей функции есть доказательство, что сигналы, которые были у Prover-а «соответствуют спецификации платы».

(3): Та самая «спецификация платы», ограничения на сигналы, их число, типы гейтов — всё это упаковывается в два набора чисел. Один нужен для доказывания этого вычисления (proving_key), другой — для верификации (verifying_key). После того, как наш Setup завершён, с помощью proving_key кто угодно может провести вычисление, получить output и сгенерировать proof. Который может быть также проверен кем угодно, у кого есть соответствующий verifying_key.

(4) и (5): Prover берёт proving_key, проводит вычисление, получает output и генерирует proof.

(6): Prover отправляет output и proof verifier-у. Свой секретный input он оставляет у себя.

(7) и (8): Verifier проверяет output + proof с помощью verifying_key, если все «ОК» верит, что output получен корректно.

Основные свойства zkSNARKs

Пришло время расшифровать аббревиатуру zkSNARKS. Ведь в ней скрыты самые важные свойства алгоритмов. Итак, zkSNARK это zero-knowledge Succinct Non-Interactive ARguments of Knowledge. Начнём читать с конца:

Arguments Of Knowledge

Это означает, что SNARK-и предоставляют проверяющему «аргументы знания» или «доказательство знания». Читать вышеописанную схему со стороны prover-а следует так: «я знаю такой input, который порождает вот это output на этом circuit-е, вот proof». Отсюда и название.

Non-interactive

Первое важное свойство SNARKS  — неинтерактивность. Интерактивным протоколам необходимо как минимум три взаимодействия: prover инициирует процедуру, verifier шлёт ему некоторый challenge, prover отвечает доказательством. В SNARK-ах (output+proof) отправляются вместе без предварительного взаимодействия с verifier-ом.

Это свойство особенно важно для блокчейнов. Когда транзакция отправляется в блокчейн, неизвестно, какой участник сети будет её процессить, и никакой интерактивности здесь быть не может. Всё должно отработать за один раз. Это также делает использование SNARKs крайне удобным для задач масштабируемости. Данные отправляются сразу пакетом вместе с proof-ами и, если всё хорошо, просто принимаются получающей стороной. Хороший пример  необходимости неинтерактивности — фотография, подписанная автором с помощью электронной цифровой подписи (ЭЦП), которая была впоследствии обработана. SNARK позволяет добавить в метаданные фотографии доказательство, что именно исходная фотография обработана алгоритмом, а ЭЦП по-прежнему верна.

Succinct

Succinctness (или «компактность») доказательств SNARK — важнейшее свойство этих систем. Оно означает, что сложность проверки доказательства алгоритмически проще, чем выполнение самого вычисления. Грубо говоря, если процесс вычисления и генерации proof-а проводится за O(N), то верификация должна занимать O(logN) или даже O(1). Если бы это было не так, то verifier мог бы сам выполнить вычисление, и проверка не понадобилась бы. Различные вариации proof-систем отличаются как раз двумя параметрами — сложностью доказывания и сложностью верификации с точки зрения сложности вычислений и размера proof-ов. Лучшие с точки зрения верификации системы позволяют провести проверку за O(1). Так вы можете доказать вычисление произвольной длины за константное время.

На поясняющей картинке в качестве input мы принимаем два числа: a и b. Перемножаем их, возводим в некоторую степень, генерируем proof и проверяем его, замеряя время и размеры данных. В первом случае мы возводим в небольшую степень (32) и видим что output генерируется быстро, а объем промежуточных данных (witness) — небольшой (красные галки). Во втором случае уже возводим в степень 200000 и видим, что время генерации proof-а сильно выросло (до 7 секунд, как и объём промежуточных данных до 13 Мб).

В зелёных кружочках размер verifying_key и время проверки proof-а. Размер ключа для верификации не изменился, а время проверки изменилось незначительно. Причем это время останется примерно таким же, какого бы размера вычисление вы не проводили. Даже если здесь будет миллиардная степень и гигабайтные proving_key и размеры witness. Это может показаться магией, но вы же не удивляетесь, что многогигабайтный файл имеет криптографический хеш размером в смешные 256bit, который используется нами для проверки целостности? Кроме того, внимательный читатель заметил, насколько тяжелым является процесс доказательства, и это одна из причин, почему мы не видим SNARK-и в каждом утюге.

Тем не менее, даже при таком тяжёлом процессе доказательства, возможность доказать огромное вычисление за O(1) является потрясающей возможностью сворачивать вычисления и исполнять их на полностью недоверенных узлах. Другие proof-системы умеют доказывать гораздо легче, усложняя процесс верификации. Этот tradeoff один из камней преткновения zk-разработчиков, вокруг которого ведутся активные исследования.

Zero knowledge

Пришло время раскрыть причину, по которой я пишу то «SNARK», то «zkSNARK». Так как мы доказываем «знание некоторых inputs», приводящих к данному output, и можем либо раскрывать эти inputs, либо не раскрывать. Это уже как нам нравится. Если по inputs вычисляемой функции нельзя узнать output (например, хеширование), и inputs не раскрываются, то мы получаем zero-knowledge систему. Именно поэтому “zk” пишут маленькими буквами, ведь мы получаем её «бонусом» к нашей proof-системе.

Поэтому zkSNARKs могут использоваться в двух ипостасях: 

Сокрытие секретных inputs и доказательство, что output получен из «некоторых» секретных данных, но удовлетворяющих нашим требованиям. Такие системы могут применяться для предъявления цифровых документов, анонимизации транзакций и прочего. Например, они доказывают, что пользователь владеет некоторым идентификатором из списка.

Масштабирование, когда input-ы не являются секретными, но свойство компактности позволяет при помощи короткого proof-а доказать их корректный процессинг на полностью trustless машинах.

Что можно строить на zkSNARKs

Proof-системы на базе zkSNARKs раскрывают себя при «очень маленьком сервере» и «очень толстом и производительном клиенте». То есть в тех случаях, когда мы хотим отдать большое вычисление на клиента (не доверяя ему), а на стороне сервера принимать готовые значения и быстренько верифицировать их. Как будто мы раздали нашим клиентам готовые устройства, производящие нужное нам вычисление, и можем быстро и компактно получать от них результаты и использовать их.

Именно поэтому технология в первую очередь важна для блокчейнов, в которых на стороне блокчейна очень минималистичные и экономные смарт-контракты. Каждый байт оплачивается, и нет никаких интерактивных схем. А оперировать результатами довольно сложных вычислений — хочется.

Hashing

Давайте начнём с функции хеширования, то есть доказательства, что мы знаем прообраз представленного как output хеша. Итак, для начала я могу взять секретное число secret, вычислить от него hash (secret) и представить этот хеш вместе с proof-ом, что я действительно знаю secret. Но зачем?

Давайте вспомним такую структуру данных, как Merkle tree. Она часто используется: под капотом, в движках и базах данных. Это такое дерево, как бинарное, но каждый узел в нём – хеш от хешей его сыновей. Удобно, что имея на сервере лишь одно число, — root этого дерева, и зная всё дерево, я могу сгенерировать доказательство, что конкретный хеш принадлежит этому дереву. Как? Публикуя путь по этому дереву до root. На стороне сервера нужно будет просто пробежать по logN хешей. И если путь привел к root, значит, доказательство верное. Ну а «пробежать» означает просто итеративное хеширование очередного элемента.

Давайте сделаем так:

  • сначала я придумал secret и посчитал hash(secret);

  • затем я публично(!) добавил свой hash(secret) в Merkle дерево  и теперь все знают его root;

  • теперь я хочу доказать, что я — в этом дереве, но не хочу раскрывать какой из листьев мой;

  • я беру свой secret и hash(secret);

  • строю Merkle proof того, что hash(secret) принадлежит дереву;

  • строю zkSNARK proof того, что:

    • я знаю некоторый secret

      • который является прообразом для некоторого hash

        • который является прообразом для следующего hash

          • который является прообразом для следующего hash

            • …

              • который привел нас к Merkle root

То есть я доказываю, что знаю какой-то secret, из которого можно построить путь по Merkle tree до root. Таким образом, я доказал, что мне «принадлежит» один из листьев дерева, но не раскрыл, какой именно.

На базе подобной схемы работают так называемые «set-membership proofs» или «доказательство нахождения в списке». На их базе можно строить анонимные голосования, предъявление и проверку цифровых документов, ну и, конечно же, миксеры. Знаменитый Tornado Cash работает именно так, как описано. Сначала криптовалюта вносится на адрес контракта, и пользователь добавляется в Merkle tree. Затем пользователь предоставляет zero-knowledge proof того, что он в этом дереве присутствует, но не раскрывает, какой из предыдущих commitment-ов принадлежит ему. А криптовалюта выводится на адрес, который нельзя связать с исходным. Эта схема очень популярна, и сейчас множество проектов на ее базе. Её используют для предъявления различных цифровых ID без лишних сливов персональных данных.

Signature check

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

Теперь пусть наша функция проверяет цифровые подписи массива транзакций. Получив пачку транзакций, сервер (например, блокчейн-нода) должна будет сохранить у себя каждую транзакцию, их публичные ключи и каждую подпись, чтобы данные были publicly verifiable. Вместо этого нижестоящий сервер может собрать все подписи, проверить каждую и сгенерировать proof, что все 100% подписей верны.

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

State processing

Давайте ещё усложним задачу. Теперь наша функция — это некоторая виртуальная машина, исполняющая код и имеющая внутреннее состояние (state). На вход мы подаем input-ы, указывающие, какой код следует исполнить, и исходное состояние, а выходом является новое состояние. Изначально в state были некоторые значения, которые, согласно input-ам и исполняемому коду, изменились, и машина перешла в новое состояние. Исполнение такого кода тоже можно доказывать с помощью SNARKs.

Примером виртуальной машины, которую хочется поместить в SNARK-и, является EVM (Ethereum Virtual Machine). В теории это позволит исполнять сложную логику чуть ли не на самих клиентах, отдавая в блокчейн только результаты и proof корректности исполнения. Такие проекты уже работают в продакшене и позволяют блокчейнам эффективно масштабироваться.

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

С помощью SNARK-ов я могу доказать, что исполнение хранимой процедуры, которая списала 20$ с баланса Васи и перевела их Пете, приведёт к определённому изменению state_root всей базы. Поэтому я могу отправить вышестоящему серверу список ячеек, которые тому надо изменить. Дополнить это я должен доказательством, что я нигде не обманул и все изменения были проведены консистентно, а логика перевода не была нарушена. Разумеется, это требует особого построения самой БД и возможности доказывать включение/исключение значений. Обычно это делается с помощью модификаций Merkle tree, а также более продвинутых методов, таких как vector commitments. Но в любом случае это вполне решаемая задача.

Ложки дёгтя

Было бы нечестно обрисовать такие вкусные перспективы и не упомянуть о проблемах. А они в этой области есть, и весьма серьёзные. Сам матаппарат доказательств существует давно. Но, как когда-то с асимметричной криптографией, реальное применение алгоритмов требовало огромных вычислительных затрат. В результате многие статьи лежали «под сукном», ожидая, когда компьютеры дозреют до возможностей имплементации. Ещё реальное применение тормозилось тем, что в Web2 эти возможности не сильно нужны. Мы просто доверяли сервисам. В Web3 так уже нельзя. Именно в блокчейнах и децентрализованных сетях потребность в полностью trustless вычислениях и неинтерактивности особенно важна. Здесь готовы примириться с проблемами, потому что уже на практике доказано, что такие алгоритмы в десятки раз снижают стоимость транзакций для пользователей и защищают их средства.

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

Не существует оптимизированного под данные операции железа. Используемые алгоритмы являются строго целочисленными, что ограничивает эффективное применение FPU. Также разработчикам proof-систем надо постоянно иметь дело с ключевым tradeoff-ом этих систем — соотношением сложности доказывания и верификации. Некоторые proof-системы имеют идеальный verifier (O(1)) но при этом очень тяжелый prover (O(NLogN)). Другие имеют эффективный и быстрый prover (O(N)), но при этом verifier зависит от сложности доказываемого кода (O(logN)).

Отдельно стоит вопрос о квантовой устойчивости этих алгоритмов. Часть из них построена на эллиптических кривых, которые не являются quantum-safe. Часть работает на хешировании, деревьях Меркла, кодах коррекции ошибок. Поэтому они лишены проблем с quantum-safe, но имеют более сложные verifier-ы. В результате ведётся постоянная борьба за ускорение prover-ов/verifier-ов как с точки зрения скорости работы, так и с точки зрения размера доказательств.

Также стоит упомянуть, что многие традиционные алгоритмы при арифметизации, то есть превращении в арифметический circuit, оказываются неэффективными. Всё, что мы привыкли использовать в обычных программах, оказывается крайне тяжелым в ZK. А всё потому, что здесь другая арифметика, а работа ведется в конечных полях. В этом случае даже сравнение двух чисел является нетривиальной задачей и потребляет много ресурсов. Часть паттернов, таких как динамическая генерация кода, практически недоступны. Бинарные операции также являются очень ресурсоёмкими. Поэтому в этой области много так называемых SNARK-friendly алгоритмов, свои алгоритмы хеширования, эллиптические кривые и подписи. Этим обусловлен огромный рост новых работ в этой области и постоянное активное развитие proof-систем.

Ещё одна важная проблема работы proof-систем — фаза Setup, довольно сложная и ресурсоёмкая. Есть proof-системы, требующие так называемый trusted setup, где сторона, проводящая setup, должна гарантированно «забыть» случайные значения, используемые при генерации proving_key и verifying_key. Это вызывает вопросы к доверию. Другие системы имеют transparent setup, не требующий такого доверия, но у них другие свойства при доказывании и верификации. Setup влияет на удобство использования proof-системы, так как при каждом обновлении заново проводить Setup процедуру неудобно. Поэтому этой проблеме также уделяют много внимания.

Что под капотом у SNARK-ов?

Совершенно нереально рассказать даже базовый аппарат под капотом SNARK-ов за одну статью. Да и вариантов реализации очень много. Если очень грубо, то под капотом большинство proof-систем построено на целочисленных полиномах очень высоких степеней и полиномиальных коммитментах (poylnomial commitments).

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

Затем схема с полиномами и polynomial commitments расширяется до доказательств того, что полином обращается в ноль, является пермутацией другого полинома и так далее. Затем всё это обобщается на множество полиномов и примерно так появляется полноценная proof-система. Эту систему очень грубо можно описать как «я знаю решение этой большой системы уравнений, но само решение не покажу». В этом случае «решение» — это корректная комбинация сигналов внутри arithmetic circuit. 

Ко всему этому добру добавляются дополнительные улучшения. Например, рекурсивные SNARK-и. Если у меня есть один SNARK, у которого быстрый prover, но медленный verifier, и второй SNARK с медленным prover и быстрым verifier, то я могу их соединить так, чтобы второй SNARK доказывал «проверку proof-a первого SNARK-a». Существуют также инкрементальные схемы, когда одно и то же вычисление может доказываться последовательно, когда следующий proof эффективно строится на основе предыдущего.

Если вам стало очень интересно, то, пожалуй, самый хороший курс по теме устройства proof-систем из тех, что я видел до недавнего времени: Zero Knowledge Proofs MOOC. Без него и близких к нему знаний разбираться в тонкостях proof-систем — нереально.

Заключение

Тема proof-систем и компактных доказательств очень обширная и развивается семимильными шагами. Сотни проектов пытаются что-то строить на этой технологии. Появилось уже множество фреймворков (Circom, zoKrates, ZKLLVM, RiscZero, ..), языков (Cairo, Noir, Leo,...), готовых библиотек (Libsnark,  Bellman, jellyfish, ..). И это лишь небольшая доля всего, что сейчас происходит в этой области. Уже реально работают и отвечают за пользовательские средства десятки проектов, от анонимизации платежей (Tornado Cash, zCash, Aztec, …) до блокчейнов L1 и L2 уровней (zkSync, Starknet, Mina, Aleo, …).

Каждая proof-система — это комбинация множества алгоритмов, арфиметизация программ, схема коммитментов, наличие рекурсивынх схем, тип Setup, и множество других аспектов. В этом большая сложность входа в технологию. Потому что в интернете вы найдете либо совсем общие статьи, вроде «что такое zero-knowledge proof», либо специализированные статьи с серьёзной математикой, требующие хорошей подготовки. Вам понадобится абстрактная алгебра, теория групп, дискретная математика, линейка, комбинаторика и куски других разделов математики, чтобы полностью въехать в то что происходит. Но оно того стоит! Ровно сейчас я наблюдаю, как академические криптографы, которые ещё 10 лет назад просто писали бы статьи в стол, активно участвуют в разработке реальных протоколов, пишут на Rust, С++ и Go, и работают там, где раньше никак не могли бы применить свои знания. Так что не прогуливайте математику, если вы учитесь :)

Я уверен, что в течение ближайших десятков лет архитектура работы с безопасностью данных благодаря proof-системам изменится до неузнаваемости. Позволит проектам процессить персональные данные без обладания ими, отдавать вычисления trustless компьютерам, применять совершенно новые схемы масштабирования сервисов. Удачи всем нам с этим :)