Предыстория и мотивация

Прежде чем мы начнем говорить об усовершенствованиях MPT, давайте сначала поговорим об основах проведения этого исследования.

Я учусь на докторскую степень и занимаюсь проектированием общественных сетей. В дополнение к основному консенсусному обновлению этой публичной цепочки: полезному доказательству работы, еще одной важной задачей является внедрение системы смарт-контрактов, совместимой с ETH. В настоящее время мы реализовали виртуальную машину на основе байт-кода Python, интегрировали ее в контрактную систему блокчейна и неожиданно сделали ее совместимой с Ethereum RPC. Мы использовали Python для создания смарт-контракта, соответствующего стандарту ERC20 для тестирования. Естественно, нам необходимо реализовать механизм данных KV, который может переносить десятки миллионов пользователей на нижний уровень исполнения контракта (аналогично Mapping в Solidity). используется для хранения каждого количества токенов под аккаунтом, таких аккаунтов могут быть сотни миллионов).

Далее, содержание работы по проектированию публичной сети естественным образом затрагивает такие концепции, как MPT и trie. Мы упомянули дизайн Ethereum, Threetrees, trie, MPT и т. д.

Найдите узкие места

К счастью, прежде чем мы были готовы реализовать смарт-контракт для вызова MPT, мы внезапно запустили простую программу тестирования дерева MPT на сервере AWS. После попытки использовать Trie и MPT для вставки объема данных в 100 миллионов КВ мы были очень удивлены, получив результат: производительность MPT-дерева на самом деле была настолько низкой.

Запустив следующий код, мы наблюдаем следующее: вставка 10 миллионов пар ключ-значение KV в Rocksdb занимает несколько минут для Trie и несколько часов для MPT. Когда мы увеличиваем объем тестовых данных до 100 миллионов, запуск программы вставки MPT занимает несколько дней. Это означает, что когда блокчейн использует структуру данных MPT для выполнения смарт-контрактов, скорость также будет сильно ограничена.

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

 test_mpt_write.py

 test_mpt_write.py

Я до сих пор помню, когда я впервые научился писать код, учителя рассказали нам основной принцип: программа = алгоритм + структура данных. Если мы ограничим структуру данных, то даже если мы отчаянно оптимизируем алгоритм (что часто требует нескольких лет академических усилий, и во многих случаях его практически невозможно улучшить), будет сложно преодолеть ограничения производительности текущего алгоритма. структура данных. Таким образом, очень академический план улучшения, поиск более эффективного алгоритма замены MPT, исследования может занять несколько лет. Как предшественник, работающий в этом направлении, Verkle Tree использует полиномиальные методы для оптимизации структуры данных блокчейна. Мы попробуем еще несколько уникальных и простых идей.

Если мы используем мышление на основе первых принципов, можем ли мы не использовать MPT? Если мы сможем обойти MPT и реализовать смарт-контракты непосредственно в Trie, больше не будет накладных расходов, вызванных MPT (первый принцип Ма Илуна: вещь, которая не существует, не будет иметь накладных расходов на производительность).

С точки зрения цены, наше недавно разработанное решение может быть несовместимо напрямую с существующим MPT, но, поскольку интерфейс Ethereum RPC не изменяется, большую часть существующей инфраструктуры Ethereum можно использовать повторно: например, Etherjs и MetaMask. Обход MPT относится к внутренней оптимизации структуры данных, которая представляет собой бесплатное исследование производительности блокчейна.

необходимые знания

Роксдб и Три

Дерево словаря Trie — это расширенная древовидная структура данных, упомянутая в учебниках для колледжей. В видео учителя Сяо MPT построен на основе дерева словаря Trie. Мы можем думать, что среда реализации Trie находится в памяти.

Однако в нашей разработке мы не можем напрямую использовать Trie для непосредственной реализации продукта, поскольку нам также необходимо сохранить данные на жестком диске. Этот шаг требует значительной инженерной оптимизации, поэтому мы обычно реализуем дерево MPT на основе Rocksdb.

