a16z: О невозможности «блокчейна без гражданства»

Первоначально написано Мирандой Крист и Джозефом Бонно.

Компиляция оригинального текста: Deep Tide TechFlow

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

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

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

нет положения

Сегодня государство огромно, но управляемо. Например, узел Bitcoin хранит около 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.

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

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

Влияние результата

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

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

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

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