/
merkle.go
151 lines (131 loc) · 5.39 KB
/
merkle.go
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
// Copyright (c) 2013-2016 The btcsuite developers
// Copyright (c) 2015-2016 The Decred developers
// Use of this source code is governed by an ISC
// license that can be found in the LICENSE file.
package blockchain
import (
"math"
"github.com/bitum-project/bitumd/chaincfg/chainhash"
"github.com/bitum-project/bitumd/bitumutil"
"github.com/bitum-project/bitumd/wire"
)
// nextPowerOfTwo returns the next highest power of two from a given number if
// it is not already a power of two. This is a helper function used during the
// calculation of a merkle tree.
func nextPowerOfTwo(n int) int {
// Return the number if it's already a power of 2.
if n&(n-1) == 0 {
return n
}
// Figure out and return the next power of two.
exponent := uint(math.Log2(float64(n))) + 1
return 1 << exponent // 2^exponent
}
// HashMerkleBranches takes two hashes, treated as the left and right tree
// nodes, and returns the hash of their concatenation. This is a helper
// function used to aid in the generation of a merkle tree.
func HashMerkleBranches(left *chainhash.Hash, right *chainhash.Hash) *chainhash.Hash {
// Concatenate the left and right nodes.
var hash [chainhash.HashSize * 2]byte
copy(hash[:chainhash.HashSize], left[:])
copy(hash[chainhash.HashSize:], right[:])
newHash := chainhash.HashH(hash[:])
return &newHash
}
// populateMerkleStore constructs the merkle tree from all transaction hashes
// before offset, saving the merkle hashes to the remaining entries in merkles
// beginning at offset.
func populateMerkleStore(offset int, merkles []*chainhash.Hash) {
// Start the array offset after the last transaction and adjusted to the
// next power of two.
for i := 0; i < len(merkles)-1; i += 2 {
switch {
// When there is no left child node, the parent is nil too.
case merkles[i] == nil:
merkles[offset] = nil
// When there is no right child, the parent is generated by
// hashing the concatenation of the left child with itself.
case merkles[i+1] == nil:
newHash := HashMerkleBranches(merkles[i], merkles[i])
merkles[offset] = newHash
// The normal case sets the parent node to the hash of the
// concatentation of the left and right children.
default:
newHash := HashMerkleBranches(merkles[i], merkles[i+1])
merkles[offset] = newHash
}
offset++
}
}
// BuildMerkleTreeStore creates a merkle tree from a slice of transactions,
// stores it using a linear array, and returns a slice of the backing array. A
// linear array was chosen as opposed to an actual tree structure since it uses
// about half as much memory. The following describes a merkle tree and how it
// is stored in a linear array.
//
// 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 Bitum 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 above stored as a linear array is as follows:
//
// [h1 h2 h3 h4 h12 h34 root]
//
// As the above shows, the merkle root is always the last element in the array.
//
// 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.
// Since this function uses nodes that are pointers to the hashes, empty nodes
// will be nil.
func BuildMerkleTreeStore(transactions []*bitumutil.Tx) []*chainhash.Hash {
// If there's an empty stake tree, return totally zeroed out merkle tree root
// only.
if len(transactions) == 0 {
return []*chainhash.Hash{new(chainhash.Hash)}
}
// Calculate how many entries are required to hold the binary merkle
// tree as a linear array and create an array of that size.
nextPoT := nextPowerOfTwo(len(transactions))
arraySize := nextPoT*2 - 1
merkles := make([]*chainhash.Hash, arraySize)
// Create the base transaction hashes and populate the array with them.
for i, tx := range transactions {
msgTx := tx.MsgTx()
txHashFull := msgTx.TxHashFull()
merkles[i] = &txHashFull
}
// Construct the merkle tree in the remaining entries of the merkles slice.
populateMerkleStore(nextPoT, merkles)
return merkles
}
// BuildMsgTxMerkleTreeStore is identical to BuildMerkleTreeStore but takes a
// slice of the wire.MsgTx transaction type instead of the bitumutil.Tx wrapper.
// See BuildMerkleTreeStore for more details.
func BuildMsgTxMerkleTreeStore(transactions []*wire.MsgTx) []*chainhash.Hash {
// If there's an empty stake tree, return totally zeroed out merkle tree root
// only.
if len(transactions) == 0 {
return []*chainhash.Hash{new(chainhash.Hash)}
}
// Calculate how many entries are required to hold the binary merkle
// tree as a linear array and create an array of that size.
nextPoT := nextPowerOfTwo(len(transactions))
arraySize := nextPoT*2 - 1
merkles := make([]*chainhash.Hash, arraySize)
// Create the base transaction hashes and populate the array with them.
for i, tx := range transactions {
txHashFull := tx.TxHashFull()
merkles[i] = &txHashFull
}
// Construct the merkle tree in the remaining entries of the merkles slice.
populateMerkleStore(nextPoT, merkles)
return merkles
}