Zero-knowledge.

За гранью анонимности в мире криптографии.

Оглавление

1. Введение
2. Эволюция доказательств
3. Появление Zero-knowledge proof
4. Примеры практического применения
5. Ускорение в бесконечность: технологические этапы
6. Вывод

Введение

Пару месяцев назад ребята из Спекуляции (закрытое сообщество romstedi) скидывали видео, в котором несложным языком объяснить, что такое zero-knowledge. Такая попытка объяснить таким образом, чтобы даже школьнику стало понятно, что это за технология и почему она важна для как для индустрии криптовалют, так и для всего мира в целом.

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

Ну это такая технология, которая используется для построения layer2 Rollup'ов, на ней построены Starknet, zkSync и Scroll, вроде. А ещё её упоминал Виталик и она станет финансовым нарративом на рынке криптовалют в будущем, так блогеры говорят.

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

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

Без дальнейших предисловий, вперёд к познанию!

Эволюция Доказательств: От Математики до Криптографии

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

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

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

Утверждение: В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов двух других сторон (катетов).

Доказательство:

Криптографические доказательства, напротив, используются в контексте информационной безопасности и конфиденциальности для демонстрации выполнения определенных условий или свойств, не раскрывая при этом конфиденциальных данных. В этом случае, основная цель - доказать утверждение, не раскрывая секретов. Важным отличием криптографических доказательств здесь выступает их вероятностная природа. То есть, криптографические доказательства истинны только с какой-то вероятностью(даже если речь идёт о вероятности 99,9999%), а математические доказательства строго либо истинны, либо ложны.

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

То есть, доказательством в этом случае можно считать знание(или расчёт) ключа.
Предлагаю рассмотреть на классическом примере - шифре Цезаря.

Один человек отправил сообщение другому человеку, которое зашифровано шифром Цезаря по русскому алфавиту, второму человеку необходимо это сообщение прочитать.

Шифр Цезаря - это форма шифра подстановки, где каждый символ в исходном тексте заменяется символом из алфавита, находящимся на постоянном расстоянии слева или справа от него.

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

Подсказка: сдвиг больше 5 символов, но меньше 10.

Существует огромное количество методов и способов шифрования, но цель всегда и везде одна - обезопасить информацию от злоумышленника, при этом сохранив доступ для конкретного адресату. У Alek OS есть несколько великолепных видео (первое, второе) про историю криптографии как науки, но там он не касается нашей темы. Крайне рекомендую его посмотреть, но уже после прочтения статьи :)

Появление Zero-Knowledge Proof

Zero-Knowledge Proof (ZKP) - это интерактивный вероятностный протокол, который позволяет подтвердить правильность утверждения, при этом Доказывающий обладает знанием этого утверждения, но не раскрывает никакой информации Проверяющему о самом содержании доказательства. Этот криптографический протокол должен соответствовать трем ключевым характеристикам:

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

Эта концепция впервые была представлена в исследованиях в 1989 году Шафи Гольдвассером, Сильвио Микали и Чарльзом Реккофом в статье «Сложность знаний интерактивных систем доказательств». За эту работу ребята получили премию Курта Гёделя в 1993 году.

В этот момент мир впервые понял, что криптографические системы могут не только скрывать данные, но и достоверно (с 99,9999% вероятностью, стремящейся к бесконечности, это важно) доказывать другому агенту, что мы владеем информацией, не раскрывая эту самую информацию.

Большинство практических реализаций технологий принято называть акронимом zk-SNARKs, что означает Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Есть ещё несколько других, которые мы затронем позже и SNORKs, который мы вообще не будет рассматривать в этой статье :)

Для полноты понимания не-технарей приведу 3 классических описания технологии на пальцах.

1) Пещера нулевого знания.
Первоначально данный пример был представлен в известной работе о доказательствах с нулевым разглашением под названием "Как объяснить доказательство с нулевым разглашением вашим детям" за авторством Жан-Жака Кискатера.

В этой работе Пегги выполняет роль Доказывающего, а Виктор — Проверяющего (в англоязычной литературе они обычно именуются Пегги и Виктор, что происходит от "Prover" и "Verifier"). Пегги знает "магическое слово" или "ключ", которое позволяет ей открыть дверь между точками A и B. Виктор желает удостовериться, что Пегги действительно знает этот пароль, несмотря на то, что она отказывается его называть. Пещера имеет круглую форму, как показано на картинке. Для решения этой задачи они применяют следующий метод: пока Виктор находится у входа в пещеру, Пегги идет к двери и выбирает произвольную сторону, куда она пойдёт. После того, как Виктор перестаёт видеть Пегги, он идет к разветвлению в точке С и дает сигнал для Пегги: "Пегги, выход справа" или "Пегги, выход слева". После каждой итерации существует вероятность 50% того, что Пегги не знает пароль и выйдет не с тобой стороны, которую указал Виктор. Если повторить этот процесс k раз, вероятность этого будет равна 1/2^k. При 20 повторениях вероятность этого становится около 10^-6 или 0.0001%, что считается достаточным для предположения о том, что Пегги знает ключ.

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

