merkletreejs - npm Package Compare versions

Comparing version 0.1.11 to 0.2.0

dist/index.d.ts

@@ -0,4 +1,7 @@
+/// <reference types="node" />
 interface Options {
     /** If set to `true`, an odd node will be duplicated and combined to make a pair to generate the layer hash. */
     duplicateOdd?: boolean;
+    /** If set to `true`, an odd node will not have a pair generating the layer hash. */
+    singleOdd?: boolean;
     /** If set to `true`, the leaves will hashed using the set hashing algorithms. */
@@ -25,2 +28,3 @@ hashLeaves?: boolean;
     duplicateOdd: boolean;
+    singleOdd: boolean;
     hashAlgo: (value: TValue) => THashAlgo;
@@ -67,6 +71,16 @@ hashLeaves: boolean;
      */
-    getLeaves(): any[];
+    getLeaves(data?: any[]): any[];
     /**
+     * getHexLeaves
+     * @desc Returns array of leaves of Merkle Tree as hex strings.
+     * @return {String[]}
+     * @example
+     *```js
+     *const leaves = tree.getHexLeaves()
+     *```
+     */
+    getHexLeaves(): string[];
+    /**
      * getLayers
-     * @desc Returns array of all layers of Merkle Tree, including leaves and root.
+     * @desc Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root.
      * @return {Buffer[]}
@@ -80,2 +94,32 @@ * @example
     /**
+     * getHexLayers
+     * @desc Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root as hex strings.
+     * @return {String[]}
+     * @example
+     *```js
+     *const layers = tree.getHexLayers()
+     *```
+     */
+    getHexLayers(): any;
+    /**
+     * getLayersFlat
+     * @desc Returns single flat array of all layers of Merkle Tree, including leaves and root.
+     * @return {Buffer[]}
+     * @example
+     *```js
+     *const layers = tree.getLayersFlat()
+     *```
+     */
+    getLayersFlat(): any;
+    /**
+     * getHexLayersFlat
+     * @desc Returns single flat array of all layers of Merkle Tree, including leaves and root as hex string.
+     * @return {String[]}
+     * @example
+     *```js
+     *const layers = tree.getHexLayersFlat()
+     *```
+     */
+    getHexLayersFlat(): any;
+    /**
      * getRoot
@@ -90,2 +134,11 @@ * @desc Returns the Merkle root hash as a Buffer.
     getRoot(): any;
+    /**
+     * getHexRoot
+     * @desc Returns the Merkle root hash as a hex string.
+     * @return {String}
+     * @example
+     *```js
+     *const root = tree.getHexRoot()
+     *```
+     */
     getHexRoot(): string;
@@ -113,2 +166,8 @@ /**
     getProof(leaf: any, index?: any): any[];
+    getProofIndices(treeIndices: any, depth: any): any[];
+    getMultiProof(tree: any, indices: any): any[];
+    getHexMultiProof(tree: any, indices: any): string[];
+    bufIndexOf(arr: any, el: any): number;
+    getProofFlags(els: any, proofs: any): any[];
+    getPairElement(idx: any, layer: any): any;
     getHexProof(leaf: any, index?: any): string[];
@@ -132,2 +191,4 @@ /**
     verify(proof: any, targetNode: any, root: any): boolean;
+    verifyMultiProof(root: any, indices: any, leaves: any, depth: any, proof: any): any;
+    getDepth(): number;
     getLayersAsObject(): any;
@@ -138,4 +199,11 @@ print(): void;
     static bufferify(x: any): any;
+    static isHexStr(v: any): boolean;
     static print(tree: any): void;
+    _bufferToHex(value: Buffer): string;
+    _bufferify(x: any): any;
+    _bufferifyFn(f: any): (x: any) => Buffer;
+    _isHexStr(v: any): boolean;
+    _log2(x: any): any;
+    _zip(a: any, b: any): any;
 }
 export default MerkleTree;

dist/index.js

 "use strict";
+var __read = (this && this.__read) || function (o, n) {
+    var m = typeof Symbol === "function" && o[Symbol.iterator];
+    if (!m) return o;
+    var i = m.call(o), r, ar = [], e;
+    try {
+        while ((n === void 0 || n-- > 0) && !(r = i.next()).done) ar.push(r.value);
+    }
+    catch (error) { e = { error: error }; }
+    finally {
+        try {
+            if (r && !r.done && (m = i["return"])) m.call(i);
+        }
+        finally { if (e) throw e.error; }
+    }
+    return ar;
+};
+var __spread = (this && this.__spread) || function () {
+    for (var ar = [], i = 0; i < arguments.length; i++) ar = ar.concat(__read(arguments[i]));
+    return ar;
+};
+var __values = (this && this.__values) || function(o) {
+    var s = typeof Symbol === "function" && Symbol.iterator, m = s && o[s], i = 0;
+    if (m) return m.call(o);
+    if (o && typeof o.length === "number") return {
+        next: function () {
+            if (o && i >= o.length) o = void 0;
+            return { value: o && o[i++], done: !o };
+        }
+    };
+    throw new TypeError(s ? "Object is not iterable." : "Symbol.iterator is not defined.");
+};
 exports.__esModule = true;
@@ -45,7 +76,8 @@ var reverse = require("buffer-reverse");
         this.duplicateOdd = !!options.duplicateOdd;
-        this.hashAlgo = bufferifyFn(hashAlgorithm);
+        this.singleOdd = !!options.singleOdd;
+        this.hashAlgo = this._bufferifyFn(hashAlgorithm);
         if (this.hashLeaves) {
             leaves = leaves.map(this.hashAlgo);
         }
-        this.leaves = leaves.map(bufferify);
+        this.leaves = leaves.map(this._bufferify);
         if (this.sortLeaves) {
@@ -77,3 +109,3 @@ this.leaves = this.leaves.sort(Buffer.compare);
                         else {
-                            if (!this.duplicateOdd) {
+                            if (!this.duplicateOdd && !this.singleOdd) {
                                 this.layers[layerIndex].push(nodes[i]);
@@ -86,3 +118,3 @@ continue;
                 var left = nodes[i];
-                var right = i + 1 == nodes.length ? left : nodes[i + 1];
+                var right = i + 1 === nodes.length ? left : nodes[i + 1];
                 var data = null;
@@ -94,3 +126,17 @@ var combined = null;
                 else {
-                    combined = [left, right];
+                    if (this.singleOdd) {
+                        right = nodes[i + 1];
+                        if (!left) {
+                            combined = [right];
+                        }
+                        else if (!right) {
+                            combined = [left];
+                        }
+                        else {
+                            combined = [left, right];
+                        }
+                    }
+                    else {
+                        combined = [left, right];
+                    }
                 }
@@ -120,8 +166,31 @@ if (this.sortPairs) {
      */
-    MerkleTree.prototype.getLeaves = function () {
+    MerkleTree.prototype.getLeaves = function (data) {
+        var _this = this;
+        if (Array.isArray(data)) {
+            if (this.hashLeaves) {
+                data = data.map(this.hashAlgo);
+                if (this.sortLeaves) {
+                    data = data.sort(Buffer.compare);
+                }
+            }
+            return this.leaves.filter(function (x) { return _this.bufIndexOf(data, x) !== -1; });
+        }
         return this.leaves;
     };
     /**
+     * getHexLeaves
+     * @desc Returns array of leaves of Merkle Tree as hex strings.
+     * @return {String[]}
+     * @example
+     *```js
+     *const leaves = tree.getHexLeaves()
+     *```
+     */
+    MerkleTree.prototype.getHexLeaves = function () {
+        var _this = this;
+        return this.leaves.map(function (x) { return _this._bufferToHex(x); });
+    };
+    /**
      * getLayers
-     * @desc Returns array of all layers of Merkle Tree, including leaves and root.
+     * @desc Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root.
      * @return {Buffer[]}
@@ -137,2 +206,58 @@ * @example
     /**
+     * getHexLayers
+     * @desc Returns multi-dimensional array of all layers of Merkle Tree, including leaves and root as hex strings.
+     * @return {String[]}
+     * @example
+     *```js
+     *const layers = tree.getHexLayers()
+     *```
+     */
+    MerkleTree.prototype.getHexLayers = function () {
+        var _this = this;
+        return this.layers.reduce(function (acc, item, i) {
+            if (Array.isArray(item)) {
+                acc.push(item.map(function (x) { return _this._bufferToHex(x); }));
+            }
+            else {
+                acc.push(item);
+            }
+            return acc;
+        }, []);
+    };
+    /**
+     * getLayersFlat
+     * @desc Returns single flat array of all layers of Merkle Tree, including leaves and root.
+     * @return {Buffer[]}
+     * @example
+     *```js
+     *const layers = tree.getLayersFlat()
+     *```
+     */
+    MerkleTree.prototype.getLayersFlat = function () {
+        var layers = this.layers.reduce(function (acc, item, i) {
+            if (Array.isArray(item)) {
+                acc.unshift.apply(acc, __spread(item));
+            }
+            else {
+                acc.unshift(item);
+            }
+            return acc;
+        }, []);
+        layers.unshift(Buffer.from([0]));
+        return layers;
+    };
+    /**
+     * getHexLayersFlat
+     * @desc Returns single flat array of all layers of Merkle Tree, including leaves and root as hex string.
+     * @return {String[]}
+     * @example
+     *```js
+     *const layers = tree.getHexLayersFlat()
+     *```
+     */
+    MerkleTree.prototype.getHexLayersFlat = function () {
+        var _this = this;
+        return this.getLayersFlat().map(function (x) { return _this._bufferToHex(x); });
+    };
+    /**
      * getRoot
@@ -149,5 +274,13 @@ * @desc Returns the Merkle root hash as a Buffer.
     };
-    // TODO: documentation
+    /**
+     * getHexRoot
+     * @desc Returns the Merkle root hash as a hex string.
+     * @return {String}
+     * @example
+     *```js
+     *const root = tree.getHexRoot()
+     *```
+     */
     MerkleTree.prototype.getHexRoot = function () {
-        return bufferToHex(this.getRoot());
+        return this._bufferToHex(this.getRoot());
     };
@@ -175,3 +308,3 @@ /**
     MerkleTree.prototype.getProof = function (leaf, index) {
-        leaf = bufferify(leaf);
+        leaf = this._bufferify(leaf);
         var proof = [];
@@ -224,4 +357,146 @@ if (typeof index !== 'number') {
     // TODO: documentation
+    MerkleTree.prototype.getProofIndices = function (treeIndices, depth) {
+        var e_1, _a, e_2, _b;
+        var leafCount = Math.pow(2, depth);
+        var maximalIndices = new Set();
+        try {
+            for (var treeIndices_1 = __values(treeIndices), treeIndices_1_1 = treeIndices_1.next(); !treeIndices_1_1.done; treeIndices_1_1 = treeIndices_1.next()) {
+                var index = treeIndices_1_1.value;
+                var x = leafCount + index;
+                while (x > 1) {
+                    maximalIndices.add(x ^ 1);
+                    x = (x / 2) | 0;
+                }
+            }
+        }
+        catch (e_1_1) { e_1 = { error: e_1_1 }; }
+        finally {
+            try {
+                if (treeIndices_1_1 && !treeIndices_1_1.done && (_a = treeIndices_1["return"])) _a.call(treeIndices_1);
+            }
+            finally { if (e_1) throw e_1.error; }
+        }
+        var a = treeIndices.map(function (index) { return leafCount + index; });
+        var b = Array.from(maximalIndices).sort(function (a, b) { return a - b; }).reverse();
+        maximalIndices = a.concat(b);
+        var redundantIndices = new Set();
+        var proof = [];
+        try {
+            for (var maximalIndices_1 = __values(maximalIndices), maximalIndices_1_1 = maximalIndices_1.next(); !maximalIndices_1_1.done; maximalIndices_1_1 = maximalIndices_1.next()) {
+                var index = maximalIndices_1_1.value;
+                if (!redundantIndices.has(index)) {
+                    proof.push(index);
+                    while (index > 1) {
+                        redundantIndices.add(index);
+                        if (!redundantIndices.has(index ^ 1))
+                            break;
+                        index = (index / 2) | 0;
+                    }
+                }
+            }
+        }
+        catch (e_2_1) { e_2 = { error: e_2_1 }; }
+        finally {
+            try {
+                if (maximalIndices_1_1 && !maximalIndices_1_1.done && (_b = maximalIndices_1["return"])) _b.call(maximalIndices_1);
+            }
+            finally { if (e_2) throw e_2.error; }
+        }
+        return proof.filter(function (index) {
+            return !treeIndices.includes(index - leafCount);
+        });
+    };
+    // TODO: documentation
+    MerkleTree.prototype.getMultiProof = function (tree, indices) {
+        var _this = this;
+        if (!indices) {
+            indices = tree;
+            tree = this.getLayersFlat();
+            if (!indices.every(function (x) { return typeof x === 'number'; })) {
+                var els = indices;
+                if (this.sortPairs) {
+                    els = els.sort(Buffer.compare);
+                }
+                var ids = els.map(function (el) { return _this.bufIndexOf(_this.leaves, el); }).sort(function (a, b) { return a === b ? 0 : a > b ? 1 : -1; });
+                if (!ids.every(function (idx) { return idx !== -1; })) {
+                    throw new Error('Element does not exist in Merkle tree');
+                }
+                var hashes_1 = [];
+                var proof = [];
+                var nextIds = [];
+                for (var i = 0; i < this.layers.length; i++) {
+                    var layer = this.layers[i];
+                    for (var j = 0; j < ids.length; j++) {
+                        var idx = ids[j];
+                        var pairElement = this.getPairElement(idx, layer);
+                        hashes_1.push(layer[idx]);
+                        if (pairElement) {
+                            proof.push(pairElement);
+                        }
+                        nextIds.push((idx / 2) | 0);
+                    }
+                    ids = nextIds.filter(function (value, i, self) { return self.indexOf(value) === i; });
+                    nextIds = [];
+                }
+                return proof.filter(function (value) { return !hashes_1.includes(value); });
+            }
+        }
+        return this.getProofIndices(indices, this._log2((tree.length / 2) | 0)).map(function (index) { return tree[index]; });
+    };
+    // TODO: documentation
+    MerkleTree.prototype.getHexMultiProof = function (tree, indices) {
+        return this.getMultiProof(tree, indices).map(this._bufferToHex);
+    };
+    // TODO: documentation
+    MerkleTree.prototype.bufIndexOf = function (arr, el) {
+        for (var i = 0; i < arr.length; i++) {
+            if (el.equals(arr[i])) {
+                return i;
+            }
+        }
+        return -1;
+    };
+    // TODO: documentation
+    MerkleTree.prototype.getProofFlags = function (els, proofs) {
+        var _this = this;
+        var ids = els.map(function (el) { return _this.bufIndexOf(_this.leaves, el); }).sort(function (a, b) { return a === b ? 0 : a > b ? 1 : -1; });
+        if (!ids.every(function (idx) { return idx !== -1; })) {
+            throw new Error('Element does not exist in Merkle tree');
+        }
+        var tested = [];
+        var flags = [];
+        var _loop_1 = function (index) {
+            var layer = this_1.layers[index];
+            ids = ids.reduce(function (ids, idx) {
+                var skipped = tested.includes(layer[idx]);
+                if (!skipped) {
+                    var pairElement = _this.getPairElement(idx, layer);
+                    var proofUsed = proofs.includes(layer[idx]) || proofs.includes(pairElement);
+                    pairElement && flags.push(!proofUsed);
+                    tested.push(layer[idx]);
+                    tested.push(pairElement);
+                }
+                ids.push((idx / 2) | 0);
+                return ids;
+            }, []);
+        };
+        var this_1 = this;
+        for (var index = 0; index < this.layers.length; index++) {
+            _loop_1(index);
+        }
+        return flags;
+    };
+    MerkleTree.prototype.getPairElement = function (idx, layer) {
+        var pairIdx = idx % 2 === 0 ? idx + 1 : idx - 1;
+        if (pairIdx < layer.length) {
+            return layer[pairIdx];
+        }
+        else {
+            return null;
+        }
+    };
+    // TODO: documentation
     MerkleTree.prototype.getHexProof = function (leaf, index) {
-        return this.getProof(leaf, index).map(function (x) { return bufferToHex(x.data); });
+        var _this = this;
+        return this.getProof(leaf, index).map(function (x) { return _this._bufferToHex(x.data); });
     };
@@ -245,4 +520,4 @@ /**
     MerkleTree.prototype.verify = function (proof, targetNode, root) {
-        var hash = bufferify(targetNode);
-        root = bufferify(root);
+        var hash = this._bufferify(targetNode);
+        root = this._bufferify(root);
         if (!Array.isArray(proof) ||
@@ -260,3 +535,3 @@ !proof.length ||
             if (typeof node === 'string') {
-                data = bufferify(node);
+                data = this._bufferify(node);
                 isLeftNode = true;
@@ -296,2 +571,52 @@ }
     // TODO: documentation
+    MerkleTree.prototype.verifyMultiProof = function (root, indices, leaves, depth, proof) {
+        var e_3, _a, e_4, _b;
+        root = this._bufferify(root);
+        leaves = leaves.map(this._bufferify);
+        proof = proof.map(this._bufferify);
+        var tree = {};
+        try {
+            for (var _c = __values(this._zip(indices, leaves)), _d = _c.next(); !_d.done; _d = _c.next()) {
+                var _e = __read(_d.value, 2), index = _e[0], leaf = _e[1];
+                tree[(Math.pow(2, depth)) + index] = leaf;
+            }
+        }
+        catch (e_3_1) { e_3 = { error: e_3_1 }; }
+        finally {
+            try {
+                if (_d && !_d.done && (_a = _c["return"])) _a.call(_c);
+            }
+            finally { if (e_3) throw e_3.error; }
+        }
+        try {
+            for (var _f = __values(this._zip(this.getProofIndices(indices, depth), proof)), _g = _f.next(); !_g.done; _g = _f.next()) {
+                var _h = __read(_g.value, 2), index = _h[0], proofitem = _h[1];
+                tree[index] = proofitem;
+            }
+        }
+        catch (e_4_1) { e_4 = { error: e_4_1 }; }
+        finally {
+            try {
+                if (_g && !_g.done && (_b = _f["return"])) _b.call(_f);
+            }
+            finally { if (e_4) throw e_4.error; }
+        }
+        var indexqueue = Object.keys(tree).map(function (x) { return +x; }).sort(function (a, b) { return a - b; });
+        indexqueue = indexqueue.slice(0, indexqueue.length - 1);
+        var i = 0;
+        while (i < indexqueue.length) {
+            var index = indexqueue[i];
+            if (index >= 2 && ({}).hasOwnProperty.call(tree, index ^ 1)) {
+                tree[(index / 2) | 0] = this.hashAlgo(Buffer.concat([tree[index - (index % 2)], tree[index - (index % 2) + 1]]));
+                indexqueue.push((index / 2) | 0);
+            }
+            i += 1;
+        }
+        return !indices.length || (({}).hasOwnProperty.call(tree, 1) && tree[1].equals(root));
+    };
+    // TODO: documentation
+    MerkleTree.prototype.getDepth = function () {
+        return this.getLayers().length - 1;
+    };
+    // TODO: documentation
     MerkleTree.prototype.getLayersAsObject = function () {
@@ -318,3 +643,3 @@ var _a;
             }
-            objs.push.apply(objs, arr);
+            objs.push.apply(objs, __spread(arr));
         }
@@ -338,4 +663,19 @@ return objs[0];
     MerkleTree.bufferify = function (x) {
-        return bufferify(x);
+        if (!Buffer.isBuffer(x)) {
+            // crypto-js support
+            if (typeof x === 'object' && x.words) {
+                return Buffer.from(x.toString(CryptoJS.enc.Hex), 'hex');
+            }
+            else if (MerkleTree.isHexStr(x)) {
+                return Buffer.from(x.replace(/^0x/, ''), 'hex');
+            }
+            else if (typeof x === 'string') {
+                return Buffer.from(x);
+            }
+        }
+        return x;
     };
+    MerkleTree.isHexStr = function (v) {
+        return (typeof v === 'string' && /^(0x)?[0-9A-Fa-f]*$/.test(v));
+    };
     // TODO: documentation
@@ -345,39 +685,33 @@ MerkleTree.print = function (tree) {
     };
+    MerkleTree.prototype._bufferToHex = function (value) {
+        return '0x' + value.toString('hex');
+    };
+    MerkleTree.prototype._bufferify = function (x) {
+        return MerkleTree.bufferify(x);
+    };
+    MerkleTree.prototype._bufferifyFn = function (f) {
+        return function (x) {
+            var v = f(x);
+            if (Buffer.isBuffer(v)) {
+                return v;
+            }
+            if (this._isHexStr(v)) {
+                return Buffer.from(v, 'hex');
+            }
+            // crypto-js support
+            return Buffer.from(f(CryptoJS.enc.Hex.parse(x.toString('hex'))).toString(CryptoJS.enc.Hex), 'hex');
+        };
+    };
+    MerkleTree.prototype._isHexStr = function (v) {
+        return MerkleTree.isHexStr(v);
+    };
+    MerkleTree.prototype._log2 = function (x) {
+        return x === 1 ? 0 : 1 + this._log2((x / 2) | 0);
+    };
+    MerkleTree.prototype._zip = function (a, b) {
+        return a.map(function (e, i) { return [e, b[i]]; });
+    };
     return MerkleTree;
 }());
 exports.MerkleTree = MerkleTree;
-function bufferToHex(value) {
-    return '0x' + value.toString('hex');
-}
-function bufferify(x) {
-    if (!Buffer.isBuffer(x)) {
-        // crypto-js support
-        if (typeof x === 'object' && x.words) {
-            return Buffer.from(x.toString(CryptoJS.enc.Hex), 'hex');
-        }
-        else if (isHexStr(x)) {
-            return Buffer.from(x.replace(/^0x/, ''), 'hex');
-        }
-        else if (typeof x === 'string') {
-            return Buffer.from(x);
-        }
-    }
-    return x;
-}
-function bufferifyFn(f) {
-    return function (x) {
-        var v = f(x);
-        if (Buffer.isBuffer(v)) {
-            return v;
-        }
-        if (isHexStr(v)) {
-            return Buffer.from(v, 'hex');
-        }
-        // crypto-js support
-        return Buffer.from(f(CryptoJS.enc.Hex.parse(x.toString('hex'))).toString(CryptoJS.enc.Hex), 'hex');
-    };
-}
-function isHexStr(v) {
-    return (typeof v === 'string' && /^(0x)?[0-9A-Fa-f]*$/.test(v));
-}
 exports["default"] = MerkleTree;

package.json

 {
   "name": "merkletreejs",
-  "version": "0.1.11",
+  "version": "0.2.0",
   "description": "Construct Merkle Trees and verify proofs",
   "main": "dist/index.js",
   "types": "dist/index.d.ts",
-  "files": ["dist"],
+  "files": [
+    "dist"
+  ],
   "scripts": {
     "test": "tape test/*.js",
     "build": "rm -rf dist/ && tsc",
+    "lint": "standardx --fix index.ts test/*.js",
     "docs:md": "rm -rf docs/ && typedoc --theme markdown index.ts --out docs --mdEngine github --mdDocusaurus --mdHideSources"
@@ -42,5 +45,9 @@ },
     "@types/node": "^11.12.1",
+    "@typescript-eslint/eslint-plugin": "^3.0.2",
+    "@typescript-eslint/parser": "^3.0.2",
     "crypto": "0.0.3",
     "ethereumjs-util": "6.1.0",
     "sha1": "^1.1.1",
+    "standard": "^14.3.4",
+    "standardx": "^5.0.0",
     "tape": "^4.9.2",
@@ -60,3 +67,13 @@ "typedoc": "^0.14.2",
     "treeify": "^1.1.0"
+  },
+  "eslintConfig": {
+    "rules": {
+      "no-unused-vars": "off",
+      "@typescript-eslint/no-unused-vars": "error"
+    }
+  },
+  "standardx": {
+    "parser": "@typescript-eslint/parser",
+    "plugins": [ "@typescript-eslint/eslint-plugin" ]
   }
 }

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

48105

increased by49.01%

Lines of code

905

increased by79.92%

Worsened metrics

Dev dependency count

12

increased by50%

No dependency changes