Дерево Меркла-Патрісії

Стан Етеріуму (сукупність усіх акаунтів, балансів та смарт-контрактів) кодується у спеціальну версію структури даних, загальновідому в інформатиці як дерево Меркла. Ця структура корисна для багатьох застосувань у криптографії, оскільки вона створює зв'язок, який можна перевірити, між усіма окремими частинами даних, пов'язаними в дереві, що в результаті дає єдине кореневе значення, яке можна використовувати для доведення фактів про дані.

Структура даних Етеріуму — це «модифіковане дерево Меркла-Патрісії», назване так тому, що воно запозичує деякі функції PATRICIA (Practical Algorithm To Retrieve Information Coded in Alphanumeric — практичний алгоритм для пошуку інформації, закодованої в алфавітно-цифровому вигляді), і тому, що воно розроблене для ефективного пошуку (retrieval) елементів даних, які складають стан Етеріуму.

Дерево Меркла-Патрісії є детермінованим і криптографічно перевірюваним: єдиний спосіб згенерувати корінь стану — це обчислити його з кожної окремої частини стану, і ідентичність двох станів можна легко довести, порівнявши кореневий хеш і хеші, які до нього призвели (доказ Меркла). І навпаки, неможливо створити два різні стани з однаковим кореневим хешем, і будь-яка спроба змінити стан іншими значеннями призведе до іншого кореневого хешу стану. Теоретично ця структура забезпечує «Святий Грааль» ефективності O(log(n)) для вставок, пошуку та видалень.

У найближчому майбутньому Етеріум планує перейти на структуру дерева Веркла, що відкриє багато нових можливостей для майбутніх покращень протоколу.

Передумови

Для кращого розуміння цієї сторінки було б корисно мати базові знання про хеші (opens in a new tab), дерева Меркла (opens in a new tab), префіксні дерева (opens in a new tab) та серіалізацію (opens in a new tab). Ця стаття починається з опису базового radix-дерева (opens in a new tab), а потім поступово вводить модифікації, необхідні для більш оптимізованої структури даних Етеріуму.

Базові radix-дерева

У базовому radix-дереві кожен вузол виглядає так:

[i_0, i_1 ... i_n, value]

Де i_0 ... i_n представляють символи алфавіту (часто двійкові або шістнадцяткові), value — це кінцеве значення у вузлі, а значення у слотах i_0, i_1 ... i_n є або NULL, або вказівниками на (у нашому випадку хешами) інші вузли. Це формує базове сховище (key, value).

Припустімо, ви хочете використати структуру даних radix-дерева для збереження порядку над набором пар ключ-значення. Щоб знайти значення, яке наразі зіставлено з ключем dog у дереві, ви спочатку перетворюєте dog на літери алфавіту (отримуючи 64 6f 67), а потім спускаєтеся по дереву цим шляхом, доки не знайдете значення. Тобто ви починаєте з пошуку кореневого хешу в плоскій базі даних ключ/значення, щоб знайти кореневий вузол дерева. Він представлений як масив ключів, що вказують на інші вузли. Ви використовуєте значення за індексом 6 як ключ і шукаєте його в плоскій базі даних ключ/значення, щоб отримати вузол на один рівень нижче. Потім вибираєте індекс 4, щоб знайти наступне значення, потім вибираєте індекс 6 і так далі, доки, пройшовши шлях: root -> 6 -> 4 -> 6 -> 15 -> 6 -> 7, ви не знайдете значення вузла і не повернете результат.

Існує різниця між пошуком чогось у «префіксному дереві» та базовій плоскій «БД» ключ/значення. Обидві вони визначають структуру ключ/значення, але базова БД може виконувати традиційний пошук ключа за 1 крок. Пошук ключа в префіксному дереві вимагає кількох пошуків у базовій БД, щоб дістатися до кінцевого значення, описаного вище. Назвемо останнє path, щоб усунути неоднозначність.

