@dashevo/dashcore-lib - npm Package Compare versions

Comparing version 0.17.3 to 0.17.4

lib/block/merkleblock.js

@@ -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

lib/deterministicmnlist/SimplifiedMNListDiff.js

@@ -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');

lib/util/merkletree.js

@@ -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
 };

package.json

 {
   "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. <[e-mail]>",

test/util/merkletree.js

@@ -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');
+    });
+  });
 });

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

2815926

increased by0.43%

Number of package files

210

increased by1.45%

Lines of code

40258

increased by0.71%

No dependency changes