forked from FactomProject/FactomCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmerkle.go
More file actions
executable file
·74 lines (62 loc) · 2.33 KB
/
merkle.go
File metadata and controls
executable file
·74 lines (62 loc) · 2.33 KB
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
package notaryapi
import (
"math"
)
// 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 *Hash, right *Hash) *Hash {
// Concatenate the left and right nodes.
var barray []byte = make ([]byte, HashSize * 2)
copy(barray[:HashSize], left.Bytes)
copy(barray[HashSize:], right.Bytes)
newSha := Sha(barray)
return newSha
}
func BuildMerkleTreeStore(hashes []*Hash) (merkles []*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(hashes))
arraySize := nextPoT*2 - 1
// fmt.Println("hashes.len=", len(hashes), ", nextPoT=", nextPoT, ", array.size=", arraySize)
merkles = make([]*Hash, arraySize)
// Create the base transaction shas and populate the array with them.
//for i, entity := range entities {
//merkles[i] = entity.ShaHash()
//}
copy(merkles[:len(hashes)], hashes[:])
// Start the array offset after the last transaction and adjusted to the
// next power of two.
offset := nextPoT
for i := 0; i < arraySize-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:
newSha := hashMerkleBranches(merkles[i], merkles[i])
merkles[offset] = newSha
// The normal case sets the parent node to the double sha256
// of the concatentation of the left and right children.
default:
newSha := hashMerkleBranches(merkles[i], merkles[i+1])
merkles[offset] = newSha
}
offset++
}
return merkles
}