handshake_types/
merkle_tree.rs

1use cryptoxide::blake2b::Blake2b;
2use cryptoxide::digest::Digest;
3use extended_primitives::Hash;
4
5//Merkle tree type for use in Handshake
6//@todo
7//@todo can I generalize this entire thing?
8#[derive(Debug)]
9pub struct MerkleTree {
10    steps: Vec<Hash>,
11}
12
13impl MerkleTree {
14    pub fn from_leaves(leaves: Vec<Hash>) -> Self {
15        let mut nodes = Vec::new();
16        // let mut steps = Vec::new();
17
18        let mut output = [0; 32];
19        let mut sh = Blake2b::new(32);
20        let bytes = [];
21        sh.input(&bytes);
22        sh.result(&mut output);
23        let sentinel = Hash::from(output);
24
25        for hash in leaves.iter() {
26            let mut sh = Blake2b::new(32);
27            let mut output = [0; 32];
28            sh.input(&[0x00]);
29            sh.input(&hash.to_array());
30            sh.result(&mut output);
31            let leaf = Hash::from(output);
32            nodes.push(leaf);
33        }
34
35        let mut len = nodes.len();
36        let mut i = 0;
37
38        if len == 0 {
39            nodes.push(sentinel);
40            return MerkleTree { steps: nodes };
41        }
42
43        // len = 3;
44        while len > 1 {
45            for j in (0..len).step_by(2) {
46                let l = j;
47                let r = j + 1;
48
49                let left = nodes[i + l];
50
51                let right = if r < len { nodes[i + r] } else { sentinel };
52
53                let mut sh = Blake2b::new(32);
54                let mut output = [0; 32];
55                sh.input(&[0x01]);
56                sh.input(&left.to_array());
57                sh.input(&right.to_array());
58                sh.result(&mut output);
59
60                nodes.push(Hash::from(output));
61            }
62
63            i += len;
64
65            //@todo review
66            // len = (len + 1) >>> 1;
67            len = (len + 1) / 2;
68        }
69
70        MerkleTree { steps: nodes }
71    }
72
73    pub fn get_root(&self) -> Hash {
74        self.steps[self.steps.len() - 1]
75    }
76}
77
78#[cfg(test)]
79mod test {
80    use super::*;
81    use encodings::hex::FromHex;
82
83    #[test]
84    fn test_merkle_tree_generation() {
85        let leaves = vec![
86            Hash::from_hex("6ccc9037d0be8b70207fd3e384565743d3925e27e0923a57fa7fc51f8e951ba9")
87                .unwrap(),
88            Hash::from_hex("fa43aa977aa4f3e4ff8bbd8c05fa81eb0d00320bfca60f0acb129e8e696d99cf")
89                .unwrap(),
90        ];
91
92        let tree = MerkleTree::from_leaves(leaves);
93
94        dbg!(tree.get_root());
95    }
96}
97
98//@todo JSON serialization.
99//@todo binary serialization.
100//@todo testing
101//@todo abstract core functionality away from here -> maybe a new crate. Then we can benchmark much
102//better
103//@todo helper functions and defaults.
handshake_types/merkle_tree.rs

handshake_types/
merkle_tree.rs
