bitcoin/util/
hash.rs

1// Rust Bitcoin Library
2// Written in 2014 by
3//     Andrew Poelstra <apoelstra@wpsoftware.net>
4// To the extent possible under law, the author(s) have dedicated all
5// copyright and related and neighboring rights to this software to
6// the public domain worldwide. This software is distributed without
7// any warranty.
8//
9// You should have received a copy of the CC0 Public Domain Dedication
10// along with this software.
11// If not, see <http://creativecommons.org/publicdomain/zero/1.0/>.
12//
13
14//! Hash functions
15//!
16//! Utility functions related to hashing data, including merkleization
17
18use std::cmp::min;
19use std::default::Default;
20
21use bitcoin_hashes::{sha256d, Hash};
22
23use consensus::encode::Encodable;
24
25/// Any collection of objects for which a merkle root makes sense to calculate
26pub trait MerkleRoot {
27    /// Construct a merkle tree from a collection, with elements ordered as
28    /// they were in the original collection, and return the merkle root.
29    fn merkle_root(&self) -> sha256d::Hash;
30}
31
32/// Calculates the merkle root of a list of txids hashes directly
33pub fn bitcoin_merkle_root(data: Vec<sha256d::Hash>) -> sha256d::Hash {
34    // Base case
35    if data.len() < 1 {
36        return Default::default();
37    }
38    if data.len() < 2 {
39        return data[0];
40    }
41    // Recursion
42    let mut next = vec![];
43    for idx in 0..((data.len() + 1) / 2) {
44        let idx1 = 2 * idx;
45        let idx2 = min(idx1 + 1, data.len() - 1);
46        let mut encoder = sha256d::Hash::engine();
47        data[idx1].consensus_encode(&mut encoder).unwrap();
48        data[idx2].consensus_encode(&mut encoder).unwrap();
49        next.push(sha256d::Hash::from_engine(encoder));
50    }
51    bitcoin_merkle_root(next)
52}
53
54impl<'a, T: BitcoinHash> MerkleRoot for &'a [T] {
55    fn merkle_root(&self) -> sha256d::Hash {
56        bitcoin_merkle_root(self.iter().map(|obj| obj.bitcoin_hash()).collect())
57    }
58}
59
60impl <T: BitcoinHash> MerkleRoot for Vec<T> {
61    fn merkle_root(&self) -> sha256d::Hash {
62        (&self[..]).merkle_root()
63    }
64}
65
66/// Objects which are referred to by hash
67pub trait BitcoinHash {
68    /// Produces a Sha256dHash which can be used to refer to the object
69    fn bitcoin_hash(&self) -> sha256d::Hash;
70}