1
|
|
|
<?php |
2
|
|
|
|
3
|
|
|
declare(strict_types=1); |
4
|
|
|
|
5
|
|
|
namespace BitWasp\Bitcoin\Block; |
6
|
|
|
|
7
|
|
|
use BitWasp\Bitcoin\Crypto\Hash; |
8
|
|
|
use BitWasp\Bitcoin\Serializable; |
9
|
|
|
use BitWasp\Bitcoin\Serializer\Block\PartialMerkleTreeSerializer; |
10
|
|
|
use BitWasp\Buffertools\Buffer; |
11
|
|
|
use BitWasp\Buffertools\BufferInterface; |
12
|
|
|
use BitWasp\Buffertools\Buffertools; |
13
|
|
|
|
14
|
|
|
class PartialMerkleTree extends Serializable |
15
|
|
|
{ |
16
|
|
|
/** |
17
|
|
|
* @var int |
18
|
|
|
*/ |
19
|
|
|
private $elementCount; |
20
|
|
|
|
21
|
|
|
/** |
22
|
|
|
* @var BufferInterface[] |
23
|
|
|
*/ |
24
|
|
|
private $vHashes = []; |
25
|
|
|
|
26
|
|
|
/** |
27
|
|
|
* @var array |
28
|
|
|
*/ |
29
|
|
|
private $vFlagBits = []; |
30
|
|
|
|
31
|
|
|
/** |
32
|
|
|
* @var bool |
33
|
|
|
*/ |
34
|
|
|
private $fBad = false; |
35
|
|
|
|
36
|
|
|
/** |
37
|
|
|
* Takes array of hashes and flag array only. Use PartialMerkleTree::create() instead of creating instance directly.. |
38
|
|
|
* |
39
|
|
|
* @param int $txCount |
40
|
|
|
* @param array $vHashes |
41
|
|
|
* @param array $vBits |
42
|
|
|
*/ |
43
|
6 |
|
public function __construct(int $txCount = 0, array $vHashes = [], array $vBits = []) |
44
|
|
|
{ |
45
|
6 |
|
$this->elementCount = $txCount; |
46
|
6 |
|
$this->vHashes = $vHashes; |
47
|
6 |
|
$this->vFlagBits = $vBits; |
48
|
6 |
|
} |
49
|
|
|
|
50
|
|
|
/** |
51
|
|
|
* Construct the Merkle tree |
52
|
|
|
* |
53
|
|
|
* @param int $txCount |
54
|
|
|
* @param array $vTxHashes |
55
|
|
|
* @param array $vMatch |
56
|
|
|
* @return PartialMerkleTree |
57
|
|
|
*/ |
58
|
6 |
|
public static function create(int $txCount, array $vTxHashes, array $vMatch) |
59
|
|
|
{ |
60
|
6 |
|
$tree = new self($txCount); |
61
|
6 |
|
$tree->traverseAndBuild($tree->calcTreeHeight(), 0, $vTxHashes, $vMatch); |
62
|
6 |
|
return $tree; |
63
|
|
|
} |
64
|
|
|
|
65
|
|
|
/** |
66
|
|
|
* Calculate tree width for a given height. |
67
|
|
|
* |
68
|
|
|
* @param int $height |
69
|
|
|
* @return int |
70
|
|
|
*/ |
71
|
6 |
|
public function calcTreeWidth(int $height) |
72
|
|
|
{ |
73
|
6 |
|
return ($this->elementCount + (1 << $height) - 1) >> $height; |
74
|
|
|
} |
75
|
|
|
|
76
|
|
|
/** |
77
|
|
|
* Calculate the tree height. |
78
|
|
|
* |
79
|
|
|
* @return int |
80
|
|
|
*/ |
81
|
6 |
|
public function calcTreeHeight(): int |
82
|
|
|
{ |
83
|
6 |
|
$height = 0; |
84
|
6 |
|
while ($this->calcTreeWidth($height) > 1) { |
85
|
4 |
|
$height++; |
86
|
|
|
} |
87
|
|
|
|
88
|
6 |
|
return $height; |
89
|
|
|
} |
90
|
|
|
|
91
|
|
|
/** |
92
|
|
|
* @return int |
93
|
|
|
*/ |
94
|
6 |
|
public function getTxCount(): int |
95
|
|
|
{ |
96
|
6 |
|
return $this->elementCount; |
97
|
|
|
} |
98
|
|
|
|
99
|
|
|
/** |
100
|
|
|
* @return BufferInterface[] |
101
|
|
|
*/ |
102
|
4 |
|
public function getHashes(): array |
103
|
|
|
{ |
104
|
4 |
|
return $this->vHashes; |
105
|
|
|
} |
106
|
|
|
|
107
|
|
|
/** |
108
|
|
|
* @return array |
109
|
|
|
*/ |
110
|
4 |
|
public function getFlagBits(): array |
111
|
|
|
{ |
112
|
4 |
|
return $this->vFlagBits; |
113
|
|
|
} |
114
|
|
|
|
115
|
|
|
/** |
116
|
|
|
* Calculate the hash for the given $height and $position |
117
|
|
|
* |
118
|
|
|
* @param int $height |
119
|
|
|
* @param int $position |
120
|
|
|
* @param \BitWasp\Buffertools\BufferInterface[] $vTxid |
121
|
|
|
* @return \BitWasp\Buffertools\BufferInterface |
122
|
|
|
*/ |
123
|
6 |
|
public function calculateHash(int $height, $position, array $vTxid): BufferInterface |
124
|
|
|
{ |
125
|
6 |
|
if ($height === 0) { |
126
|
6 |
|
return $vTxid[$position]; |
127
|
|
|
} else { |
128
|
4 |
|
$left = $this->calculateHash($height - 1, $position * 2, $vTxid); |
129
|
4 |
|
if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) { |
130
|
4 |
|
$right = $this->calculateHash($height - 1, ($position * 2 + 1), $vTxid); |
131
|
|
|
} else { |
132
|
|
|
$right = $left; |
133
|
|
|
} |
134
|
|
|
|
135
|
4 |
|
return Hash::sha256d(Buffertools::concat($left, $right)); |
136
|
|
|
} |
137
|
|
|
} |
138
|
|
|
|
139
|
|
|
/** |
140
|
|
|
* Construct the list of Merkle Tree hashes |
141
|
|
|
* |
142
|
|
|
* @param int $height |
143
|
|
|
* @param int $position |
144
|
|
|
* @param array $vTxid - array of Txid's in the block |
145
|
|
|
* @param array $vMatch - reference to array to populate |
146
|
|
|
*/ |
147
|
6 |
|
public function traverseAndBuild(int $height, int $position, array $vTxid, array &$vMatch) |
148
|
|
|
{ |
149
|
6 |
|
$parent = false; |
150
|
6 |
|
for ($p = $position << $height; $p < ($position + 1) << $height && $p < $this->elementCount; $p++) { |
151
|
6 |
|
$parent |= $vMatch[$p]; |
152
|
|
|
} |
153
|
|
|
|
154
|
6 |
|
$this->vFlagBits[] = $parent; |
155
|
|
|
|
156
|
6 |
|
if (0 === $height || !$parent) { |
|
|
|
|
157
|
6 |
|
$this->vHashes[] = $this->calculateHash($height, $position, $vTxid); |
158
|
|
|
} else { |
159
|
4 |
|
$this->traverseAndBuild($height - 1, $position * 2, $vTxid, $vMatch); |
160
|
4 |
|
if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) { |
161
|
4 |
|
$this->traverseAndBuild($height - 1, $position * 2 + 1, $vTxid, $vMatch); |
162
|
|
|
} |
163
|
|
|
} |
164
|
6 |
|
} |
165
|
|
|
|
166
|
|
|
/** |
167
|
|
|
* Traverse the Merkle Tree hashes and extract those which have a matching bit. |
168
|
|
|
* |
169
|
|
|
* @param int $height |
170
|
|
|
* @param int $position |
171
|
|
|
* @param int $nBitsUsed |
172
|
|
|
* @param int $nHashUsed |
173
|
|
|
* @param BufferInterface[] $vMatch |
174
|
|
|
* @return BufferInterface |
175
|
|
|
*/ |
176
|
6 |
|
public function traverseAndExtract(int $height, int $position, &$nBitsUsed, &$nHashUsed, &$vMatch): BufferInterface |
177
|
|
|
{ |
178
|
6 |
|
if ($nBitsUsed >= count($this->vFlagBits)) { |
179
|
|
|
$this->fBad = true; |
180
|
|
|
return new Buffer(); |
181
|
|
|
} |
182
|
|
|
|
183
|
6 |
|
$parent = $this->vFlagBits[$nBitsUsed++]; |
184
|
6 |
|
if (0 === $height || !$parent) { |
185
|
6 |
|
if ($nHashUsed >= count($this->vHashes)) { |
186
|
|
|
$this->fBad = true; |
187
|
|
|
return new Buffer(); |
188
|
|
|
} |
189
|
6 |
|
$hash = $this->vHashes[$nHashUsed++]; |
190
|
6 |
|
if ($height === 0 && $parent) { |
191
|
6 |
|
$vMatch[] = $hash->flip(); |
192
|
|
|
} |
193
|
6 |
|
return $hash; |
194
|
|
|
} else { |
195
|
4 |
|
$left = $this->traverseAndExtract($height - 1, $position * 2, $nBitsUsed, $nHashUsed, $vMatch); |
196
|
4 |
|
if (($position * 2 + 1) < $this->calcTreeWidth($height - 1)) { |
197
|
4 |
|
$right = $this->traverseAndExtract($height - 1, ($position * 2 + 1), $nBitsUsed, $nHashUsed, $vMatch); |
198
|
4 |
|
if ($right === $left) { |
199
|
4 |
|
$this->fBad = true; |
200
|
|
|
} |
201
|
|
|
} else { |
202
|
2 |
|
$right = $left; |
203
|
|
|
} |
204
|
|
|
|
205
|
4 |
|
return Hash::sha256d(Buffertools::concat($left, $right)); |
206
|
|
|
} |
207
|
|
|
} |
208
|
|
|
|
209
|
|
|
/** |
210
|
|
|
* Extract matches from the tree into provided $vMatch reference. |
211
|
|
|
* |
212
|
|
|
* @param BufferInterface[] $vMatch - reference to array of extracted 'matching' hashes |
213
|
|
|
* @return BufferInterface - this will be the merkle root |
214
|
|
|
* @throws \Exception |
215
|
|
|
*/ |
216
|
6 |
|
public function extractMatches(array &$vMatch): BufferInterface |
217
|
|
|
{ |
218
|
6 |
|
$nTx = $this->getTxCount(); |
219
|
6 |
|
if (0 === $nTx) { |
220
|
|
|
throw new \Exception('ntx = 0'); |
221
|
|
|
} |
222
|
|
|
|
223
|
6 |
|
if ($nTx > BlockInterface::MAX_BLOCK_SIZE / 60) { |
224
|
|
|
throw new \Exception('ntx > bound size'); |
225
|
|
|
} |
226
|
|
|
|
227
|
6 |
|
if (count($this->vHashes) > $nTx) { |
228
|
|
|
throw new \Exception('nHashes > nTx'); |
229
|
|
|
} |
230
|
|
|
|
231
|
6 |
|
if (count($this->vFlagBits) < count($this->vHashes)) { |
232
|
|
|
throw new \Exception('nBits < nHashes'); |
233
|
|
|
} |
234
|
|
|
|
235
|
6 |
|
$height = $this->calcTreeHeight(); |
236
|
6 |
|
$nBitsUsed = 0; |
237
|
6 |
|
$nHashesUsed = 0; |
238
|
6 |
|
$merkleRoot = $this->traverseAndExtract($height, 0, $nBitsUsed, $nHashesUsed, $vMatch); |
239
|
6 |
|
$merkleRoot = $merkleRoot->flip(); |
240
|
6 |
|
if ($this->fBad) { |
241
|
|
|
throw new \Exception('bad data'); |
242
|
|
|
} |
243
|
|
|
|
244
|
6 |
|
if (ceil(($nBitsUsed + 7) / 8) !== ceil((count($this->vFlagBits)+7)/8)) { |
245
|
|
|
throw new \Exception('Not all bits consumed'); |
246
|
|
|
} |
247
|
|
|
|
248
|
6 |
|
if ($nHashesUsed !== count($this->vHashes)) { |
249
|
|
|
throw new \Exception('Not all hashes consumed'); |
250
|
|
|
} |
251
|
|
|
|
252
|
6 |
|
return $merkleRoot; |
253
|
|
|
} |
254
|
|
|
|
255
|
|
|
/** |
256
|
|
|
* @return BufferInterface |
257
|
|
|
*/ |
258
|
1 |
|
public function getBuffer(): BufferInterface |
259
|
|
|
{ |
260
|
1 |
|
return (new PartialMerkleTreeSerializer())->serialize($this); |
261
|
|
|
} |
262
|
|
|
} |
263
|
|
|
|
In PHP, under loose comparison (like
==
, or!=
, orswitch
conditions), values of different types might be equal.For
integer
values, zero is a special case, in particular the following results might be unexpected: