Демистификация ZK Программирования
Децентрализованные Приватные Вычисления в Aleo
Перевод презентации Howard Wu на Zero Knowledge Summit Berlin 2022.
Ссылка на запись презентации: https://youtu.be/5hO9NbtFc0g?t=2069
Мой Discord: useless_dorozhkina#1394
Привет всем! Меня зовут Howard, если вы меня не знаете, я соучредитель Aleo. Сегодня я хотел бы немного обсудить программирование с нулевым разглашением и его модель. На протяжении последних нескольких лет активно обсуждалось создание виртуальных машин ZK, и особенно активно — создание zkEVM. Поэтому я подумал, что стоит использовать данную возможность, чтобы поговорить о новых проблемах, связанных с моделью аккаунтов, о возможных способах их решения, и, говоря в общем, о том, как создать необходимые инструменты и инфраструктуру вокруг них.
Большинство из того, о чем я сегодня буду рассказывать было представлено несколько лет назад в научной работе под названием ZEXE. Она была опубликована в Окленде, в 2020-м году, и описывала протокол, который расширял ZeroCash так, чтобы последний поддерживал приложения общего назначения.
Перед тем, как я начну, поскольку в данную сферу приходит множество новых людей, я думаю, важно на самом базовом уровне рассказать о том, как работает Нулевое Разглашение.
Концепция нулевого разглашения принципиально заключается в том, какие доверительные предположения существуют между доказывающим и проверяющим; о них я поговорю далее.
Презентация будет разделена на три части. Главное, о чем я хочу сообщить — это zkSNARK. Я надеюсь, помочь понять вам на более высоком уровне, как они работают. А затем мы пойдем дальше, и поговорим о концепции ZK L1 и о том, как можно создать виртуальную машину на блокчейне, которая будет доказуемо проверяемой. И, наконец, о том, как мы реализуем подобные вещи в Aleo.
zkSNARK становятся практичными для Web3 приложений.
Часть 1. Что такое zkSNARK?
Чтобы приступить к ним, нужно начать с самых базовых примитивов:
- Криптография — это очень мощный инструмент для создания безопасных систем.
- Большинство криптографии, которое мы используем сегодня, нужна для того, чтобы предоставить гарантию безопасности данных.
Под этим я имею в виду, что когда в сети вы передаете информацию между двумя сторонами, вы хотите зашифровать сообщение таким образом, чтобы только отправитель и получатель смогли его увидеть. Поэтому мы используем криптографию для шифрования!
Другой вариант, который сейчас часто используется — это улучшение свойств безопасности с помощью аутентификации. Когда отправитель и получатель взаимодействуют друг с другом в сети, нужно быть уверенным, что получатель на самом деле принимает сообщение от отправителя. Один из способов осуществить это — подписать сообщение и только затем отправить его.
Это и есть два основополагающих механизма, которые используются в криптографии! На самом деле, речь идет лишь о защите данных.
Но вопрос состоит в том, возможно ли использовать данный вид криптографии, чтобы пойти дальше и давать гарантии о самих вычислениях? И именно здесь криптографические доказательства вступают в игру.
Криптографические доказательства предоставляют сохраняющую приватность целостность для вычислений.
По-моему, это совсем новая сфера, она становится практичной и готова быть использована в мире. В частности, криптографическое доказательство сообщает: "Хэй! Я безопасно провел вычисление уравнения y = function(x) и получил y в результате! Цель состоит в том, чтобы убедить другие стороны в Интернете, что я действительно это сделал."
Когда вы погружаетесь еще дальше, вы видите, что существует еще и отдельный сегмент криптографических доказательств, которые называются доказательства с нулевым разглашением!
Доказательство с Нулевым Разглашением (ZKP)
Криптографическое доказательство, сохраняющее приватность целостности вычисления.
На самом деле, это шаг вперед для криптографических доказательств! Здесь доказательство говорит: "Я знаю x такой, что y = f(x), где x — это приватные входные данные".
Когда вы находитесь в сети, порой вам неохота делиться чем-либо, что у вас есть или о чем вы знаете. Особенно когда это касается личной информации, PII. Но чтобы другие люди имели возможность проверить, что вы действительно запускали программу и получили в результате y, им нужно каким-либо образом поверить в то, что вы использовали верные входные данные. И если вы не хотите делиться этими данными, то доказательство с нулевым разглашением становится очень полезным примитивом!
Другой способ описания доказательства с нулевым разглашением — это сказать:
Я знаю секрет. Я не могу его вам рассказать. Но я могу доказать вам, что я действительно его знаю.
Это и есть самая суть подобных доказательств. На самом деле, все сводится к возможности передать информацию другой стороне, не раскрывая эту информацию полностью.
Для это имеется конкретный, очень каноничный пример, который возможно многие из вас видели в Интернете, задача "Где Уолли?".
Можно показать другой стороне, что вы действительно нашли Уолли, взяв большой лист белой бумаги (намного больше, чем само изображение) и накрыв им весь экран. Также потребуется вырезать маленькое отверстие размером с Уолли. Таким образом, когда другой человек зайдет в комнату и увидит огромный холст с маленькой дырочкой с высовывающимся Уолли, он будет убежден, что Уолли есть на карте, он существует, и вы его нашли. Теперь, если вы попросите человека покинуть комнату, снимите холст, человек сможет вернуться и теперь уже самостоятельно попытаться найти Уолли. Это и есть способ доказать, что Уолли есть на карте и вы его нашли, не показывая при этом, где именно на карте он находится.
Это действительно очень канонический пример. Но я хочу быстро продемонстрировать еще один, Пещеру Али-Бабы. Этот пример происходит от статьи 1989-го года под названием "Как объяснить своим детям протоколы с нулевым разглашением".
Основа примера лежит в том, что Alice и Bob стоят около пещеры. Alice заходит в пещеру, в которой находит два пути: путь A и путь B. Оба пути соединены между собой задней дверью (черная линия на картинке). Когда Alice зашла, Bob подбрасывает монету и говорит: "Я хочу, чтобы ты вышла через A, если выпадет орел, и B — если решка." Если у Alice есть ключ, она сможет воспользоваться дверью так, чтобы выйти с правильной стороны. И если Alice решит пройти через B:
но Bob скажет выходить через A, у Alice должна быть возможность открыть дверь и пройти через нее:
Но имеется также и "счастливая случайность", что Alice выбрала путь B, Bob подбросил монету, и выпала решка, и Alice может выйти путем B даже без ключа! Таким образом, пример становится более проблематичным. Нужно провести несколько раундов этой игры. После нескольких раундов, в конце концов, вы сможете ограничить вероятность того, что Alice врет до нуля. Предел такой вероятности будет стремиться к нулю.
Это еще один канонический способ объяснения работы протокола нулевого разглашения. Большинство схем, особенно описанных давно, были созданы на основе интерактивного взаимодействия между доказывающим и проверяющим.
Первое ZKP из [GMR89]
Первое доказательство с нулевым разглашением было изобретено в 1989-м году Micali и Rackoff. Тогда модель выглядела следующим образом:
- Функцией F,
- Зафиксированным выходным значением y
- И приватным входным значением x.
Также был Проверяющий, который знал
Цель заключалась в том, чтобы доказательство говорило: "Я знаю такое приватное входное значение, что y = F(x)".
Проверяющий, в свою очередь, говорит: "Докажи, что ты знаешь x".
Затем между доказывающим и проверяющим происходит несколько раундов взаимодействий, в ходе которых проверяющий отправляет задачи доказывающему, а доказывающих решает их и отправляет ответы назад. Это повторяется несколько раз также, как и в примере с пещерой Али-Бабы. Проведя несколько таких раундов, вероятность становится таковой, что проверяющий убеждается в наличии у доказывающего секрета! Потому что, если бы у доказывающего его не было, он не смог бы ответить на все запросы.
Таким образом, все было задумано. Но в этой модели 1989-го года, как вы сами понимаете, присутствовало множество компромиссов.
- Во-первых, например, то, что взаимодействия были интерактивными. Если представить нечто подобное в Интернете с двумя незнакомцами, необходимо было бы, чтобы они оба были онлайн одновременно, чтобы взаимодействовать; это было бы очень неудобно.
- Во-вторых, сам по себе данный дизайн не был краток. Это значит, что проверка самого доказательства занимала примерно такое же количество времени, которое ушло бы на вычисление функции F. Поэтому, если вы захотели бы делегировать некие свои вычисления третьим лицам, у вас бы ушло столько же времени на проверку правильности вычислений, сколько ушло у них на генерацию доказательства.
- И, наконец, что сама эффективность подобной модели была очень низкой. У доказывающего уходило очень-очень-очень много времени на генерацию доказательства для вас. И поэтому, в контексте реального мира, эта модель была непрактичной. Конечно, с точки зрения теоретики и науки, нечто подобное было невероятно.
Для того чтобы исправить некоторые из этих проблем в 1994-м Silvio Micali опубликовал научную работу, которая продемонстрировала первый краткий не интерактивный аргумент знания с нулевым разглашением.
Первый Краткий Не Интерактивный ZKP из [Micali94]
Идея опять-таки заключалась в том, что
Но теперь Проверяющий становится очень маленьким:
И в этом и заключается свойство краткости.
В этом случае доказывающий утверждает то же, что и в прошлом: "Я знаю x такой, что y = F(x)". Проверяющий также просит: "Докажи, что ты знаешь x". Но теперь вместо того, чтобы проводить несколько раундов взаимодействий, они используют случайный оракул (например, Poseidon). Предпосылка состояла в том, чтобы вместо того, чтобы использовать проверяющего, придумать случайные задачи, которые можно было бы отправлять доказывающему, который затем решал бы их и отправлял назад. Проверяющий затем пробовал бы отправлять новые задачи, чтобы получить больше ответов. Они оба могли бы договориться использовать определенную хеш-функцию, и сказать: "Это предварительный образ, с которого мы начнем. С него мы оба можем начать хешировать и использовать одинаковые предположения о том, что должно быть вычислено". Поэтому проверяющий сможет сказать: "Я знаю, с чего ты начинал, и я могу итеративно проверить, что ты вызывал те же функции, что использовались бы, если бы мы использовали обыкновенные взаимодействия". И такая модель сохраняется на потребности обоих сторон взаимодействовать друг с другом.
В конечном результате, доказывающему потребуется лишь отправить одно доказательство проверяющему. Таким образом, данная схема и стала не интерактивной!
Таким образом, прошло 20-30 лет между первоначальной концепцией доказательства с нулевым разглашением и тем, что мы используем сегодня. С тех пор было достигнуто множество успехов, особенно в теории. Но и с точки зрения технической части тоже, потому как теперь мы можем использовать эту модель в реальной жизни с очень сложными утверждениями.
Я не уверен, как много людей тут знакомы с zkSNARK, поэтому кратко опишу их конструкцию.
Что значит zkSNARK?
zkSNARK означают Zero-Knowledge Scalable Transparent Argument of Knowledge — «краткий не интерактивный аргумент знания с нулевым разглашением». В этом определнии много жаргона:
- "Нулевое разглашение" значит, что доказательство не раскрывает свидетеля. Свидетелем в данном случае чаще всего называют приватные входные данные, секрет, который вы не хотели бы раскрывать.
- "Краткий", потому что доказательство маленькое, Кбайт или даже меньше; и их верификация занимает мало времени, 10-20 мс. Такое количество времени, которое практично было бы занимать на проверку в браузере.
- "Не интерактивный", так как между доказывающим и проверяющим может не происходить никакого взаимодействия.
- И, наконец, "аргумент" означает надежность полиномиально ограниченного проверяющего. Это более техническое определение, потому что имеются как статистические ограничения, так и вычислительные ограничения, которые можно задать проверяющему.
Надеюсь, это немного раскрыло для вас завесу того, что такое zkSNARK. И теперь я хочу поговорить о том, как их можно использовать, чтобы создать модель программирования Layer 1.
Часть 2. Как создать ZK L1?
Честно гововоря, я думаю, что проще всего начать с модели аккаунтов, потому что, по-моему, почти все собравшиеся хотя бы раз взаимодействовали с Ethereum.
Перед тем, как мы начнем, хорошо бы было отметить, что людям очень нравится писать приложения в Web 3! И для них находится множество способов применения.
Вопрос состоит в том, можно ли создать L1 для них всех? Короткий ответ — да, но придется столкнуться со множеством ограничений.
Как работают децентрализованные реестры?
Проверка путем повторного вычисления
Первое из ограничений заключается в том, что, когда вы создаете децентрализованные реестры, нужно действовать, верифицируя и подверждая все транзакции, т.е. проводя повторные вычисления. Под этим я имею в виду, что имеется:
1. Пользователь, который отправляет транзакцию, что состоит из приложения, входных данных и подписи:
Пользователь транслирует эту транзакцию в сеть,
2. И затем каждая нода в сети повторно проводит вычисление, относящееся к данной транзакции.
3. Если вычисления выполнены верно, и подпись является достоверной, то приложение обновляется.
Как вы уже можете видеть, в этой модели происходит огромное количество повторных вычислений. Позвольте рассказать вам, какие ограничения это накладывает:
1. Повторное вычисление в реестрах вредит масштабируемости.
В общем случае, каждая нода повторно проводит каждую транзакцию в сети, что влечет за собой огромное количество потраченной впустую работы.
Если взять для примера структуру Ethereum, eth1 (я только что понял, что после слияния приведенные цифры придется поменять!), в которой имеются 3000 нод, и предположить, что на вычисление каждого блока уходит 5 секунд, в результате получится 15000 секунд (или 4 часа) повторных вычислений!
Учитывая предыдущие слайды о том, что такое zkSNARK, становится очевидно, что вместо этого было бы лучше создавать доказательства правильности вычислений. С их помощью каждой ноде не придется проводить повторные вычисления. И это очень важно, потому что модель, подобная eth1, очень нерациональна!
2. Повторное вычисление в реестрах вредит приватности.
В существующей модели децентрализованных приложений вы можете узнать все, что угодно! Вы можете узнать, кто является вызывающим, кто получателем, о том, какая программа вызывалась, о ее логике и данных. И, по-моему, нужно будет учитывать слишком много нюансов, если мы хотим использовать подобную конструкцию в Web 3.
Классический пример: допустим, я хочу перевести вам деньги, для этого вы даете мне номер своего банковского счета. Номер вашего счета не раскрывает для меня информации о том, сколько денег на нем вы храните, сколько денег вы зарабатываете, сколько тратите, на что и когда. Ничего из этого не раскрывается. Но если вы дадите мне свой адрес Ethereum, я узнаю все эти вещи о вас, а также смогу следить за вами все оставшееся время!
Это принципиальный UX/UI вызов, который нам бросает Web 3 и о котором нам нужно задуматься, если мы действительно хотим использовать подобные технологии в реальной жизни.
Поэтому мы и создали нечто под названием "Aleo"!
Aleo означает "Autonomous Ledger Executions Off-Chain" — автономное вычисление реестров off-chain.
Сам по себе, Aleo является децентрализованным реестром. Он дает возможность пользователям выполнять программы off-chain и завершать его состояние on-chain.
Реестр обладает следующими свойствами:
1. Масштабируемость: тысячи транзакций включаются в блок.
2. Приватность: транзакции не раскрывают пользовательстких данных в выполненных программах.
3. Краткость: транзакции могут быть проверены за время poly(k):
|транзакция| ~ 1 Кбайт Проверка(транзакции) < 50 мс
Наши программы также обладают несколькими свойствами:
- Расширяемость (любые программы, заданные пользователем)
- Изолирование (вредоносные программы не могут повлиять на честных пользователей)
- Межпроцессное взаимодействие (функции программ могут взаимодействовать между собой)
Чтобы увидеть, как мы достигли такой конструкции, давайте начнем с анализа популярного фреймворка под названием "модель аккаунта".
Модель Аккаунта
В модели аккаунта, по сути, используется децентрализованный реестр, который отслеживает все аккаунты с помощью глобального состояния.
Чтобы совершить переход состояния, обычно пользователю нужно подписать транзакцию, которая передает запрос выполнить какую-либо программу с заданными входными полями. Когда транзакция верифицирована, она передается реестром в следующий блок, при этом состояние аккаунта обновляется автоматически. Это внутренняя операция, и таким образом аккаунт переходит из предыдущего состояния в новое состояние программы.
Интуитивно видно, что пользователи применяют входные данные с помощью транзакций, а реестр обновляет внутреннее состояние, исходя из результата этой транзакции.
Естественно, однм из самых существенных преимуществ такой модели аккаунта является ее простота. Разработчикам легко управлять ей и состоянием между множеством участвующих сторон.
Но также есть и несколько недостатков:
Один из них порождает другой, так как сложные задачи требуют большого количества времени на выполнение. А огромные очереди из неподтвержденных транзакций могут привести к существенным скачкам в ценах комиссий.
3. Отсутствие приватности в существующей сегодня модели аккаунтов.
Транзакции раскрывают свое содержание всем участникам сети. Получатель, отправитель, входные и выходные данные — все публично доступны.
Поэтому мы и хотим реконструировать этот реестр, минимизировать повторное выполнение и максимизировать приватность. Как мы можем добиться этого? Конечно же добавив немного zkSNARK! Мы хоти расширить модель аккаунта и посмотреть, что из этого получится.
Попытка 1: Расширение Модели Аккаунта
Наитие: Приватные Смарт-Контракты
Вместо того, чтобы раскрывать в транзакции ваши значения, данные и подпись, мы можем зафиксировать значения, зашифровать данные и использовать криптографические доказательства вместо подписи.
А для состояния on-chain вместо того, чтобы показывать публично ваш адрес, код и память, почему бы не использовать фиксацию баланса, предикат кода и зашифрованную память?
Мы можем сказать, что когда теперь пользователь создает транзакцию, он открывает в ней незначительное количество информации. А то, что загружается on-chain на самом деле не является данными, это переход фиксаций и зашифрованной информации из предыдущего состояния в новое.
Но если бы все было так просто, я бы не стоял тут и не рассказывал бы вам об этой модели! Поэтому давайте подумаем о свойствах данной конструкции.
Почему так не работает?
Во-первых, параллельность — это огромная проблема. Допустим, у нас есть пользователь А, который хочет обновить состояние. Поэтому он вызывает обновление программы А транзакцией 1. Если подключается пользователь В, который также хочет обновиться с помощью транзакции 2, это не сработает! Потому что все состояние становится зашифрованным, и только один пользователь может обновить его.
Вторая проблема заключается в том, что мы до сих пор не можем добиться полной приватности в этой модели аккаунта. Почему? Потому что все могут увидеть, что пользователь А обновил программу А. Причина этого в том, что транзакция до сих пор раскрывает адрес! И не только адрес пользователя, но и адрес контракта, на который он ссылается!
Если вернуться к примеру с банковским счетом: если я захочу отправить вам деньги, и вы дадите мне свой номер счета, я могу и не узнать, сколько вы тратите. Но я узнаю, что вы используете этот аккаунт, какие приложения вы используете, сгруппировать это и сделать вывод о том, как часто вы совершаете сделки, где вы это делаете, кто выплачивает вам зарплату, и кто возвращает вам долг. Поэтому эта модель и не является приватной, по крайней мере, в каноническом понимании.
Давайте проанализируем свойства более подробно.
Наше Решение: Модель Записей
В модели записей децентрализованный реестр все так же отслеживает записи каждого аккаунта в глобальном состоянии.
Теперь, чтобы выполнить переход состояния, пользователи генерируют транзакции, вычисляя докозательство с нулевым разглашением, которое удостоверяет переход состояния для заданного выполнения программы. Когда транзакция проверяется и подтверждается в следующем блоке реестра, программа внутренне обновляет сама себя! Это и осуществляет переход из предыдущего состяния в новое состояние программы.
Наитие: Пользователи используют только те записи, которые необходимы для осуществления желаемого перехода состояния их программы. И теперь вам не нужно задействовать все состояние!
Таким образом, мы добиваемся параллельности! Потому что я работаю только лишь с записями аккаунта, принадлежащего мне. И затем я могу взять свои записи и провести переход состояния с их помощью.
Это также решает и проблему двойного расходования! Как? Так как в данной модели состояние вашего аккаунта должным образом идентифицируется с использованием записей, если вы попытаетесь потратить одну и ту же запись дважды, это будет легко замечено в сети. Эта модель предоставляет консеснусу легкий способ криптографически удостовериться в том, что запись была использована единожды, при этом не раскрыв её содержание.
Свойсва Aleo
Теперь, когда мы абстрагировались до модели записей, мы на самом деле можем добиться приватности аккаунта. Потому что децентрализованный реестр идентифицирует глобальное состояние на основе ID программ. Эти ID можно кластеризировать, в отличие от адреса вашего аккаунта. И это принципиально решает все проблемы предыдущей модели приватности.
Также мы можем добиться очень эффективных обновлений состояния, потому как теперь вы можете использовать только те записи в программе, которые принадлежат вам, или те, которые вы на самом деле хотите использовать для перехода состояния.
И, наконец, вы можете выполнять параллельные переходы, потому что внутри программы теперь используется система записей. Она позволяет использование только принадлежащих вам записей для ваших обновлений. В то же время другие люди могут использовать их записи для их обновлений. Подобный тип изоляции позволяет множеству сторон взаимодействовать с одним и тем же приложением одновременно.
Часть 3. Используем SNARK!
Теперь мы хотим создать экземпляр подобной модели. Нам нужно испоьзовать множество технологий и дисциплин, чтобы собраться вместе и создать нечто подобное! Aleo стоит на пересечении множества дисциплин. От математики до теории сложности вычислений, до криптографии, до компьютерной безопасности и языков программирования.
Мы создали образец кривых, которые задействуют удобные для использования SNARK криптографические примитивы.
А именно мы создали 377 битовые кривые со степенью изгиба 12, которые мы называем BLS12-377. Эти кривые замечательны, потому что они поддерживают быструю верификацию доказательств в нашей конструкции.
Мы также создали образец скрученных кривых Эдвардса (Edwards-BLS12), которые полезны для эффективного хеширования Педерсона, для фиксаций, а также для подписей. И, в общем случае, Edwards-BLS12 делают возможными эффективные операции со схемами.
И, наконец, мы создали образец нашего SNARK, Marlin. Marlin был опубликован в Eurocrypt 2020-го года. И Marlin прекрасен, потому что он требует лишь одной универсальной настройки для всех программ. Это Универсальная Настройка, о которой Alex рассказывал ранее.
Если вы хотите посмотреть наши работы, они имеют открытый исходный код!
Все работы, которые относятся к Leo, Aleo и самому AVM, можно найти на GitHub. Поэтому на высоком уровне можно взять часть кода Leo, скомпилировать его до Инструкций Aleo, похожих на Assembly, а затем сериализовать их до байт-кодов AVM, которые могут быть развернуты в сети. Сама по себе программа содержит предикат, который может быть представлен в отношении байт-кода AVM. А весь код до этого создается off-chain разработчиками, которые и решают, как будут взаимодействовать между собой две стороны.
Здесь вы можете посмотреть на синтаксис Инструкций Aleo:
function main: <- инициализирует функцию "main"
input r0 as field.public; <- вводит публичный реестр "r0"
input r1 as field.private; <- вводит приватный реестр "r1"
mul r0 r1 into r2; <- умножает "r0" и "r1" на "r2"
output r2 as field.private; <- выводит приватный реестр "r2"Вы можете увидеть функцию main, и входные данные, реестры r0 и r1. В данной примере я хочу умножить эти два числа. Я могу ввести публичный и приватный элементы, умножить эти два числа на реестр r2. И затем я могу вывести приватный результат умножения.
Так как придерживается модель аккаунта, на самом деле, когда я хочу транслировать в сеть приватное состояние, мне нужно его зашифровать с помощью адреса моего аккаунта. Поэтому только я со своим аккаунтом смогу увидеть результат этого вычисления в сети с помощью моего ключа просмотра.
Это и есть разница между существующей моделью программирования в системах, основанных на EVM, и набором новых ZK L1, которые, по-моему, будут использовать приведенную выше модель.
Спасибо!
Напоследок я хочу сказать вам спасибо!
Мы гордимся тем, что Aleo написан на Rust. Мы написали огромное множество строк кода. Возможно, нам даже нужно проделать некоторый рефакторинг. Но над Aleo работало замечательное сообщество из 40+ участников, которые пишут на Aleo и помогают ему реализоваться.
Вы можете найти нас на GitHub: https://github.com/AleoHQ.
И, наконец, Testnet 3 уже запущен! Если вы хотите поиграть с нашей сетью, вы можете изучить Документацию для Разработчика Aleo: https://developer.aleo.org/.
Спасибо вам за ваши время и внимание! Желаю вам всем отличного дня! Спасибо!