Как сделать дерево Modified Merkle Patricia Trie?

[webgraph]

У MPT (Merkle Patricia Trie) — есть 3 типа узлов:

• Branch Node — для ветвления, содержит от 1 до 16 ссылок на другие узлы, а также может содержать значение
  
• Extension Node — хранит часть пути, общую для нескольких дочерних узлов, содержит ссылку на Branch Node, который лежит далее
  
• Leaf Node — содержит часть пусти и хранимое значение, является конечным в цепочке.

Ссылка на высокое разрешение изображения https://i.stack.imgur.com/YZGxe.png

Что мне не понятно — так это то, когда должен создаваться Extension Node или Leaf Node?


Если читать записанную структуру, то всё выглядит понятно:

/*
 *

    Допустим нам надо получить значение какого-то ключа, хеш (путь) которого равен 
    aec952b24ff4d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff.

    Что мы делаем:

    1. Сначала переходим в 10 узел (первый полубайт/ниббл [a] хеша)
    2. Потом идём в 14 узел (второй ниббл [e] хеша)
    3. Потом идём в 12 узел (третий ниббл [c] хеша)
    4. Потом идём в 9 узел (четвёртый ниббл [9] хеша)
    5. Потом приходим в конечный узел 52b2...80ff (оставшаяся часть хеша) где и лежит значение нашего ключа.

 *
 */

    const MerklePatriciaTrie = {
        "type": "branch",
        "children": [
            {}, {}, {}, {}, {}, {}, {}, {}, {},

            // 10-ый узел первого уровня
            {
                "type": "branch",
                "children": [
                    {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},

                    // 14-ый узел второго уровня
                    {
                        "type": "branch",
                        "children": [
                            {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},

                            // 12-ый узел третьего уровня
                            {
                                "type": "branch",
                                "children": [
                                    {}, {}, {}, {}, {}, {}, {}, {},

                                    // 9-ый узел четвёртого уровня
                                    {
                                        "type": "leaf",
                                        "partPath": "52b24ff4d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff",
                                        "value": {
                                            "name": "Patricia Trie"
                                        }
                                    },
                                    {}, {}, {}, {}, {}, {}, {}, {}
                                ]
                            },
                            {}, {}, {}, {}, {}
                        ]
                    },
                    {}, {}, {}
                ]
            },
            {}, {}, {}, {}, {}, {}, {}
        ]
    };

Но если бы у нас был ещё и Extension Node где-то между начальной и конечной точкой, то, возможно это должно выглядеть так?

//a e c952b24ff 4 d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff
    const MPTWithExtension = {
        "type": "branch",
        "children": [
            {}, {}, {}, {}, {}, {}, {}, {}, {},

            // 10-ый узел первого уровня
            {
                "type": "branch",
                "children": [
                    {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {},

                    // ******************* 14-ый  EXTENSION узел второго уровня ********************
                    /*
                        То, что мне точно известно — это то, что Extension Node содержит
                        только ссылку на Branch Node.
                        Что касается выражения "partPath" — это только мои догадки...  Не знаю
                        верно ли понимаю эту часть дерева.

                        Понимаю, что Extension Node используется оптимизации — т.е. вместо хранения 16 узлов
                        - хранится только одна ссылка на Branch Node. Именно поэтому у меня складывается мнение,
                        что Extension Node должен содержать какую часть пути (хеша). Если это не так, то прошу
                        поправить меня и объяснить как правильно понимать это.
                     */
                    {
                        "type": "extension",
                        "partPath": "c952b24ff",
                        "nextNode": [
                            {}, {}, {},

                            // 4-ый узел третьего уровня
                            {
                                "type": "leaf",
                                "partPath": "d98ea50564c44c2af448a3647bf5dd89da81a801e154fd8180ff",
                                "value": {
                                    "name": "Patricia Trie"
                                }
                            },
                            {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}, {}
                        ]
                    },
                    {}, {}, {}
                ]
            },
            {}, {}, {}, {}, {}, {}, {}
        ]
    };

Так вот. Как это устроено в целом понятно.

Не понятно как это по итогу записывается? Ну, т.е. по какому принципу создаётся Leaf или Extension узел? И как вообще прокладывается и создаётся этот "ПУТЬ"?

Каким образом функция вычисляет количество вложенных уровней и вообще делает ли она это? Или как это устроено?

Можете показать функцию, которая бы добавляла в дерево новые значения на примере хешей (путей), чьё начало имеет одинаковые нибблы?

[webgraph]

Хочется отметить, что Branch Node хранит в себе именно ссылки. То есть в вышеприведённом коде отображается только визуальная логика, так сказать "виртуальный путь".

На деле каждый узел хранится в отдельном ключе базы данных типа Key->Value:

// Если в виде Map()
    const mapDB = new Map([
        ["key1", "value"],
        ["key2", "value"],
    ]);

    // Если в виде Object
    const objectDB = {
        "key1": "value",
        "key2": "value"
    }

    // Или другой встраиваемой БД

[webgraph]

Есть вообще у кого идеи?) Или после TS нету?...

[voraa]

Ну не все же занимались MPT и знают, что это такое (я - не знаю, поэтому идей нет)

[webgraph]

voraa,
Да, бывает.. А это не ты ли как-то в одной из тем завел речь про бинарное дерево?)

[voraa]

Вполне возможно, что это какое то дерево. Зачем такое? Может для экономии памяти, может для ускорения поиска.
Насколько я понимаю, это все работает в двоичном формате и алгоритмы их обработки написаны на компилируемых языках. И я сомневаюсь, что будет какая то экономия при реализации на интерпретируемом языке почти совсем не предназначенном для обработки двоичных данных.

[webgraph]

Вполне возможно, что это какое то дерево. Зачем такое? Может для экономии памяти, может для ускорения поиска.
Насколько я понимаю, это все работает в двоичном формате и алгоритмы их обработки написаны на компилируемых языках. И я сомневаюсь, что будет какая то экономия при реализации на интерпретируемом языке почти совсем не предназначенном для обработки двоичных данных.

Это дерево создано для проверки целостности данных и скорости поиска, равное O(log n).

Конкретно в их реализации используется встраиваемая база данных LevelDB от Google.

Более того, алгоритм построен на постоянном кодировании и декодировании данных. Т.е. каждый раз, когда нужно что-то прочитать из БД — идёт декодирование каждого узла дерева всех уровней его пути до значения (и самого значения). Они для этого используют собственный алгоритм кодирования LRP.

Данные только записываются для хранения в двоичном формате. При каждом запросе к БД для их поиска они декодируются. И когда находятся — также декодируются.

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

[webgraph]

voraa,
Или я что-то путаю? и само кодирование и декодирование — тоже всё в двоичном формате происходит?..

[webgraph]

voraa,
даже если и так, то здесь суть в том, чтобы понять алгоритм и то как он работает. Понимая это, можно позже реализовать на Go. (для начала его изучив ХЫ) или другом низкоуровневом языке.

[webgraph]

Вообще Patricia Trie — это префиксное дерево, которое работает со строками. Merkle Tree — дерево хешей данных. А Modified Merkle Patricia Trie — объединяет их свойства.

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