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

Comparing version 0.4.1 to 0.4.2

CHANGELOG.md

@@ -6,2 +6,6 @@ # Change Log
 
+## [0.4.2](https://github.com/ChainSafe/persistent-merkle-tree/compare/@chainsafe/persistent-merkle-tree@0.4.1...@chainsafe/persistent-merkle-tree@0.4.2) (2022-05-31)
+
+* Fix treeZeroAfterIndex for negative index (#268)
+
 ## [0.4.1](https://github.com/ChainSafe/persistent-merkle-tree/compare/@chainsafe/persistent-merkle-tree@0.4.0...@chainsafe/persistent-merkle-tree@0.4.1) (2022-04-14)
@@ -8,0 +12,0 @@

lib/proof/index.d.ts

@@ -5,3 +5,4 @@ import { Gindex } from "../gindex";
     single = "single",
-    treeOffset = "treeOffset"
+    treeOffset = "treeOffset",
+    multi = "multi"
 }
@@ -23,3 +24,3 @@ /**
 /**
- * A proof for possibly multiple leaves in a tree.
+ * A proof for multiple leaves in a tree.
  *
@@ -33,3 +34,14 @@ * See https://github.com/protolambda/eth-merkle-trees/blob/master/tree_offsets.md
 }
-export declare type Proof = SingleProof | TreeOffsetProof;
+/**
+ * A proof for multiple leaves in a tree.
+ *
+ * See https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md#merkle-multiproofs
+ */
+export interface MultiProof {
+    type: ProofType.multi;
+    leaves: Uint8Array[];
+    witnesses: Uint8Array[];
+    gindices: Gindex[];
+}
+export declare type Proof = SingleProof | TreeOffsetProof | MultiProof;
 export interface SingleProofInput {
@@ -43,3 +55,7 @@ type: ProofType.single;
 }
-export declare type ProofInput = SingleProofInput | TreeOffsetProofInput;
+export interface MultiProofInput {
+    type: ProofType.multi;
+    gindices: Gindex[];
+}
+export declare type ProofInput = SingleProofInput | TreeOffsetProofInput | MultiProofInput;
 export declare function createProof(rootNode: Node, input: ProofInput): Proof;
@@ -46,0 +62,0 @@ export declare function createNodeFromProof(proof: Proof): Node;

lib/proof/index.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
 exports.deserializeProof = exports.serializeProof = exports.createNodeFromProof = exports.createProof = exports.ProofTypeSerialized = exports.ProofType = void 0;
+const multi_1 = require("./multi");
 const single_1 = require("./single");
@@ -10,2 +11,3 @@ const treeOffset_1 = require("./treeOffset");
     ProofType["treeOffset"] = "treeOffset";
+    ProofType["multi"] = "multi";
 })(ProofType = exports.ProofType || (exports.ProofType = {}));
@@ -17,3 +19,4 @@ /**
     ProofType.single,
-    ProofType.treeOffset, // 1
+    ProofType.treeOffset,
+    ProofType.multi, // 2
 ];
@@ -39,2 +42,11 @@ function createProof(rootNode, input) {
         }
+        case ProofType.multi: {
+            const [leaves, witnesses, gindices] = multi_1.createMultiProof(rootNode, input.gindices);
+            return {
+                type: ProofType.multi,
+                leaves,
+                witnesses,
+                gindices,
+            };
+        }
         default:
@@ -51,2 +63,4 @@ throw new Error("Invalid proof type");
             return treeOffset_1.createNodeFromTreeOffsetProof(proof.offsets, proof.leaves);
+        case ProofType.multi:
+            return multi_1.createNodeFromMultiProof(proof.leaves, proof.witnesses, proof.gindices);
         default:
@@ -60,2 +74,3 @@ throw new Error("Invalid proof type");
         case ProofType.single:
+        case ProofType.multi:
             throw new Error("Not implemented");
@@ -80,2 +95,3 @@ case ProofType.treeOffset: {
         case ProofType.single:
+        case ProofType.multi:
             throw new Error("Not implemented");
@@ -82,0 +98,0 @@ case ProofType.treeOffset: {

lib/proof/single.js

@@ -29,3 +29,3 @@ "use strict";
     let node = node_1.LeafNode.fromRoot(leaf);
-    const w = witnesses.reverse();
+    const w = witnesses.slice().reverse();
     while (gindex > 1) {
@@ -32,0 +32,0 @@ const sibling = node_1.LeafNode.fromRoot(w.pop());

lib/proof/util.d.ts

@@ -28,11 +28,20 @@ import { Gindex, GindexBitstring } from "../gindex";
 /**
+ * Sort generalized indices in decreasing order
+ */
+export declare function sortDecreasingBitstrings(gindices: GindexBitstring[]): GindexBitstring[];
+/**
  * Filter out parent generalized indices
  */
 export declare function filterParentBitstrings(gindices: GindexBitstring[]): GindexBitstring[];
+export declare enum SortOrder {
+    InOrder = 0,
+    Decreasing = 1,
+    Unsorted = 2
+}
 /**
  * Return the set of generalized indices required for a multiproof
- * This includes all leaves and any necessary witnesses
+ * This may include all leaves and any necessary witnesses
  * @param gindices leaves to include in proof
- * @returns all generalized indices required for a multiproof (leaves and witnesses), deduplicated and sorted in-order according to the tree
+ * @returns all generalized indices required for a multiproof (leaves and witnesses), deduplicated and sorted
  */
-export declare function computeMultiProofBitstrings(gindices: GindexBitstring[]): GindexBitstring[];
+export declare function computeMultiProofBitstrings(gindices: GindexBitstring[], includeLeaves?: boolean, sortOrder?: SortOrder): GindexBitstring[];

