trie/
lib.rs

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

trie/
lib.rs
