1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110

use crypto::digest::Digest;

use tree::{ Tree };
use merkledigest::{ MerkleDigest };

pub use proof::{
    Proof,
    ProofBlock
};

/// A Merkle tree is a binary tree, with values of type `T` at the leafs,
/// and where every node holds the hash of the concatenation of the hashes of
/// its children nodes.
pub struct MerkleTree<D, T> {
    /// The hashing function used by this Merkle tree
    pub digest: D,

    /// The inner binary tree
    pub tree: Tree<T>,

    /// The height of the tree
    pub height: usize,

    /// The number of leaf nodes in the tree
    pub count: usize
}

impl <D, T> MerkleTree<D, T> where D: Digest + Clone, T: Into<Vec<u8>> + Clone {

    /// Constructs a Merkle Tree from a vector of data blocks
    pub fn from_vec(mut digest: D, values: Vec<T>) -> Self {
        if values.is_empty() {
            panic!("Cannot build a Merkle tree from an empty vector.");
        }

        let count      = values.len();
        let mut height = 0;

        let mut cur = Vec::with_capacity(count);

        for v in values.into_iter() {
            let leaf = Tree::make_leaf(&mut digest, v);
            cur.push(leaf);
        }

        while cur.len() > 1 {
            let mut next = Vec::new();
            while cur.len() > 0 {
                if cur.len() == 1 {
                    next.push(cur.remove(0));
                }
                else {
                    let left  = cur.remove(0);
                    let right = cur.remove(0);

                    let combined_hash = digest.combine_hashes(
                        left.get_hash(),
                        right.get_hash()
                    );

                    let node = Tree::Node {
                       hash: combined_hash,
                       left: Box::new(left),
                       right: Box::new(right)
                    };

                    next.push(node);
                }
            }

            height += 1;

            cur = next;
        }

        assert!(cur.len() == 1);

        let tree = cur.remove(0);

        MerkleTree {
            digest: digest,
            tree: tree,
            height: height,
            count: count
        }
    }

    /// Returns the tree's root hash
    pub fn root_hash(&self) -> &Vec<u8> {
        self.tree.get_hash()
    }

    /// Generate an inclusion proof for the given value.
    /// `None` is returned if the given value is not found in the tree.
    pub fn gen_proof(&self, value: &T) -> Option<Proof<D, T>> {
        let mut digest = self.digest.clone();
        let hash       = digest.hash_bytes(&value.clone().into());

        ProofBlock::new(&self.tree, &hash).map(|block|
            Proof {
                digest: digest,
                root_hash: self.root_hash().clone(),
                block: block,
                value: value.clone()
            }
        )
    }

}