2) Судоку

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

Каким образом можно доказать, что мы решили судоку, без демонстрации полной картины, т.к. второму человеку будет просто неинтересно играть.
Очень просто: мы можем просто вырезать каждый столбец или строку, перетасовать их и закрыть. В таком формате мы отправляем другу этот вариант и он может проверить произвольную строку из нашего варианта решения, убедившись, что мы не лжём.
Примерно также будут действовать верификаторы сети zk-Rollup'a, они будут брать некие произвольные транзакции, которые батчами засылает прувер (то есть секвенсор) в L1 и проверять их истинность, таким образом будет достигнуто сильное увеличение пропускной способности без проверки каждой отдельной транзакции при заливе на первый слой Ethereum.

3) Игра Where is Waldo?
Смысл игры заключается в том, чтобы продемонстрировать знание о том, что вы знаете где Waldo, но не показывая на него, чтобы об этом узнали другие.
Сам Waldo выглядит вот так:

Так вот, можете попробовать найти его сами в этом саду земных наслаждений, но за авторством, увы, не Иеронима Босха.

Очевидным решением этой задачки - это вырезать Waldo по контурам из картинки и скинуть его проверяющему, таким образом, мы не выдаём положение Waldo и достоверно указываем, что мы его нашли. Задачка имеет изъяны и не тянет на достоверную информацию, но всё же она показательная.
Точно также можно приводить пример с паспортом. Условно, сейчас, чтобы доказать, что вам есть 18 лет в магазине при покупке алкоголя, мы должны демонстрировать паспорт, который может спалить всю инфу о нас - имя, фамилию, дату рождения и так далее, хотя продавцу необходима только информация, что нам есть 18. Решением проблемы может стать децентрализованное хранилище отпечатка пальца в соответствии с твоим днём рождения. Таким образом, внутрь полной базы данных залезть нельзя, но по отпечатку смарт-контракт может верифицировать вас, как совершеннолетнего. Это только пример, не съедайте меня, лишь демонстрация :)

Примеры практического применения

Окей, ваш вопрос принят в обработку, ожидайте обратного звонка...Но если серьёзно, давайте на пальцах.

Сейчас что Bitcoin, что Ethereum нам валидируют отдельные узлы - у биткоина это майнеры, у эфириума - стейкеры в нодах, каждый из них проверяет правильность каждой транзакции. Для нужд децентрализации, каждый отдельный узел проверяет каждую транзакцию, а потом консенсусом решают, какие транзакции являются "правильными" и какие из них стоит включать в блок.

Из-за этого нам необходимо ждать довольно долго(по меркам вычислительных машин), чтобы большинство узлов проверила каждый блок и подтвердила его.

Также, мы уже знаем, кто такие Проверяющие и Доказывающие. Если под Ethereum будет имплементирован zk-Rollup, то для создания доказательства необходим будет только 1 узел, который создаёт доказательство (читай секвенсор), а остальные будут его только проверять, смекаешь?!

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

Ещё один из вариантов, который не связан с блокчейном - хранение аккаунта и пароля в web3 мире. В данный момент, некоторые сайты до сих пор хранят пароли в незашифрованном виде в базе данных, что очень плохо, т.к. если база будет взломана, то пароли и аккаунты утекут к злоумышленникам! Но даже если пароль будет преобразован в хэш, то злоумышленник всё ещё может завладеть вашим аккаунтом, если получит доступ к паролю, либо сможет "расхэшировать" ваш пароль - это скорее к варианту, когда пароль у вас выглядит как "пароль", не сложно подобрать хэш под это слово. На помощь приходит мир web3! Вы можете заходить в свой аккаунт в связке "логин-пароль", генерировать доказательство и заходить по нему! По такой связке, не имея доступа к обоим элементам, злоумышленник не сможет получить к вашему аккаунту доступ.

Логином в этом случае может выступать или почта, или публичный ключ вашего кошелька, а паролем обычный пароль от почты, либо подпись сообщения приватным ключом. В некоторых привычных вам сервисах (Debank, Dune) реализовано что-то подобное, при подключении вашего метамаска и подпись, что вы являетесь владельцем, так будет выглядеть фронт для вас, а под капотом трудится zkp, чтобы избежать коллизий и других неприятных штук. И не надо будет делать разные пароли везде, нужно лишь хранить сид-фразу и всё! Да, это не исключает проблемы полностью, если вы пользуетесь паролем "пароль", но всё же это небольшой шаг в сторону оптимизации связки логин-пароль.

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

