trie/
lib.rs

1//! Merkle trie implementation for Ethereum.
2
3extern crate bigint;
4extern crate rlp;
5extern crate sha3;
6#[cfg(test)] extern crate hexutil;
7
8use bigint::H256;
9use rlp::Rlp;
10use sha3::{Digest, Keccak256};
11use std::collections::{HashMap, HashSet};
12use merkle::{MerkleValue, MerkleNode};
13use merkle::nibble::{self, NibbleVec, NibbleSlice, Nibble};
14
15macro_rules! empty_nodes {
16    () => (
17        [MerkleValue::Empty, MerkleValue::Empty,
18         MerkleValue::Empty, MerkleValue::Empty,
19         MerkleValue::Empty, MerkleValue::Empty,
20         MerkleValue::Empty, MerkleValue::Empty,
21         MerkleValue::Empty, MerkleValue::Empty,
22         MerkleValue::Empty, MerkleValue::Empty,
23         MerkleValue::Empty, MerkleValue::Empty,
24         MerkleValue::Empty, MerkleValue::Empty]
25    )
26}
27
28macro_rules! empty_trie_hash {
29    () => {
30        {
31            use std::str::FromStr;
32
33            H256::from_str("0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421").unwrap()
34        }
35    }
36}
37
38pub mod merkle;
39mod ops;
40mod memory;
41mod mutable;
42
43use ops::{insert, delete, build, get};
44
45pub use memory::*;
46pub use mutable::*;
47
48/// An immutable database handle.
49pub trait DatabaseHandle {
50    /// Get a raw value from the database.
51    fn get<'a>(&'a self, key: H256) -> &'a [u8];
52}
53
54/// Change for a merkle trie operation.
55pub struct Change {
56    /// Additions to the database.
57    pub adds: HashMap<H256, Vec<u8>>,
58    /// Removals to the database.
59    pub removes: HashSet<H256>,
60}
61
62impl Default for Change {
63    fn default() -> Self {
64        Change {
65            adds: HashMap::new(),
66            removes: HashSet::new(),
67        }
68    }
69}
70
71impl Change {
72    /// Change to add a new raw value.
73    pub fn add_raw(&mut self, key: H256, value: Vec<u8>) {
74        self.adds.insert(key, value);
75        self.removes.remove(&key);
76    }
77
78    /// Change to add a new node.
79    pub fn add_node<'a, 'b, 'c>(&'a mut self, node: &'c MerkleNode<'b>) {
80        let subnode = rlp::encode(node).to_vec();
81        let hash = H256::from(Keccak256::digest(&subnode).as_slice());
82        self.add_raw(hash, subnode);
83    }
84
85    /// Change to add a new node, and return the value added.
86    pub fn add_value<'a, 'b, 'c>(&'a mut self, node: &'c MerkleNode<'b>) -> MerkleValue<'b> {
87        if node.inlinable() {
88            MerkleValue::Full(Box::new(node.clone()))
89        } else {
90            let subnode = rlp::encode(node).to_vec();
91            let hash = H256::from(Keccak256::digest(&subnode).as_slice());
92            self.add_raw(hash, subnode);
93            MerkleValue::Hash(hash)
94        }
95    }
96
97    /// Change to remove a raw key.
98    pub fn remove_raw(&mut self, key: H256) {
99        self.adds.remove(&key);
100        self.removes.insert(key);
101    }
102
103    /// Change to remove a node. Return whether there's any node being
104    /// removed.
105    pub fn remove_node<'a, 'b, 'c>(&'a mut self, node: &'c MerkleNode<'b>) -> bool {
106        if node.inlinable() {
107            false
108        } else {
109            let subnode = rlp::encode(node).to_vec();
110            let hash = H256::from(Keccak256::digest(&subnode).as_slice());
111            self.remove_raw(hash);
112            true
113        }
114    }
115
116    /// Merge another change to this change.
117    pub fn merge(&mut self, other: &Change) {
118        for (key, value) in &other.adds {
119            self.add_raw(*key, value.clone());
120        }
121
122        for v in &other.removes {
123            self.remove_raw(*v);
124        }
125    }
126}
127
128/// Get the empty trie hash for merkle trie.
129pub fn empty_trie_hash() -> H256 {
130    empty_trie_hash!()
131}
132
133/// Insert to a merkle trie. Return the new root hash and the changes.
134pub fn insert<D: DatabaseHandle>(
135    root: H256, database: &D, key: &[u8], value: &[u8]
136) -> (H256, Change) {
137    let mut change = Change::default();
138    let nibble = nibble::from_key(key);
139
140    let (new, subchange) = if root == empty_trie_hash!() {
141        insert::insert_by_empty(nibble, value)
142    } else {
143        let old = MerkleNode::decode(&Rlp::new(database.get(root)));
144        change.remove_raw(root);
145        insert::insert_by_node(old, nibble, value, database)
146    };
147    change.merge(&subchange);
148    change.add_node(&new);
149
150    let hash = H256::from(Keccak256::digest(&rlp::encode(&new).to_vec()).as_slice());
151    (hash, change)
152}
153
154/// Insert to an empty merkle trie. Return the new root hash and the
155/// changes.
156pub fn insert_empty<D: DatabaseHandle>(
157    key: &[u8], value: &[u8]
158) -> (H256, Change) {
159    let mut change = Change::default();
160    let nibble = nibble::from_key(key);
161
162    let (new, subchange) = insert::insert_by_empty(nibble, value);
163    change.merge(&subchange);
164    change.add_node(&new);
165
166    let hash = H256::from(Keccak256::digest(&rlp::encode(&new).to_vec()).as_slice());
167    (hash, change)
168}
169
170/// Delete a key from a markle trie. Return the new root hash and the
171/// changes.
172pub fn delete<D: DatabaseHandle>(
173    root: H256, database: &D, key: &[u8]
174) -> (H256, Change) {
175    let mut change = Change::default();
176    let nibble = nibble::from_key(key);
177
178    let (new, subchange) = if root == empty_trie_hash!() {
179        return (root, change)
180    } else {
181        let old = MerkleNode::decode(&Rlp::new(database.get(root)));
182        change.remove_raw(root);
183        delete::delete_by_node(old, nibble, database)
184    };
185    change.merge(&subchange);
186
187    match new {
188        Some(new) => {
189            change.add_node(&new);
190
191            let hash = H256::from(Keccak256::digest(&rlp::encode(&new).to_vec()).as_slice());
192            (hash, change)
193        },
194        None => {
195            (empty_trie_hash!(), change)
196        },
197    }
198}
199
200/// Build a merkle trie from a map. Return the root hash and the
201/// changes.
202pub fn build(map: &HashMap<Vec<u8>, Vec<u8>>) -> (H256, Change) {
203    let mut change = Change::default();
204
205    if map.len() == 0 {
206        return (empty_trie_hash!(), change);
207    }
208
209    let mut node_map = HashMap::new();
210    for (key, value) in map {
211        node_map.insert(nibble::from_key(key.as_ref()), value.as_ref());
212    }
213
214    let (node, subchange) = build::build_node(&node_map);
215    change.merge(&subchange);
216    change.add_node(&node);
217
218    let hash = H256::from(Keccak256::digest(&rlp::encode(&node).to_vec()).as_slice());
219    (hash, change)
220}
221
222/// Get a value given the root hash and the database.
223pub fn get<'a, 'b, D: DatabaseHandle>(
224    root: H256, database: &'a D, key: &'b [u8]
225) -> Option<&'a [u8]> {
226    if root == empty_trie_hash!() {
227        None
228    } else {
229        let nibble = nibble::from_key(key);
230        let node = MerkleNode::decode(&Rlp::new(database.get(root)));
231        get::get_by_node(node, nibble, database)
232    }
233}
trie/lib.rs

trie/
lib.rs
