-
Notifications
You must be signed in to change notification settings - Fork 27
/
merkle_tree.go
148 lines (136 loc) · 3.63 KB
/
merkle_tree.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
package util
import (
"fmt"
)
/*MerkleTree - A data structure that implements MerkleTreeI interface */
type MerkleTree struct {
tree []string
leavesCount int
levels int
}
func VerifyMerklePath(hash string, path *MTPath, root string) bool {
mthash := hash
pathNodes := path.Nodes
pl := len(pathNodes)
idx := path.LeafIndex
for i := 0; i < pl; i++ {
if idx&1 == 1 {
mthash = MHash(pathNodes[i], mthash)
} else {
mthash = MHash(mthash, pathNodes[i])
}
idx = (idx - idx&1) / 2
}
return mthash == root
}
func (mt *MerkleTree) computeSize(leaves int) (int, int) {
if leaves == 1 {
return 2, 2
}
var tsize int
var levels int
for ll := leaves; ll > 1; ll = (ll + 1) / 2 {
tsize += ll
levels++
}
tsize++
levels++
return tsize, levels
}
/*ComputeTree - given the leaf nodes, compute the merkle tree */
func (mt *MerkleTree) ComputeTree(hashes []Hashable) {
var tsize int
tsize, mt.levels = mt.computeSize(len(hashes))
mt.leavesCount = len(hashes)
mt.tree = make([]string, tsize)
for idx, hashable := range hashes {
mt.tree[idx] = hashable.GetHash()
}
if len(hashes) == 1 {
mt.tree[1] = DecodeAndMHash(mt.tree[0], mt.tree[0])
return
}
for pl0, plsize := 0, mt.leavesCount; plsize > 1; pl0, plsize = pl0+plsize, (plsize+1)/2 {
l0 := pl0 + plsize
for i, j := 0, 0; i < plsize; i, j = i+2, j+1 {
mt.tree[pl0+plsize+j] = DecodeAndMHash(mt.tree[pl0+i], mt.tree[pl0+i+1])
}
if plsize&1 == 1 {
mt.tree[l0+plsize/2] = DecodeAndMHash(mt.tree[pl0+plsize-1], mt.tree[pl0+plsize-1])
}
}
}
/*GetRoot - get the root of the merkle tree */
func (mt *MerkleTree) GetRoot() string {
return mt.tree[len(mt.tree)-1]
}
/*GetTree - get the entire merkle tree */
func (mt *MerkleTree) GetTree() []string {
return mt.tree
}
/*SetTree - set the entire merkle tree */
func (mt *MerkleTree) SetTree(leavesCount int, tree []string) error {
size, levels := mt.computeSize(leavesCount)
if size != len(tree) {
return fmt.Errorf("Merkle tree with leaves %v should have size %v but only %v is given", leavesCount, size, len(tree))
}
mt.levels = levels
mt.tree = tree
mt.leavesCount = leavesCount
return nil
}
/*GetLeafIndex - Get the index of the leaf node in the tree */
func (mt *MerkleTree) GetLeafIndex(hash Hashable) int {
hs := hash.GetHash()
for i := 0; i < mt.leavesCount; i++ {
if mt.tree[i] == hs {
return i
}
}
return -1
}
/*GetPath - get the path that can be used to verify the merkle tree */
func (mt *MerkleTree) GetPath(hash Hashable) *MTPath {
hidx := mt.GetLeafIndex(hash)
if hidx < 0 {
return &MTPath{}
}
return mt.GetPathByIndex(hidx)
}
/*VerifyPath - given a leaf node and the path, verify that the node is part of the tree */
func (mt *MerkleTree) VerifyPath(hash Hashable, path *MTPath) bool {
hs := hash.GetHash()
return VerifyMerklePath(hs, path, mt.GetRoot())
}
/*GetPathByIndex - get the path of a leaf node at index i */
func (mt *MerkleTree) GetPathByIndex(idx int) *MTPath {
path := make([]string, mt.levels-1)
mpath := &MTPath{LeafIndex: idx}
if idx&1 == 1 {
path[0] = mt.tree[idx-1]
} else {
if idx+1 < mt.leavesCount {
path[0] = mt.tree[idx+1]
} else {
path[0] = mt.tree[idx]
}
}
for pl0, plsize, pi := 0, mt.leavesCount, 1; plsize > 2; pl0, plsize, pi = pl0+plsize, (plsize+1)/2, pi+1 {
l0 := pl0 + plsize
idx = (idx - idx&1) / 2
if idx&1 == 1 {
//path = append(path, mt.tree[l0+idx-1])
path[pi] = mt.tree[l0+idx-1]
} else {
if l0+idx+1 < l0+(plsize+1)/2 {
//path = append(path, mt.tree[l0+idx+1])
path[pi] = mt.tree[l0+idx+1]
} else {
//path = append(path, mt.tree[l0+idx])
path[pi] = mt.tree[l0+idx]
}
}
}
mpath.Nodes = path
return mpath
}