# Merkle Tree на Rust

[![Build Status](https://travis-ci.org/LooMaclin/merkle_tree_rs.svg?branch=master)](https://travis-ci.org/LooMaclin/merkle_tree_rs)

[![Coverage Status](https://coveralls.io/repos/github/LooMaclin/merkle_tree_rs/badge.svg?branch=master)](https://coveralls.io/github/LooMaclin/merkle_tree_rs?branch=master)


## Технические решения

### Итерация мыслей 0

Если с большинством пунктов задачи всё достаточно просто, то с третьим пунктом не очень.
Каким должен быть прагматичный API?

Было выяснено, что у Merkle Tree нет как такового "стандарта" реализации, следовательно:

1) Тип используемой хэш-функции может быть отличным от SHA-2. Делаем вывод, что пользователь должен 
    иметь способ при создании экземпляра этой структуры выбрать необходимую ему хэш-функцию. В Rust, есть библиотека 
    для криптографии решающая данный вопрос - это [rust-crypto](https://github.com/DaGenix/rust-crypto/). 
    Типаж [Digest](https://docs.rs/rust-crypto/0.2.36/crypto/digest/trait.Digest.html) реализован для наибольшего 
    количества хэш-функций, включая SHA-1,SHA-2,MD5 и других, поэтому было решено использовать его.
    
2) Тип данных "листьев" дерева в котором они будут отображены перед непосредственно хэшированием не известен, 
    так же заранее не известно каким типом данных будет располагать пользователь. Это могут быть не только строки 
    (как это обычно делают в реализациях/примерах Merkle Tree), но и примитивные типы, кастомные структуры, коллекции. 
    Следовательно необходимо иметь какой-то типаж, который позволит на стороне пользователя указывать, что его данные 
    сериализуемы и желательно, если эти данные представлены структурой, выводить код для сериализации автоматически.
    Сообществом для этих целей была разработана библиотека [Serde](https://serde.rs/). Типаж [Serialize](https://docs.serde.rs/serde/trait.Serialize.html) 
    позволит передавать пользователю любые типы, которые его реализуют. Типаж [Serializer](https://docs.rs/serde/1.0.8/serde/ser/trait.Serializer.html) 
    позволит передавать пользователю сериализатор нужного ему формата данных.
    
3) Пользователь должен иметь возможность: инициализировать пустое дерево, для этого будет использоваться типаж 
    [Default](https://doc.rust-lang.org/std/default/trait.Default.html) из стандартной библиотеки; 
    инициализировать дерево на основе нескольких "листьев"; и на одном "листке".
    При этом функция инициализации должна принимать как векторы, так и массивы - явный признак того, что в сигнатуре 
    функции, в качестве аргумента следует использовать слайс (он абстрагирует нас от конкретной коллекции).
    
### Итерация мыслей 1

1) Была предпринята попытка реализовать функцию принимающую `Serializer` и сериализующую любой `Serialize`-value.
Не удалось, так как с этим есть сейчас проблемы: https://github.com/serde-rs/serde/issues/552
Решил использовать enum с тремя типами. Можно закидывать в качестве листьев-транзакций дерева любые типы реализующие Serialize.

2) Отказался от идеи разных вариантов хэширования - в пользу хранения фиксированного размера массива.

3) Пробовал использовать `SmallVec` для оптимизации обработки небольших деревьев на стеке. Роста скорости не дало, избавился.

4) Добавил возможность параллелить генерацию новых слоёв дерева при помощи библиотеки Rayon. Чем больше количество 
   листъев тем заметней прирости по скорости. На обработку деревьев различных размеров, Rayon 
   давал выигрыш прирост от 50% до 100% по скорости построения:
   ```
    test tests::build_1000000_tree_parallel_bincode ... bench: 608,845,363 ns/iter (+/- 139,315,093)
    test tests::build_1000000_tree_sequence_bincode ... bench: 1,062,443,268 ns/iter (+/- 74,610,158)
   ```
   
5) Пробовал несколько вариантов хранения бинарного дерева:

- хранение в виде `enum` варианты которого структуры олицетворяют узлы дерева (Root { left, right, hash } , 
Interior { parent, left, right, hash}, Leaf { parent, hash }) - решил, что скорость доступа к листьям будет низка + 
оверхед на хранение ссылок и большая возможность ошибиться при неправильном обращении с типом который будет сокрывать тип 
для того, чтобы компилятор "съел" циклические ссылки на тот же тип в типе.

- "стандартный" способ хранения в виде плоского вектора, простая индексация, быстрый доступ - один минус сложно будет преаллоцировать,
куски памяти для каждого из слоёв, + формула для индексации если хранить листья в начале не такая тривиальная как у следующего способа, 
в любом случае даже если хранить листья в конце будет происходить реаллокация при добавлении новых узлов сумм хэшей но "верхние" слои;

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

6) Узнал, что дерево используется не только для высчитывания merkle tree root hash. Так же из него получают Audit Proof Path - 
состоящий из хэшей пути хэша транзакции к корню, так же в ходе этой операции обычно чекается валидность этих хэшей. Добавил 
соответствующую операцию в библиотеку.