lib/proof/util.js

 "use strict";
 Object.defineProperty(exports, "__esModule", { value: true });
-exports.computeMultiProofBitstrings = exports.filterParentBitstrings = exports.sortInOrderBitstrings = exports.computeProofBitstrings = exports.computeProofGindices = void 0;
+exports.computeMultiProofBitstrings = exports.SortOrder = exports.filterParentBitstrings = exports.sortDecreasingBitstrings = exports.sortInOrderBitstrings = exports.computeProofBitstrings = exports.computeProofGindices = void 0;
 const gindex_1 = require("../gindex");
@@ -59,6 +59,42 @@ // Not currently in use, but simpler implementation useful for testing
 /**
+ * Sort generalized indices in decreasing order
+ */
+function sortDecreasingBitstrings(gindices) {
+    if (!gindices.length) {
+        return [];
+    }
+    return gindices.sort((a, b) => {
+        if (a.length < b.length) {
+            return 1;
+        }
+        else if (b.length < a.length) {
+            return -1;
+        }
+        let aPos0 = a.indexOf("0");
+        let bPos0 = b.indexOf("0");
+        // eslint-disable-next-line no-constant-condition
+        while (true) {
+            if (aPos0 === -1) {
+                return -1;
+            }
+            else if (bPos0 === -1) {
+                return 1;
+            }
+            if (aPos0 < bPos0) {
+                return 1;
+            }
+            else if (bPos0 < aPos0) {
+                return -1;
+            }
+            aPos0 = a.indexOf("0", aPos0 + 1);
+            bPos0 = b.indexOf("0", bPos0 + 1);
+        }
+    });
+}
+exports.sortDecreasingBitstrings = sortDecreasingBitstrings;
+/**
  * Filter out parent generalized indices
  */
 function filterParentBitstrings(gindices) {
-    const sortedBitstrings = gindices.sort((a, b) => a.length - b.length);
+    const sortedBitstrings = gindices.slice().sort((a, b) => a.length - b.length);
     const filtered = [];
@@ -78,11 +114,18 @@ outer: for (let i = 0; i < sortedBitstrings.length; i++) {
 exports.filterParentBitstrings = filterParentBitstrings;
+var SortOrder;
+(function (SortOrder) {
+    SortOrder[SortOrder["InOrder"] = 0] = "InOrder";
+    SortOrder[SortOrder["Decreasing"] = 1] = "Decreasing";
+    SortOrder[SortOrder["Unsorted"] = 2] = "Unsorted";
+})(SortOrder = exports.SortOrder || (exports.SortOrder = {}));
 /**
  * Return the set of generalized indices required for a multiproof
- * This includes all leaves and any necessary witnesses
+ * This may include all leaves and any necessary witnesses
  * @param gindices leaves to include in proof
- * @returns all generalized indices required for a multiproof (leaves and witnesses), deduplicated and sorted in-order according to the tree
+ * @returns all generalized indices required for a multiproof (leaves and witnesses), deduplicated and sorted
  */
-function computeMultiProofBitstrings(gindices) {
-    // Initialize the proof indices with the leaves
-    const proof = new Set(filterParentBitstrings(gindices));
+function computeMultiProofBitstrings(gindices, includeLeaves = true, sortOrder = SortOrder.InOrder) {
+    const leaves = filterParentBitstrings(gindices);
+    // Maybe initialize the proof indices with the leaves
+    const proof = new Set(includeLeaves ? leaves : []);
     const paths = new Set();
@@ -92,3 +135,3 @@ const branches = new Set();
     let maxBitLength = 1;
-    for (const gindex of proof) {
+    for (const gindex of leaves) {
         if (gindex.length > maxBitLength)
@@ -104,4 +147,11 @@ maxBitLength = gindex.length;
     branches.forEach((g) => proof.add(g));
-    return sortInOrderBitstrings(Array.from(proof), maxBitLength);
+    switch (sortOrder) {
+        case SortOrder.InOrder:
+            return sortInOrderBitstrings(Array.from(proof), maxBitLength);
+        case SortOrder.Decreasing:
+            return sortDecreasingBitstrings(Array.from(proof));
+        case SortOrder.Unsorted:
+            return Array.from(proof);
+    }
 }
 exports.computeMultiProofBitstrings = computeMultiProofBitstrings;

lib/tree.js

@@ -580,2 +580,7 @@ "use strict";
     // ```
+    // Degenerate case where tree is zero after a negative index (-1).
+    // All positive indexes are zero, so the entire tree is zero. Return cached zero node as root.
+    if (index < 0) {
+        return zeroNode_1.zeroNode(nodesDepth);
+    }
     /**
@@ -582,0 +587,0 @@ * Contiguous filled stack of parent nodes. It get filled in the first descent

package.json

 {
   "name": "@chainsafe/persistent-merkle-tree",
-  "version": "0.4.1",
+  "version": "0.4.2",
   "description": "Merkle tree implemented as a persistent datastructure",
@@ -39,3 +39,3 @@ "main": "lib/index.js",
   },
-  "gitHead": "42c30c4c797ef1ec06ef0139d4967c4725dca4e7"
+  "gitHead": "2199073977689e7949428561a1df970812ac668b"
 }

Fixed alerts

New author

Supply chain risk

A new npm collaborator published a version of the package for the first time. New collaborators are usually benign additions to a project, but do indicate a change to the security surface area of a package.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

111581

increased by8.16%

Number of package files

30

increased by7.14%

Lines of code

2454

increased by9.26%

Number of medium supply chain risk alerts

0

decreased by-100%

No dependency changes