ELI5 Как работает дерево Merkle-Patricia-trie?

Я понимаю, что дерево Меркла - это хэши хэшей, у них есть то преимущество, что вы можете проверить только поддерево. Но как же Патрисия ? Что значит три ? И как это используется в Ethereum?

Ответы (2)

Trie (также называемое цифровым деревом, префиксным trie или radix trie)

Упорядоченная древовидная структура данных, которая используется для хранения динамического набора или ассоциативного массива, где ключами обычно являются строки. Положение узла в дереве определяет ключ, с которым он связан. https://en.wikipedia.org/wiki/Три

введите описание изображения здесь

Попытка для ключей "A", "to", "tea", "ted", "ten", "i", "in" и "inn".

Патриция - Практический алгоритм извлечения информации, закодированной в алфавитно -цифровом коде ( источник ) ( исходная статья Дональда Р. Моррисона ). Patricia trie — это двоичный radix trie — бинарный выбор в каждом узле при обходе trie; это изменено в Ethereum.

введите описание изображения здесьИсточник: https://en.wikipedia.org/wiki/File:An_example_of_how_to_find_a_string_in_a_Patricia_trie.png

В Эфириуме используется шестнадцатеричный формат — X символов из 16-символьного «алфавита». Следовательно, узлы в дереве имеют 16 дочерних узлов (16-символьный шестнадцатеричный «алфавит») и максимальную глубину X. Обратите внимание, что шестнадцатеричный символ называется «полубайтом».

Меркл Патрисия Три

Как описано здесь , термин Merkle подразумевает, что

корневой узел становится криптографическим отпечатком всей структуры данных

Модифицированный Ethereum Merkle Patricia Trie

В желтой бумаге описывается модифицированный merkle patricia trie. Это определяет три разных типа узлов; расширение, ветвь и лист. Они описаны с использованием упрощенного состояния мира на диаграмме ниже:

введите описание изображения здесь

Разве ключ не должен world-stateсодержать 8 полубайтов (32 байта)? В вашем примере (последнее изображение) он содержит 7 кусочков, что составляет 28 байтов. @atomh33ls
@Alper, спасибо ... Я сократил его, чтобы сделать его более кратким. Я думаю, что 8 кусочков — это всего лишь 4 байта… а 7 — это 3,5 байта. Мне нужно 64 шестнадцатеричных символа для 32 байт...
Что делают конечный узел и узлы расширения дерева?
Спасибо! Как устаревшее дерево синхронизируется с современным деревом? (например, когда клиент подключается к сети через один день). Он просто скачивает все актуальное дерево, или для синхронизации принимается какой-то "дифф"?
@HelinWang Нет проблем, я думаю, это зависит от реализации, поэтому лучше задать новый вопрос ...
Спасибо @atomh33ls ! Я только что просмотрел исходный код go eth trie, кажется, есть еще один тип узла: hashNode, если я правильно понимаю, это ссылка на любой вид узла, иллюстрирующий ваш график в базе данных. Возможно, ваш график можно было бы улучшить, указав на это.

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

Схема из википедии

Дополнительные сведения о разнице между деревом trie и radix (Patricia) см.

https://stackoverflow.com/questions/14708134/какая-есть-разница-между-три-и-основанием-три-данными-структурами

Дополнительные спецификации дерева Merkle Patricia, которое использует Ethereum, можно найти в блоге ethereum.

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

ELI5 Как работает дерево Merkle-Patricia-trie?
СпросиСетьПолитика конфиденциальности1y, 0v