Полностью приватные приложения: протокол ZEXE
Оригинал статьи: https://www.entropy1729.com/zexe/
Мой Discord: useless_dorozhkina#1394
Введение
Один из ключевых вопросов в современном мире заключается в том, как достичь согласия между сторонами, не доверяющими друг другу. Распределенные реестры стали популярными с момента появления криптовалют, построенных на технологии, известной как блокчейн. Одна из главных проблем заключается в том, что эти реестры не обеспечивают полную конфиденциальность и весьма ограничены в типе программ, которые они могут запускать. Aleo предоставляет full-stack подход для создания приватных приложений. Одним из его основных компонентов является протокол ZEXE, первая система реестра, в которой приложения могут выполняться конфиденциально, не требуя доверия, и могут быть легко масштабированы.
Как мы уже упомянули, системы, основанные на реестрах могут поддерживать насыщенные приложения, но часто страдают от двух основных недостатков:
- Проверка транзакции требует повторного выполнения перехода состояния, к которому она относится.
- Транзакции не являются приватными; они раскрывают информацию о пользователях и о состоянии системы.
Последнее создает огромное количество проблем там, где конфиденциальность имеет решающее значение, поскольку может произойти утечка информации, касающейся истории болезни, платежей, записей о знакомых и торговых партнерах и т.д., которая может быть использована в интересах злоумышленников.
Первый недостаток, с другой стороны, создает проблемы с масштабируемостью, поскольку каждый переход должен быть пересчитан каждым устройством (которые могут иметь очень разную вычислительную мощность), формирующим сеть, при этом самое слабое устройство действует как помеха. Это привело к внедрению таких механизмов, как gas, чтобы заставить пользователей платить больше за дорогостоящие вычисления и препятствовать атакам типа "отказ в обслуживании".
Некоторые протоколы, такие как ZeroCash, обеспечивают платежи с сохранением приватности, а Hawk позволяет осуществлять такие переходы между состояниями, что личные данные остаются скрытыми от третьих лиц. Можно сказать, что они обеспечивают конфиденциальность данных, но не конфиденциальность функций, потому что выполняемая функция перехода не скрыта (хотя входные и выходные параметры могут быть засекречены). Конфиденциальность функции означает, что наблюдатель не может отличить различные вычисления, выполняемые офлайн, друг от друга.
Цель ZEXE - предоставить масштабируемое решение этих проблем, при котором достигается приватность как данных, так и функций. Это может послужить прочной основой для новых форм обмена данными, финансовых систем и управления. Основные идеи основаны на следующем:
- Мы можем запускать программы офлайн (или делегировать их выполнение мощному, но ненадежному серверу) и получить доказательство, подтверждающее правильность вычислений.
- Мы можем быстро проверить правильность вычисления или перехода, проверив доказательство; эта операция будет менее дорогостоящей с точки зрения вычислений, чем выполнение всего вычисления.
- Переходы могут быть приняты в layer путем проверки доказательств.
Чтобы эта система работала, доказательства должны будут удовлетворять двум свойствам:
— Приватность: Доказательства не должны раскрывать ничего, кроме достоверности утверждения.
— Лаконичность: Доказательство может быть проверено за время, не зависящее от стоимости вычислений, правильность которых оно подтверждает.
ZEXE предложит пользователям богатый функционал офлайн вычислений, используемых для реализации переходов состояний нескольких приложений, работающих поверх одного реестра. Общая среда выполнения предоставляет следующие свойства:
— Расширяемость: пользователи могут запускать произвольные функции, не спрашивая ни у кого разрешения.
— Изоляция: функции злоумышленников не могут вмешиваться в вычисления и данные честных пользователей.
— Межпроцессное взаимодействие: функции могут обмениваться данными друг с другом.
В следующем разделе мы рассмотрим основные компоненты и то, как работает протокол: такие термины, как zk-SNARK, эллиптическая криптография, пары и т.д., будут объяснены.
Компоненты
Децентрализованные приватные вычисления
Основная часть ZEXE опирается на новый криптографический примитив для выполнения вычислений в реестре, известный как децентрализованные приватные вычисления (DPC), который расширяет идеи работы ZeroCash. Мы можем выполнить вычисления офлайн и предоставить доказательство, подтверждающее, что это был действительный переход в реестре; доказательство может быть быстро проверено нодами реестра (гораздо быстрее, чем потребовалось бы каждой из них, чтобы повторить наш первоначальный расчет) и принято. Недостатком является то, что, хоть доказательства и могут быть быстро проверены, их получение может быть довольно дорогостоящим (помните, что мы хотим позволить пользователю запускать произвольные программы; таким образом, система доказательства должна быть способна справляться со многими различными типами утверждений и инструкций). Мы можем улучшить эту конструкцию и сформировать делегируемые DPC: создать сервисы или устройства, не требующие доверия, которые будут выполнять вычисления и предоставлять нам доказательства того, что эти вычисления были выполнены как положено и без утечки существенной информации.
Составными элементами схем DPC являются:
— Хеш-функция, устойчивая к коллизиям.
— Семейство псевдослучайных функций.
— NIZK: не интерактивные аргументы знания с нулевым разглашением (доказательства).
Чтобы активировать делегируемые DPC, нам нужен дополнительный компонент: случайные подписи.
Записи
Когда в ZeroCash создаются монеты, их фиксации (1) публикуются в реестре; когда последние поглощаются, публикуется их серийный номер. Каждая транзакция сообщает о том, что некоторое количество "старых" монет было потрачено на создание "новых": транзакция имеет серийный номер потраченных монет, фиксации "новых" монет и доказательство того, что значения "старых" и "новых" монет суммируются (доказательство показывает, что это была верная транзакция и что никакие дополнительные деньги не были созданы или уничтожены во время обмена). Транзакция является приватной, потому что мы не знаем количества или адресов обмененных монет. Так как серийный номер публикуется, ни одна монета не может быть потрачена более, чем один раз.
Единица данных, называемые записями (монеты в ZEXE), привязаны к произвольным программам и определяют условия, при которых запись может быть создана и использована. Можно думать о них как о токенах или монетах, которые мы можем потратить на запуск программ и получение доказательств, что то, что мы сделали, верно (как в аркадных играх). Чтобы распространить эту идею на произвольные функции, можно думать о записи как о хранении полезной нагрузки произвольных данных. Фиксация записи публикуется каждый раз, когда запись создается, а ее серийный номер раскрывается при ее использовании. Транзакция в реестре содержит в себе информацию о созданных и использованных во время операции записях и доказательство того, что вызов функции для полезной нагрузки данных старой записи создает полезную нагрузку данных новых записей.
— Предикаты рождения и смерти.
— Нонс с серийным номером.
Фиксация записи - это фиксация по отношению ко всем вышеупомянутым атрибутам (открытому ключу, полезной нагрузке, предикатам рождения и смерти и серийному нонсу).
Наноядро Записей (The Record Nano Kernel, RNK)
Это среда выполнения, работающая с записями. Мы можем представить ее как некую операционную систему для реестра. Она обеспечивает изоляцию процессов, владение данными, обработку межпроцессных коммуникаций и т.д. RNK гарантирует, что предикаты рождения и смерти соблюдены, так что в течение срока службы записи применяются определенные ограничения. Иными словами, в зависимости от входных данных, предикаты могут решать, разрешены ли определенные взаимодействия с этой записью или нет.
Переходы и транзакции
В реестре транзакции содержат в себе следующую информацию:
- Серийный номер всех использованных во время транзакции записей.
- Фиксации всех записей, созданных в транзакции.
- Меморандум. Это строковый тип данных, связанный с транзакцией.
- Другую информацию, относящуюся к конкретной конструкции.
Недавно транзакции были обновлены и состоят из переходов. Иначе говоря, транзакция состоит из нескольких переходов.
zk-SNARK
Краткие не интерактивные аргументы знания с нулевым разглашением (для друзей просто zk-SNARK) - это криптографические примитивы, которые позволяют одной стороне (доказывающему) убедить другую сторону (проверяющего) в правильности определенного утверждения/вычисления. Они обладают следующими свойствами:
— Завершенность: Имея утверждение и свидетеля (например, я знаю такой x, что g^x =b), доказывающий может убедить честного проверяющего.
— Надежность: Злонамеренный доказывающий не может убедить проверяющего в ложном утверждении.
— Нулевое разглашение: Доказательство не раскрывает ничего, кроме достоверности утверждения; оно не раскрывает свидетеля.
— Краткость: Доказательство невелико и его "легко" проверить.
Учитывая то, что мы хотим предоставить пользователям возможность выполнять произвольные вычисления, нам нужно, чтобы система доказательства могла обрабатывать множество различных утверждений довольно общим способом; на это потребуются самые большие затраты в протоколе ZEXE. Эти утверждения относятся к классу NP (недетерминированное полиномиальное время): он включает в себя задачи, которые можно эффективно решить за полиномиальное время. Утверждения NP, которые нам нужно доказать, содержат определенные пользователем предикаты; они заставили бы нас создавать все на zk-SNARK для универсальных вычислений, требующих очень дорогих инструментов. Преимуществом zk-SNARK является то, что проверка выполняется за определенное времени; другими словами, количество времени, необходимое для проверки, не зависит от размера вычислений. Это свойство предпочтительно с точки зрения приватности, поскольку разное время проверки может намекать о том, какие операции выполняются.
Чтобы решить эту проблему, протокол полагается на рекурсивную композицию доказательств: вместо проверки произвольного утверждения NP мы можем проверить краткие доказательства, подтверждающие достоверность утверждения. Таким образом, мы можем отказаться от zk-SNARK для универсальных вычислений и вместо них сосредоточиться на кратких доказательствах, которые могут быть жестко закодированы в утверждении. Мы можем достичь цели, используя доказательства, несущие данные: добавив к сообщению краткое доказательство, подтверждающее непротиворечивый результат. Например, вместо того, чтобы непосредственно проверять предикаты рождения и смерти (которые могут быть довольно-таки общими), мы можем проверить краткие доказательства πb и πd, свидетельствующие об удовлетворении этих предикатов. Поскольку внутренние доказательства являются краткими, их проверка обходится (относительно) недорого. Более того, поскольку внешние доказательства — с нулевым разглашением (следовательно, не раскрывают ничего, что используется для создания доказательства), внутренние доказательства не обязательно должны быть с нулевым разглашением; это еще больше упрощает вычисления.
Мы можем свести любое NP-утверждение к эквивалентной NP-полной задаче, такой как раскраска графа или выполнимость булевой схемы. ZEXE доказывает правильность вычислений, преобразуя нашу произвольную программу в задачу выполнимости арифметической схемы, определенную в конечной области Fr. Возникает проблема, заключающаяся в том, что проверка доказательств включает в себя операции в области Fq, где r ≠ q. В принципе, возможно имитировать операции в Fq вместо Fr, но это довольно затратно и сделало бы всю систему обременительной. Альтернативой этому является работа с парой эллиптических кривых с некоторыми желаемыми свойствами; мы называем их эллиптическими кривыми, удобными для сопряжения.
Эллиптические Кривые, Удобные для Сопряжения.
С данной эллиптической кривой E, заданной в конечной области Fq, мы можем задать операцию над точками кривой таким образом, чтобы под этой операцией они образовывали группу. Порядок подгруппы G (то есть количество элементов) = r, где r ≠ q. Две кривые первого порядка E1 и E2 в областях Fq и Fr называются удобными для сопряжения, если размер области F одой кривой равняется порядку подгруппы другой, и наоборот.
Сопряжение эллиптических кривых — это функция e: G1 × G2 → GT, имеет билинейную форму. Здесь G1 и G2 — это группы на эллиптических кривых. Билинейная форма означает, что для двух заданных точек P1 и Q1 в G1 и P2 and Q2 в G2 выполняются следующие свойства (мы опишем все операции над группами в качестве дополнения):
Из соображений эффективности нам нужно, чтобы в обоих полях были подгруппы, порядки которых — большие степени 2. ZEXE использует кривую из семейства Barreto-Scott-Lynn, Ebls (со степенью встраивания(2) 12), который консервативно обеспечивает 128 бит безопасности. Подходящая для сопряжения кривая генерируется с помощью метода Cocks-Pinch, Ecp. Это очень трудоемкий шаг, поскольку он включает в себя изучение множества различных кривых, пока мы не найдем одну с желаемыми свойствами.
Учитывая, что базовая область Ecp больше, чем у Ebls, операции над первой обходятся дороже. Чтобы устранить этот недостаток, соотношение Re разделяется на два: Rbls и Rcp. Последнее из них отвечает за проверку доказательств удовлетворения предикатов, в то время как все остальные проверки зависят от кривой Ebls.
Фиксации и устойчивые к коллизиям хэш-функции могут быть выражены в виде эффективных арифметических схем для конструкций типа Pedersen над кривыми Эдвардса. Следовательно, две дополнительные кривые EEd,BLS и EEd,CP выбираются в областях Fr и Fq так, чтобы реализовать важные криптографические примитивы, такие как хеширование, фиксации и рандомизируемые подписи. Это позволяет нам уменьшить сложность многократных проверок равенств NP.
Выводы
ZEXE — это протокол, который был разработан, чтобы предоставить пользователям возможность выполнять произвольные программы через общедоступные ресстры без ущерба для конфиденциальности. На данный момент он устраняет два основных недостатка распределенных реестров: во-первых, вычисления могут выполняться офлайн, а доказательство правильности вычислений передается в реестр. Доказательство может быть быстро проверено, что позволяет избежать проблемы простого повторного выполнения и предоставляет масштабируемые решения. Во-вторых, это обеспечивает приватность как данных, так и функций: наблюдатели не могут получить информацию о данных, участвующих в вычислениях, и даже о том, какие конкретно функции вызываются.
Протокол вводит новые криптографические примитивы, такие как DPC и делегируемый DPC; последний позволяет пользователям с менее мощными устройствами (такими как смартфоны) передавать свои вычисления не вызывающим доверия сторонам и получать доказательства, которые показывают, что полученные результаты соответствуют правильному выполнению программы. Они поддерживаются zk-SNARK, полагаясь на пары эллиптических кривых и инструменты для преобразования произвольных программ в арифметическую схему, в которой мы можем проверить правильность вычислений.
Это основывает фундамент для полностью приватных приложений, становясь идеальной платформой для децентрализованных приложений, связанных, например, с финансами, играми, аутентификацией, управлением и многим другим.
Примечания
(1) Фиксация позволяет пользователю зафиксировать одно значение с возможностью последующего его раскрытия. Например, в ставке в рулетке, я мог бы поставить на "25" (если я очень уверен в себе) и зафиксировать это значение "25", связав себя с ним (хотя никто не мог знать заранее, что я выбрал 25, поскольку оно скрыто). Этого можно добиться, используя устойчивую к коллизиям хеш-функцию и публикуя полученный хеш (чтобы заставить его работать, нам нужно добавить что-то еще, в противном случае мы сможем хешировать все возможности и посмотреть, какая из них имеет соответствующий хеш). Если затем я попытаюсь изменить свою ставку, хеш не будет совпадать с моей первоначальной ставкой.
(2) Степень вложения эллиптической кривой в области Fq — это наименьшее положительное целое число k такое, что q^k − 1 делится на r, т.е. на порядок группы. Степень встраивания должна быть высокой, чтобы задачу дискретного логарифмирования было трудно решить. Однако, если k слишком велико, арифметика кривых становится заметно замедляется.