Деревья Меркла в Эфириуме

Деревья Меркла — основа блокчейна Эфириума. Хотя теоретически возможно создать блокчейн и без них, просто добавляя в него заголовки блоков со всеми данными транзакций, такой блокчейн масштабировался бы настолько плохо, что через сравнительно небольшое время обрабатывать его смогли бы только мощные суперкомпьютеры. Благодаря деревьям Меркла узлы Эфириума могут работать на домашних компьютерах, ноутбуках, смартфонах и даже устройствах IoT, в том числе тех, которые в скором времени выведет на рынок компания Slock.it. Как же работают деревья Меркла и чем они полезны?

Для начала давайте разберемся с основами. В самом общем смысле дерево Меркла — это структура данных, которая хеширует большое количество элементов данных (chunk). Для этого несколько элементов объединяются в блоки (bucket), эти блоки хешируются, получившиеся в результате хеши объединяются в новые блоки и т. д., пока в итоге мы не получаем один-единственный корневой хеш.

Чаще всего используется простейшее дерево Меркла — двоичное. В нем каждый блок содержит два хеша:

В чем же преимущества такого необычного алгоритма хеширования? Почему бы нам не объединить все элементы в один большой блок и не хешировать сразу все данные? Потому, что дерево Меркла делает возможными так называемые доказательства Меркла (Merkle proof).

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

Доказательства Меркла в Биткойне

Как многие уже догадались, Сатоши Накамото использовал доказательства Меркла в Биткойне для сохранения сведений о транзакциях в блоках.

Эта схема используется для упрощенной верификации платежей (SPV): вместо того чтобы скачивать все транзакции и все блоки, «облегченный» клиент может скачать лишь цепочку заголовков блоков, каждый из которых содержит всго 80 байтов:

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

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

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

Доказательства Меркла в Эфириуме

Каждый заголовок блока в Эфириуме содержит не одно, а целых три дерева Меркла для объектов трех разных типов:

• транзакции;
• квитанции (по сути, данные о результатах выполнения каждой транзакции);
• состояния.

Это позволило создать улучшенный протокол для облегченных клиентов, благодаря которому они могут легко получать ответы на многие нетривиальные запросы:

• Содержится ли данная транзакция в конкретном блоке?
• Сколько событий данного типа (например, успешных окончаний краудфандинг-кампаний) было сгенерировано данным адресом за последние 30 дней?
• Каков текущий баланс моего счета?
• Существует ли данный счет?
• Каким будет результат выполнения этой транзакции для данного контракта?

Ответ на первый запрос можно получить с помощью дерева транзакций, на третий и четвертый — с помощью дерева состояний, а на второй — с помощью дерева квитанций.

Пятый запрос также обрабатывается с помощью дерева состояний, но несколько сложнее. В этом случае нам нужна конструкция, которую можно назвать Меркл-доказательством изменения состояния. По сути, это доказательство того, что «если выполнить транзакцию T в состоянии с корнем S, результатом будет состояние с корнем S’, протоколом (log) L и выводом O» (теоретически «вывод» не требуется, но в Эфириуме он имеет место, потому что каждая транзакция представляет собой вызов функции).

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

Префиксное дерево

Выше было сказано, что простейшим деревом Меркла является двоичное, но в Эфириуме используются его более сложная разновидность — префиксное дерево Меркла (Merkle Patricia tree). Здесь я опишу только основы, а подробности вы можете найти в этой и этой статьях.

Двоичные деревья Меркла хороши для проверки информации, представленной в виде списка, — по сути, последовательности элементов. Они неплохо подходят и для представления деревьев транзакций, потому что редактировать их не нужно: как только дерево транзакций создано, оно остается таким навсегда.

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

{
    "0000000000000000000000000000000000000001": {
        "balance": "1"
    },
    "0000000000000000000000000000000000000002": {
        "balance": "1"
    },
    "0000000000000000000000000000000000000003": {
        "balance": "1"
    },
    "0000000000000000000000000000000000000004": {
        "balance": "1"
    },
    "102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
        "balance": "160693804425...993782792835301376"
    }
}

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

• Глубина дерева должна быть ограниченной из-за угрозы того, что злоумышленник может попытаться создать как можно более глубокое дерево для проведения DoS-атаки (чтобы каждое обновление дерева занимало много времени).
• Корень дерева должен зависеть только от данных, но не от порядка выполнения обновлений. Применение обновлений в другом порядке и даже пересчет дерева с нуля не должны изменять корень.

Префиксное дерево — это структура данных, которая, похоже, лучше всего соответствует описанным критериям. В таком дереве ключ, по которому хранится значение, кодируется в виде ветви дерева. У каждого узла есть 16 дочерних узлов, что позволяет кодировать ключи в шестнадцатеричной системе счисления. Например, ключ dog, которому соответствуют ASCII-коды 64, 6F и 67, определяет ветвь «корень, 6-й дочерний узел, 4-й дочерний узел и т. д.» вплоть до значения — «листа» ветви. На практике дерево с «редкой кроной» можно оптимизировать, но вдаваться в эту тему мы не будем. Если вас интересуют подробности, см. две указанных выше статьи.

Источник: blog.ethereum.org

Виталик Бутерин

• Эфириум
• Ethereum