Эффективное Частное Делегирование Доказывающих zkSNARK на Саммите ZK
Посмотрите презентацию Пратюша Мишры на ZK Summit 2022 в Амстердаме, где он обсуждает эффективную частную делегацию Доказывающих zkSNARK: https://www.youtube.com/watch?v=pBGejTXkxLk
Мой Дискорд: useless_dorozhkina#1394
Привет всем! Это фантастика — находиться здесь и видеть множество знакомых, а также незнакомых лиц вживую.
Привет всем! Меня зовут Пратюш, и сегодня я буду рассказывать о нашей работе над делегированием, или же аутсорсингом Доказывающих zkSNARK с сохранением приватности. Это наш совместный труд вместе с моим замечательных соавтором, Алессандро Райаном.
Давайте начинать! Итак, я знаю, что никому тут не нравятся zkSNARK, но я все же быстро повторю, что они делают.
Итак, zkSNARK — это протокол для доказывающего, который убеждает проверяющего в том, что какое-либо убеждение правдиво, без необходимости показывать, почему это так. То есть скрывая некоторые тайны, которые проверяющий может быстро проверить. Краткое доказательство можно эффективно проверить.
Нулевое Разглашение: Проверяющий ничего не знает о w, кроме того, что F(x, w) = 1
Краткое Доказательство: Проверяющему требуется времени меньше, чем |F|
- Анонимные учетные данные [DFKP16]
- Доказательство наличия уязвимости в системе безопасности [DAPRA Sieve, OBW22]
- Голосование, не поддающееся принуждению [MACI]
- …
У zkSNARK имеется множество способов применения, в частности у Нулевого Разглашения. Есть вещи такие, как приватные транзакции, приватные смарт-контракты, о которых тут рассказывали всего минуту назад. Вещи, как децентрализованные многопользовательские игры со спрятанной информацией и так далее. Вы можете сделать множество крутых вещей с этими zkSNARK. Но, к сожалению, применяя zkSNARK к приложениям, вы столкнетесь с одним препятствием, с доказательством.
Проблема: Доказательство занимает много времени
Мы все знаем, что доказательство занимает очень-очень-очень много времени. Поэтому если вы пытаетесь проверить хэш размером в 10 килобайт данных с помощью SHA2 на телефоне, то это займет у вас больше двух минут. Но это займет пару миллисекунд, или даже микросекунд на вашем компьютере. Итак, SNARK занимают много времени.
Потенциальное Решение: Аутсорсинговое Доказательство!
Вы можете сказать: “Окей, я не буду запускать это на моем телефоне, я просто скину это в облако, и пусть какое-нибудь мощное устройство запустит это за меня и предоставит мне доказательство через какое-то время.” Если ваше вычисление особенно большое, вы даже можете использовать кластер, например Spark-кластер, чтобы провести свое вычисление. Есть работа под названием “DIZK”, которая показывает, как это сделать и получить хорошую масштабируемость.
Но проблема всех этих способов заключается в том, что вы раскрываете свою секретную информацию. Кластер или индивидуальный сервер, который вы используете, узнает ваше секретное доказательство, которое вы хотите оставить скрытым.
Проблема: Это раскрывает секреты работникам!
Поэтому идеально было бы сделать доказательство аутсорсинговым, но приватным. Мы хотим спрятать доказательство, при этом не генерируя его.
Итак, нам нужно что-то наподобие протокола или схемы делегирования, в котором делегат может затемнить доказательство перед тем, как он каким-либо образом загрузит его в облако.
Цель: Аутсорсинговое Приватное Доказательство!
При этом между облаком и делегатом могут происходить какие-либо взаимодействия. И, в конце концов, делегат получает доказательство, которое он может показать, кому захочет.
Цель №1: Эффективность
Работа делегата должна быть гораздо меньше доказательства
Первое, что мы хотим получить от таких протоколов делегирование — это эффективность. Аутсорсинг вашего доказательства в облако должен быть гораздо дешевле, чем локальное генерирование доказательства, потому что в ином случае в протоколе не будет никакого смысла.
Цель №2:
Доказательство делегата должно быть скрыто от работников
Это цель по приватности. Мы не хотим показывать доказательство, в ином случае нам стоит создавать доказательство на своем устройстве.
Проблема: Этого невозможно достичь без тяжелых инструментов, как FHE.
Теперь проблема состоит в том, что простые подходы, как MPC и FHE очень много весят. Поэтому, когда вы попытаетесь использовать криптографические инструменты, ваше общее время выполнение во много раз превысит время выполнения такого же вычисления на вашем телефоне. Для нас это нежелательно.
У вас не получится использовать один-единственный сервер. Но вы сможете немного ослабить гарантию безопасности, сказать, что вы беспокоитесь только о пороговой приватности, и передать ваше доказательство совокупности устройств, чтобы они провзаимодействовали и вычислили для вас доказательство с помощью какого-либо криптографического протокола.
Цель: Аутсорсинговое Доказательство с Пороговой Приватностью!
Цель №1: Эффективность
Работа делегата должна быть гораздо меньше доказательства
Гарантия в этом случае состоит в том, что до тех пор, пока хотя бы один из данных работников честен и не вступает в сговор с остальными, мое доказательство скрыто. До тех пор, пока хотя бы одна из этих машин ведет себя честно, все в порядке. Допустим, одна из них — это AEC, вторая — Google Cloud, а третья — Azure. Они не будут вступать в сговор друг с другом, потому что соревнуются друг с другом.
Цель №2: Приватность
Доказательство делегата должно быть спрятано от работников до тех пор, пока хотя бы один работник ведет себя честно
Такая цель выглядит более достижимой. Посмотрим, что мы с этим можем сделать.
Данная работа: Делегирование Доказательства zkSNARK
Данный труд, который еще не был опубликован онлайн, является конструкцией как раз таки таких типов протоколов делегирования для популярного класса доказывающих zkSNARK, которые основываются на полиномиальных операциях ввода-вывода. Все последние работы о zkSNARK попадают в эту категорию, и мы покажем, как создавать схемы делегирования для всего этого класса SNARK.
Мы построим схемы делегирования для:
- Полиномиальных обязательств, о которых я расскажу через пару минут;
- Полиномиальных операциях ввода-вывода.
- Компилятора, который берет эти две схемы делегирования для субкомпонента, и создает схему делегирования для всего zkSNARK.
Итак, мы внедрили и вычислили наши протоколы, у нас есть множество метрик, о которых мы поговорим в конце работы. Но, коротко говоря, когда вы делегируете со своего телефона на облачный сервер, генерация доказательства от начала до конца занимает в 26 раз меньше времени!
Техника соломенного человека заключается в том, чтобы использовать, что называется, MPC, или же Протоколы Конфиденциального Вычисления. Это криптографическая техника, которая позволяет нескольким участникам, заинтересованным в том, чтобы сохранить данные в тайне друг от друга, совместно проводить вычисления с их данными. Таким образом, они получают результат, но ни один участник не узнает никакой информации о вводных данных других участников. Вводные данные каждого участника сохраняются в тайне. По сути, это способ распределить вычисления над секретными данными.
Проблема в том, что доступные подобные инструменты очень-очень-очень дорогие, а также требуют выражения алгоритма доказывающего как арифметической схемы.
Проблема: Схема доказательства слишком большая у популярных zkSNARK.
Почему эта схема такая большая? Что ж, как я уже упомянул, мы сфокусируемся на классе SNARK, которые основываются на полиномиальных операциях ввода-вывода и полиномиальных обязательствах.
Итак, полиномиальные операции ввода-вывода - это интерактивный протокол между утверждающим и проверяющим, в котором сообщения доказывающего - полиномы.
Второй компонент называется схемой полиномиальных обязательств. По сути, эта схема позволяет вам зафиксировать многочлен, и лишь потом доказать, что вычисление этого многочлена верное. Имеется много подобных экземпляров инструкций, например, KZG10; вещей, основывающиеся на внутренних аргументах продукта: DARK, Hyrax и т.д.
Итак, схема доказывающего в zkSNARK состоит из подсхем каждого из этих компонентов. И оба эти компонента - тяжелые криптографические объекты. Я уже упомянул, что они сами по себе могут быть очень сложными, поэтому мы хотим упростить как сам знак сложения, так и эти компоненты.
Давайте приступим к решению первой проблемы. Перед этим я быстро напомню, как вы можете создать подобные схемы, потому что это будет полезно для дальнейшего обсуждения.
1. Обзор: полиномиальные схемы ввода-вывода + схемы полиномиальных обязательств = SNARK.
В SNARK, которые основываются на полиномиальных схемах ввода-вывода, доказывающий zkSNARK запускает эту полиномиальную схему. То же самое делает и проверяющий. Доказывающий создает какой-то многочлен, который вы фиксируете, используя полиномиальное обязательство, и отправляет его. Проверяющий запускает полиномиальную верификацию этого многочлена. Так может продолжаться в течение нескольких раундов. Затем наступает фаза очереди, в которой вы должны доказать, что вычисления зафиксированных многочленов, если их вычислить в порядке образовавшейся очереди, окажутся верными. Это общий обзор, который не нужно понимать досконально. Главное, что вы создаете полиномы и фиксируете их. Затем позже доказываете, что вычисления этих полиномов совпадают результатом с тем, что вы объявили ранее.
2. Строительный блок: Аддитивные Разделения Секрета
Следующий строительный блок, который мы затронем, это понятие об аддитивных тайных долях. Возможно вы слышали о схеме разделения секрета Шамира, наш блок - очень упрощенная его версия.
Вы можете взять сообщение и разделить его на m кусков таким образом, что до тех пор, пока у вас не будет всех m кусков, не происходит утечки информации. Даже в случае, если у вас не хватает только одного разделения для данного сообщения, вы не сможете узнать никакой информации о нем. С другой стороны, если у вас есть все m разделений, вы сможете соединить их обратно в одно сообщение.
Еще одно интересное для нас свойство, то, что называется гомоморфизм, или аддитивный гомоморфизм. Оно заключается в том, что, если у меня есть часть секрета а и часть секрета b, я могу сложить эти две части и получить кусок от секрета a+b.
Проблема №1: Соединять подсхемы дорого
Давайте приступим к решению наших проблем по порядку, начиная с проблемы соединения подсхем. Наша проблема заключается в том, что мы пытаемся представить доказывающего zkSNARK как монолитный объект и набросить на него протокол конфиденциального вычисления. Но на самом деле наш доказывающий zkSNARK имеет внутреннюю структуру. Давайте попытаемся воспользоваться этим. Мы получим преимущество от природы модели доказывающего, и вместо того, чтобы использовать монолитное конфиденциальное вычисление (MPC), мы построим протокол конфиденциального вычисления для делегирования только полиномиальной схемы ввода-вывода и соединим это с протокол MPC для делегирования схемы полиномиальных обязательств. Таким образом, мы получим протокол для делегирования zkSNARK. Это структура высшего уровня.
Посмотрим, как мы сможем воплотить это. Допустим, два блока слева даны нам по условию. Мы начинаем с того, что делегат отправляет разделения секрета свидетеля каждой из машин работников. Для примера возьмем всего две.
Машины берут кусочки секрета и запускают протокол конфиденциального вычисления для доказывающего в схеме полиномиального ввода-вывода, таким образом, получая разделения секрета первого полинома. Итак, это первый полином, созданный в первом раунде.
Затем они используют MPC для делегирования схем полиномиальных обязательств и получают куски зафиксированного полинома, полученного в первом раунде. И они могут повторять это действие снова и снова, также как и в стандартных SNARK. Они повторяют эти две операции по порядку снова и снова до тех пор, пока не получат векторы полиномов и векторы фиксаций, соответствующие каждому из раундов. После этого они могут приступить к этапу доказательства, чтобы создать доказательства решения этих фиксаций.
На выходе работники получают разделения финального доказательства zkSNARK: у них есть куски фиксаций, доказательства правильности вычислений и куски самих решений. Они отправляют все это обратно делегату, он объединяет все куски и восстанавливает доказательство zkSNARK, которое может использовать в любом приложении, в котором хочет.
Итак, это обзор компилятора, который использует эти две схемы делегирования для базовых компонентов. Теперь давайте посмотрим, как мы можем создать такие базовые схемы делегирования. И это подводит нас к решению проблему получения дешевых субкомпонентов.
Начнем с того, чтобы создать схемы делегирования для доказывающих в полиномиальных схемах ввода-вывода.
Мы хотим получить нечто, которое при получении части секрета о текущем состоянии доказывающего в конкретном раунде, будет возвращать нам полином этого раунда. Или же разделения секрета многочлена данного раунда. Перед тем, как мы сможем говорить о том, как ускорить этот процесс или как эффективно воплотить его в жизнь, нам нужно понять, какие операции на самом деле выполняют доказывающие в полиномиальных схемах ввода-вывода. И для всех интересующих нас SNARK это всего 4 операции:
- Мы хотим вычислить наш многочлен по какой-либо из подгрупп.
- Мы хотим разделить наш полином на некоторый исчезающий многочлен, принадлежащий к такой же подгруппе.
- Мы хотим провести несколько аффинных операций, например, сложение, вычитание, добавление константы и т.д.
- И, наконец, мы хотим выполнить умножение кусочков секретных полиномов.
К счастью, первые три действия могут быть выполнены с помощью линейных операций с нашими разделениями секретов полинома. Поэтому они не требуют никакого взаимодействия между работниками. Это очень эффективные действия, так как мы можем просто провести локальные операции с нашими полиномами и получить кусочки секрета этих результатов.
Но это не касается умножения полиномов. Чтобы умножить два многочлена, скажем, второй степени, нам нужно:
1. Использовать быстрое преобразование Фурье (FFT), чтобы получить значения этих полиномов в нашей подгруппе, в нашей области умножения, или же вычисления.
2. Провести поточечное умножение этих двух вычислений, а затем - обратное быстрое преобразование Фурье, чтобы получить интерполяцию.
3. Вернуться от этих вычислений к форме с коэффициентами.
Опять-таки, к счастью, первый и третий шаг - линейные действия. В них просто выполняется обратное преобразование Фурье, поэтому они не требуют никаких умножений секретов. Но, к сожалению для нас, второй шаг - это умножение двух частей секрета. К этим частях относится гомоморфизм, но не мультипликативный, это значит, что мы не можем просто умножить две части секрета и получить новую часть.
Для многих MPC эта проблема является камнем преткновения, обрабатывать умножения логических операторов ИЛИ-НЕ - это очень дорогая часть протоколов MPC.
Но, в нашем случае, у нас есть помощник! У нас есть делегат, поэтому, если у работников имеется части секрета, которые они хотят умножить, они могут отправить эти куски обратно делегату. Он может соединить эти части секрета, вычислить продукт, и отправить назад новые разделения продукта.
Таким образом, мы можем воспользоваться помощью делегата. Главная особенность заключается в том, что умножение полей обходится очень дешево. Мы не просим делегата провести масштабное умножение, это было бы дорого и сделало бы делегирование бессмысленным. Но подобные умножения полей выполняются за несколько наносекунд, они довольно-таки эффективны. Так мы можем использовать делегата, чтобы получить очень дешевое умножение полиномов всего с одним раундом взаимодействия с делегатом. В нашей работе приводятся и другие техники, которые вы можете использовать, в которых делегат даже не принимает участия в выполнении протокола. Вы можете просто заранее отправить некий предварительно обработанный материал, выйти из сети и потом получить доказательство.
Итак, это то, как мы можем очень эффективно выполнить 99% операций, которые происходят в современных проверяющих zkSNARK или схемах ввода-вывода.
Это, что касается первого компонента. А что насчет делегирования схем полиномиальных обязательств? Я буду рассматривать только KGZ10, потому что это самая популярная подобная схема. И помните, что мы хотим сделать две вещи: во-первых, получить разделение секрета многочлена и разделение секрета фиксации. А, во-вторых, имея часть секрета полинома и вычисление, мы хотим доказать, что зафиксированный многочлен на самом деле вычисляется так, как было заявлено.
Круто то, что схема коммиттера также линейно гомоморфная, поэтому фиксирование частей секрета полинома - это части фиксации полинома. Предположим, что вектор разделений имеет такую структуру. Тогда фиксация, или разделение фиксации - это стандартная вещь, которую вы бы сделали с KZG - вычисление многомасштабного умножения. То есть, по сути, нет никаких отличий с алгоритмом KZG.
То же самое происходит и тогда, когда мы хотим произвести доказательство правильности вычисления.
Вы вычисляете разделения полинома свидетеля, часть с коэффициентами на слайде, независимо от того, какое у вас выражение. Здорово то, что эта часть также не требует умножения секретов, это линейная операция. В общем, получается, что степень сложности находится на том же уровне, что и для стандартных KZG.
Таким образом, фиксация секретных разделения полинома и доказательство его вычисления - это одно и то же, нет никаких отличий.
Тонны дополнительной оптимизации!
В работе представлены еще тонны дополнительной оптимизации. Вы можете получить существенную выгоду от того, что у вас, в некотором смысле, есть доверенная третья сторона, которая выполняет несколько дорогих операций за вас. Поэтому, когда работа выйдет онлайн, я бы посоветовал вам ее прочитать! Мы рассматриваем оптимизацию со стороны крипто-техник также, как и со стороны систем. Так, будем надеяться, что мы решили обе представленные проблемы.
Но вопрос в том, действительно ли это улучшает показатели?
Сможете ли вы использовать эти протоколы и получить результат, выполнить их и ускорить свое приложение? К счастью, ответ - да!
Мы реализовали протоколы, используя Arkwork. Итак, мы получили протоколы делегирования для KZG, и мы также хотим реализовать их для схемы аргументов внутреннего продукта. Для полиномиальных схемах ввода-вывода Marlin это должно быть довольно просто - расширить их до таких вещей, как Plonk, любого варианта Plonk. Составляя все это вместе с нашим компилятором, мы получаем схему делегирования для zkSNARK Marlin.
Что касается конкретных показателей, мы проанализировали наши схемы в трех разных условиях:
- На ноутбуке с очень быстрым Интернет-соединением мы увидели уменьшение задержки в 9 раз по сравнению с обычным выполнением. Но гораздо интереснее два последние столбика. Первый говорит о том, как много времени делегат на самом деле тратит, активно вычисляя что-либо, по сравнению с тем, чтобы просто ждать, пока что-либо посчитается. В результате время активного вычисления снижается практически в 600 раз! Это огромная экономия энергии, в это время вы можете делать что угодно на своем компьютере. Другая польза состоит в том, что вы можете доказать гораздо более объемные экземпляры, затрачивая тот же объем памяти, что вы использовали бы, если бы доказывали локально. Показатель увеличился в 256 раз, то есть если на своем компьютере вы могли доказать что-то размером в миллион составляющих, теперь вы сможете провести вычисление в аутсорсинге и доказать схему размером в 256 миллионов, и это просто невероятно!
- Следующим условием был ноутбук со стандартным домашним соединением. Здесь результаты не столь впечатляющие из-за накладных коммуникаций, происходящих то в одну сторону, то в другую.
- И финальным экспериментом было использование мобильного телефона. Так как телефон намного быстрее, даже несмотря на медленный Интернет, мы все равно можем увидеть довольно-таки значительные улучшения показателей.
Окей, это и подводит итог моей презентации. Эта работа скоро будет опубликована, также как и код, будем надеяться!