Операції оновлення та видалення для radix-дерев можна визначити так:

    def update(node_hash, path, value):
        curnode = db.get(node_hash) if node_hash else [NULL] * 17
        newnode = curnode.copy()
        if path == "":
            newnode[-1] = value
        else:
            newindex = update(curnode[path[0]], path[1:], value)
            newnode[path[0]] = newindex
        db.put(hash(newnode), newnode)
        return hash(newnode)

    def delete(node_hash, path):
        if node_hash is NULL:
            return NULL
        else:
            curnode = db.get(node_hash)
            newnode = curnode.copy()
            if path == "":
                newnode[-1] = NULL
            else:
                newindex = delete(curnode[path[0]], path[1:])
                newnode[path[0]] = newindex

            if all(x is NULL for x in newnode):
                return NULL
            else:
                db.put(hash(newnode), newnode)
                return hash(newnode)

Radix-дерево «Меркла» будується шляхом зв'язування вузлів за допомогою детерміновано згенерованих криптографічних хеш-дайджестів. Ця контентна адресація (у БД ключ/значення key == keccak256(rlp(value))) забезпечує криптографічну гарантію цілісності збережених даних. Якщо кореневий хеш певного дерева є загальновідомим, то будь-хто, хто має доступ до базових даних листків, може побудувати доказ того, що дерево містить певне значення за певним шляхом, надавши хеші кожного вузла, що з'єднує певне значення з коренем дерева.

Зловмисник не може надати доказ неіснуючої пари (path, value), оскільки кореневий хеш зрештою базується на всіх хешах під ним. Будь-яка базова модифікація змінить кореневий хеш. Ви можете думати про хеш як про стиснене представлення структурної інформації про дані, захищене властивістю стійкості до знаходження першовзору (pre-image resistance) функції хешування.

Ми будемо називати атомарну одиницю radix-дерева (наприклад, один шістнадцятковий символ або 4-бітне двійкове число) «ніблом» (nibble). Під час проходження шляху по одному ніблу за раз, як описано вище, вузли можуть максимально посилатися на 16 нащадків, але включають елемент value. Тому ми представляємо їх як масив довжиною 17. Ми називаємо ці 17-елементні масиви «вузлами розгалуження» (branch nodes).

Дерево Меркла-Патрісії

Radix-дерева мають одне суттєве обмеження: вони неефективні. Якщо ви хочете зберегти одну прив'язку (path, value), де шлях, як в Етеріумі, має довжину 64 символи (кількість ніблів у bytes32), нам знадобиться понад кілобайт додаткового простору для зберігання одного рівня на символ, і кожен пошук або видалення займе повні 64 кроки. Дерево Патрісії, представлене нижче, вирішує цю проблему.

Оптимізація

Вузол у дереві Меркла-Патрісії є одним із наступних:

NULL (представлено як порожній рядок)
branch 17-елементний вузол [ v0 ... v15, vt ]
leaf 2-елементний вузол [ encodedPath, value ]
extension 2-елементний вузол [ encodedPath, key ]

Зі шляхами довжиною 64 символи неминуче, що після проходження перших кількох рівнів дерева ви досягнете вузла, де немає розбіжних шляхів принаймні на частині шляху вниз. Щоб уникнути створення до 15 розріджених вузлів NULL вздовж шляху, ми скорочуємо спуск, встановлюючи вузол extension у формі [ encodedPath, key ], де encodedPath містить «частковий шлях» для пропуску вперед (використовуючи компактне кодування, описане нижче), а key призначений для наступного пошуку в БД.

Для вузла leaf, який може бути позначений прапорцем у першому ніблі encodedPath, шлях кодує всі фрагменти шляху попереднього вузла, і ми можемо шукати value безпосередньо.

Однак ця оптимізація вносить неоднозначність.

Під час проходження шляхів у ніблах ми можемо отримати непарну кількість ніблів для проходження, але оскільки всі дані зберігаються у форматі bytes. Неможливо розрізнити, наприклад, нібл 1 та нібли 01 (обидва мають зберігатися як <01>). Щоб вказати непарну довжину, до часткового шляху додається префікс із прапорцем.

Специфікація: Компактне кодування шістнадцяткової послідовності з необов'язковим термінатором

