@dashevo/dashcore-lib
Advanced tools
Comparing version 0.17.3 to 0.17.4
@@ -12,4 +12,4 @@ /* eslint-disable */ | ||
var Hash = require('../crypto/hash'); | ||
var JSUtil = require('../util/js'); | ||
var Transaction = require('../transaction'); | ||
var PartialMerkleTree = require('./PartialMerkleTree'); | ||
var $ = require('../util/preconditions'); | ||
@@ -21,3 +21,8 @@ | ||
* | ||
* @param {*} - A Buffer, JSON string, or Object representing a MerkleBlock | ||
* @param {Buffer|string|{ | ||
* header: BlockHeader|Object, | ||
* numTransactions: number, | ||
* hashes: string[], | ||
* flags: number[] | ||
* }} arg A Buffer, JSON string, or Object representing a MerkleBlock | ||
* @returns {MerkleBlock} | ||
@@ -75,2 +80,22 @@ * @constructor | ||
/** | ||
* Builds merkle block from block header, transaction hashes and filter matches | ||
* @param {BlockHeader|Object} header | ||
* @param {Buffer[]} transactionHashes | ||
* @param {boolean[]} filterMatches | ||
* @return {MerkleBlock} | ||
*/ | ||
MerkleBlock.build = function build(header, transactionHashes, filterMatches) { | ||
var partialTree = new PartialMerkleTree({ | ||
transactionHashes: transactionHashes, | ||
filterMatches: filterMatches | ||
}); | ||
return new MerkleBlock({ | ||
header: header, | ||
numTransactions: partialTree.totalTransactions, | ||
hashes: partialTree.merkleHashes, | ||
flags: partialTree.merkleFlags | ||
}); | ||
}; | ||
/** | ||
* @param {Buffer} - MerkleBlock data in a Buffer object | ||
@@ -77,0 +102,0 @@ * @returns {MerkleBlock} - A MerkleBlock object |
@@ -12,3 +12,3 @@ /* eslint-disable */ | ||
var SimplifiedMNListEntry = require('./SimplifiedMNListEntry'); | ||
var PartialMerkleTree = require('./PartialMerkleTree'); | ||
var PartialMerkleTree = require('../block/PartialMerkleTree'); | ||
var Transaction = require('../transaction'); | ||
@@ -15,0 +15,0 @@ var constants = require('../constants'); |
@@ -40,5 +40,90 @@ /* eslint-disable */ | ||
/** | ||
* Helper function to efficiently calculate the number of nodes at given height in the merkle tree | ||
* @param {number} totalElementsCount | ||
* @param {number} height | ||
* @return {number} | ||
*/ | ||
function calculateTreeWidth(totalElementsCount, height) { | ||
return (totalElementsCount + (1 << height ) - 1) >> height; | ||
} | ||
/** | ||
* @param {number} hashesCount | ||
* @return {number} | ||
*/ | ||
function calculateTreeHeight(hashesCount) { | ||
var treeHeight = 0; | ||
while (calculateTreeWidth(hashesCount, treeHeight) > 1) { | ||
treeHeight++; | ||
} | ||
return treeHeight; | ||
} | ||
/** | ||
* | ||
* @param {number} height | ||
* @param {number} position | ||
* @param {Buffer[]} hashes | ||
* @return {Buffer} | ||
*/ | ||
function calculateHashAtHeight(height, position, hashes) { | ||
if (height === 0) { | ||
return hashes[position]; | ||
} else { | ||
// calculate left hash | ||
var left = calculateHashAtHeight(height - 1, position * 2, hashes); | ||
var right = left; | ||
// calculate right hash if not beyond the end of the array - copy left hash otherwise | ||
if (position * 2 + 1 < calculateTreeWidth(hashes.length, height - 1)) { | ||
right = calculateHashAtHeight(height - 1, position * 2 + 1, hashes); | ||
} | ||
var concatenatedHashes = Buffer.concat([Buffer.from(left).reverse(), Buffer.from(right).reverse()]); | ||
return Buffer.from(doubleSha256(concatenatedHashes), 'hex').reverse(); | ||
} | ||
} | ||
/** | ||
* @param {number} height | ||
* @param {number} position | ||
* @param {Buffer[]} hashes | ||
* @param {boolean[]} matches | ||
* @return {{flags: boolean[], merkleHashes: string[]}} | ||
*/ | ||
function traverseAndBuildPartialTree(height, position, hashes, matches) { | ||
var flags = []; | ||
var merkleHashes = []; | ||
// determine whether this node is the parent of at least one matched txid | ||
var parentOfMatch = false; | ||
for (var p = position << height; p < (position + 1) << height && p < hashes.length; p++) { | ||
parentOfMatch |= matches[p]; | ||
} | ||
// store as flag bit | ||
flags.push(Boolean(parentOfMatch)); | ||
if (height === 0 || !Boolean(parentOfMatch)) { | ||
// if at height 0, or nothing interesting below, store hash and stop | ||
merkleHashes.push(calculateHashAtHeight(height, position, hashes).toString('hex')); | ||
} else { | ||
// otherwise, don't store any hash, but descend into the subtrees | ||
var tree = traverseAndBuildPartialTree(height - 1, position * 2, hashes, matches); | ||
flags = flags.concat(tree.flags); | ||
merkleHashes = merkleHashes.concat(tree.merkleHashes); | ||
if (position * 2 + 1 < calculateTreeWidth(hashes.length,height - 1)) { | ||
tree = traverseAndBuildPartialTree(height - 1, position * 2 + 1, hashes, matches); | ||
flags = flags.concat(tree.flags); | ||
merkleHashes = merkleHashes.concat(tree.merkleHashes); | ||
} | ||
} | ||
return { flags: flags, merkleHashes: merkleHashes }; | ||
} | ||
module.exports = { | ||
getMerkleTree: getMerkleTree, | ||
getMerkleRoot: getMerkleRoot | ||
getMerkleRoot: getMerkleRoot, | ||
calculateTreeWidth: calculateTreeWidth, | ||
calculateTreeHeight: calculateTreeHeight, | ||
calculateHashAtHeight: calculateHashAtHeight, | ||
traverseAndBuildPartialTree: traverseAndBuildPartialTree | ||
}; |
{ | ||
"name": "@dashevo/dashcore-lib", | ||
"version": "0.17.3", | ||
"version": "0.17.4", | ||
"description": "A pure and powerful JavaScript Dash library.", | ||
@@ -5,0 +5,0 @@ "author": "Dash Core Group, Inc. <dev@dash.org>", |
@@ -6,2 +6,4 @@ /* eslint-disable */ | ||
var getMerkleRoot = merkleTreeUtil.getMerkleRoot; | ||
var calculateTreeWidth = merkleTreeUtil.calculateTreeWidth; | ||
var calculateHashAtHeight = merkleTreeUtil.calculateHashAtHeight; | ||
@@ -57,2 +59,51 @@ var hashes = [ | ||
}); | ||
describe('calculateTreeWidth', function () { | ||
var calculateTreeWidthTestCases = [ | ||
{elementsCount: 10, height: 0, expectedWidth: 10}, | ||
{elementsCount: 10, height: 1, expectedWidth: 5}, | ||
{elementsCount: 10, height: 2, expectedWidth: 3}, | ||
{elementsCount: 10, height: 3, expectedWidth: 2}, | ||
{elementsCount: 10, height: 4, expectedWidth: 1}, | ||
{elementsCount: 10, height: 5, expectedWidth: 1}, | ||
{elementsCount: 10, height: 6, expectedWidth: 1} | ||
]; | ||
calculateTreeWidthTestCases.forEach(function (args) { | ||
var testCaseName = 'For tree with ' + args.elementsCount + ' elements, width at height ' | ||
+ args.height + ' should be equal to ' + args.expectedWidth; | ||
it(testCaseName, function () { | ||
var width = calculateTreeWidth(args.elementsCount, args.height); | ||
expect(width).to.be.equal(args.expectedWidth); | ||
}); | ||
}); | ||
}); | ||
describe('calculateHashAtHeight', function () { | ||
it('Should calculate hash at height', function () { | ||
// Here we have 6 hashes, meaning that tree on the level 0 will have 6 hashes, | ||
// 3 on the level 1, 2 on the level 2, and 1 on the level 3. | ||
// This means, that 0 hash on the level 1 should be equal to hash of the first two | ||
// hashes on the level 0, meaning: | ||
// 5f616a1319f9d10fc444a5fabd3fc4e60161f5b63471bdddeca1e8a25b833db2 = | ||
// hash(reverse(bf3ae3deccfdee0ebf03fc924aea3dad4b1068acdd27e98d9e6cc9a140e589d1) + | ||
// reverse(9ecb5c68a93c51e8db403f97b83a910edf0878c70b7d7ee02422c0f7c7c9885f)); | ||
// | ||
// Note: Original bitcoin's core has a very strange merkle algorithm, where all | ||
// hashes always get reversed, so result would be a little bit different from | ||
// what may be expected | ||
var hashes = [ | ||
'bf3ae3deccfdee0ebf03fc924aea3dad4b1068acdd27e98d9e6cc9a140e589d1', | ||
'9ecb5c68a93c51e8db403f97b83a910edf0878c70b7d7ee02422c0f7c7c9885f', | ||
'e1d496484925f015078d6269e2e9ed28698f9d5f609da930d6e8ce50e07c2e22', | ||
'27306aa8c486a38f1afcc2a077f4cd09643065c3c7fa487e0b36383b30184de7', | ||
'f2f8af2e212a3db4b88dc59b2271f9600376d126bf17d4f3c413cf22586c3457', | ||
'0fe0981234cf8077f113327052876bd9f997965f9012b0723dd891903a27f7a1' | ||
].map(function (hash) { return Buffer.from(hash, 'hex'); }); | ||
var height1position0hash = calculateHashAtHeight(1, 0, hashes).toString('hex'); | ||
expect(height1position0hash).to.be.equal('5f616a1319f9d10fc444a5fabd3fc4e60161f5b63471bdddeca1e8a25b833db2'); | ||
var height2position2hash = calculateHashAtHeight(2, 1, hashes).toString('hex'); | ||
expect(height2position2hash).to.be.equal('82734783f7f853307a856f23566c1907d734905aa8021c6621e46c2fc810e0dc'); | ||
var actualRoot = calculateHashAtHeight(3, 0, hashes).toString('hex'); | ||
expect(actualRoot).to.be.equal('5e91c568f9812b9efbaf33c9ceceb32b1f947ef7e749e73e698257a77acb963e'); | ||
}); | ||
}); | ||
}); |
Sorry, the diff of this file is not supported yet
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
2815926
210
40258