1 | 'use strict';
|
2 |
|
3 | var _ = require('lodash');
|
4 | var BlockHeader = require('./blockheader');
|
5 | var BufferUtil = require('../util/buffer');
|
6 | var BufferReader = require('../encoding/bufferreader');
|
7 | var BufferWriter = require('../encoding/bufferwriter');
|
8 | var Hash = require('../crypto/hash');
|
9 | var JSUtil = require('../util/js');
|
10 | var Transaction = require('../transaction');
|
11 | var errors = require('../errors');
|
12 | var $ = require('../util/preconditions');
|
13 |
|
14 |
|
15 |
|
16 |
|
17 |
|
18 |
|
19 |
|
20 |
|
21 |
|
22 | function MerkleBlock(arg) {
|
23 |
|
24 |
|
25 | if (!(this instanceof MerkleBlock)) {
|
26 | return new MerkleBlock(arg);
|
27 | }
|
28 |
|
29 | var info = {};
|
30 | if (BufferUtil.isBuffer(arg)) {
|
31 | info = MerkleBlock._fromBufferReader(BufferReader(arg));
|
32 | } else if (_.isObject(arg)) {
|
33 | var header;
|
34 | if(arg.header instanceof BlockHeader) {
|
35 | header = arg.header;
|
36 | } else {
|
37 | header = BlockHeader.fromObject(arg.header);
|
38 | }
|
39 | info = {
|
40 | |
41 |
|
42 |
|
43 |
|
44 | header: header,
|
45 | |
46 |
|
47 |
|
48 |
|
49 | numTransactions: arg.numTransactions,
|
50 | |
51 |
|
52 |
|
53 |
|
54 | hashes: arg.hashes,
|
55 | |
56 |
|
57 |
|
58 |
|
59 | flags: arg.flags
|
60 | };
|
61 | } else {
|
62 | throw new TypeError('Unrecognized argument for MerkleBlock');
|
63 | }
|
64 | _.extend(this,info);
|
65 | this._flagBitsUsed = 0;
|
66 | this._hashesUsed = 0;
|
67 |
|
68 | return this;
|
69 | }
|
70 |
|
71 |
|
72 |
|
73 |
|
74 |
|
75 | MerkleBlock.fromBuffer = function fromBuffer(buf) {
|
76 | return MerkleBlock.fromBufferReader(BufferReader(buf));
|
77 | };
|
78 |
|
79 |
|
80 |
|
81 |
|
82 |
|
83 | MerkleBlock.fromBufferReader = function fromBufferReader(br) {
|
84 | return new MerkleBlock(MerkleBlock._fromBufferReader(br));
|
85 | };
|
86 |
|
87 |
|
88 |
|
89 |
|
90 | MerkleBlock.prototype.toBuffer = function toBuffer() {
|
91 | return this.toBufferWriter().concat();
|
92 | };
|
93 |
|
94 |
|
95 |
|
96 |
|
97 |
|
98 | MerkleBlock.prototype.toBufferWriter = function toBufferWriter(bw) {
|
99 | if (!bw) {
|
100 | bw = new BufferWriter();
|
101 | }
|
102 | bw.write(this.header.toBuffer());
|
103 | bw.writeUInt32LE(this.numTransactions);
|
104 | bw.writeVarintNum(this.hashes.length);
|
105 | for (var i = 0; i < this.hashes.length; i++) {
|
106 | bw.write(Buffer.from(this.hashes[i], 'hex'));
|
107 | }
|
108 | bw.writeVarintNum(this.flags.length);
|
109 | for (i = 0; i < this.flags.length; i++) {
|
110 | bw.writeUInt8(this.flags[i]);
|
111 | }
|
112 | return bw;
|
113 | };
|
114 |
|
115 |
|
116 |
|
117 |
|
118 | MerkleBlock.prototype.toObject = MerkleBlock.prototype.toJSON = function toObject() {
|
119 | return {
|
120 | header: this.header.toObject(),
|
121 | numTransactions: this.numTransactions,
|
122 | hashes: this.hashes,
|
123 | flags: this.flags
|
124 | };
|
125 | };
|
126 |
|
127 |
|
128 |
|
129 |
|
130 |
|
131 | MerkleBlock.prototype.validMerkleTree = function validMerkleTree() {
|
132 | $.checkState(_.isArray(this.flags), 'MerkleBlock flags is not an array');
|
133 | $.checkState(_.isArray(this.hashes), 'MerkleBlock hashes is not an array');
|
134 |
|
135 |
|
136 | if(this.hashes.length > this.numTransactions) {
|
137 | return false;
|
138 | }
|
139 |
|
140 |
|
141 | if(this.flags.length * 8 < this.hashes.length) {
|
142 | return false;
|
143 | }
|
144 |
|
145 | var height = this._calcTreeHeight();
|
146 | var opts = { hashesUsed: 0, flagBitsUsed: 0 };
|
147 | var root = this._traverseMerkleTree(height, 0, opts);
|
148 | if(opts.hashesUsed !== this.hashes.length) {
|
149 | return false;
|
150 | }
|
151 | return BufferUtil.equals(root, this.header.merkleRoot);
|
152 | };
|
153 |
|
154 |
|
155 |
|
156 |
|
157 |
|
158 | MerkleBlock.prototype.filterdTxsHash = function filterdTxsHash() {
|
159 | $.checkState(_.isArray(this.flags), 'MerkleBlock flags is not an array');
|
160 | $.checkState(_.isArray(this.hashes), 'MerkleBlock hashes is not an array');
|
161 |
|
162 |
|
163 | if(this.hashes.length > this.numTransactions) {
|
164 | throw new errors.MerkleBlock.InvalidMerkleTree();
|
165 | }
|
166 |
|
167 |
|
168 | if(this.flags.length * 8 < this.hashes.length) {
|
169 | throw new errors.MerkleBlock.InvalidMerkleTree();
|
170 | }
|
171 |
|
172 |
|
173 | if(this.hashes.length === 1) {
|
174 | return [];
|
175 | };
|
176 |
|
177 | var height = this._calcTreeHeight();
|
178 | var opts = { hashesUsed: 0, flagBitsUsed: 0 };
|
179 | var txs = this._traverseMerkleTree(height, 0, opts, true);
|
180 | if(opts.hashesUsed !== this.hashes.length) {
|
181 | throw new errors.MerkleBlock.InvalidMerkleTree();
|
182 | }
|
183 | return txs;
|
184 | };
|
185 |
|
186 |
|
187 |
|
188 |
|
189 |
|
190 |
|
191 |
|
192 |
|
193 |
|
194 |
|
195 |
|
196 |
|
197 |
|
198 |
|
199 |
|
200 | MerkleBlock.prototype._traverseMerkleTree = function traverseMerkleTree(depth, pos, opts, checkForTxs) {
|
201 |
|
202 |
|
203 |
|
204 | opts = opts || {};
|
205 | opts.txs = opts.txs || [];
|
206 | opts.flagBitsUsed = opts.flagBitsUsed || 0;
|
207 | opts.hashesUsed = opts.hashesUsed || 0;
|
208 | var checkForTxs = checkForTxs || false;
|
209 |
|
210 | if(opts.flagBitsUsed > this.flags.length * 8) {
|
211 | return null;
|
212 | }
|
213 | var isParentOfMatch = (this.flags[opts.flagBitsUsed >> 3] >>> (opts.flagBitsUsed++ & 7)) & 1;
|
214 | if(depth === 0 || !isParentOfMatch) {
|
215 | if(opts.hashesUsed >= this.hashes.length) {
|
216 | return null;
|
217 | }
|
218 | var hash = this.hashes[opts.hashesUsed++];
|
219 | if(depth === 0 && isParentOfMatch) {
|
220 | opts.txs.push(hash);
|
221 | }
|
222 | return Buffer.from(hash, 'hex');
|
223 | } else {
|
224 | var left = this._traverseMerkleTree(depth-1, pos*2, opts);
|
225 | var right = left;
|
226 | if(pos*2+1 < this._calcTreeWidth(depth-1)) {
|
227 | right = this._traverseMerkleTree(depth-1, pos*2+1, opts);
|
228 | }
|
229 | if (checkForTxs){
|
230 | return opts.txs;
|
231 | } else {
|
232 | return Hash.sha256sha256(new Buffer.concat([left, right]));
|
233 | };
|
234 | }
|
235 | };
|
236 |
|
237 |
|
238 |
|
239 |
|
240 |
|
241 |
|
242 |
|
243 | MerkleBlock.prototype._calcTreeWidth = function calcTreeWidth(height) {
|
244 | return (this.numTransactions + (1 << height) - 1) >> height;
|
245 | };
|
246 |
|
247 |
|
248 |
|
249 |
|
250 |
|
251 |
|
252 | MerkleBlock.prototype._calcTreeHeight = function calcTreeHeight() {
|
253 | var height = 0;
|
254 | while (this._calcTreeWidth(height) > 1) {
|
255 | height++;
|
256 | }
|
257 | return height;
|
258 | };
|
259 |
|
260 |
|
261 |
|
262 |
|
263 |
|
264 |
|
265 | MerkleBlock.prototype.hasTransaction = function hasTransaction(tx) {
|
266 | $.checkArgument(!_.isUndefined(tx), 'tx cannot be undefined');
|
267 | $.checkArgument(tx instanceof Transaction || typeof tx === 'string',
|
268 | 'Invalid tx given, tx must be a "string" or "Transaction"');
|
269 |
|
270 | var hash = tx;
|
271 | if(tx instanceof Transaction) {
|
272 |
|
273 | hash = BufferUtil.reverse(Buffer.from(tx.id, 'hex')).toString('hex');
|
274 | }
|
275 |
|
276 | var txs = [];
|
277 | var height = this._calcTreeHeight();
|
278 | this._traverseMerkleTree(height, 0, { txs: txs });
|
279 | return txs.indexOf(hash) !== -1;
|
280 | };
|
281 |
|
282 |
|
283 |
|
284 |
|
285 |
|
286 |
|
287 | MerkleBlock._fromBufferReader = function _fromBufferReader(br) {
|
288 | $.checkState(!br.finished(), 'No merkleblock data received');
|
289 | var info = {};
|
290 | info.header = BlockHeader.fromBufferReader(br);
|
291 | info.numTransactions = br.readUInt32LE();
|
292 | var numHashes = br.readVarintNum();
|
293 | info.hashes = [];
|
294 | for (var i = 0; i < numHashes; i++) {
|
295 | info.hashes.push(br.read(32).toString('hex'));
|
296 | }
|
297 | var numFlags = br.readVarintNum();
|
298 | info.flags = [];
|
299 | for (i = 0; i < numFlags; i++) {
|
300 | info.flags.push(br.readUInt8());
|
301 | }
|
302 | return info;
|
303 | };
|
304 |
|
305 |
|
306 |
|
307 |
|
308 |
|
309 | MerkleBlock.fromObject = function fromObject(obj) {
|
310 | return new MerkleBlock(obj);
|
311 | };
|
312 |
|
313 | module.exports = MerkleBlock;
|