a16z: Почему блокчейны без сохранения состояния не могут существовать

Автор: Миранда Крист (аспирантка по информатике в Колумбийском университете/стажер по исследованию шифрования a16z), Джозеф Бонно (a16zcrypto) Источник: a16z crypto, составитель: Ивонн, MarsBit

Поскольку блокчейн поддерживает больше пользователей и более частые транзакции, объем информации («состояния»), хранимой валидаторами для проверки транзакций, растет. Например, в Биткойне состояние состоит из набора неизрасходованных выходов транзакций (utxo). В Ethereum состояние состоит из баланса каждой учетной записи, а также кода и хранилища каждого смарт-контракта.

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

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

государство без гражданства

Сегодня размер государства велик, но управляем. Например, узел Биткойн хранит около 7 ГБ данных, а узел Эфириума — около 650 ГБ данных. Однако нагрузка на хранилище на полных узлах масштабируется примерно линейно в зависимости от пропускной способности цепочки (транзакций в секунду или TPS), которая в настоящее время неприемлемо низка. Согласно нынешнему проекту, состояние, необходимое для реальной поддержки ежедневных транзакций (от сотен тысяч до миллионов TPS), станет неуправляемым, требующим использования нескольких терабайт или даже петабайт дискового пространства.

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

Несмотря на большое количество исследований блокчейнов без сохранения состояния (например, Тодд, Бутерин, Бонех и др., Сринивасан и др.), они далеки от практичности, и, насколько нам известно, ни один из них не был развернут. Фундаментальная проблема всех известных блокчейнов без сохранения состояния заключается в том, что они требуют от пользователей хранить дополнительные данные, называемые свидетелями, чтобы помочь валидаторам проверять транзакции с участием их учетных записей. Например, этот свидетель может быть доказательством включения Merkle, показывающим, что учетная запись пользователя и ее баланс включены в глобальное государственное обязательство. Когда пользователь совершает транзакцию, он передает это свидетельство валидатору, показывая, что на его счету имеется достаточный баланс.

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

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

Исследование

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

Сначала мы строим дерево Меркла, в котором каждая пара (идентификатор счета, баланс) (a, b) включена в качестве листа. Состояние V постоянного размера, хранимое валидаторами, является корнем этого дерева, которое действует как обязательство для набора пар балансов счетов. Каждый пользователь сохраняет свое подтверждение Merkle о включении пары (идентификатор счета, баланс) в качестве свидетеля. Доказательство Меркла включения листа ( a , b ) состоит из узлов-партнеров ( v 1 , …, vk ) на пути к корню дерева. Учитывая транзакцию пользователя, использующего учетную запись a и требующего баланса b, валидатор может проверить, что b действительно является балансом учетной записи a, проверив, что (a, b) подтверждает (v 1 , …, vk ) с его текущим состоянием V . Если это так, валидатор выполнит транзакцию и должен соответствующим образом обновить баланс счета. Удобным свойством деревьев Меркла является то, что, учитывая доказательство содержания Меркла для листа, легко вычислить результирующий корень при изменении этого листа. Другими словами, валидатор может легко вычислить обновленное состояние V', которое фиксирует новый баланс счета a после выполнения транзакции.

Подход с использованием дерева Меркла имеет два основных недостатка. Во-первых, количество пользователей-свидетелей относительно велико и растет логарифмически по отношению к общему количеству учетных записей в системе. В идеале они должны иметь постоянный размер, чего мы можем достичь, используя такие схемы, как аккумуляторы RSA (Boneh и др. в контексте блокчейнов без сохранения состояния).

Второго недостатка избежать труднее: всякий раз, когда другие пользователи совершают транзакцию, подтверждение пары «счет-баланс» меняется. Напомним, что доказательство листа состоит из узлов-партнеров на пути от этого листа к корню дерева. Если изменяется какой-либо другой лист, изменяется один из этих узлов, что приводит к проблемам на практике. Большинство пользователей блокчейна хотят пассивно хранить свои монеты в кошельке, входя в систему только тогда, когда они хотят совершить транзакцию. Однако в практике этого блокчейна без сохранения состояния пользователи должны постоянно отслеживать транзакции других людей, чтобы держать своих свидетелей в курсе событий. (Хотя третьи лица могут осуществлять этот мониторинг от имени пользователей, это отличается от стандартной модели блокчейна без сохранения состояния. Мы обсудим этот вопрос в конце этой статьи.) Фактически, это проблема для блокчейнов без сохранения состояния. ложится тяжелым бременем на пользователей.

Наш вывод: безгражданство невозможно

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

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

В основе нашего доказательства лежит теоретико-информационный аргумент. Центральный принцип теории информации, предложенный Клодом Шенноном, заключается в том, что если Алиса случайным образом выбирает объект из набора размером 2n и желает сообщить Бобу, какой объект она выбрала, она должна послать ему как минимум n битов. Если существует схема блокчейна без сохранения состояния, в которой пользователи редко обновляют свои свидетели, то Алиса может сообщить Бобу, какой объект она выбрала, менее чем за n битов — Шеннон доказывает, что это невозможно. Следовательно, такой блокчейн без сохранения состояния не может существовать.