Rocksdb — это ответвление FB с открытым исходным кодом, основанное на leveldb и использующее LSMT внизу (см. статью Дерево слияния с журнальной структурой). С абстрактной точки зрения мы можем думать о Rocksdb как об оптимизированном и постоянном словарном дереве.

Основное использование Rocksdb очень просто. В основном он использует три основные операции: получение данных и запрос по префиксу. Итерация.

государственная машина

Конечный автомат — это инструмент, который люди часто используют для моделирования блокчейнов. Он очень прост: добавьте входные данные к исходному состоянию, чтобы получить новое состояние.

Глобальное состояние Ethereum можно понимать как состояние конечного автомата. Например, в блоке 1 значения KV всех смарт-контрактов представляют собой глобальное состояние. Все транзакции в блоке выполняются EVM и их можно понять. в качестве конечного автомата. Входные данные, такие как вызов контракта Mint, приводят к изменению переменных Balance и Total контракта на 1000 в блоке 2.

Концепция конечного автомата, которую легко упустить из виду, называется функцией перехода состояний, которая определяет правила ввода. Когда входные данные необоснованны, входная информация будет отклонена. Например, когда мы пытаемся передать кому-то отрицательную сумму, такая транзакция не будет выполнена (конечно, глючный смарт-контракт может принять такую ​​транзакцию. В ETH функция перехода состояния может автоматически выполнить ее через Тьюринг -полное определение языка).

Введение в МПТ

Возможно, вы слышали о трех деревьях в Эфириуме: дереве транзакций, дереве статусов и дереве квитанций. Все это деревья MPT, полное имя которых — Меркл Патрисия Трис. Среди них дерево состояний, вероятно, является лучшим вариантом использования структуры данных MPT. Более подробную информацию можно найти в видеообъяснении Учителя Сяо.

Дерево MPT основано на структуре данных Trie и может вычислять все данные о состоянии в корневом хеше, таком как дерево Меркла, и помещать его в заголовок блока Ethereum. В заголовке блока Ethereum есть три корневых хеша деревьев MPT, которые мы обычно называем тремя деревьями.

Можно ли не размещать корень глобального состояния в заголовке блока? Да, транзакции помещаются в блоки Биткойн, а корень транзакции Меркла помещается в заголовок блока (используется дерево Меркла, но не используется MPT). Но у Биткойна нет смарт-контрактов, как у Эфириума, и нет концепции глобального состояния. Когда Ethereum изначально разработал блокчейн со смарт-контрактами, он отказался от конструкции блока Биткойна размером 1 М и UTXO, выбрал структуру данных MPT и модель учетной записи и использовал Gas для решения проблемы простоя, удовлетворяя потребности смарт-контрактов во время работы. Требования для глобальных. состояние.

Итак, какова цель использования MPT в Ethereum?

  1. Найдите соответствующее состояние блокчейна через корень Меркла в заголовке блока.

  2. Экономьте место, занимаемое повторяющимися данными.

  3. Правильное состояние можно проверить с помощью корневого хеша.

Первый момент — это жесткое требование: во время выполнения EVM необходимо считывать различные состояния. Если используется шаблон проектирования, аналогичный Bitcoin UTXO, необходимо отследить множество блоков, чтобы получить состояние баланса счета определенного пользователя. Использование MPT очень хорошо удовлетворяет этим потребностям.

Пункт 2: MPT экономит место, а состояние блокчейна можно рассматривать как огромный словарь. В каждом блоке обновляется лишь небольшая часть ключей, а большинство ключей по-прежнему сохраняют свои исходные значения. Используя дерево MPT, вы можете обновлять только те ключевые значения, которые необходимо обновить, не копируя неизмененное состояние в каждом блоке.

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

Выполнив пункты 1 и 2 без использования MPT, мы можем обойти накладные расходы MPT. Поэтому нам нужно разработать решение на основе Trie (можно понимать как Rocksdb) для хранения данных о состоянии блокчейна.

дизайн

В основном мы разрабатываем решение на основе Trie для хранения статуса в цепочке. Согласно основным принципам, если нет структуры данных MPT, для запуска MPT не требуются системные накладные расходы. Если система смарт-контрактов на основе Trie может быть реализована и работать правильно, это означает, что оптимизация завершена. На практике мы можем думать о Rocksdb как о Trie. Проще говоря, это высокопроизводительная база данных KV.