Позначення як непарної чи парної довжини часткового шляху, що залишився, так і вузла-листка чи вузла розширення, як описано вище, знаходиться в першому ніблі часткового шляху будь-якого 2-елементного вузла. Вони призводять до наступного:

шістнадцятковий символ	біти	тип вузла	довжина шляху
0	0000	розширення	парна
1	0001	розширення	непарна
2	0010	кінцевий (листок)	парна
3	0011	кінцевий (листок)	непарна

Для парної довжини шляху, що залишився (0 або 2), завжди слідуватиме ще один «заповнюючий» (padding) нібл 0.

    def compact_encode(hexarray):
        term = 1 if hexarray[-1] == 16 else 0
        if term:
            hexarray = hexarray[:-1]
        oddlen = len(hexarray) % 2
        flags = 2 * term + oddlen
        if oddlen:
            hexarray = [flags] + hexarray
        else:
            hexarray = [flags] + [0] + hexarray
        # Тепер hex-масив має парну довжину, де перший напівбайт — це прапорці.
        o = ""
        for i in range(0, len(hexarray), 2):
            o += chr(16 * hexarray[i] + hexarray[i + 1])
        return o

Приклади:

    > [1, 2, 3, 4, 5, ...]
    '11 23 45'
    > [0, 1, 2, 3, 4, 5, ...]
    '00 01 23 45'
    > [0, f, 1, c, b, 8, 10]
    '20 0f 1c b8'
    > [f, 1, c, b, 8, 10]
    '3f 1c b8'

Ось розширений код для отримання вузла в дереві Меркла-Патрісії:

    def get_helper(node_hash, path):
        if path == []:
            return node_hash
        if node_hash == "":
            return ""
        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
        if len(curnode) == 2:
            (k2, v2) = curnode
            k2 = compact_decode(k2)
            if k2 == path[: len(k2)]:
                return get(v2, path[len(k2) :])
            else:
                return ""
        elif len(curnode) == 17:
            return get_helper(curnode[path[0]], path[1:])

    def get(node_hash, path):
        path2 = []
        for i in range(len(path)):
            path2.push(int(ord(path[i]) / 16))
            path2.push(ord(path[i]) % 16)
        path2.push(16)
        return get_helper(node_hash, path2)

Приклад дерева

Припустімо, ми хочете дерево, що містить чотири пари шлях/значення: ('do', 'verb'), ('dog', 'puppy'), ('doge', 'coins'), ('horse', 'stallion').

Спочатку ми перетворюємо як шляхи, так і значення на bytes. Нижче фактичні байтові представлення для шляхів позначені як <>, хоча значення все ще показані як рядки, позначені як '', для полегшення розуміння (вони також насправді були б bytes):

<64 6f> : 'verb'
    <64 6f 67> : 'puppy'
    <64 6f 67 65> : 'coins'
    <68 6f 72 73 65> : 'stallion'

Тепер ми будуємо таке дерево з наступними парами ключ/значення в базовій БД:

