rs_merkletree/lib.rs
1//! # rs-merkletree
2//!
3//! `rs-merkletree` is a Rust library to create Merkle trees.It allows creation of Merkle Trees using an [Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html) of data. It is possible to check whether a certain hash is included in the tree.
4//! Currently, supports merklization from a Vec of [&str](https://doc.rust-lang.org/std/primitive.str.html).
5//!
6//!
7//! # About Merkle Trees
8//! In cryptography and computer science, a hash tree or Merkle tree is a tree in which every "leaf" node is labelled with the cryptographic hash of a data block, and every node that is not a leaf (called a branch, inner node, or inode) is labelled with the cryptographic hash of the labels of its child nodes. A hash tree allows efficient and secure verification of the contents of a large data structure.
9//!
10//!
11//! # Examples
12//!
13//! Create a Merkle Tree and print the Root Hash
14//! ```
15//! use rs_merkletree::MerkleTree;
16//! let data: Vec<&str> = vec!["Hello", "World", "From", "Rust"];
17//! let mut tree = MerkleTree::new(None);
18//! let rootNode = tree.build_tree(data);
19//! let root_hash = rootNode.root_node().unwrap().hash();
20//! assert_eq!(
21//! String::from_utf8(root_hash),
22//! Ok(String::from(
23//! "725367a8cee028cf3360c19d20c175733191562b01e60d093e81d8570e865f81"
24//! ))
25//! );
26//! ```
27//!
28//! Check inclusion of a hash in a Merkle Tree
29//! ```
30//! use rs_merkletree::MerkleTree;
31//! let data: Vec<&str> = vec!["Hello", "World", "From", "Rust"];
32//! let mut tree = MerkleTree::new(None);
33//! let rootNode = tree.build_tree(data);
34//! let root_hash = rootNode.root_node().unwrap().hash();
35//! assert_eq!(
36//! String::from_utf8(root_hash),
37//! Ok(String::from(
38//! "725367a8cee028cf3360c19d20c175733191562b01e60d093e81d8570e865f81"
39//! ))
40//! );
41//! let path = tree.includes(
42//! "d9aa89fdd15ad5c41d9c128feffe9e07dc828b83f85296f7f42bda506821300e".as_bytes(),
43//! );
44//! println!("{}",path);
45//! ```
46
47#![allow(non_snake_case)]
48
49use crypto::{digest::Digest, sha2::Sha256};
50use std::collections::VecDeque;
51
52
53
54
55
56/// [MerkleTree](struct.MerkleTree.html) is the primary struct to hold Merkle Tree.
57///
58/// This is the main struct which cotains public functions to build the Merkle Tree from user data. It also contains functions to check for inclusion of a specific hash value.
59/// # Examples
60///
61/// ```
62/// use rs_merkletree::MerkleTree;
63/// let data: Vec<&str> = vec!["Hello", "World", "From", "Rust"];
64/// let mut tree = MerkleTree::new(None);
65/// let rootNode = tree.build_tree(data);
66/// let root_hash = rootNode.root_node().unwrap().hash();
67///
68/// assert_eq!(String::from_utf8(root_hash),
69/// Ok(String::from("725367a8cee028cf3360c19d20c175733191562b01e60d093e81d8570e865f81"))
70/// );
71/// ```
72#[derive(Debug, Clone)]
73pub struct MerkleTree {
74 root_node: Option<Box<Node>>,
75}
76
77/// [Node](struct.Node.html) is the struct to hold each node of the Merkle Tree.
78///
79/// * `left_node`: Holds node of the left child. Can be `None` if it does not have a left child or is a leaf node.
80///
81/// * `right_node`: Holds node of the right child. Can be `None` if it does not have a left child or is a leaf node.
82///
83/// * `hash`: Contains the hash content of the node. Formulated as Hash(left_node.hash,right_node.hash)
84#[derive(Debug, Clone,PartialEq)]
85pub struct Node {
86 left_node: Option<Box<Node>>,
87 right_node: Option<Box<Node>>,
88 hash: Vec<u8>,
89}
90
91impl Node {
92
93 /// Function to create new instance of [Node](struct.Node.html).
94 ///
95 /// Accepts: Hash, Optional leftNode, Optional rightNode.
96 ///
97 /// Return type [Node](struct.Node.html)
98 pub fn new(hash: Vec<u8>, leftNode: Option<Box<Node>>, rightNode: Option<Box<Node>>) -> Node {
99 return Node {
100 left_node: leftNode,
101 right_node: rightNode,
102 hash,
103 };
104 }
105 /// Returns the Left Child of the Current Node which is of type [Node](struct.Node.html). Returns `None` if left child does note exist.
106 pub fn left_node(&self) -> Option<Node> {
107 let root_node = &self.left_node;
108 match root_node {
109 Some(node) => return Some(*node.left_node.clone().unwrap()),
110 None => return None,
111 }
112 }
113
114 /// Returns the Right Child of the Current Node which is of type [Node](struct.Node.html). Returns `None` if right child does note exist.
115 pub fn right_node(&self) -> Option<Node> {
116 let root_node = &self.right_node;
117 match root_node {
118 Some(node) => return Some(*node.right_node.clone().unwrap()),
119 None => return None,
120 }
121 }
122
123 /// Return the Hash Value of the current [Node](struct.Node.html) as type `Vec<u8>`
124 pub fn hash(&self) -> Vec<u8> {
125 let hash = &self.hash;
126 return hash.to_vec();
127 }
128
129
130 pub fn depth(&self)->usize{
131 let left_depth = self.left_node.as_ref().map_or(0, |node| node.depth());
132 let right_depth = self.right_node.as_ref().map_or(0, |node| node.depth());
133
134 // The depth is the maximum depth of the subtrees plus one for the current node
135 usize::max(left_depth, right_depth) + 1
136
137 }
138}
139
140impl MerkleTree {
141 /// Function to build a new instance of [MerkleTree](struct.MerkleTree.html)
142 /// ```
143 /// use rs_merkletree::MerkleTree;
144 /// let mut tree = MerkleTree::new(None);
145 /// ```
146 pub fn new(rootNode: Option<Box<Node>>) -> MerkleTree {
147 println!("Building Merkle Tree");
148 return MerkleTree {
149 root_node: rootNode,
150 };
151 }
152
153 /// Returns the `RootNode` which is of type [Node](struct.Node.html)
154 ///
155 /// Returns `None` if the `RootNode` does not exist
156 pub fn root_node(&self) -> Option<Node> {
157 let root = &self.root_node;
158 match root {
159 Some(node) => return Some(*node.clone()),
160 None => return None,
161 }
162 }
163
164 /// Helper function to build the first layer of nodes.
165 ///
166 /// This involves taking in the data provided by user and converting it to the respective hashes and form the leaf nodes of the merkle tree
167 fn build_leaves(&self, data: Vec<&str>) -> Vec<Node> {
168 let size = data.len();
169 let mut ground_layer: Vec<Node> = Vec::new();
170 let mut i = 0;
171 while i < size {
172 let current_hash = self.hasher_leaf(data[i]);
173 let current_node = Node::new(current_hash, None, None);
174 ground_layer.push(current_node);
175 i += 1;
176 }
177 ground_layer
178 }
179
180 ///Function to hash leaf data.
181 /// Specific to leaf nodes as they are always singluar data hashes.
182 fn hasher_leaf(&self, data: &str) -> Vec<u8> {
183 let mut hasher = Sha256::new();
184 hasher.input(data.as_bytes());
185 let hash: Vec<u8> = hasher.result_str().as_bytes().to_vec();
186 return hash;
187 }
188
189 ///Function to hash any level other than the leaf.
190 fn hasher_nodes(&self, left_data: Vec<u8>, right_data: Vec<u8>) -> Vec<u8> {
191 let mut hasher = Sha256::new();
192 hasher.input(left_data.as_slice());
193 hasher.input(right_data.as_slice());
194 let hash = hasher.result_str().as_bytes().to_vec();
195 hash
196 }
197
198 ///Helper function to build the intermediate levels between the root and the leaves
199 fn build_upper_layer(&self, leaves: Vec<Node>) -> Vec<Node> {
200 let level = leaves.len();
201 let mut layer: Vec<Node> = Vec::new();
202
203 let mut i = 0;
204 while i < level {
205 if i + 1 >= level {
206 let current_hash =
207 self.hasher_nodes(leaves[i].hash.clone(), leaves[i].hash.clone());
208
209 let current_node = Node::new(current_hash, Some(Box::new(leaves[i].clone())), None);
210 layer.push(current_node);
211 i = i + 1;
212 } else {
213 let current_hash =
214 self.hasher_nodes(leaves[i].hash.clone(), leaves[i + 1].hash.clone());
215
216 let current_node = Node::new(
217 current_hash,
218 Some(Box::new(leaves[i].clone())),
219 Some(Box::new(leaves[i + 1].clone())),
220 );
221 layer.push(current_node);
222 i = i + 2;
223 }
224 }
225 let size = layer.len();
226 for j in 0..size {
227 println!(
228 "After build_upper_layer: {:?}",
229 String::from_utf8(layer[j].hash.clone())
230 );
231 }
232 layer
233 }
234
235 ///Helper function to build the root node
236 fn build_root(&self, leftNode: Node, rightNode: Node) -> Node {
237 println!(
238 "Root left values being hashed:{:?}",
239 String::from_utf8(leftNode.clone().hash)
240 );
241 println!(
242 "Root left values being hashed:{:?}",
243 String::from_utf8(rightNode.clone().hash)
244 );
245 let hash = self.hasher_nodes(leftNode.clone().hash, rightNode.clone().hash);
246 return Node {
247 left_node: Some(Box::new(leftNode)),
248 right_node: Some(Box::new(rightNode)),
249 hash: hash,
250 };
251 }
252
253 ///Main Function to build the Merkle Tree
254 ///
255 /// Parameters are the direct data provided by user. currently accepts `Vec<&str>` as input.
256 /// Returns type [MerkleTree](struct.MerkleTree.html)
257 pub fn build_tree(&mut self, data: Vec<&str>) -> &MerkleTree {
258 let mut leaves: Vec<Node> = self.build_leaves(data);
259
260 for i in 0..leaves.len() {
261 println!("Leaf Value:{:?}", String::from_utf8(leaves[i].hash.clone()));
262 }
263
264 let upper_layer = self.build_upper_layer(leaves.clone());
265 let mut size = upper_layer.len();
266 leaves.extend(upper_layer.clone());
267 // println!("Size:{}", size);
268
269 if size == 1 {
270 let root_node = leaves.pop().unwrap();
271 let root = Node::new(root_node.hash, root_node.left_node, root_node.right_node);
272 self.root_node = Some(Box::new(root));
273 return self;
274 }
275 while size > 2 {
276 let upper_layer = self.build_upper_layer(upper_layer.clone());
277 size = upper_layer.len();
278 leaves.extend(upper_layer);
279 }
280 let root = self.build_root(
281 leaves[leaves.len() - 2].clone(),
282 leaves[leaves.len() - 1].clone(),
283 );
284 // leaves.push(root);
285 println!("Final Tree: ");
286 for j in 0..leaves.len() {
287 println!("{:?}", String::from_utf8(leaves[j].clone().hash));
288 }
289 self.root_node = Some(Box::new(root));
290 return self;
291 }
292
293
294 //Function to get the depth of the Tree
295 ///
296 /// Returns the depth of the tree from the Root Node to the leaf as [usize](https://doc.rust-lang.org/std/primitive.usize.html)
297 pub fn depth(&self)->usize{
298 self.root_node().unwrap().depth()
299 }
300
301 ///Function to get the number of leaves in the tree
302 ///
303 /// Returns the number of leaves in the tree as [usize](https://doc.rust-lang.org/std/primitive.usize.html)
304 pub fn count_leaves(&self)->usize{
305 let mut count=0;
306 let mut data_array = VecDeque::new();
307 if let Some(ref root) = self.root_node {
308 data_array.push_front(root.as_ref());
309 }
310 while let Some(node) = data_array.pop_front() {
311 match (&node.left_node, &node.right_node) {
312 (None, None) => {
313 count += 1; // It's a leaf node
314 }
315 (Some(left), Some(right)) => {
316 data_array.push_back(right.as_ref());
317 data_array.push_back(left.as_ref());
318 }
319 (Some(left), None) => {
320 data_array.push_back(left.as_ref());
321 }
322 (None, Some(right)) => {
323 data_array.push_back(right.as_ref());
324 }
325 }
326 }
327
328 count
329 }
330
331 ///Function to check whether a specififc hash is present in the tree. Returns `True` if hash is present, else `False`.
332 ///
333 /// Note: Input parameter should be a hash; not the actual string
334 pub fn includes(&self, data: &[u8]) -> bool {
335 let mut data_array = VecDeque::new();
336 data_array.push_front(self.root_node.clone());
337 while data_array.len() > 0 {
338 let element = data_array.pop_front().unwrap();
339 // println!("ELement in include func:{:?}", element);
340
341 if element.clone().unwrap().hash == data {
342 return true;
343 } else {
344 if element.clone().unwrap().right_node.is_some() {
345 data_array.push_front(element.clone().unwrap().right_node);
346 }
347 if element.clone().unwrap().left_node.is_some() {
348 data_array.push_front(element.clone().unwrap().left_node);
349 }
350 }
351 }
352
353 false
354 }
355}