TrieTree implementation

[code-monad]

This PR brings a new implementation for SparseMerkleTree (check trie_tree.rs), typically called TrieTree, which is:

• Less read/write operations while updating compared to the original one
• Less storage space compared to the original one
• Compatible with the original tree hashes
  • Same root if tree has same leaf
  • Same MerkleProof&Compiled MerkleProof
  • *The branches_map won't be the same since the storage is not the same

Reference

Read/Write performace comparison:

Here's some bench data with rw operations counters This can reproduced by the benchmark : benches/store_counter_benchmark.rs with command: cargo bench --features trie -- --test and cargo bench -- --test

New

cargo bench --features trie -- --test
#...
random update 100 keys, store counters: Counters { get_branch_counter: 1740, get_leaf_counter: 0, insert_branch_counter: 660, insert_leaf_counter: 100, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update 10000 keys, store counters: Counters { get_branch_counter: 370570, get_leaf_counter: 0, insert_branch_counter: 131628, insert_leaf_counter: 10000, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update_all 100 keys, store counters: Counters { get_branch_counter: 1731, get_leaf_counter: 0, insert_branch_counter: 657, insert_leaf_counter: 100, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update_all 10000 keys, store counters: Counters { get_branch_counter: 371504, get_leaf_counter: 0, insert_branch_counter: 131988, insert_leaf_counter: 10000, remove_branch_counter: 0, remove_leaf_counter: 0 }

Original

cargo bench -- --test
#...
random update 100 keys, store counters: Counters { get_branch_counter: 25600, get_leaf_counter: 0, insert_branch_counter: 25600, insert_leaf_counter: 100, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update 10000 keys, store counters: Counters { get_branch_counter: 2560000, get_leaf_counter: 0, insert_branch_counter: 2560000, insert_leaf_counter: 10000, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update_all 100 keys, store counters: Counters { get_branch_counter: 24836, get_leaf_counter: 0, insert_branch_counter: 24935, insert_leaf_counter: 100, remove_branch_counter: 0, remove_leaf_counter: 0 }
random update_all 10000 keys, store counters: Counters { get_branch_counter: 2418267, get_leaf_counter: 0, insert_branch_counter: 2428266, insert_leaf_counter: 10000, remove_branch_counter: 0, remove_leaf_counter: 0 }

[TheWaWaR]

Others just look good to me, I'll approve if all above comments resolved.