forked from cpacia/BitcoinCash-Wallet
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mblock.go
177 lines (161 loc) · 5.19 KB
/
mblock.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
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
package bitcoincash
import (
"fmt"
"errors"
"github.com/gcash/bchd/chaincfg/chainhash"
"github.com/gcash/bchd/wire"
)
func MakeMerkleParent(left *chainhash.Hash, right *chainhash.Hash) (*chainhash.Hash, error) {
// dupes can screw things up; CVE-2012-2459. check for them
if left != nil && right != nil && left.IsEqual(right) {
return nil, errors.New("DUP HASH CRASH")
}
// if left child is nil, output nil. Need this for hard mode.
if left == nil {
return nil, errors.New("Left child is nil")
}
// if right is nil, hash left with itself
if right == nil {
right = left
}
// Concatenate the left and right nodes
var sha [64]byte
copy(sha[:32], left[:])
copy(sha[32:], right[:])
newSha := chainhash.DoubleHashH(sha[:])
return &newSha, nil
}
type merkleNode struct {
p uint32 // position in the binary tree
h *chainhash.Hash // hash
}
// given n merkle leaves, how deep is the tree?
// iterate shifting left until greater than n
func treeDepth(n uint32) (e uint8) {
for ; (1 << e) < n; e++ {
}
return
}
// smallest power of 2 that can contain n
func nextPowerOfTwo(n uint32) uint32 {
return 1 << treeDepth(n) // 2^exponent
}
// check if a node is populated based on node position and size of tree
func inDeadZone(pos, size uint32) bool {
msb := nextPowerOfTwo(size)
last := size - 1 // last valid position is 1 less than size
if pos > (msb<<1)-2 { // greater than root; not even in the tree
log.Debug(" ?? greater than root ")
return true
}
h := msb
for pos >= h {
h = h>>1 | msb
last = last>>1 | msb
}
return pos > last
}
// take in a merkle block, parse through it, and return txids indicated
// If there's any problem return an error. Checks self-consistency only.
// doing it with a stack instead of recursion. Because...
// OK I don't know why I'm just not in to recursion OK?
func checkMBlock(m *wire.MsgMerkleBlock) ([]*chainhash.Hash, error) {
if m.Transactions == 0 {
return nil, fmt.Errorf("No transactions in merkleblock")
}
if len(m.Flags) == 0 {
return nil, fmt.Errorf("No flag bits")
}
var s []merkleNode // the stack
var r []*chainhash.Hash // slice to return; txids we care about
// set initial position to root of merkle tree
msb := nextPowerOfTwo(m.Transactions) // most significant bit possible
pos := (msb << 1) - 2 // current position in tree
var i uint8 // position in the current flag byte
var tip int
// main loop
for {
tip = len(s) - 1 // slice position of stack tip
// First check if stack operations can be performed
// is stack one filled item? that's complete.
if tip == 0 && s[0].h != nil {
if s[0].h.IsEqual(&m.Header.MerkleRoot) {
return r, nil
}
return nil, fmt.Errorf("computed root %s but expect %s\n",
s[0].h.String(), m.Header.MerkleRoot.String())
}
// is current position in the tree's dead zone? partial parent
if inDeadZone(pos, m.Transactions) {
// create merkle parent from single side (left)
h, err := MakeMerkleParent(s[tip].h, nil)
if err != nil {
return r, err
}
s[tip-1].h = h
s = s[:tip] // remove 1 from stack
pos = s[tip-1].p | 1 // move position to parent's sibling
continue
}
// does stack have 3+ items? and are last 2 items filled?
if tip > 1 && s[tip-1].h != nil && s[tip].h != nil {
//fmt.Printf("nodes %d and %d combine into %d\n",
// s[tip-1].p, s[tip].p, s[tip-2].p)
// combine two filled nodes into parent node
h, err := MakeMerkleParent(s[tip-1].h, s[tip].h)
if err != nil {
return r, err
}
s[tip-2].h = h
// remove children
s = s[:tip-1]
// move position to parent's sibling
pos = s[tip-2].p | 1
continue
}
// no stack ops to perform, so make new node from message hashes
if len(m.Hashes) == 0 {
return nil, fmt.Errorf("Ran out of hashes at position %d.", pos)
}
if len(m.Flags) == 0 {
return nil, fmt.Errorf("Ran out of flag bits.")
}
var n merkleNode // make new node
n.p = pos // set current position for new node
if pos&msb != 0 { // upper non-txid hash
if m.Flags[0]&(1<<i) == 0 { // flag bit says fill node
n.h = m.Hashes[0] // copy hash from message
m.Hashes = m.Hashes[1:] // pop off message
if pos&1 != 0 { // right side; ascend
pos = pos>>1 | msb
} else { // left side, go to sibling
pos |= 1
}
} else { // flag bit says skip; put empty on stack and descend
pos = (pos ^ msb) << 1 // descend to left
}
s = append(s, n) // push new node on stack
} else { // bottom row txid; flag bit indicates tx of interest
if pos >= m.Transactions {
// this can't happen because we check deadzone above...
return nil, fmt.Errorf("got into an invalid txid node")
}
n.h = m.Hashes[0] // copy hash from message
m.Hashes = m.Hashes[1:] // pop off message
if m.Flags[0]&(1<<i) != 0 { //txid of interest
r = append(r, n.h)
}
if pos&1 == 0 { // left side, go to sibling
pos |= 1
} // if on right side we don't move; stack ops will move next
s = append(s, n) // push new node onto the stack
}
// done with pushing onto stack; advance flag bit
i++
if i == 8 { // move to next byte
i = 0
m.Flags = m.Flags[1:]
}
}
return nil, fmt.Errorf("ran out of things to do?")
}