Используйте [globalstate as prefix_contract_address_variable name_block height_block hash] в качестве значения ключа базы данных KV, например, в следующем формате. Среди них 0x1 — адрес контракта, Total — имя переменной, 1 — высота блока и ABC1234 — хеш-значение блока (позже будет опущено).

globalstate_0x1_total_1_abc1234

В Ethereum Solidity переменные могут быть определены как Memory, Storage и Calldata. Мы в основном фокусируемся на типе Storage, поскольку он будет храниться в глобальном состоянии. В дополнение к простым переменным мы также рассматриваем сопоставление. Поскольку порядок величины пользователей в блокчейне является глобальным, сопоставление KV будет чрезвычайно большим. Кроме того, мы будем рассматривать такие типы данных, как Array, как простые структуры данных и напрямую хранить их в формате Json в Rocksdb. Когда мы кодируем, мы, естественно, должны оценить величину данных Value в структуре данных KV, чтобы выбрать подходящий метод хранения.

Переменные состояния хранения контракта

Как мы можем достичь первой и второй целей проектирования MPT без использования MPT?

Предположим, у нас есть переменная Total в контракте ERC20. Эта переменная будет меняться только тогда, когда общее количество токенов увеличивается (Mint) или уменьшается (Burn), но значение Total сохраняется, когда пользователь A переводит деньги (Transfer) пользователю B. постоянный.

Для простоты предположим, что адрес контракта равен 0x1. Когда высота блока равна 1, владелец контракта выполнил Mint 2000. На блоках высотой 2–8 пользователь совершил несколько передач. Текущая высота блока равна 9. .

На этом этапе нам нужно только запросить в базе данных ключ с префиксом [globalstate_0x1_total_]. Хотя наш текущий последний блок равен 9, поскольку переменная Total не изменилась в блоках 2-8, первым результатом приведенного выше запроса будет значение [globalstate_0x1_total_1], поэтому мы находим последнее значение переменной Total, Total переменная, которая изменилась в блоке 1.

В это время генерируется новый блок. Предположим, что пользователь выполняет Mint еще дважды в блоке 9 и блоке 11. Здесь мы находим особенность Rocksdb, если у нас есть следующий ключ.

globalstate_0x1_total_1 : 2000

globalstate_0x1_total_9 : 4000

globalstate_0x1_total_11 : 6000

Тогда первым результатом поиска всегда будет блок 1, а не самый последний блок 11. Поскольку мы еще не нашли в документации Rocksdb параметр для изменения порядка результатов поиска, мы применили небольшой трюк, используя большее число, например 100, чтобы вычесть высоту блока (на самом деле она будет намного больше) и дополнить ее. с нулями, поэтому последние блоки будут занимать первое место в результатах поиска.

globalstate_0x1_total_089 : 6000

globalstate_0x1_total_091: 4000

globalstate_0x1_total_099 : 2000

Тип сопоставления хранилища

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

Полагая, что адрес пользователя 0x2, немного расширяем предыдущий формат ключа хранилища:

[globalstate_0x1_[balance_0x2]_2] : 2000

Предыдущее [имя переменной] здесь было расширено до [имя переменной + ключ словаря сопоставления]

Приведенные выше данные показывают, что балансовый баланс пользователя 0x2 в высоте блока 2 равен 2000. Если нет обновленных данных для покрытия текущего баланса, то данные пользователя в блоке 2 представляют последний статус.

globalstate_0x1_balance_0x2_098 : 2000

globalstate_0x1_total_0x1_099 : 2000

Проверить блокировку

Как и корень дерева Меркла, корень дерева MPT также представляет собой проверку глобального состояния. Пока мы можем гарантировать согласованность данных блока, необходимость использования MPT и записи Root в заголовок блока является дизайнерским выбором.

Мы внесли некоторые улучшения в конструкцию блока, так что заголовок блока содержит два тела: одно — это блок данных транзакции, а другое — блок данных обновления статуса.

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

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

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

