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

// Copyright 2019 Stichting Organism
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright (c) 2019 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.

use crate::hash::H256;

// fast_merkle_root treats the provided slice of hashes as leaves of a merkle tree
// and returns the resulting merkle root.
//
// A merkle tree is a tree in which every non-leaf node is the hash of its
// children nodes.  A diagram depicting how this works for Organism transactions
// where h(x) is a blake256 hash follows:
//
//	         root = h1234 = h(h12 + h34)
//	        /                           \
//	  h12 = h(h1 + h2)            h34 = h(h3 + h4)
//	   /            \              /            \
//	h1 = h(tx1)  h2 = h(tx2)    h3 = h(tx3)  h4 = h(tx4)
//
// The number of inputs is not always a power of two which results in a
// balanced tree structure as above.  In that case, parent nodes with no
// children are also zero and parent nodes with only a single left node
// are calculated by concatenating the left node with itself before hashing.
pub fn fast_merkle_root(mut leaves: Vec<H256>) -> H256 {
    // All zero.
    if leaves.len() == 0 {
        return H256::zero();
    }

    if leaves.len() < 2 {
        return leaves[0];
    }
    // The following algorithm works by replacing the leftmost entries in the
    // slice with the concatenations of each subsequent set of 2 hashes and
    // shrinking the slice by half to account for the fact that each level of
    // the tree is half the size of the previous one.  In the case a level is
    // unbalanced (there is no final right child), the final node is duplicated
    // so it ultimately is concatenated with itself.
    //
    // For example, the following illustrates calculating a tree with 5 leaves:
    //
    // [0 1 2 3 4]                              (5 entries)
    // 1st iteration: [h(0||1) h(2||3) h(4||4)] (3 entries)
    // 2nd iteration: [h(h01||h23) h(h44||h44)] (2 entries)
    // 3rd iteration: [h(h0123||h4444)]         (1 entry)
    while leaves.len() > 1 {
        // When there is no right child, the parent is generated by hashing the
        // concatenation of the left child with itself.
        if leaves.len() & 1 != 0 {
            leaves.push(leaves[leaves.len() - 1]);
        }

        // Set the parent node to the hash of the concatenation of the left and
        // right children.
        let mut i = 0;
        while i < leaves.len() / 2 {
            let left = leaves[i * 2].hash_with(leaves[i * 2 + 1]);
            leaves[i] = left;
            i += 1;
        }
        let drain_start = leaves.len() / 2;
        leaves.split_off(drain_start);
    }

    leaves[0]
}

#[test]
fn test_to_merkle_fast_short() {
    let _inputs = vec![
        H256::from_hex("5e574591d900f7f9abb8f8eb31cc9330247d27ba293ad79c348d602ece717b8b").unwrap(),
        H256::from_hex("b3b70fe08c2da744c9559d533e8db35b3bfefba1b0f1c7b31e7d9d523c00a426").unwrap(),
        H256::from_hex("dd3058a7fc691ff4dee0a8cd6030f404ffda7e7aee88aff3985f7b2bbe4792f7").unwrap(),
        H256::from_hex("5e574591d900f7f9abb8f8eb31cc9330247d27ba293ad79c348d602ece717b8b").unwrap(),
        H256::from_hex("b3b70fe08c2da744c9559d533e8db35b3bfefba1b0f1c7b31e7d9d523c00a426").unwrap(),
        H256::from_hex("dd3058a7fc691ff4dee0a8cd6030f404ffda7e7aee88aff3985f7b2bbe4792f7").unwrap(),
        H256::from_hex("5e574591d900f7f9abb8f8eb31cc9330247d27ba293ad79c348d602ece717b8b").unwrap(),
        H256::from_hex("b3b70fe08c2da744c9559d533e8db35b3bfefba1b0f1c7b31e7d9d523c00a426").unwrap(),
        H256::from_hex("dd3058a7fc691ff4dee0a8cd6030f404ffda7e7aee88aff3985f7b2bbe4792f7").unwrap(),
    ];

    //assert_eq!(fast_merkle_root(&mut inputs),  H256::from_hex("a144c719391569aa20bf612bf5588bce71cd397574cb6c060e0bac100f6e5805").unwrap());
}

#[test]
fn test_to_merkle_fast_zero() {
    assert_eq!(fast_merkle_root(vec![H256::zero()]), H256::zero());
}