К другим вариантам использования вернёмся немного позже.

Ускорение в бесконечность: технологические этапы

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

1) Pinocchio zkp - система доказательств, которая появилась в 2013 году для эффективных вычислений общего вида, опирающаяся только на криптографические предположения. Размер доказательства составляет 288
байт, независимо от выполняемых вычислений и размера входных и выходных данных. Это первая практическая реализация ZKP. Технология использовалась в криптовалюте zCash (старички помнят). Ознакомиться можно здесь - тык.

2) Groth16 - вторая крупная реализация после Pinocchio, значительно ускоренная за счёт уменьшения числа входящих элементов, входящих в объекты доказательства. Теперь размер доказательства мог варьироваться в зависимости от входящих данных. Эту технологию используют в данный момент TornadoCash, Sui, Loopring и некоторые другие. Ознакомиться можно здесь - тык.

3) Bulletproofs - новое поколение zkp, которое уже не является SNARK'ом. Оно использует ещё более укороченное доказательство, размер которого равен логарифму входных данных. Она используется в таких проектах как Grin и Beam. Ознакомиться можно здесь - тык.

4) PLONK - современнейший протокол из SNARK'ов, который был представлен в 2022 году ребятами из Aztec. Там же он и применяется, вот документация этого самого Aztec. По ней писал свой пост Vitalik в своём блоге. По этому протоколу я пройдусь немного больше, чем по предыдущим.

Я настоятельно рекомендую ознакомиться самим с его статьёй, но для самых ленивых сделаю TL:DR.

Если вкратце, то:

• Почти каждый SNARK перед началом генерации доказательств должен пройти фазу доверительной настройки, чтобы он не генерировал ложные доказательства, а также, после каждого перезапуска системы (чтобы настроить её на другие доказательства, например), эту процедуру необходимо снова проходить. PLONK не нуждается в доверенной настройке для разных вариантов доказательств, т.к. обладает "универсальной и обновляемой" первичной настройке. Также, в этой первичной настройке могут участвовать несколько сторон и система всё ещё будет оставаться безопасной.
• PLONK использует "модную криптографию" (fancy cryptography в оригинале), которая использует на полиномиальное обязательство (не пугайтесь, полином - это многочлен, более сложной математики тут не будет). Оно построено на принципе, что "из коробки" PLONK работает на схеме обязательства Кейт, но вполне может быть заменено на схему FRI, либо DARK.

Таким образом, последнее достижение в области SNARK'ов является очень гибким инструментом в работе с доказательствами и может меняться в зависимости от задачи. Если хотите плотно с этим ознакомиться, вот оригинальная публикаций ребят - тык. Но, справедливости ради, вам хватит и статьи Виталика, поверьте :|

С полным списком снарков и других стеков на zkp вы можете ознакомиться здесь - тык. А мы откатимся на пару лет назад и займёмся разбором самого вкусного пирожка в этом магазине криптографических булочек.

Встречайте - zk-STARK.

zk-STARK (Zero-Knowledge Scalable Transparent Argument of Knowledge) - технология, разработанная профессором Израильского технологического института Илаем Бен-Сассоном совместно с Иддо Бентовом, Иином Хорешом и Михаилом Рябцевым в 2018 году, которая привнесла значительное улучшение в области систем с нулевым разглашением тем, что предоставила значительное ускорение процесса масштабирования. Эта технология исключила необходимость предварительной доверительной настройки, что представляло угрозу конфиденциальности в предыдущих протоколах.

Этот протокол в ближайшее время позволит развивать масштабируемость эфира практически до бесконечных масштабов, если верить словам разработчиков. С презентацией технологии можно ознакомиться в их слайд-шоу 2018 года от компании StarkWare - тык. Также можете ознакомиться с самой научной публикацией, которая в полной мере раскрывает методику работы технологии - тык.

Если кому-то лень читать полную презентацию, оставлю здесь табличку с ключевыми метриками по основным ZKP:

Из интересного по метрикам в отличиях STARK'ов и SNARK'ов:
1) Нам больше не нужно проводить фазу доверительной настройки, мошенников будет наказывать сама система, что открывает большой и долгий путь для децентрализации верификаторов секвенсора от Starknet.

2) Постквантовость zk-STARK позволяет не переживать за монструозные вычислительные мощности (aka взлом наших любимых фантиков), которые в ближайшее время могут появиться в руках человека с появлением квантовых компьютеров.

