@chainsafe/persistent-merkle-tree - npm Package Compare versions

Comparing version 0.3.3 to 0.3.4

CHANGELOG.md

 # Changelog
 
-## [v0.3.3](https://github.com/ChainSafe/persistent-merkle-tree/tree/v0.3.3) (2021-06-18)
+## [v0.3.4](https://github.com/ChainSafe/persistent-merkle-tree/tree/v0.3.4) (2021-08-18)
 
-[Full Changelog](https://github.com/ChainSafe/persistent-merkle-tree/compare/origin...v0.3.3)
+[Full Changelog](https://github.com/ChainSafe/persistent-merkle-tree/compare/v0.3.3...v0.3.4)
 
+**Merged pull requests:**
 
+- Bump yargs-parser from 13.1.1 to 13.1.2 [\#57](https://github.com/ChainSafe/persistent-merkle-tree/pull/57) (@dependabot[bot])
+- Bump path-parse from 1.0.6 to 1.0.7 [\#56](https://github.com/ChainSafe/persistent-merkle-tree/pull/56) (@dependabot[bot])
+- Bump glob-parent from 5.1.0 to 5.1.2 [\#44](https://github.com/ChainSafe/persistent-merkle-tree/pull/44) (@dependabot[bot])
+- Bump lodash from 4.17.19 to 4.17.21 [\#43](https://github.com/ChainSafe/persistent-merkle-tree/pull/43) (@dependabot[bot])
+- Bump hosted-git-info from 2.8.5 to 2.8.9 [\#38](https://github.com/ChainSafe/persistent-merkle-tree/pull/38) (@dependabot[bot])
+- Bump handlebars from 4.5.3 to 4.7.7 [\#36](https://github.com/ChainSafe/persistent-merkle-tree/pull/36) (@dependabot[bot])
 
+
+

lib/gindex.d.ts

@@ -5,3 +5,3 @@ export declare type Gindex = bigint;
 export declare function toGindex(depth: number, index: bigint): Gindex;
-export declare function toGindexBitstring(depth: number, index: bigint): GindexBitstring;
+export declare function toGindexBitstring(depth: number, index: number): GindexBitstring;
 export declare function countToDepth(count: bigint): number;
@@ -8,0 +8,0 @@ /**

lib/gindex.js

@@ -17,3 +17,3 @@ "use strict";
 function toGindexBitstring(depth, index) {
-    const str = index ? index.toString(2) : "";
+    const str = index ? Number(index).toString(2) : "";
     if (str.length > depth) {
@@ -20,0 +20,0 @@ throw new Error("index too large for depth");

lib/hash.d.ts

@@ -0,1 +1,2 @@
+import { HashObject } from "@chainsafe/as-sha256";
 /**
@@ -5,1 +6,7 @@ * Hash two 32 byte arrays
 export declare function hash(a: Uint8Array, b: Uint8Array): Uint8Array;
+/**
+ * Hash 2 objects, each store 8 numbers (equivalent to Uint8Array(32))
+ */
+export declare function hashTwoObjects(a: HashObject, b: HashObject): HashObject;
+export declare function hashObjectToUint8Array(obj: HashObject): Uint8Array;
+export declare function uint8ArrayToHashObject(byteArr: Uint8Array): HashObject;

lib/hash.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.hash = void 0;
+exports.uint8ArrayToHashObject = exports.hashObjectToUint8Array = exports.hashTwoObjects = exports.hash = void 0;
 const as_sha256_1 = require("@chainsafe/as-sha256");
@@ -15,1 +15,18 @@ const input = new Uint8Array(64);
 exports.hash = hash;
+/**
+ * Hash 2 objects, each store 8 numbers (equivalent to Uint8Array(32))
+ */
+function hashTwoObjects(a, b) {
+    return as_sha256_1.default.digestTwoHashObjects(a, b);
+}
+exports.hashTwoObjects = hashTwoObjects;
+function hashObjectToUint8Array(obj) {
+    const byteArr = new Uint8Array(32);
+    as_sha256_1.hashObjectToByteArray(obj, byteArr, 0);
+    return byteArr;
+}
+exports.hashObjectToUint8Array = hashObjectToUint8Array;
+function uint8ArrayToHashObject(byteArr) {
+    return as_sha256_1.byteArrayToHashObject(byteArr);
+}
+exports.uint8ArrayToHashObject = uint8ArrayToHashObject;

lib/node.d.ts

@@ -1,8 +0,19 @@
-export declare abstract class Node {
-    get root(): Uint8Array;
-    isLeaf(): boolean;
-    get left(): Node;
-    get right(): Node;
-    rebindLeft(left: Node): Node;
-    rebindRight(right: Node): Node;
+import { HashObject } from "@chainsafe/as-sha256";
+export declare abstract class Node implements HashObject {
+    h0: number;
+    h1: number;
+    h2: number;
+    h3: number;
+    h4: number;
+    h5: number;
+    h6: number;
+    h7: number;
+    abstract root: Uint8Array;
+    abstract rootHashObject: HashObject;
+    abstract left: Node;
+    abstract right: Node;
+    applyHash(root: HashObject): void;
+    abstract isLeaf(): boolean;
+    abstract rebindLeft(left: Node): Node;
+    abstract rebindRight(right: Node): Node;
 }
@@ -12,10 +23,8 @@ export declare class BranchNode extends Node {
     private _right;
-    private _root;
     constructor(_left: Node, _right: Node);
+    get rootHashObject(): HashObject;
     get root(): Uint8Array;
     isLeaf(): boolean;
     get left(): Node;
-    set left(n: Node);
     get right(): Node;
-    set right(n: Node);
     rebindLeft(left: Node): Node;
@@ -25,6 +34,10 @@ rebindRight(right: Node): Node;
 export declare class LeafNode extends Node {
-    private _root;
     constructor(_root: Uint8Array);
+    get rootHashObject(): HashObject;
     get root(): Uint8Array;
     isLeaf(): boolean;
+    get left(): Node;
+    get right(): Node;
+    rebindLeft(): Node;
+    rebindRight(): Node;
 }
@@ -31,0 +44,0 @@ export declare type Link = (n: Node) => Node;

lib/node.js

@@ -6,24 +6,24 @@ "use strict";
 const ERR_INVALID_TREE = "Invalid tree";
-const ERR_NOT_IMPLEMENTED = "Not implemented";
 class Node {
-    get root() {
-        throw new Error(ERR_NOT_IMPLEMENTED);
+    constructor() {
+        // this is to save an extra variable to check if a node has a root or not
+        this.h0 = null;
+        this.h1 = 0;
+        this.h2 = 0;
+        this.h3 = 0;
+        this.h4 = 0;
+        this.h5 = 0;
+        this.h6 = 0;
+        this.h7 = 0;
     }
-    isLeaf() {
-        throw new Error(ERR_NOT_IMPLEMENTED);
+    applyHash(root) {
+        this.h0 = root.h0;
+        this.h1 = root.h1;
+        this.h2 = root.h2;
+        this.h3 = root.h3;
+        this.h4 = root.h4;
+        this.h5 = root.h5;
+        this.h6 = root.h6;
+        this.h7 = root.h7;
     }
-    get left() {
-        throw new Error(ERR_NOT_IMPLEMENTED);
-    }
-    get right() {
-        throw new Error(ERR_NOT_IMPLEMENTED);
-    }
-    // eslint-disable-next-line @typescript-eslint/no-unused-vars
-    rebindLeft(left) {
-        throw new Error(ERR_NOT_IMPLEMENTED);
-    }
-    // eslint-disable-next-line @typescript-eslint/no-unused-vars
-    rebindRight(right) {
-        throw new Error(ERR_NOT_IMPLEMENTED);
-    }
 }
@@ -36,12 +36,14 @@ exports.Node = Node;
         this._right = _right;
-        this._root = null;
         if (!_left || !_right)
             throw new Error(ERR_INVALID_TREE);
     }
-    get root() {
-        if (!this._root) {
-            this._root = hash_1.hash(this.left.root, this.right.root);
+    get rootHashObject() {
+        if (this.h0 === null) {
+            super.applyHash(hash_1.hashTwoObjects(this.left.rootHashObject, this.right.rootHashObject));
         }
-        return this._root;
+        return this;
     }
+    get root() {
+        return hash_1.hashObjectToUint8Array(this.rootHashObject);
+    }
     isLeaf() {
@@ -53,11 +55,5 @@ return false;
     }
-    set left(n) {
-        this._left = n;
-    }
     get right() {
         return this._right;
     }
-    set right(n) {
-        this._right = n;
-    }
     rebindLeft(left) {
@@ -74,8 +70,11 @@ return new BranchNode(left, this.right);
         super();
-        this._root = _root;
         if (_root.length !== 32)
             throw new Error(ERR_INVALID_TREE);
+        this.applyHash(hash_1.uint8ArrayToHashObject(_root));
     }
+    get rootHashObject() {
+        return this;
+    }
     get root() {
-        return this._root;
+        return hash_1.hashObjectToUint8Array(this);
     }
@@ -85,2 +84,14 @@ isLeaf() {
     }
+    get left() {
+        throw Error("LeafNode has no left node");
+    }
+    get right() {
+        throw Error("LeafNode has no right node");
+    }
+    rebindLeft() {
+        throw Error("LeafNode has no left node");
+    }
+    rebindRight() {
+        throw Error("LeafNode has no right node");
+    }
 }
@@ -87,0 +98,0 @@ exports.LeafNode = LeafNode;

lib/tree.d.ts

@@ -1,3 +0,3 @@
-import { Gindex } from "./gindex";
-import { Node, Link } from "./node";
+import { Gindex, GindexBitstring } from "./gindex";
+import { Node } from "./node";
 import { Proof, ProofInput } from "./proof";
@@ -13,9 +13,8 @@ export declare type Hook = (v: Tree) => void;
     get root(): Uint8Array;
-    getNode(index: Gindex): Node;
-    setter(index: Gindex, expand?: boolean): Link;
-    setNode(index: Gindex, n: Node, expand?: boolean): void;
-    getRoot(index: Gindex): Uint8Array;
-    setRoot(index: Gindex, root: Uint8Array, expand?: boolean): void;
-    getSubtree(index: Gindex): Tree;
-    setSubtree(index: Gindex, v: Tree, expand?: boolean): void;
+    getNode(index: Gindex | GindexBitstring): Node;
+    setNode(gindex: Gindex | GindexBitstring, n: Node, expand?: boolean): void;
+    getRoot(index: Gindex | GindexBitstring): Uint8Array;
+    setRoot(index: Gindex | GindexBitstring, root: Uint8Array, expand?: boolean): void;
+    getSubtree(index: Gindex | GindexBitstring): Tree;
+    setSubtree(index: Gindex | GindexBitstring, v: Tree, expand?: boolean): void;
     clone(): Tree;
@@ -30,3 +29,10 @@ getSingleProof(index: Gindex): Uint8Array[];
     iterateNodesAtDepth(depth: number, startIndex: number, count: number): IterableIterator<Node>;
+    /**
+     * Fast read-only iteration
+     * In-order traversal of nodes at `depth`
+     * starting from the `startIndex`-indexed node
+     * iterating through `count` nodes
+     */
+    getNodesAtDepth(depth: number, startIndex: number, count: number): Node[];
     getProof(input: ProofInput): Proof;
 }

lib/tree.js

@@ -70,37 +70,52 @@ "use strict";
     }
-    setter(index, expand = false) {
-        let link = node_1.identity;
+    setNode(gindex, n, expand = false) {
         let node = this.rootNode;
-        const iterator = gindex_1.gindexIterator(index);
-        for (const i of iterator) {
-            if (i) {
-                if (node.isLeaf()) {
-                    if (!expand)
-                        throw new Error(ERR_INVALID_TREE);
-                    else {
-                        const child = zeroNode_1.zeroNode(iterator.remainingBitLength() - 1);
-                        node = new node_1.BranchNode(child, child);
-                    }
+        // Pre-compute entire bitstring instead of using an iterator (25% faster)
+        let bitstring;
+        if (typeof gindex === "string") {
+            bitstring = gindex;
+        }
+        else {
+            if (gindex < 1) {
+                throw new Error("Invalid gindex < 1");
+            }
+            bitstring = gindex.toString(2);
+        }
+        // Keep a list of all parent nodes of node at gindex `index`. Then walk the list
+        // backwards to rebind them "recursively" with the new nodes without using functions
+        const parentNodes = [this.rootNode];
+        // Ignore the first bit, left right directions are at bits [1,..]
+        // Ignore the last bit, no need to push the target node to the parentNodes array
+        for (let i = 1; i < bitstring.length - 1; i++) {
+            if (node.isLeaf()) {
+                if (!expand) {
+                    throw new Error(ERR_INVALID_TREE);
                 }
-                link = node_1.compose(node.rebindRight.bind(node), link);
+                else {
+                    node = zeroNode_1.zeroNode(bitstring.length - i);
+                }
+            }
+            // Compare to string directly to prevent unnecessary type conversions
+            if (bitstring[i] === "1") {
                 node = node.right;
             }
             else {
-                if (node.isLeaf()) {
-                    if (!expand)
-                        throw new Error(ERR_INVALID_TREE);
-                    else {
-                        const child = zeroNode_1.zeroNode(iterator.remainingBitLength() - 1);
-                        node = new node_1.BranchNode(child, child);
-                    }
-                }
-                link = node_1.compose(node.rebindLeft.bind(node), link);
                 node = node.left;
             }
+            parentNodes.push(node);
         }
-        return node_1.compose(node_1.identity, link);
+        node = n;
+        // Ignore the first bit, left right directions are at bits [1,..]
+        // Iterate the list backwards including the last bit, but offset the parentNodes array
+        // by one since the first bit in bitstring was ignored in the previous loop
+        for (let i = bitstring.length - 1; i >= 1; i--) {
+            if (bitstring[i] === "1") {
+                node = parentNodes[i - 1].rebindRight(node);
+            }
+            else {
+                node = parentNodes[i - 1].rebindLeft(node);
+            }
+        }
+        this.rootNode = node;
     }
-    setNode(index, n, expand = false) {
-        this.rootNode = this.setter(index, expand)(n);
-    }
     getRoot(index) {
@@ -159,3 +174,3 @@ return this.getNode(index).root;
         let currCount = 0;
-        const startGindex = gindex_1.toGindexBitstring(depth, BigInt(startIndex));
+        const startGindex = gindex_1.toGindexBitstring(depth, startIndex);
         const nav = [];
@@ -201,2 +216,79 @@ for (const i of gindex_1.gindexIterator(startGindex)) {
     }
+    /**
+     * Fast read-only iteration
+     * In-order traversal of nodes at `depth`
+     * starting from the `startIndex`-indexed node
+     * iterating through `count` nodes
+     */
+    getNodesAtDepth(depth, startIndex, count) {
+        // Strategy:
+        // First nagivate to the starting Gindex node,
+        // At each level record the tuple (current node, the navigation direction) in a list (Left=0, Right=1)
+        // Once we reach the starting Gindex node, the list will be length == depth
+        // Begin emitting nodes: Outer loop:
+        //   Yield the current node
+        //   Inner loop
+        //     pop off the end of the list
+        //     If its (N, Left) (we've nav'd the left subtree, but not the right subtree)
+        //       push (N, Right) and set set node as the n.right
+        //       push (N, Left) and set node as n.left until list length == depth
+        //   Inner loop until the list length == depth
+        // Outer loop until the list is empty or the yield count == count
+        if (startIndex < 0 || count < 0 || depth < 0) {
+            throw new Error(ERR_PARAM_LT_ZERO);
+        }
+        if (BigInt(1) << BigInt(depth) < startIndex + count) {
+            throw new Error(ERR_COUNT_GT_DEPTH);
+        }
+        if (count === 0) {
+            return [];
+        }
+        if (depth === 0) {
+            return [this.rootNode];
+        }
+        const nodes = [];
+        let node = this.rootNode;
+        let currCount = 0;
+        const startGindex = gindex_1.toGindexBitstring(depth, startIndex);
+        const nav = [];
+        for (const i of gindex_1.gindexIterator(startGindex)) {
+            nav.push([node, i]);
+            if (i) {
+                if (node.isLeaf())
+                    throw new Error(ERR_INVALID_TREE);
+                node = node.right;
+            }
+            else {
+                if (node.isLeaf())
+                    throw new Error(ERR_INVALID_TREE);
+                node = node.left;
+            }
+        }
+        while (nav.length && currCount < count) {
+            nodes.push(node);
+            currCount++;
+            if (currCount === count) {
+                break;
+            }
+            do {
+                const [parentNode, direction] = nav.pop();
+                // if direction was left
+                if (!direction) {
+                    // now navigate right
+                    nav.push([parentNode, 1]);
+                    if (parentNode.isLeaf())
+                        throw new Error(ERR_INVALID_TREE);
+                    node = parentNode.right;
+                    // and then left as far as possible
+                    while (nav.length !== depth) {
+                        nav.push([node, 0]);
+                        if (node.isLeaf())
+                            throw new Error(ERR_INVALID_TREE);
+                        node = node.left;
+                    }
+                }
+            } while (nav.length && nav.length !== depth);
+        }
+        return nodes;
+    }
     getProof(input) {
@@ -203,0 +295,0 @@ return proof_1.createProof(this.rootNode, input);

package.json

 {
   "name": "@chainsafe/persistent-merkle-tree",
-  "version": "0.3.3",
+  "version": "0.3.4",
   "description": "Merkle tree implemented as a persistent datastructure",
@@ -13,3 +13,5 @@ "main": "lib/index.js",
     "lint": "eslint --color --ext .ts src/",
-    "test": "mocha -r ts-node/register 'test/**/*.test.ts'"
+    "benchmark": "node --max-old-space-size=4096 --expose-gc -r ts-node/register ./node_modules/.bin/benchmark 'test/perf/*.perf.ts'",
+    "benchmark:local": "yarn benchmark --local",
+    "test": "mocha -r ts-node/register 'test/unit/**/*.test.ts'"
   },
@@ -36,7 +38,9 @@ "pre-push": [
   "devDependencies": {
+    "@dapplion/benchmark": "^0.1.6",
     "@types/chai": "^4.2.0",
-    "@types/mocha": "^5.2.7",
+    "@types/mocha": "^9.0.0",
     "@types/node": "^14.14.0",
     "@typescript-eslint/eslint-plugin": "4.9.0",
     "@typescript-eslint/parser": "4.9.0",
+    "@dapplion/benchmark": "^0.1.6",
     "chai": "^4.2.0",
@@ -49,11 +53,11 @@ "eslint": "^7.14.0",
     "karma": "^4.3.0",
-    "mocha": "^6.2.0",
+    "mocha": "^8.3.0",
     "nyc": "^14.1.1",
     "prettier": "^2.2.1",
-    "ts-node": "^9.1.0",
+    "ts-node": "^9.1.1",
     "typescript": "^4.1.3"
   },
   "dependencies": {
-    "@chainsafe/as-sha256": "^0.2.2"
+    "@chainsafe/as-sha256": "^0.2.3"
   }
 }

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

63619

increased by11.98%

Lines of code

1237

increased by13.38%

Worsened metrics

Dev dependency count

18

increased by5.88%

Dependency changes

• Updated@chainsafe/as-sha256@^0.2.3