forked from nknorg/nkn
-
Notifications
You must be signed in to change notification settings - Fork 0
/
merkleTree.go
111 lines (99 loc) · 2.32 KB
/
merkleTree.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
package crypto
import (
"bytes"
"crypto/sha256"
"errors"
"github.com/nknorg/nkn/v2/common"
)
var (
DOUBLE_SHA256 = func(s []common.Uint256) common.Uint256 {
b := new(bytes.Buffer)
for _, d := range s {
d.Serialize(b)
}
temp := sha256.Sum256(b.Bytes())
f := sha256.Sum256(temp[:])
return common.Uint256(f)
}
)
type MerkleTree struct {
Depth uint
Root *MerkleTreeNode
}
type MerkleTreeNode struct {
Hash common.Uint256
Left *MerkleTreeNode
Right *MerkleTreeNode
}
func (t *MerkleTreeNode) IsLeaf() bool {
return t.Left == nil && t.Right == nil
}
//use []Uint256 to create a new MerkleTree
func NewMerkleTree(hashes []common.Uint256) (*MerkleTree, error) {
if len(hashes) == 0 {
return nil, errors.New("NewMerkleTree input no item error.")
}
var height uint
height = 1
nodes := generateLeaves(hashes)
for len(nodes) > 1 {
nodes = levelUp(nodes)
height += 1
}
mt := &MerkleTree{
Root: nodes[0],
Depth: height,
}
return mt, nil
}
//Generate the leaves nodes
func generateLeaves(hashes []common.Uint256) []*MerkleTreeNode {
var leaves []*MerkleTreeNode
for _, d := range hashes {
node := &MerkleTreeNode{
Hash: d,
}
leaves = append(leaves, node)
}
return leaves
}
//calc the next level's hash use double sha256
func levelUp(nodes []*MerkleTreeNode) []*MerkleTreeNode {
var nextLevel []*MerkleTreeNode
for i := 0; i < len(nodes)/2; i++ {
var data []common.Uint256
data = append(data, nodes[i*2].Hash)
data = append(data, nodes[i*2+1].Hash)
hash := DOUBLE_SHA256(data)
node := &MerkleTreeNode{
Hash: hash,
Left: nodes[i*2],
Right: nodes[i*2+1],
}
nextLevel = append(nextLevel, node)
}
if len(nodes)%2 == 1 {
var data []common.Uint256
data = append(data, nodes[len(nodes)-1].Hash)
data = append(data, nodes[len(nodes)-1].Hash)
hash := DOUBLE_SHA256(data)
node := &MerkleTreeNode{
Hash: hash,
Left: nodes[len(nodes)-1],
Right: nodes[len(nodes)-1],
}
nextLevel = append(nextLevel, node)
}
return nextLevel
}
//input a []uint256, create a MerkleTree & calc the root hash
func ComputeRoot(hashes []common.Uint256) (common.Uint256, error) {
if len(hashes) == 0 {
return common.Uint256{}, errors.New("NewMerkleTree input no item error.")
}
if len(hashes) == 1 {
return hashes[0], nil
}
tree, _ := NewMerkleTree(hashes)
return tree.Root.Hash, nil
}