Предположим, что в мире существует 10 000 узлов. Когда мы бросаем игральную кость и устанавливаем вероятность выполнения транзакции в 1%, около 100 узлов будут выполнять транзакцию между блоками, а другие узлы будут полагаться на содержимое обновления статуса соединения. блок данных. Тогда эта область. Многие узлы в системе блокчейна смогут сохранить множество повторяющихся операций.

выполнить

Выполнив предыдущий дизайн, мы сразу приступили к реализации этой идеи.

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

Что касается компилятора, Solidity необходимо разработать специальный компилятор для преобразования исходного кода в байт-код EVM. Используя Python, вы можете легко преобразовать исходный код Python в байт-код PY с помощью этого превосходного инфраструктурного языка с тридцатилетней историей. Пользователи вряд ли заметят время компиляции.

Наш репозиторий кода виртуальной машины выглядит следующим образом. Каждый может высказать свое мнение и исправить потенциальные проблемы безопасности:

Ссылка: https://github.com/EcoPoW/python_stf_vm На втором этапе мы разработали версию ERC20 для Python, и код постоянно обновляется. В отличие от Solidity, мы не используем ключевые слова для определения того, как хранятся переменные, все локальные переменные находятся в памяти, и мы используем глобальные функции _get и _put для чтения и записи состояния. Ссылка: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

https://github.com/EcoPoW/BitPoW/blob/master/state.py

Внедрение и улучшение

От постановки вопросов до проектирования и реализации кода у нас ушло около двух месяцев.

После целого лета разработки + фактического кодирования новая система смарт-контрактов, которая использует только словарное дерево Trie, не полагаясь на структуру данных MPT, готова к запуску (вы можете попробовать запустить тестовый узел локально через клон Github). Обход хранилища смарт-контрактов на основе MPT означает, что при достаточной пропускной способности время синхронизации узла размером 100 миллионов КВ можно сократить с нескольких дней до нескольких минут. Эффективность выполнения смарт-контрактов также станет выше, и больше вычислений, потребляемых ЦП, будет использоваться для выполнения байт-кода вместо хэш-операций, необходимых для построения дерева Меркла. Нам повезло, что при реализации смарт-контрактов в проекте мы не следовали напрямую «отраслевому стандарту». Вместо этого мы сначала попробовали оптимизацию и вычитание и получили блокчейн смарт-контракта с правильной «структурой данных». Потому что в отличие от продуктов Web2, которые мы сравниваем со сменой шин во время вождения автомобиля, блокчейн Web3 больше похож на запуск ракеты. Трудно внести серьезные структурные улучшения в работающий блокчейн, поэтому мы можем только улучшить «следующую» систему и быть полностью готовыми к выходу в Интернет.

В настоящее время развернута тестовая сеть Testnet2 разработанного нами блокчейна BitPoW. Каждый может использовать MetaMask для подключения к этому блокчейну через RPC для тестирования и опробовать передачу ERC20 на основе виртуальной машины Python. В то же время нам еще предстоит проделать много работы, и нам все еще нужно полагаться на сообщество в продвижении этой новой инфраструктуры блокчейна.

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

Подвести итог

До сих пор мы обходили MPT и разработали решение для хранения смарт-контрактов, основанное непосредственно на Trie. В настоящее время мы реализуем это улучшение в блокчейне на основе виртуальной машины Python в качестве доказательства осуществимости. Нам потребовалось около трех месяцев от обнаружения проблемы до предложения решения и его реализации в коде. Но что еще важнее в этом исследовании, так это то, что, как и многие обычные люди, после изучения знаний MPT в классе, мы больше не думали. улучшая его. Решение несложное, но требует практики и действий. Решение несложное, но требует практики и действий. Только активно думая на практике, мы можем найти вдохновение и внедрять инновации. Я очень благодарен LXDAO за поддержку этого исследования и надеюсь встретить больше друзей в сообществе, которые интересуются нижним слоем блокчейна. Отрасль еще очень молода, а инфраструктура еще далека от зрелости. Мы надеемся способствовать популяризации основных знаний о блокчейне, чтобы больше людей могли участвовать в авангарде технологических инноваций.