7) После первоначального билда дерева добавил возможность добавлять новые узлы с автоматическим перестроением оставшейся 
части узлов вверх по дереву.

8) Буду честным сказав, что в один момент запутался в проверках и сделал копию дерева основанную на хранении String, 
где вместо хэширования использовал конкатенацию строк. Таким образом отладил алгоритм. И после вернулся к хранению массива байт хэша.
Оставил в коде структуру `MerkleTreeString` для истории.

9) В начале я использовал правило нечётности элементов на слое дерева так - количество элементов нечётное - добавлял обязательно дубликат последнего узла в слой,
потом понял, что это лишняя операция и можно отказаться от его добавления;

## Минусы реализации
- не знаю можно ли это считать минусом но в отличии от многих примеров здесь не используется двойное хэширование;
- каноникализация на стороне пользователя;
- возмонжо есть оптимизации позволяющие более эффективно использовать память при вставках новых узлов в дерево
- нет возможности выбрать функцию хэширования, типаж Digest реализован для разных хэш-функций и следовательно те выдают
своё собственное количество байт на хэш;
- не самый лучший на мой взгляд алгоритм добавления нового узла после построения дерева;
- не превентит добавление дубликата транзакции в листья, а наверное всё таки надо;
- нет встроенной возможности сохранить листья дерева на диск (вручную если только) и после поднять его в память, 
построи и валидировать;

## Плюсы реализации
- возможность параллелизации при построении дерева за счёт использования итераторов из Rayon;
- возможность в качестве добавляемых транзакций использовать любые типы реализующие Serialize;
- эффективно по памяти;

## Пример

```rust
// подключаем крэйт
extern crate merkle_tree;

// подключаем структуру дерева и перечисление отвечающее за формат сериализации
use merkle_tree::{MerkleTree, SerializationFormat};

fn main() {
    // создаём дерево на основе 3-ёх "листьев"
    let mut merkle_tree = MerkleTree::from(&mut ["a", "b", "c"], SerializationFormat::Json);
    // вызываем построение дерева    
    merkle_tree.build().unwrap();
    // печатаем вычисленный хэш рут дерева
    println!("Merkle tree root hash: {:?}", merkle_tree.get_merkle_root());
    // печатаем пруф-путь для транзакции b
    println!("Merkle tree audit proot: {:?}", merkle_tree.audit_proof(&[172, 141, 131, 66, 187, 178, 54, 45, 19, 240, 165, 89, 163, 98, 27, 180, 7, 1, 19, 104, 137, 81, 100, 182, 40, 165, 79, 127, 195, 63, 196, 60]).unwrap());
    // добавляем в дерево хэш транзакции d
    merkle_tree.push(&String::from("d"));
    // печатаем рут хэш дерева
    println!("Merkle tree root hash: {:?}", merkle_tree.get_merkle_root());
    // печатаем пруф-путь для транзакции b
    println!("Merkle tree audit proot: {:?}", merkle_tree.audit_proof(&[172, 141, 131, 66, 187, 178, 54, 45, 19, 240, 165, 89, 163, 98, 27, 180, 7, 1, 19, 104, 137, 81, 100, 182, 40, 165, 79, 127, 195, 63, 196, 60]).unwrap());
}
```

## Использовавшиеся материалы:
- [Статья о Merkle Tree на wikipedia](https://en.wikipedia.org/wiki/Merkle_tree)
- [7-ая глава книги Mastering Bitcoin](http://chimera.labs.oreilly.com/books/1234000001802/ch07.html#merkle_trees)
- [Страница в глоссарии на Bitcoin.org](https://bitcoin.org/en/glossary/merkle-tree)
- [Статья в bitcoin developer guide](https://bitcoin.org/en/developer-guide#transaction-data)
- [Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis](https://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf)
- [Tree Hash EXchange format (THEX)](http://adc.sourceforge.net/draft-jchapweske-thex-02.html#anchor2)
- [Building a Merkle Tree in C++](https://codetrips.com/2016/06/19/implementing-a-merkle-tree-in-c/)
- [Understanding merkle trees](https://www.codeproject.com/Articles/1176140/Understanding-Merkle-Trees-Why-use-them-who-uses-t)
- [Подпись Меркла](https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D1%8C_%D0%9C%D0%B5%D1%80%D0%BA%D0%BB%D0%B0)
- [What is MTP (Merkle Tree Proof) and why is it an ideal Proof of Work algorithm?](https://github.com/zcoinofficial/zcoin/wiki/What-is-MTP-(Merkle-Tree-Proof)-and-why-is-it-an-ideal-Proof-of-Work-algorithm%3F)
- [What is a merkle tree](https://www.weusecoins.com/what-is-a-merkle-tree/)
- [Patricia Tree](https://github.com/ethereum/wiki/wiki/Patricia-Tree)