rootHash: [ <16>, hashA ]
    hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, [ <20 6f 72 73 65>, 'stallion' ], <>, <>, <>, <>, <>, <>, <>, <> ]
    hashB:    [ <00 6f>, hashC ]
    hashC:    [ <>, <>, <>, <>, <>, <>, hashD, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
    hashD:    [ <17>, [ <>, <>, <>, <>, <>, <>, [ <35>, 'coins' ], <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ] ]

Коли один вузол посилається всередині іншого вузла, включається keccak256(rlp.encode(node)), якщо len(rlp.encode(node)) >= 32, інакше node, де rlp.encode — це функція кодування RLP.

Зверніть увагу, що під час оновлення дерева потрібно зберегти пару ключ/значення (keccak256(x), x) у постійній таблиці пошуку, якщо новостворений вузол має довжину >= 32. Однак, якщо вузол коротший за це значення, нічого зберігати не потрібно, оскільки функція f(x) = x є оборотною.

Дерева в Етеріумі

Усі дерева Меркла на рівні виконання Етеріуму використовують дерево Меркла-Патрісії.

Із заголовка блоку є 3 корені з 3 таких дерев.

stateRoot
transactionsRoot
receiptsRoot

Дерево стану

Існує одне глобальне дерево стану, і воно оновлюється щоразу, коли клієнт обробляє блок. У ньому path — це завжди: keccak256(ethereumAddress), а value — це завжди: rlp(ethereumAccount). Точніше, account Етеріуму — це масив із 4 елементів [nonce,balance,storageRoot,codeHash]. На цьому етапі варто зазначити, що цей storageRoot є коренем іншого дерева Патрісії:

Префіксне дерево сховища

Префіксне дерево сховища — це місце, де зберігаються всі дані контракту. Для кожного акаунта існує окреме префіксне дерево сховища. Щоб отримати значення на певних позиціях сховища за заданою адресою, потрібні адреса сховища, цілочисельна позиція збережених даних у сховищі та ідентифікатор блоку. Потім їх можна передати як аргументи до eth_getStorageAt, визначеного в JSON-RPC API, наприклад, щоб отримати дані в слоті сховища 0 для адреси 0x295a70b2de5e3953354a6a8344e616ed314d7251:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x0", "latest"], "id": 1}' localhost:8545

{"jsonrpc":"2.0","id":1,"result":"0x00000000000000000000000000000000000000000000000000000000000004d2"}

Отримання інших елементів у сховищі є трохи складнішим, оскільки спочатку потрібно обчислити позицію в префіксному дереві сховища. Позиція обчислюється як хеш keccak256 адреси та позиції сховища, обидва доповнені нулями зліва до довжини 32 байти. Наприклад, позиція для даних у слоті сховища 1 для адреси 0x391694e7e0b0cce554cb130d723a9d27458f9298 становить:

keccak256(decodeHex("000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"))

У консолі Geth це можна обчислити так:

> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
undefined
> web3.sha3(key, {"encoding": "hex"})
"0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9"

Тому path дорівнює keccak256(<6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9>). Тепер це можна використовувати для отримання даних із префіксного дерева сховища, як і раніше:

curl -X POST --data '{"jsonrpc":"2.0", "method": "eth_getStorageAt", "params": ["0x295a70b2de5e3953354a6a8344e616ed314d7251", "0x6661e9d6d8b923d5bbaab1b96e1dd51ff6ea2a93520fdc9eb75d059238b8c5e9", "latest"], "id": 1}' localhost:8545

{"jsonrpc":"2.0","id":1,"result":"0x000000000000000000000000000000000000000000000000000000000000162e"}

Примітка: storageRoot для акаунта Етеріуму за замовчуванням порожній, якщо це не акаунт контракту.

Дерево транзакцій

Для кожного блоку існує окреме дерево транзакцій, яке знову ж таки зберігає пари (key, value). Шлях тут такий: rlp(transactionIndex), що представляє ключ, який відповідає значенню, визначеному:

if legacyTx:
  value = rlp(tx)
else:
  value = TxType | encode(tx)

Більше інформації про це можна знайти в документації EIP-2718 (opens in a new tab).

Дерево квитанцій

Кожен блок має власне дерево квитанцій. path тут такий: rlp(transactionIndex). transactionIndex — це його індекс у блоці, до якого він був включений. Дерево квитанцій ніколи не оновлюється. Подібно до дерева транзакцій, існують поточні та застарілі (legacy) квитанції. Щоб зробити запит на певну квитанцію в дереві квитанцій, потрібні індекс транзакції в її блоці, корисне навантаження квитанції та тип транзакції. Повернута квитанція може бути типу Receipt, який визначається як конкатенація TransactionType та ReceiptPayload, або вона може бути типу LegacyReceipt, який визначається як rlp([status, cumulativeGasUsed, logsBloom, logs]).

Більше інформації про це можна знайти в документації EIP-2718 (opens in a new tab).

Дерево Меркла-Патрісії

Передумови

Базові radix-дерева

Дерево Меркла-Патрісії

Оптимізація

Специфікація: Компактне кодування шістнадцяткової послідовності з необов'язковим термінатором

Приклад дерева

Дерева в Етеріумі

Дерево стану

Префіксне дерево сховища

Дерево транзакцій

Дерево квитанцій

Подальше читання