Сценарист: Миранда Крист, Джозеф Бонно

Составил: Shenchao TechFlow

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

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

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

апатрид

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

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

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

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

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

Предыстория нашего исследования

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

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

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

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

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

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

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

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

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

Кодировка: Алиса тратит по одной монете с каждого счета в A. Используя схему блокчейна без сохранения состояния, Алиса вычисляет обновленное состояние 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, таких как серверы Rollup. Накопительные пакеты (оптимистические или ZK) обычно хранят на L1 большое обещание состояния с небольшим значением. Это состояние включает учетную запись каждого пользователя на уровне L2. Мы хотим, чтобы эти пользователи могли выводить средства непосредственно на L1 (без сотрудничества с серверами L2), опубликовав свидетельство баланса своего текущего счета. Эта установка также является примером системы отзывных доказательств в нашей модели. Фактически, можно сказать, что блокчейны без сохранения состояния уже реализованы на практике в форме L2 Rollup.

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