Merkle Tree

В проекте представлены основные классы данных, которые используются в блокчейне. Необходимо написать реализацию методов и проверить правильность с помощью тестов.
Для запуска тестов необходимо установить nodejs и необходимые библиотеки.

Установка

Клонируйте репозиторий, перейдите в каталог проекта и установите зависимости.

git clone https://github.com/labintsev/merkle-tree
cd merkle-tree
npm install

Запуск всех тестов

npx mocha test

1. Blockhain primitive

Блокчейн - это структура данных, состоящая из нескольких блоков. В этом упражнении класс Block представляет собой простую обертку над некоторыми данными. Для упрощения мы считаем что data - это просто некоторая строка.

Кроме данных, блок содержит поле previousHash, которое хранит в себе хэш предыдущего блока в блокчейне. Хэш блока вычисляется от конкатенации двух полей data + previousHash.

Итерактивное демо https://blockchaindemo.io/

Блокчейн можно представить как связный список, в котором каждый следующий блок добавляется к предыдущему. Новый блокчейн инициализируется с первым блоком, который называется генезис-блоком. Задание 1. Создайте генезис-блок в блокчейне.

Каждый новый блок добавляется в блокчейн через вызов метода addBlock(block). Перед добавлением в цепочку в поле block.previousHash необходимо записать хэш предыдущего блока. Задание 2. Реализуйте эту логику.

Когда к сети подключается новый участник, он должен проверить правильность построения всей цепочки. Метод isValid() возвращает true, если для каждого блока в цепочке в поле previousHash содержится хэш предыдущего блока. При любом несовпадении возвращается false. Задание 3. Реализуйте эту логику.

Запуск теста:

npx mocha test/Blockchain.js

2. Transaction output

Объект Transaction содержит информацию об адресе владельца, получателя и количестве монет. Реализуйте конструктор транзакции с полями from, to, value, spent, hash.

Метод spend() означает проведение транзакции и может быть вызван только один раз. Реализуйте метод spend(), который будет устанавливать поле spent в значение true. При попытке провести транзакцию дважды должна бросаться ошибка Error('Already spended!').

Запуск теста:

npx mocha test/Transaction.js

3. Binary search tree

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

Мы пойдем от простого к сложному и для начала вспомним, как реализуются основные методы классического бинарного дерева поиска. Класс Node является узлом бинарного дерева, помимо полезных данных от содержит ссылки на левого и правого потомка. Здесь важно не запутаться в синонимах, под словом Node мы также можем иметь ввиду узел вычислительной сети. Практически всегда можно понять о какой ноде идет речь из контекста повествования.

Класс Tree - классическое бинарное дерево поиска.

В файле Tree.js реализуйте метод addNode(node) для добавления узла.

Реализуйте метод hasNode(data) для проверки, есть ли в дереве узел с таким содержимым.

Запуск теста:

npx mocha test/Tree.js

4. Merkle tree

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

Merkle root вычисляется следующим способом. Все транзакции, которые входят в блок, хешируются. Хеши размещаются в линейный массив, порядок имеет значение. Для каждой пары хешей вычисляется новый хеш, рекурсивно слой за слоем, пока не будет получен слой из одного элемента - Merkle root.

      ABCDEFGH <-- Merkle Root  
       /    \  
    ABCD     EFGH  
    / \      / \  
   AB  CD   EF  GH  
  / \  / \  / \ / \  
  A B  C D  E F G H

В этом примере каждая буква представляет собой уникальное значение хеша транзакции. Комбинация АВ означает, что мы берем хеш от конкатенации этих двух хешей.

В учебных целях мы используем очень простую функцию строковой конкатенации:

function concatHashes(a, b) {
    return `Hash(${a} + ${b})`;
}

Внимательно изучите реализацию методов getConcatLeaves и getProof.

Метод getConcatLeaves слой за слоем конкатенирует хеши, от нижнего уровня листьев до самой вершины - корневого хеша.

Метод getProof(index), возвращает цепочку из дополняющих узлов, от корня root до листа с индексом index.
proof - это цепочка хешей, которая служит для быстрого доказательства принадлежности листа данному дереву.

Реализуйте функцию verifyProof(proof, nodeHash, rootHash) для проверки того, входит ли узел в данное дерево.
proof - массив из объектов, имющих поля hash и left ,
nodeHash - хеш проверяемого узла,
rootHash - корневой хеш дерева.

Запуск теста:

npx mocha test/MerkleTree.js

5. Trie (prefix tree)

Модифицированное дерево Меркла - это сочетание эффективного доказательства целостности данных и быстрых операций чтения/вставки.
Рассмотрим, как работает простое префиксное дерево Trie.

Класс TrieNode - узел префиксного дерева. Каждый узел имеет ключ key, состоящий из одного символа. В отличии от узла бинарного дерева, поле children может содержать несколько потомков. Все промежуточные узлы префиксного дерева содержат цепочки хешей, общие для их потомков. Флаг isWord служит для пометки листов, содержащих данные (слово, или хеш в случае с блокчейном). Все промежуточные узлы помечаются isWord=false, т.к. содержат лишь префиксную часть слова.

Класс Trie - структура данных префиксное дерево.

       null <-- Trie Root  
      /     \  
     D       C  
    / \     / \  
   A   O   A   R 
  /   /   / \   \ 
 G   G   T   R   A
                  \ 
                   B

Реализуйте метод insert(word) для вставки нового слова в префиксное дерево.

Запуск теста:

npx mocha test/Trie.js