3) Хоть SNARK'и и обладают высоким сопротивлениям к коллизиям хэша - это когда на разные входные данные могут выдать одинаковый выходной хэш, а если проще говоря, 100 транзакций с одним содержанием и другие 100 транзакций в блоке могут выдать один и тот же хэш, что открывает возможность подменить данные в блоке - но STARK'и буквально обладают устойчивостью к коллизиям!

4) STARK'и дороже при отсылке транзакций на эфир, в отличие от SNARK'ов при маленьком количестве транзакций(что мы и видим сейчас на примерах Arbitrum и Optimism в сравнении с Starknet). С ростом количества транзакций и окончанием реализации стоимость транзакций значительно снизится.

Варианты применения zk-STARK

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

• В первую же очередь, на момент выхода статьи, Илай пишет, что zk-STARK может использовать как систему распознавания ДНК различных людей без раскрытия данных что самой ДНК, так как доказательство будет выглядеть намного короче, чем сама ДНК.
  Представим, проводятся выборы президента. Если база данных ДНК хранится в распределённом реестре, то можно использовать zk-STARK, чтобы проверить, находится ли код цепочки дезоксирибонуклеиновой кислоты кандидата в базе данных преступников. Такая же система будет использоваться и для рецидивистов, которых ловят на других преступлениях. Это уже не говоря о том, что мы можем и не доверять полиции, которая даёт квази-экспертное заключение, что в базе был кто-то найден, тогда как криптография не может нам лгать.
• Есть вариант использования zk-STARK для верификации человека в какое-либо учреждение, условно, банковское приложение. По отпечатку, как это мы делаем сейчас, но база будет хранится на распределённом реестре, чтобы банк не обладал информацией о нас(здесь скорее речь о центральных банках, чем о коммерческих, я полагаю).
• Также, мы можем использоваться zk-STARK для системы дистанционного электронного голосования. Выглядит это примерно так: сейчас мы не можем доверять государству, которое хочет провести голосование по выбору, допустим, мэра или губернатора, т.к. проводится оно будет на непубличном блокчейне в угоду конфиденциальности голоса (в России это ФЗ-67 статья 7). Хорошо, но мы можем использовать криптографию, чтобы убедится, что человек голосовал за того, за кого он хотел (а не за кого-то другого) и его голос не был подтасован, не раскрывая при этом за кого конкретно он голосовал. Таким образом, мы сохраняем голос в тайне, а система бдит за махинациями.

Немного душных оговорок, чтобы криптанам всё ещё было о чём спорить в вечных холиварах:

Я понимаю, что zk-STARK встроен уже не только в Starknet. Недавно zkSync объявили, что встраивают систему под названием Boojum к себе, причём без регенезиса сети, это прекрасно, многие стали писать мол "смотрите, технологии одни и те же, а Starknet как был не очень, так им и остался", - но ведь это не вся правда. Ускорение работы секвенсора - это не первостепенная задача для Starknet, они занимаются исследовательской работой по этому направлению zkp, а увеличение пропускной способности - вопрос желания команды, вот один из примеров, как это может быть достигнуто - распараллеливание, читайте пункт Sequencer parallelization.

Вывод

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

Не обманывайтесь мнимыми рассуждениями о том, мол "в Starknet комиссия за транзакцию ~15 центов, какое радикальное снижение комиссий и масштабируемость, гон это всё и кэшгрэб!", - ведь любая математическая концепция не сразу входила в нашу жизнь с её появлением. Вспомните комплексные числа (это которые √-1), в начале какие-то математики эту бурду придумали в середине 16 века, потом к началу 18 века была построена теория корней уравнений для любой степени, и только к 1831 году Карл Гаусс ввёл официальный термин, причём до их использования мы ещё даже не дошли! Только с 19 века комплексные числа начали использовать для расчётов сложных электрических цепей - всякие углы наклона тока и сопротивления(всем, кто сдавал в универе теоретические основы электротехники, привет, у меня тоже флешбеки начались!). Вы замечали, как в характеристиках наушников пишут "Импеданс", а не "Сопротивление" - вот это оно и есть.

В наше время происходит экспоненциальное ускорение всех технических "искусств", поэтому нам не придётся ждать 200 лет для реализации всех придумок математиков(хотя вот для таких, может и понадобится, лол).

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

Материалы, неупомянутые в тексте:

• ZK 101 - What is ZK & Why Should You Care?
• Introduction zk SNARKs STARKs Eli Ben Sasson Technion Cyber and Computer Security Summer School
• ZK-STARK-wiki