Для простоты мы опишем здесь доказательство несколько более слабого утверждения: не может быть блокчейна без сохранения состояния, в котором пользователям никогда не нужно обновлять свои свидетели. Ключевая идея заключается в том, что Алиса кодирует свое сообщение Бобу, используя схему блокчейна без сохранения состояния. Изначально и Алиса, и Боб знают полные пары балансов счетов для всех n пользователей. Предположим, что на каждой учетной записи есть хотя бы одна монета. И Алиса, и Боб также знают краткое состояние V блокчейна без сохранения состояния и свидетелей wi для всех пар балансов счетов (ai, bi). Алиса и Боб также договариваются о сопоставлении сообщений и наборов учетных записей. Алиса выберет набор учетных записей A, соответствующих ее сообщению, и потратит токены с этих учетных записей. Она будет использовать блокчейн без сохранения состояния для связи с Бобом с набором, который она выберет, и из этого набора он сможет узнать, каковы ее сообщения.

Кодирование: Алиса тратит по одному жетону с каждого аккаунта А. Используя схему блокчейна без сохранения состояния, Алиса вычисляет обновленное состояние V' и отправляет V' Бобу.

Декодирование: для каждого i Боб проверяет, есть ли Verify(wi, (ai, bi)). Боб выводит набор учетных записей B такой, что Verify(wi, (ai, bi)) = false.

Боб успешно выводит тот же набор, который выбрала Алиса: B = A. Во-первых, обратите внимание, что если Алиса потратила один токен со счета ai, больше не должно приниматься никаких свидетелей ее старого баланса — в противном случае Алиса сможет удвоить трату. Следовательно, для каждой учетной записи ai в A Verify(wi, (ai, bi)) = false, и Боб включит эту учетную запись в B. С другой стороны, Боб никогда не включит в B учетную запись, идентифицированную Алисой. Нет возможности потратить монету, потому что балансы этих счетов остаются прежними, и (вспомните расплывчатое утверждение, которое мы пытались доказать) их свидетели никогда не меняются. Следовательно, B в точности равен A.

Наконец, противоречие разрешается путем вычисления количества битов, которые Алиса должна отправить Бобу. Она может выбрать 2n возможных подмножеств учетных записей, и согласно закону Шеннона она должна отправить Бобу не менее n битов. Однако она отправляет только состояние V' постоянного размера, намного короче n бит.

(Читатели, знакомые с криптографией, могут заметить, что мы здесь умалчиваем некоторые детали; например, декодирование Боба не удается с пренебрежимо малой вероятностью. В нашей статье содержится полное доказательство.)

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

ВЛИЯНИЕ РЕЗУЛЬТАТОВ

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

Некоторые потенциальные решения действительно существуют, но они отходят от строго модели блокчейна без сохранения состояния. Эта модель позволяет третьей стороне (ни пользователю, ни валидатору) нести ответственность за хранение полного состояния. Эта сторона называется узлом службы проверки (с наиболее строгими проверками Шринивасана и др.) и использует полное состояние для создания актуальных свидетелей от имени пользователей. Затем пользователи могут использовать этих свидетелей для транзакций, как в обычном блокчейне без сохранения состояния, где валидаторы по-прежнему хранят только компактное состояние. Механизм стимулирования системы, особенно то, как пользователи компенсируют узлы доказательства обслуживания, является интересным открытым направлением исследований.

Хотя до сих пор наше обсуждение было сосредоточено на блокчейнах L1, наши результаты также имеют значение для систем L2, таких как серверы объединения. Свертывание (оптимистическое или ZK) обычно принимает большое состояние и фиксирует его с использованием небольшого значения, хранящегося в L1. Это состояние включает в себя учетную запись каждого пользователя на уровне L2. Мы хотим, чтобы эти пользователи могли выводить средства непосредственно на L1 (без сотрудничества с серверами L2), опубликовав свидетельство баланса своего текущего счета. Эта установка также является примером обратимой системы доказательства в нашей модели. Фактически, можно утверждать, что блокчейны без сохранения состояния уже реализованы на практике в виде объединений L2.

К сожалению, это означает, что наши результаты о невозможности применимы напрямую. Свидетель вывода накопительного пакета пользователя должен часто меняться, иначе почти все состояние L2 пришлось бы записывать в L1. В результате сегодня коллекции обычно предполагают наличие комитета по доступности данных (иногда называемого «комитетом по достоверности»), который функционирует как «узел службы проверки», который помогает пользователям вычислить новых свидетелей, когда они готовы выйти. Наши результаты показывают, что предупреждения для пользователей в документации Ethereum — «Без доступа к данным транзакций пользователи не могут вычислить доказательства Меркла, необходимые для доказательства владения средствами и выполнения вывода средств» — будут применяться всегда.

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