codechain-io / rust-merkle-trie

Merkle trie for CodeChain

Merkle-Trie

The merkle trie used by CodeChain and Foundry.

Usage

The rust-merkle-trie crate provides merkle trie implementations. CodeChain and Foundry use a merkle trie to hold the states with authentication. We differ from the merkle patricia trie in Ethereum; details can be found here.

Let's use the merkle trie to show an example:

use merkle_trie::{Trie, TrieFactory, TrieMut};
use cdb::MemoryDB;
use primitives::H256;

// initialize
let mut memdb = MemoryDB::new();
let mut root = H256::zero();
let mut trie = TrieDBMut::new(&mut memdb, &mut root);

// insert
trie.insert(&[0x01u8, 0x23], &[0x01u8, 0x23]).unwrap();
assert_eq!(*trie.root(), trie_root(vec![(vec![0x01u8, 0x23], vec![0x01u8, 0x23])]));

// get
assert_eq!(trie.get(&0x01u8, 0x23]).unwrap().unwrap(), vec!0x01u8, 0x23]);
assert_eq!(t.get(&[0x02u8]), Ok(None));

// remove
trie.remove(&0x01u8, 0x23]).unwrap();
assert_eq!(t.get(&0x01u8, 0x23]), Ok(None));

Build

Download foundry code

git clone [email protected]:CodeChain-io/rust-merkle-trie.git
cd rust-merkle-trie

Build in debug mode

cargo build

Test

Developers are strongly encouraged to write unit tests for new code, and to submit new unit tests for old code. Unit tests can be compiled and run with: cargo test --all. For more details, please refer to Unit Tests.

Benchmark

Official documentation for usage of cargo bench:
https://doc.rust-lang.org/1.15.1/book/benchmark-tests.html

We can run the benchmark test with cargo bench:

cargo bench

rust-merkle-trie's Issues

Hash inlining

The Branch node in the Merkle Trie contains its children's hashes, by which the node's data can be searched in the DB. However, when the size of the node's data is less than the size of hash, the node's data itself can be stored in the Branch node. By doing this, DB operations can be reduced.

Upload it to crates.io

Let's make it reusable by other Rust projects.

Add malicious case of unit tests on Merkle proof

Currently, all tests generates only well-formed proofs (though they may be invalid). However we can fabricate ill-formed proofs. We need to test whether the verifier can return false (not true nor runtime error) in such malicious case.

Implement Merkle proof

It might involve:

• Abstraction of cryptographic proof itself
• A new data structure of Merkle proof (also a new Rust struct)
• Discussion about possible dependency with current Merkle trie optimization
• Unit tests

Optimize "contains" method of the interface "Trie"

Currently, contains method utilizes get method and checks if the value is Some. Let's optimize this method to make it faster than get

Add README.md

Add benchmark tests

We need benchmark tests before working on performance optimizations such as CodeChain-io/foundry#45 and CodeChain-io/foundry#46.

Enhance the caching policy

Currently, it caches each node with a node address instead of a key-value pair.
It's helpful because it reduces the disk IO queries, but the cache can be redundant, depending on the usages.
If the real usage is querying some keys repeatedly, caching key-value pairs is enough, and caching all nodes is just a memory wasting.
However, if the assumption is wrong, caching a key-value pair would not be helpful because of the high missing rates. We should investigate the real scenario before changing the policy.

Fix the term 'trie' to 'tree'

Transactions are in 'tree' not 'trie', but some part of the code misuses the terminology.

Add cache to the Merkle Trie

It is possible to insert a cache between DB operation and node handling operation.

Multiple DB operations are needed, during the insert, remove and lookup operations are executing.
The overhead derived from DB operations will be reduced by adding cache.

Make proof to hold only hash of the value

Current implementation composes a proof with an actual value in it.
Thus proof grows larger as the value does.
We can optimize this by taking hash of value only.