Меркл Патрісія Тріє

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

Структура даних Ethereum — це «модифіковане дерево Меркла-Патриції», назване так, тому що воно запозичує деякі функції з PATRICIA (практичний алгоритм для отримання інформації, закодованої в буквено-цифровому форматі), і тому що воно призначене для ефективного видобування даних елементів, що складають стан Ethereum.

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

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

Передумови

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

Базові кореневі префіксні дерева

У базових спробах числення кожен елемент виглядає наступним чином:

1    [i_0, i_1 ... i_n, value]

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

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

Існує різниця між пошуком чогось у "trie" та базовою площею flat key/value 'DB'. Вони обидва визначають структуру key/value, але базова DB може виконувати традиційний пошук ключа в один крок. Пошук ключа в тріаді вимагає багаторазового пошуку в базовій DB, щоб отримати кінцеве значення, описане вище. Назвімо останній шляхом, щоб усунути неоднозначність.

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

1    def update(node_hash, path, value):
2        curnode = db.get(node_hash) if node_hash else [NULL] * 17
3        newnode = curnode.copy()
4        if path == "":
5            newnode[-1] = value
6        else:
7            newindex = update(curnode[path[0]], path[1:], value)
8            newnode[path[0]] = newindex
9        db.put(hash(newnode), newnode)
10        return hash(newnode)
11
12    def delete(node_hash, path):
13        if node_hash is NULL:
14            return NULL
15        else:
16            curnode = db.get(node_hash)
17            newnode = curnode.copy()
18            if path == "":
19                newnode[-1] = NULL
20            else:
21                newindex = delete(curnode[path[0]], path[1:])
22                newnode[path[0]] = newindex
23
24            if all(x is NULL for x in newnode):
25                return NULL
26            else:
27                db.put(hash(newnode), newnode)
28                return hash(newnode)
Показати все

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

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

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

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

Радиксне дерево має одне суттєве обмеження: вони неефективні. Якщо ви хочете зберегти одне зв’язування (path, value), де шлях, як в Ethereum, має 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>). Щоб вказати непарну довжину, до часткового шляху додається прапорець.

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

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

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

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

1    def compact_encode(hexarray):
2        term = 1 if hexarray[-1] == 16 else 0
3        if term:
4            hexarray = hexarray[:-1]
5        oddlen = len(hexarray) % 2
6        flags = 2 * term + oddlen
7        if oddlen:
8            hexarray = [flags] + hexarray
9        else:
10            hexarray = [flags] + [0] + hexarray
11        # hexarray now has an even length whose first nibble is the flags.
12        o = ""
13        for i in range(0, len(hexarray), 2):
14            o += chr(16 * hexarray[i] + hexarray[i + 1])
15        return o
Показати все

Приклади:

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

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

1    def get_helper(node_hash, path):
2        if path == []:
3            return node_hash
4        if node_hash == "":
5            return ""
6        curnode = rlp.decode(node_hash if len(node_hash) < 32 else db.get(node_hash))
7        if len(curnode) == 2:
8            (k2, v2) = curnode
9            k2 = compact_decode(k2)
10            if k2 == path[: len(k2)]:
11                return get(v2, path[len(k2) :])
12            else:
13                return ""
14        elif len(curnode) == 17:
15            return get_helper(curnode[path[0]], path[1:])
16
17    def get(node_hash, path):
18        path2 = []
19        for i in range(len(path)):
20            path2.push(int(ord(path[i]) / 16))
21            path2.push(ord(path[i]) % 16)
22        path2.push(16)
23        return get_helper(node_hash, path2)
Показати все

Приклад префіксного дерева

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

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

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

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

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

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

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

Префіксні дерева в Ethereum

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

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

stateRoot
transactionsRoot
receiptsRoot

Дерево стану

Існує одне глобальне дерево стану, і воно оновлюється щоразу, коли клієнт обробляє блок. У ньому path — це завжди: keccak256(ethereumAddress), а value — це завжди: rlp(ethereumAccount). Точніше, обліковий запис Ethereum — це масив із 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:

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

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

1> var key = "000000000000000000000000391694e7e0b0cce554cb130d723a9d27458f9298" + "0000000000000000000000000000000000000000000000000000000000000001"
2undefined
3> web3.sha3(key, {"encoding": "hex"})
4"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 для облікового запису Ethereum є порожнім за замовчуванням, якщо це не обліковий запис контракту.

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

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

1if legacyTx:
2  value = rlp(tx)
3else:
4  value = TxType | encode(tx)

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

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

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