Socket
Socket
Sign inDemoInstall

@chainsafe/persistent-merkle-tree

Package Overview
Dependencies
Maintainers
5
Versions
25
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

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

Comparing version 0.3.7 to 0.4.0

lib/packedNode.d.ts
lib/packedNode.js

90

CHANGELOG.md

@@ -1,8 +0,92 @@

# Changelog
# Change Log
## [v0.3.7](https://github.com/ChainSafe/persistent-merkle-tree/tree/v0.3.7) (2021-08-26)
All notable changes to this project will be documented in this file.
See [Conventional Commits](https://conventionalcommits.org) for commit guidelines.
[Full Changelog](https://github.com/ChainSafe/persistent-merkle-tree/compare/v0.3.6...v0.3.7)
# [0.4.0](https://github.com/ChainSafe/persistent-merkle-tree/compare/@chainsafe/persistent-merkle-tree@0.3.7...@chainsafe/persistent-merkle-tree@0.4.0) (2022-03-24)
* SSZ v2 (#223) ([9d167b7](https://github.com/ChainSafe/persistent-merkle-tree/commit/9d167b703b1e974ee4943be15710aa9783183986)), closes [#223](https://github.com/ChainSafe/persistent-merkle-tree/issues/223) [#227](https://github.com/ChainSafe/persistent-merkle-tree/issues/227)
* Convert as-sha256 to typescript (#244) ([2d4e3fe](https://github.com/ChainSafe/persistent-merkle-tree/commit/2d4e3febec89ca8ca7c89a19c6949c3213c2c45c)), closes [#244](https://github.com/ChainSafe/persistent-merkle-tree/issues/244)
### BREAKING CHANGES
* complete refactor, see packages/ssz/README.md for details
* export digest* functions as named exports
## 0.3.7 (2021-08-26)
- Support setHashObjectFn ([35bad6](https://github.com/chainsafe/persistent-merkle-tree/commit/35bad6))
## 0.3.2 (2021-06-17)
## Chores
- Use singleton uint8array for hash ([219e3a](https://github.com/chainsafe/persistent-merkle-tree/commit/219e3a))
## 0.3.2 (2021-05-06)
## Chores
- Update as-sha256 ([116029](https://github.com/chainsafe/persistent-merkle-tree/commit/116029))
## 0.3.1 (2021-05-04)
## Features
- Use digest64 instead of digest to hash merkle nodes ([eeea76](https://github.com/chainsafe/persistent-merkle-tree/commit/eeea76))
## 0.3.0 (2021-03-26)
## BREAKING CHANGES
- Use WeakRef on tree hook ([dd23ed](https://github.com/chainsafe/persistent-merkle-tree/commit/dd23ed))
## Features
- Add proof serialization logic ([44ec21](https://github.com/chainsafe/persistent-merkle-tree/commit/44ec21))
## Bug Fixes
- Fix off-by-one in iterateAtDepth ([84e05e](https://github.com/chainsafe/persistent-merkle-tree/commit/84e05e))
## 0.2.3 (2021-02-13)
## Features
- Add tree-offset multiproof code ([a35181](https://github.com/chainsafe/persistent-merkle-tree/commit/a35181))
## 0.2.2 (2021-02-11)
## Features
- Add concatGindices ([bb74df](https://github.com/chainsafe/persistent-merkle-tree/commit/bb74df))
## 0.2.1 (2020-07-32)
## Bug Fixes
- Fix subtreeFillToContents edge cases ([8a2012](https://github.com/chainsafe/persistent-merkle-tree/commit/8a2012))
## 0.2.0 (2020-07-27)
## Features
- Add iterateNodestDepth ([24ca18](https://github.com/chainsafe/persistent-merkle-tree/commit/24ca18))
## BREAKING CHANGES
- Rearrange params, depth first where appropriate ([24ca18](https://github.com/chainsafe/persistent-merkle-tree/commit/24ca18))
## 0.1.3 (2020-06-07)
### Chores
- remove bigint literals ([461fb7](https://github.com/chainsafe/persistent-merkle-tree/commit/461fb7))
## 0.1.2 (2020-02-26)
### Chores
- use @chainsafe/as-sha256 sha2 implementation ([b9bcfe](https://github.com/chainsafe/persistent-merkle-tree/commit/b9bcfe))

10

lib/gindex.js

@@ -11,3 +11,3 @@ "use strict";

if (index >= anchor) {
throw new Error("index too large for depth");
throw new Error(`index ${index} too large for depth ${depth}`);
}

@@ -28,8 +28,7 @@ return anchor | index;

function convertGindexToBitstring(gindex) {
let bitstring;
if (typeof gindex === "string") {
if (!gindex.length) {
if (gindex.length === 0) {
throw new Error(ERR_INVALID_GINDEX);
}
bitstring = gindex;
return gindex;
}

@@ -40,5 +39,4 @@ else {

}
bitstring = gindex.toString(2);
return gindex.toString(2);
}
return bitstring;
}

@@ -45,0 +43,0 @@ exports.convertGindexToBitstring = convertGindexToBitstring;

4

lib/hash.js

@@ -12,3 +12,3 @@ "use strict";

input.set(b, 32);
return as_sha256_1.default.digest64(input);
return as_sha256_1.digest64(input);
}

@@ -20,3 +20,3 @@ exports.hash = hash;

function hashTwoObjects(a, b) {
return as_sha256_1.default.digestTwoHashObjects(a, b);
return as_sha256_1.digest64HashObjects(a, b);
}

@@ -23,0 +23,0 @@ exports.hashTwoObjects = hashTwoObjects;

5

lib/index.d.ts
export * from "./gindex";
export * from "./hash";
export * from "./node";
export * from "./zeroNode";
export * from "./packedNode";
export * from "./proof";
export * from "./subtree";
export * from "./tree";
export * from "./proof";
export * from "./zeroNode";

5

lib/index.js

@@ -16,5 +16,6 @@ "use strict";

__exportStar(require("./node"), exports);
__exportStar(require("./zeroNode"), exports);
__exportStar(require("./packedNode"), exports);
__exportStar(require("./proof"), exports);
__exportStar(require("./subtree"), exports);
__exportStar(require("./tree"), exports);
__exportStar(require("./proof"), exports);
__exportStar(require("./zeroNode"), exports);

51

lib/node.d.ts
import { HashObject } from "@chainsafe/as-sha256";
/**
* An immutable binary merkle tree node
*/
export declare abstract class Node implements HashObject {
/**
* May be null. This is to save an extra variable to check if a node has a root or not
*/
h0: number;

@@ -11,11 +17,18 @@ h1: number;

h7: number;
/** The root hash of the node */
abstract root: Uint8Array;
/** The root hash of the node as a `HashObject` */
abstract rootHashObject: HashObject;
/** The left child node */
abstract left: Node;
/** The right child node */
abstract right: Node;
constructor(h0: number, h1: number, h2: number, h3: number, h4: number, h5: number, h6: number, h7: number);
applyHash(root: HashObject): void;
/** Returns true if the node is a `LeafNode` */
abstract isLeaf(): boolean;
abstract rebindLeft(left: Node): Node;
abstract rebindRight(right: Node): Node;
}
/**
* An immutable binary merkle tree node that has a `left` and `right` child
*/
export declare class BranchNode extends Node {

@@ -30,7 +43,24 @@ private _left;

get right(): Node;
rebindLeft(left: Node): Node;
rebindRight(right: Node): Node;
}
/**
* An immutable binary merkle tree node that has no children
*/
export declare class LeafNode extends Node {
constructor(_root: Uint8Array | HashObject);
static fromRoot(root: Uint8Array): LeafNode;
/**
* New LeafNode from existing HashObject.
*/
static fromHashObject(ho: HashObject): LeafNode;
/**
* New LeafNode with its internal value set to zero. Consider using `zeroNode(0)` if you don't need to mutate.
*/
static fromZero(): LeafNode;
/**
* LeafNode with HashObject `(uint32, 0, 0, 0, 0, 0, 0, 0)`.
*/
static fromUint32(uint32: number): LeafNode;
/**
* Create a new LeafNode with the same internal values. The returned instance is safe to mutate
*/
clone(): LeafNode;
get rootHashObject(): HashObject;

@@ -41,4 +71,8 @@ get root(): Uint8Array;

get right(): Node;
rebindLeft(): Node;
rebindRight(): Node;
writeToBytes(data: Uint8Array, start: number, size: number): void;
getUint(uintBytes: number, offsetBytes: number, clipInfinity?: boolean): number;
getUintBigint(uintBytes: number, offsetBytes: number): bigint;
setUint(uintBytes: number, offsetBytes: number, value: number, clipInfinity?: boolean): void;
setUintBigint(uintBytes: number, offsetBytes: number, valueBN: bigint): void;
bitwiseOrUint(uintBytes: number, offsetBytes: number, value: number): void;
}

@@ -48,1 +82,4 @@ export declare type Link = (n: Node) => Node;

export declare function compose(inner: Link, outer: Link): Link;
export declare function getNodeH(node: Node, hIndex: number): number;
export declare function setNodeH(node: Node, hIndex: number, value: number): void;
export declare function bitwiseOrNodeH(node: Node, hIndex: number, value: number): void;

304

lib/node.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.compose = exports.identity = exports.LeafNode = exports.BranchNode = exports.Node = void 0;
exports.bitwiseOrNodeH = exports.setNodeH = exports.getNodeH = exports.compose = exports.identity = exports.LeafNode = exports.BranchNode = exports.Node = void 0;
const hash_1 = require("./hash");
const ERR_INVALID_TREE = "Invalid tree";
const TWO_POWER_32 = 2 ** 32;
/**
* An immutable binary merkle tree node
*/
class Node {
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;
constructor(h0, h1, h2, h3, h4, h5, h6, h7) {
this.h0 = h0;
this.h1 = h1;
this.h2 = h2;
this.h3 = h3;
this.h4 = h4;
this.h5 = h5;
this.h6 = h6;
this.h7 = h7;
}

@@ -30,9 +32,17 @@ applyHash(root) {

exports.Node = Node;
/**
* An immutable binary merkle tree node that has a `left` and `right` child
*/
class BranchNode extends Node {
constructor(_left, _right) {
super();
// First null value is to save an extra variable to check if a node has a root or not
super(null, 0, 0, 0, 0, 0, 0, 0);
this._left = _left;
this._right = _right;
if (!_left || !_right)
throw new Error(ERR_INVALID_TREE);
if (!_left) {
throw new Error("Left node is undefined");
}
if (!_right) {
throw new Error("Right node is undefined");
}
}

@@ -57,22 +67,35 @@ get rootHashObject() {

}
rebindLeft(left) {
return new BranchNode(left, this.right);
}
rebindRight(right) {
return new BranchNode(this.left, right);
}
}
exports.BranchNode = BranchNode;
/**
* An immutable binary merkle tree node that has no children
*/
class LeafNode extends Node {
constructor(_root) {
super();
if (hash_1.isHashObject(_root)) {
this.applyHash(_root);
}
else {
if (_root.length !== 32)
throw new Error(ERR_INVALID_TREE);
this.applyHash(hash_1.uint8ArrayToHashObject(_root));
}
static fromRoot(root) {
return this.fromHashObject(hash_1.uint8ArrayToHashObject(root));
}
/**
* New LeafNode from existing HashObject.
*/
static fromHashObject(ho) {
return new LeafNode(ho.h0, ho.h1, ho.h2, ho.h3, ho.h4, ho.h5, ho.h6, ho.h7);
}
/**
* New LeafNode with its internal value set to zero. Consider using `zeroNode(0)` if you don't need to mutate.
*/
static fromZero() {
return new LeafNode(0, 0, 0, 0, 0, 0, 0, 0);
}
/**
* LeafNode with HashObject `(uint32, 0, 0, 0, 0, 0, 0, 0)`.
*/
static fromUint32(uint32) {
return new LeafNode(uint32, 0, 0, 0, 0, 0, 0, 0);
}
/**
* Create a new LeafNode with the same internal values. The returned instance is safe to mutate
*/
clone() {
return LeafNode.fromHashObject(this);
}
get rootHashObject() {

@@ -93,8 +116,156 @@ return this;

}
rebindLeft() {
throw Error("LeafNode has no left node");
writeToBytes(data, start, size) {
// TODO: Optimize
data.set(this.root.slice(0, size), start);
}
rebindRight() {
throw Error("LeafNode has no right node");
getUint(uintBytes, offsetBytes, clipInfinity) {
const hIndex = Math.floor(offsetBytes / 4);
// number has to be masked from an h value
if (uintBytes < 4) {
const bitIndex = (offsetBytes % 4) * 8;
const h = getNodeH(this, hIndex);
if (uintBytes === 1) {
return 0xff & (h >> bitIndex);
}
else {
return 0xffff & (h >> bitIndex);
}
}
// number equals the h value
else if (uintBytes === 4) {
return getNodeH(this, hIndex) >>> 0;
}
// number spans 2 h values
else if (uintBytes === 8) {
const low = getNodeH(this, hIndex);
const high = getNodeH(this, hIndex + 1);
if (high === 0) {
return low >>> 0;
}
else if (high === -1 && low === -1 && clipInfinity) {
// Limit uint returns
return Infinity;
}
else {
return (low >>> 0) + (high >>> 0) * TWO_POWER_32;
}
}
// Bigger uint can't be represented
else {
throw Error("uintBytes > 8");
}
}
getUintBigint(uintBytes, offsetBytes) {
const hIndex = Math.floor(offsetBytes / 4);
// number has to be masked from an h value
if (uintBytes < 4) {
const bitIndex = (offsetBytes % 4) * 8;
const h = getNodeH(this, hIndex);
if (uintBytes === 1) {
return BigInt(0xff & (h >> bitIndex));
}
else {
return BigInt(0xffff & (h >> bitIndex));
}
}
// number equals the h value
else if (uintBytes === 4) {
return BigInt(getNodeH(this, hIndex) >>> 0);
}
// number spans multiple h values
else {
const hRange = Math.ceil(uintBytes / 4);
let v = BigInt(0);
for (let i = 0; i < hRange; i++) {
v += BigInt(getNodeH(this, hIndex + i) >>> 0) << BigInt(32 * i);
}
return v;
}
}
setUint(uintBytes, offsetBytes, value, clipInfinity) {
const hIndex = Math.floor(offsetBytes / 4);
// number has to be masked from an h value
if (uintBytes < 4) {
const bitIndex = (offsetBytes % 4) * 8;
let h = getNodeH(this, hIndex);
if (uintBytes === 1) {
h &= ~(0xff << bitIndex);
h |= (0xff && value) << bitIndex;
}
else {
h &= ~(0xffff << bitIndex);
h |= (0xffff && value) << bitIndex;
}
setNodeH(this, hIndex, h);
}
// number equals the h value
else if (uintBytes === 4) {
setNodeH(this, hIndex, value);
}
// number spans 2 h values
else if (uintBytes === 8) {
if (value === Infinity && clipInfinity) {
setNodeH(this, hIndex, -1);
setNodeH(this, hIndex + 1, -1);
}
else {
setNodeH(this, hIndex, value & 0xffffffff);
setNodeH(this, hIndex + 1, (value / TWO_POWER_32) & 0xffffffff);
}
}
// Bigger uint can't be represented
else {
throw Error("uintBytes > 8");
}
}
setUintBigint(uintBytes, offsetBytes, valueBN) {
const hIndex = Math.floor(offsetBytes / 4);
// number has to be masked from an h value
if (uintBytes < 4) {
const value = Number(valueBN);
const bitIndex = (offsetBytes % 4) * 8;
let h = getNodeH(this, hIndex);
if (uintBytes === 1) {
h &= ~(0xff << bitIndex);
h |= (0xff && value) << bitIndex;
}
else {
h &= ~(0xffff << bitIndex);
h |= (0xffff && value) << bitIndex;
}
setNodeH(this, hIndex, h);
}
// number equals the h value
else if (uintBytes === 4) {
setNodeH(this, hIndex, Number(valueBN));
}
// number spans multiple h values
else {
const hEnd = hIndex + Math.ceil(uintBytes / 4);
for (let i = hIndex; i < hEnd; i++) {
setNodeH(this, i, Number(valueBN & BigInt(0xffffffff)));
valueBN = valueBN >> BigInt(32);
}
}
}
bitwiseOrUint(uintBytes, offsetBytes, value) {
const hIndex = Math.floor(offsetBytes / 4);
// number has to be masked from an h value
if (uintBytes < 4) {
const bitIndex = (offsetBytes % 4) * 8;
bitwiseOrNodeH(this, hIndex, value << bitIndex);
}
// number equals the h value
else if (uintBytes === 4) {
bitwiseOrNodeH(this, hIndex, value);
}
// number spans multiple h values
else {
const hEnd = hIndex + Math.ceil(uintBytes / 4);
for (let i = hIndex; i < hEnd; i++) {
bitwiseOrNodeH(this, i, value & 0xffffffff);
value >>= 32;
}
}
}
}

@@ -112,1 +283,64 @@ exports.LeafNode = LeafNode;

exports.compose = compose;
function getNodeH(node, hIndex) {
if (hIndex === 0)
return node.h0;
else if (hIndex === 1)
return node.h1;
else if (hIndex === 2)
return node.h2;
else if (hIndex === 3)
return node.h3;
else if (hIndex === 4)
return node.h4;
else if (hIndex === 5)
return node.h5;
else if (hIndex === 6)
return node.h6;
else if (hIndex === 7)
return node.h7;
else
throw Error("hIndex > 7");
}
exports.getNodeH = getNodeH;
function setNodeH(node, hIndex, value) {
if (hIndex === 0)
node.h0 = value;
else if (hIndex === 1)
node.h1 = value;
else if (hIndex === 2)
node.h2 = value;
else if (hIndex === 3)
node.h3 = value;
else if (hIndex === 4)
node.h4 = value;
else if (hIndex === 5)
node.h5 = value;
else if (hIndex === 6)
node.h6 = value;
else if (hIndex === 7)
node.h7 = value;
else
throw Error("hIndex > 7");
}
exports.setNodeH = setNodeH;
function bitwiseOrNodeH(node, hIndex, value) {
if (hIndex === 0)
node.h0 |= value;
else if (hIndex === 1)
node.h1 |= value;
else if (hIndex === 2)
node.h2 |= value;
else if (hIndex === 3)
node.h3 |= value;
else if (hIndex === 4)
node.h4 |= value;
else if (hIndex === 5)
node.h5 |= value;
else if (hIndex === 6)
node.h6 |= value;
else if (hIndex === 7)
node.h7 |= value;
else
throw Error("hIndex > 7");
}
exports.bitwiseOrNodeH = bitwiseOrNodeH;

9

lib/proof/index.d.ts

@@ -11,2 +11,6 @@ import { Gindex } from "../gindex";

export declare const ProofTypeSerialized: ProofType[];
/**
* A common merkle proof.
* A proof for a single leaf in a tree.
*/
export interface SingleProof {

@@ -18,2 +22,7 @@ type: ProofType.single;

}
/**
* A proof for possibly multiple leaves in a tree.
*
* See https://github.com/protolambda/eth-merkle-trees/blob/master/tree_offsets.md
*/
export interface TreeOffsetProof {

@@ -20,0 +29,0 @@ type: ProofType.treeOffset;

4

lib/proof/single.js

@@ -28,6 +28,6 @@ "use strict";

function createNodeFromSingleProof(gindex, leaf, witnesses) {
let node = new node_1.LeafNode(leaf);
let node = node_1.LeafNode.fromRoot(leaf);
const w = witnesses.reverse();
while (gindex > 1) {
const sibling = new node_1.LeafNode(w.pop());
const sibling = node_1.LeafNode.fromRoot(w.pop());
if (gindex % BigInt(2) === BigInt(0)) {

@@ -34,0 +34,0 @@ node = new node_1.BranchNode(node, sibling);

2

lib/proof/treeOffset.js

@@ -48,3 +48,3 @@ "use strict";

else if (leaves.length === 1) {
return new node_1.LeafNode(leaves[0]);
return node_1.LeafNode.fromRoot(leaves[0]);
}

@@ -51,0 +51,0 @@ else {

4

lib/subtree.d.ts
import { Node } from "./node";
export declare function subtreeFillToDepth(bottom: Node, depth: number): Node;
export declare function subtreeFillToLength(bottom: Node, depth: number, length: number): Node;
/**
* WARNING: Mutates the provided nodes array.
* TODO: Don't mutate the nodes array.
*/
export declare function subtreeFillToContents(nodes: Node[], depth: number): Node;

49

lib/subtree.js

@@ -6,5 +6,2 @@ "use strict";

const zeroNode_1 = require("./zeroNode");
const ERR_NAVIGATION = "Navigation error";
const ERR_TOO_MANY_NODES = "Too many nodes";
// subtree filling
function subtreeFillToDepth(bottom, depth) {

@@ -22,3 +19,3 @@ let node = bottom;

if (length > maxLength)
throw new Error(ERR_TOO_MANY_NODES);
throw new Error("ERR_TOO_MANY_NODES");
if (length === maxLength)

@@ -30,3 +27,3 @@ return subtreeFillToDepth(bottom, depth);

else
throw new Error(ERR_NAVIGATION);
throw new Error("ERR_NAVIGATION");
}

@@ -45,24 +42,40 @@ if (depth === 1) {

exports.subtreeFillToLength = subtreeFillToLength;
/**
* WARNING: Mutates the provided nodes array.
* TODO: Don't mutate the nodes array.
*/
function subtreeFillToContents(nodes, depth) {
const maxLength = 2 ** depth;
if (nodes.length > maxLength)
throw new Error(ERR_TOO_MANY_NODES);
if (nodes.length > maxLength) {
throw new Error(`nodes.length ${nodes.length} over maxIndex at depth ${depth}`);
}
if (nodes.length === 0) {
return zeroNode_1.zeroNode(depth);
}
if (depth === 0) {
if (!nodes.length)
return zeroNode_1.zeroNode(0);
return nodes[0];
}
if (depth === 1) {
if (!nodes.length)
return zeroNode_1.zeroNode(1);
return new node_1.BranchNode(nodes[0], nodes[1] || zeroNode_1.zeroNode(0));
return nodes.length > 1
? // All nodes at depth 1 available
new node_1.BranchNode(nodes[0], nodes[1])
: // Pad with zero node
new node_1.BranchNode(nodes[0], zeroNode_1.zeroNode(0));
}
const pivot = Math.floor(maxLength / 2);
if (nodes.length <= pivot) {
return new node_1.BranchNode(subtreeFillToContents(nodes, depth - 1), zeroNode_1.zeroNode(depth - 1));
let count = nodes.length;
for (let d = depth; d > 0; d--) {
const countRemainder = count % 2;
const countEven = count - countRemainder;
// For each depth level compute the new BranchNodes and overwrite the nodes array
for (let i = 0; i < countEven; i += 2) {
nodes[i / 2] = new node_1.BranchNode(nodes[i], nodes[i + 1]);
}
if (countRemainder > 0) {
nodes[countEven / 2] = new node_1.BranchNode(nodes[countEven], zeroNode_1.zeroNode(depth - d));
}
// If there was remainer, 2 nodes are added to the count
count = countEven / 2 + countRemainder;
}
else {
return new node_1.BranchNode(subtreeFillToContents(nodes.slice(0, Number(pivot)), depth - 1), subtreeFillToContents(nodes.slice(Number(pivot)), depth - 1));
}
return nodes[0];
}
exports.subtreeFillToContents = subtreeFillToContents;

188

lib/tree.d.ts
import { Gindex, GindexBitstring } from "./gindex";
import { Node } from "./node";
import { HashObject } from "@chainsafe/as-sha256";
import { Proof, ProofInput } from "./proof";
export declare type Hook = (v: Tree) => void;
export declare type HashObjectFn = (hashObject: HashObject) => HashObject;
export declare type Hook = (newRootNode: Node) => void;
/**
* Binary merkle tree
*
* Wrapper around immutable `Node` to support mutability.
*
* Mutability between a parent tree and subtree is achieved by maintaining a `hook` callback, which updates the parent when the subtree is updated.
*/
export declare class Tree {
private _node;
private _rootNode;
private hook?;
constructor(node: Node, hook?: Hook);
/**
* Create a `Tree` from a `Proof` object
*/
static createFromProof(proof: Proof): Tree;
/**
* The root node of the tree
*/
get rootNode(): Node;
set rootNode(n: Node);
/**
*
* Setting the root node will trigger a call to the tree's `hook` if it exists.
*/
set rootNode(newRootNode: Node);
/**
* The root hash of the tree
*/
get root(): Uint8Array;
getNode(index: Gindex | GindexBitstring): Node;
setNode(gindex: Gindex | GindexBitstring, n: Node, expand?: boolean): void;
/**
* Return a copy of the tree
*/
clone(): Tree;
/**
* Return the subtree at the specified gindex.
*
* Note: The returned subtree will have a `hook` attached to the parent tree.
* Updates to the subtree will result in updates to the parent.
*/
getSubtree(index: Gindex | GindexBitstring): Tree;
/**
* Return the node at the specified gindex.
*/
getNode(gindex: Gindex | GindexBitstring): Node;
/**
* Return the node at the specified depth and index.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
getNodeAtDepth(depth: number, index: number): Node;
/**
* Return the hash at the specified gindex.
*/
getRoot(index: Gindex | GindexBitstring): Uint8Array;
getHashObject(index: Gindex | GindexBitstring): HashObject;
setRoot(index: Gindex | GindexBitstring, root: Uint8Array, expand?: boolean): void;
setHashObject(index: Gindex | GindexBitstring, hashObject: HashObject, expand?: boolean): void;
/**
* Traverse from root node to node, get hash object, then apply the function to get new node
* and set the new node. This is a convenient method to avoid traversing the tree 2 times to
* Set the node at at the specified gindex.
*/
setNode(gindex: Gindex | GindexBitstring, n: Node): void;
/**
* Traverse to the node at the specified gindex,
* then apply the function to get a new node and set the node at the specified gindex with the result.
*
* This is a convenient method to avoid traversing the tree 2 times to
* get and set.
*/
setHashObjectFn(gindex: Gindex | GindexBitstring, hashObjectFn: HashObjectFn, expand?: boolean): void;
getSubtree(index: Gindex | GindexBitstring): Tree;
setSubtree(index: Gindex | GindexBitstring, v: Tree, expand?: boolean): void;
clone(): Tree;
getSingleProof(index: Gindex): Uint8Array[];
setNodeWithFn(gindex: Gindex | GindexBitstring, getNewNode: (node: Node) => Node): void;
/**
* Set the node at the specified depth and index.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
setNodeAtDepth(depth: number, index: number, node: Node): void;
/**
* Set the hash at the specified gindex.
*
* Note: This will set a new `LeafNode` at the specified gindex.
*/
setRoot(index: Gindex | GindexBitstring, root: Uint8Array): void;
/**
* Fast read-only iteration

@@ -36,4 +87,6 @@ * In-order traversal of nodes at `depth`

* iterating through `count` nodes
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
iterateNodesAtDepth(depth: number, startIndex: number, count: number): IterableIterator<Node>;
getNodesAtDepth(depth: number, startIndex: number, count: number): Node[];
/**

@@ -44,15 +97,98 @@ * Fast read-only iteration

* iterating through `count` nodes
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
getNodesAtDepth(depth: number, startIndex: number, count: number): Node[];
getProof(input: ProofInput): Proof;
iterateNodesAtDepth(depth: number, startIndex: number, count: number): IterableIterator<Node>;
/**
* Traverse the tree from root node, ignore the last bit to get all parent nodes
* of the specified bitstring.
* Return a merkle proof for the node at the specified gindex.
*/
private getParentNodes;
getSingleProof(index: Gindex): Uint8Array[];
/**
* Build a new tree structure from bitstring, parentNodes and a new node.
* Note: keep the same Tree, just mutate the root node.
* Return a merkle proof for the proof input.
*
* This method can be used to create multiproofs.
*/
private rebindNodeToRoot;
getProof(input: ProofInput): Proof;
}
/**
* Return the node at the specified gindex.
*/
export declare function getNode(rootNode: Node, gindex: Gindex | GindexBitstring): Node;
/**
* Set the node at at the specified gindex.
* Returns the new root node.
*/
export declare function setNode(rootNode: Node, gindex: Gindex | GindexBitstring, n: Node): Node;
/**
* Traverse to the node at the specified gindex,
* then apply the function to get a new node and set the node at the specified gindex with the result.
*
* This is a convenient method to avoid traversing the tree 2 times to
* get and set.
*
* Returns the new root node.
*/
export declare function setNodeWithFn(rootNode: Node, gindex: Gindex | GindexBitstring, getNewNode: (node: Node) => Node): Node;
/**
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
export declare function getNodeAtDepth(rootNode: Node, depth: number, index: number): Node;
/**
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
export declare function setNodeAtDepth(rootNode: Node, nodesDepth: number, index: number, nodeChanged: Node): Node;
/**
* Set multiple nodes in batch, editing and traversing nodes strictly once.
*
* - gindexes MUST be sorted in ascending order beforehand.
* - All gindexes must be at the exact same depth.
* - Depth must be > 0, if 0 just replace the root node.
*
* Strategy: for each gindex in `gindexes` navigate to the depth of its parent,
* and create a new parent. Then calculate the closest common depth with the next
* gindex and navigate upwards creating or caching nodes as necessary. Loop and repeat.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
export declare function setNodesAtDepth(rootNode: Node, nodesDepth: number, indexes: number[], nodes: Node[]): Node;
/**
* Fast read-only iteration
* In-order traversal of nodes at `depth`
* starting from the `startIndex`-indexed node
* iterating through `count` nodes
*
* **Strategy**
* 1. Navigate down to parentDepth storing a stack of parents
* 2. At target level push current node
* 3. Go up to the first level that navigated left
* 4. Repeat (1) for next index
*/
export declare function getNodesAtDepth(rootNode: Node, depth: number, startIndex: number, count: number): Node[];
/**
* @see getNodesAtDepth but instead of pushing to an array, it yields
*/
export declare function iterateNodesAtDepth(rootNode: Node, depth: number, startIndex: number, count: number): IterableIterator<Node>;
/**
* Zero's all nodes right of index with constant depth of `nodesDepth`.
*
* For example, zero-ing this tree at depth 2 after index 0
* ```
* X X
* X X -> X 0
* X X X X X 0 0 0
* ```
*
* Or, zero-ing this tree at depth 3 after index 2
* ```
* X X
* X X X 0
* X X X X -> X X 0 0
* X X X X X X X X X X X 0 0 0 0 0
* ```
*
* The strategy is to first navigate down to `nodesDepth` and `index` and keep a stack of parents.
* Then navigate up re-binding:
* - If navigated to the left rebind with zeroNode()
* - If navigated to the right rebind with parent.left from the stack
*/
export declare function treeZeroAfterIndex(rootNode: Node, nodesDepth: number, index: number): Node;

812

lib/tree.js
"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.Tree = void 0;
exports.treeZeroAfterIndex = exports.iterateNodesAtDepth = exports.getNodesAtDepth = exports.setNodesAtDepth = exports.setNodeAtDepth = exports.getNodeAtDepth = exports.setNodeWithFn = exports.setNode = exports.getNode = exports.Tree = void 0;
const zeroNode_1 = require("./zeroNode");
const gindex_1 = require("./gindex");

@@ -8,9 +9,12 @@ const node_1 = require("./node");

const single_1 = require("./proof/single");
const zeroNode_1 = require("./zeroNode");
const ERR_INVALID_TREE = "Invalid tree operation";
const ERR_PARAM_LT_ZERO = "Param must be >= 0";
const ERR_COUNT_GT_DEPTH = "Count extends beyond depth limit";
/**
* Binary merkle tree
*
* Wrapper around immutable `Node` to support mutability.
*
* Mutability between a parent tree and subtree is achieved by maintaining a `hook` callback, which updates the parent when the subtree is updated.
*/
class Tree {
constructor(node, hook) {
this._node = node;
this._rootNode = node;
if (hook) {

@@ -25,10 +29,20 @@ if (typeof WeakRef === "undefined") {

}
/**
* Create a `Tree` from a `Proof` object
*/
static createFromProof(proof) {
return new Tree(proof_1.createNodeFromProof(proof));
}
/**
* The root node of the tree
*/
get rootNode() {
return this._node;
return this._rootNode;
}
set rootNode(n) {
this._node = n;
/**
*
* Setting the root node will trigger a call to the tree's `hook` if it exists.
*/
set rootNode(newRootNode) {
this._rootNode = newRootNode;
if (this.hook) {

@@ -39,3 +53,3 @@ // WeakRef should not change status during a program's execution

if (typeof WeakRef === "undefined") {
this.hook(this);
this.hook(newRootNode);
}

@@ -45,3 +59,3 @@ else {

if (hookVar) {
hookVar(this);
hookVar(newRootNode);
}

@@ -55,85 +69,86 @@ else {

}
/**
* The root hash of the tree
*/
get root() {
return this.rootNode.root;
}
getNode(index) {
let node = this.rootNode;
const bitstring = gindex_1.convertGindexToBitstring(index);
for (let i = 1; i < bitstring.length; i++) {
if (bitstring[i] === "1") {
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;
}
}
return node;
/**
* Return a copy of the tree
*/
clone() {
return new Tree(this.rootNode);
}
setNode(gindex, n, expand = false) {
// 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);
}
const parentNodes = this.getParentNodes(bitstring, expand);
this.rebindNodeToRoot(bitstring, parentNodes, n);
/**
* Return the subtree at the specified gindex.
*
* Note: The returned subtree will have a `hook` attached to the parent tree.
* Updates to the subtree will result in updates to the parent.
*/
getSubtree(index) {
return new Tree(this.getNode(index), (node) => this.setNode(index, node));
}
/**
* Return the node at the specified gindex.
*/
getNode(gindex) {
return getNode(this.rootNode, gindex);
}
/**
* Return the node at the specified depth and index.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
getNodeAtDepth(depth, index) {
return getNodeAtDepth(this.rootNode, depth, index);
}
/**
* Return the hash at the specified gindex.
*/
getRoot(index) {
return this.getNode(index).root;
}
getHashObject(index) {
return this.getNode(index);
/**
* Set the node at at the specified gindex.
*/
setNode(gindex, n) {
this.rootNode = setNode(this.rootNode, gindex, n);
}
setRoot(index, root, expand = false) {
this.setNode(index, new node_1.LeafNode(root), expand);
}
setHashObject(index, hashObject, expand = false) {
this.setNode(index, new node_1.LeafNode(hashObject), expand);
}
/**
* Traverse from root node to node, get hash object, then apply the function to get new node
* and set the new node. This is a convenient method to avoid traversing the tree 2 times to
* Traverse to the node at the specified gindex,
* then apply the function to get a new node and set the node at the specified gindex with the result.
*
* This is a convenient method to avoid traversing the tree 2 times to
* get and set.
*/
setHashObjectFn(gindex, hashObjectFn, expand = false) {
// 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);
}
const parentNodes = this.getParentNodes(bitstring, expand);
const lastParentNode = parentNodes[parentNodes.length - 1];
const lastBit = bitstring[bitstring.length - 1];
const oldNode = lastBit === "1" ? lastParentNode.right : lastParentNode.left;
const newNode = new node_1.LeafNode(hashObjectFn(oldNode));
this.rebindNodeToRoot(bitstring, parentNodes, newNode);
setNodeWithFn(gindex, getNewNode) {
this.rootNode = setNodeWithFn(this.rootNode, gindex, getNewNode);
}
getSubtree(index) {
return new Tree(this.getNode(index), (v) => this.setNode(index, v.rootNode));
/**
* Set the node at the specified depth and index.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
setNodeAtDepth(depth, index, node) {
this.rootNode = setNodeAtDepth(this.rootNode, depth, index, node);
}
setSubtree(index, v, expand = false) {
this.setNode(index, v.rootNode, expand);
/**
* Set the hash at the specified gindex.
*
* Note: This will set a new `LeafNode` at the specified gindex.
*/
setRoot(index, root) {
this.setNode(index, node_1.LeafNode.fromRoot(root));
}
clone() {
return new Tree(this.rootNode);
/**
* Fast read-only iteration
* In-order traversal of nodes at `depth`
* starting from the `startIndex`-indexed node
* iterating through `count` nodes
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
getNodesAtDepth(depth, startIndex, count) {
return getNodesAtDepth(this.rootNode, depth, startIndex, count);
}
getSingleProof(index) {
return single_1.createSingleProof(this.rootNode, index)[1];
}
/**

@@ -144,206 +159,501 @@ * Fast read-only iteration

* iterating through `count` nodes
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
*iterateNodesAtDepth(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);
iterateNodesAtDepth(depth, startIndex, count) {
return iterateNodesAtDepth(this.rootNode, depth, startIndex, count);
}
/**
* Return a merkle proof for the node at the specified gindex.
*/
getSingleProof(index) {
return single_1.createSingleProof(this.rootNode, index)[1];
}
/**
* Return a merkle proof for the proof input.
*
* This method can be used to create multiproofs.
*/
getProof(input) {
return proof_1.createProof(this.rootNode, input);
}
}
exports.Tree = Tree;
/**
* Return the node at the specified gindex.
*/
function getNode(rootNode, gindex) {
const gindexBitstring = gindex_1.convertGindexToBitstring(gindex);
let node = rootNode;
for (let i = 1; i < gindexBitstring.length; i++) {
if (node.isLeaf()) {
throw new Error(`Invalid tree - found leaf at depth ${i}`);
}
if (BigInt(1) << BigInt(depth) < startIndex + count) {
throw new Error(ERR_COUNT_GT_DEPTH);
// If bit is set, means navigate right
node = gindexBitstring[i] === "1" ? node.right : node.left;
}
return node;
}
exports.getNode = getNode;
/**
* Set the node at at the specified gindex.
* Returns the new root node.
*/
function setNode(rootNode, gindex, n) {
// Pre-compute entire bitstring instead of using an iterator (25% faster)
const gindexBitstring = gindex_1.convertGindexToBitstring(gindex);
const parentNodes = getParentNodes(rootNode, gindexBitstring);
return rebindNodeToRoot(gindexBitstring, parentNodes, n);
}
exports.setNode = setNode;
/**
* Traverse to the node at the specified gindex,
* then apply the function to get a new node and set the node at the specified gindex with the result.
*
* This is a convenient method to avoid traversing the tree 2 times to
* get and set.
*
* Returns the new root node.
*/
function setNodeWithFn(rootNode, gindex, getNewNode) {
// Pre-compute entire bitstring instead of using an iterator (25% faster)
const gindexBitstring = gindex_1.convertGindexToBitstring(gindex);
const parentNodes = getParentNodes(rootNode, gindexBitstring);
const lastParentNode = parentNodes[parentNodes.length - 1];
const lastBit = gindexBitstring[gindexBitstring.length - 1];
const oldNode = lastBit === "1" ? lastParentNode.right : lastParentNode.left;
const newNode = getNewNode(oldNode);
return rebindNodeToRoot(gindexBitstring, parentNodes, newNode);
}
exports.setNodeWithFn = setNodeWithFn;
/**
* Traverse the tree from root node, ignore the last bit to get all parent nodes
* of the specified bitstring.
*/
function getParentNodes(rootNode, bitstring) {
let node = rootNode;
// 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 = [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++) {
// Compare to string directly to prevent unnecessary type conversions
if (bitstring[i] === "1") {
node = node.right;
}
if (count === 0) {
return;
else {
node = node.left;
}
if (depth === 0) {
yield this.rootNode;
return;
parentNodes.push(node);
}
return parentNodes;
}
/**
* Build a new tree structure from bitstring, parentNodes and a new node.
* Returns the new root node.
*/
function rebindNodeToRoot(bitstring, parentNodes, newNode) {
let node = newNode;
// 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 = new node_1.BranchNode(parentNodes[i - 1].left, node);
}
let node = this.rootNode;
let currCount = 0;
const startGindex = gindex_1.toGindexBitstring(depth, startIndex);
const nav = [];
for (let i = 1; i < startGindex.length; i++) {
const bit = Number(startGindex[i]);
nav.push([node, bit]);
if (bit) {
if (node.isLeaf())
throw new Error(ERR_INVALID_TREE);
node = node.right;
else {
node = new node_1.BranchNode(node, parentNodes[i - 1].right);
}
}
return node;
}
/**
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
function getNodeAtDepth(rootNode, depth, index) {
if (depth === 0) {
return rootNode;
}
if (depth === 1) {
return index === 0 ? rootNode.left : rootNode.right;
}
// Ignore first bit "1", then substract 1 to get to the parent
const depthiRoot = depth - 1;
const depthiParent = 0;
let node = rootNode;
for (let d = depthiRoot; d >= depthiParent; d--) {
node = isLeftNode(d, index) ? node.left : node.right;
}
return node;
}
exports.getNodeAtDepth = getNodeAtDepth;
/**
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
function setNodeAtDepth(rootNode, nodesDepth, index, nodeChanged) {
// TODO: OPTIMIZE (if necessary)
return setNodesAtDepth(rootNode, nodesDepth, [index], [nodeChanged]);
}
exports.setNodeAtDepth = setNodeAtDepth;
/**
* Set multiple nodes in batch, editing and traversing nodes strictly once.
*
* - gindexes MUST be sorted in ascending order beforehand.
* - All gindexes must be at the exact same depth.
* - Depth must be > 0, if 0 just replace the root node.
*
* Strategy: for each gindex in `gindexes` navigate to the depth of its parent,
* and create a new parent. Then calculate the closest common depth with the next
* gindex and navigate upwards creating or caching nodes as necessary. Loop and repeat.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
*/
function setNodesAtDepth(rootNode, nodesDepth, indexes, nodes) {
// depth depthi gindexes indexes
// 0 1 1 0
// 1 0 2 3 0 1
// 2 - 4 5 6 7 0 1 2 3
// '10' means, at depth 1, node is at the left
//
// For index N check if the bit at position depthi is set to navigate right at depthi
// ```
// mask = 1 << depthi
// goRight = (N & mask) == mask
// ```
// If depth is 0 there's only one node max and the optimization below will cause a navigation error.
// For this case, check if there's a new root node and return it, otherwise the current rootNode.
if (nodesDepth === 0) {
return nodes.length > 0 ? nodes[0] : rootNode;
}
/**
* Contiguous filled stack of parent nodes. It get filled in the first descent
* Indexed by depthi
*/
const parentNodeStack = new Array(nodesDepth);
/**
* Temp stack of left parent nodes, index by depthi.
* Node leftParentNodeStack[depthi] is a node at d = depthi - 1, such that:
* ```
* parentNodeStack[depthi].left = leftParentNodeStack[depthi]
* ```
*/
const leftParentNodeStack = new Array(nodesDepth);
// Ignore first bit "1", then substract 1 to get to the parent
const depthiRoot = nodesDepth - 1;
const depthiParent = 0;
let depthi = depthiRoot;
let node = rootNode;
// Insert root node to make the loop below general
parentNodeStack[depthiRoot] = rootNode;
// TODO: Iterate to depth 32 to allow using bit ops
// for (; depthi >= 32; depthi--) {
// node = node.left;
// }
for (let i = 0; i < indexes.length; i++) {
const index = indexes[i];
// Navigate down until parent depth, and store the chain of nodes
//
// Starts from latest common depth, so node is the parent node at `depthi`
// When persisting the next node, store at the `d - 1` since its the child of node at `depthi`
//
// Stops at the level above depthiParent. For the re-binding routing below node must be at depthiParent
for (let d = depthi; d > depthiParent; d--) {
node = isLeftNode(d, index) ? node.left : node.right;
parentNodeStack[d - 1] = node;
}
depthi = depthiParent;
// If this is the left node, check first it the next node is on the right
//
// - If both nodes exist, create new
// / \
// x x
//
// - If only the left node exists, rebind left
// / \
// x -
//
// - If this is the right node, only the right node exists, rebind right
// / \
// - x
// d = 0, mask = 1 << d = 1
const isLeftLeafNode = (index & 1) !== 1;
if (isLeftLeafNode) {
// Next node is the very next to the right of current node
if (index + 1 === indexes[i + 1]) {
node = new node_1.BranchNode(nodes[i], nodes[i + 1]);
// Move pointer one extra forward since node has consumed two nodes
i++;
}
else {
if (node.isLeaf())
throw new Error(ERR_INVALID_TREE);
node = node.left;
node = new node_1.BranchNode(nodes[i], node.right);
}
}
while (nav.length && currCount < count) {
yield node;
currCount++;
if (currCount === count) {
return;
else {
node = new node_1.BranchNode(node.left, nodes[i]);
}
// Here `node` is the new BranchNode at depthi `depthiParent`
// Now climb upwards until finding the common node with the next index
// For the last iteration, climb to the root at `depthiRoot`
const isLastIndex = i >= indexes.length - 1;
const diffDepthi = isLastIndex ? depthiRoot : findDiffDepthi(index, indexes[i + 1]);
// When climbing up from a left node there are two possible paths
// 1. Go to the right of the parent: Store left node to rebind latter
// 2. Go another level up: Will never visit the left node again, so must rebind now
// 🡼 \ Rebind left only, will never visit this node again
// 🡽 /\
//
// / 🡽 Rebind left only (same as above)
// 🡽 /\
//
// 🡽 /\ 🡾 Store left node to rebind the entire node when returning
//
// 🡼 \ Rebind right with left if exists, will never visit this node again
// /\ 🡼
//
// / 🡽 Rebind right with left if exists (same as above)
// /\ 🡼
for (let d = depthiParent + 1; d <= diffDepthi; d++) {
// If node is on the left, store for latter
// If node is on the right merge with stored left node
if (isLeftNode(d, index)) {
if (isLastIndex || d !== diffDepthi) {
// If it's last index, bind with parent since it won't navigate to the right anymore
// Also, if still has to move upwards, rebind since the node won't be visited anymore
node = new node_1.BranchNode(node, parentNodeStack[d].right);
}
else {
// Only store the left node if it's at d = diffDepth
leftParentNodeStack[d] = node;
node = parentNodeStack[d];
}
}
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;
}
else {
const leftNode = leftParentNodeStack[d];
if (leftNode !== undefined) {
node = new node_1.BranchNode(leftNode, node);
leftParentNodeStack[d] = undefined;
}
} while (nav.length && nav.length !== depth);
else {
node = new node_1.BranchNode(parentNodeStack[d].left, node);
}
}
}
// Prepare next loop
// Go to the parent of the depth with diff, to switch branches to the right
depthi = diffDepthi;
}
/**
* 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);
}
// Done, return new root node
return node;
}
exports.setNodesAtDepth = setNodesAtDepth;
/**
* Fast read-only iteration
* In-order traversal of nodes at `depth`
* starting from the `startIndex`-indexed node
* iterating through `count` nodes
*
* **Strategy**
* 1. Navigate down to parentDepth storing a stack of parents
* 2. At target level push current node
* 3. Go up to the first level that navigated left
* 4. Repeat (1) for next index
*/
function getNodesAtDepth(rootNode, depth, startIndex, count) {
// Optimized paths for short trees (x20 times faster)
if (depth === 0) {
return startIndex === 0 && count > 0 ? [rootNode] : [];
}
else if (depth === 1) {
if (count === 0) {
return [];
}
if (depth === 0) {
return [this.rootNode];
else if (count === 1) {
return startIndex === 0 ? [rootNode.left] : [rootNode.right];
}
const nodes = [];
let node = this.rootNode;
let currCount = 0;
const startGindex = gindex_1.toGindexBitstring(depth, startIndex);
const nav = [];
for (let i = 1; i < startGindex.length; i++) {
const bit = Number(startGindex[i]);
nav.push([node, bit]);
if (bit) {
if (node.isLeaf())
throw new Error(ERR_INVALID_TREE);
node = node.right;
else {
return [rootNode.left, rootNode.right];
}
}
// Ignore first bit "1", then substract 1 to get to the parent
const depthiRoot = depth - 1;
const depthiParent = 0;
let depthi = depthiRoot;
let node = rootNode;
// Contiguous filled stack of parent nodes. It get filled in the first descent
// Indexed by depthi
const parentNodeStack = new Array(depth);
const isLeftStack = new Array(depth);
const nodes = new Array(count);
// Insert root node to make the loop below general
parentNodeStack[depthiRoot] = rootNode;
for (let i = 0; i < count; i++) {
for (let d = depthi; d >= depthiParent; d--) {
if (d !== depthi) {
parentNodeStack[d] = node;
}
else {
if (node.isLeaf())
throw new Error(ERR_INVALID_TREE);
node = node.left;
}
const isLeft = isLeftNode(d, startIndex + i);
isLeftStack[d] = isLeft;
node = isLeft ? node.left : node.right;
}
while (nav.length && currCount < count) {
nodes.push(node);
currCount++;
if (currCount === count) {
nodes[i] = node;
// Find the first depth where navigation when left.
// Store that height and go right from there
for (let d = depthiParent; d <= depthiRoot; d++) {
if (isLeftStack[d] === true) {
depthi = d;
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;
node = parentNodeStack[depthi];
}
getProof(input) {
return proof_1.createProof(this.rootNode, input);
}
/**
* Traverse the tree from root node, ignore the last bit to get all parent nodes
* of the specified bitstring.
*/
getParentNodes(bitstring, expand = false) {
let node = this.rootNode;
// 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);
}
else {
node = zeroNode_1.zeroNode(bitstring.length - i);
}
return nodes;
}
exports.getNodesAtDepth = getNodesAtDepth;
/**
* @see getNodesAtDepth but instead of pushing to an array, it yields
*/
function* iterateNodesAtDepth(rootNode, depth, startIndex, count) {
const endIndex = startIndex + count;
// Ignore first bit "1", then substract 1 to get to the parent
const depthiRoot = depth - 1;
const depthiParent = 0;
let depthi = depthiRoot;
let node = rootNode;
// Contiguous filled stack of parent nodes. It get filled in the first descent
// Indexed by depthi
const parentNodeStack = new Array(depth);
const isLeftStack = new Array(depth);
// Insert root node to make the loop below general
parentNodeStack[depthiRoot] = rootNode;
for (let index = startIndex; index < endIndex; index++) {
for (let d = depthi; d >= depthiParent; d--) {
if (d !== depthi) {
parentNodeStack[d] = node;
}
// Compare to string directly to prevent unnecessary type conversions
if (bitstring[i] === "1") {
node = node.right;
const isLeft = isLeftNode(d, index);
isLeftStack[d] = isLeft;
node = isLeft ? node.left : node.right;
}
yield node;
// Find the first depth where navigation when left.
// Store that height and go right from there
for (let d = depthiParent; d <= depthiRoot; d++) {
if (isLeftStack[d] === true) {
depthi = d;
break;
}
else {
node = node.left;
}
parentNodes.push(node);
}
return parentNodes;
node = parentNodeStack[depthi];
}
}
exports.iterateNodesAtDepth = iterateNodesAtDepth;
/**
* Zero's all nodes right of index with constant depth of `nodesDepth`.
*
* For example, zero-ing this tree at depth 2 after index 0
* ```
* X X
* X X -> X 0
* X X X X X 0 0 0
* ```
*
* Or, zero-ing this tree at depth 3 after index 2
* ```
* X X
* X X X 0
* X X X X -> X X 0 0
* X X X X X X X X X X X 0 0 0 0 0
* ```
*
* The strategy is to first navigate down to `nodesDepth` and `index` and keep a stack of parents.
* Then navigate up re-binding:
* - If navigated to the left rebind with zeroNode()
* - If navigated to the right rebind with parent.left from the stack
*/
function treeZeroAfterIndex(rootNode, nodesDepth, index) {
// depth depthi gindexes indexes
// 0 1 1 0
// 1 0 2 3 0 1
// 2 - 4 5 6 7 0 1 2 3
// '10' means, at depth 1, node is at the left
//
// For index N check if the bit at position depthi is set to navigate right at depthi
// ```
// mask = 1 << depthi
// goRight = (N & mask) == mask
// ```
/**
* Build a new tree structure from bitstring, parentNodes and a new node.
* Note: keep the same Tree, just mutate the root node.
* Contiguous filled stack of parent nodes. It get filled in the first descent
* Indexed by depthi
*/
rebindNodeToRoot(bitstring, parentNodes, newNode) {
let node = newNode;
// 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);
}
const parentNodeStack = new Array(nodesDepth);
// Ignore first bit "1", then substract 1 to get to the parent
const depthiRoot = nodesDepth - 1;
const depthiParent = 0;
let depthi = depthiRoot;
let node = rootNode;
// Insert root node to make the loop below general
parentNodeStack[depthiRoot] = rootNode;
// Navigate down until parent depth, and store the chain of nodes
//
// Stops at the depthiParent level. To rebind below down to `nodesDepth`
for (let d = depthi; d >= depthiParent; d--) {
node = isLeftNode(d, index) ? node.left : node.right;
parentNodeStack[d - 1] = node;
}
depthi = depthiParent;
// Now climb up re-binding with either zero of existing tree.
for (let d = depthiParent; d <= depthiRoot; d++) {
if (isLeftNode(d, index)) {
// If navigated to the left, then all the child nodes of the right node are NOT part of the new tree.
// So re-bind new `node` with a zeroNode at the current depth.
node = new node_1.BranchNode(node, zeroNode_1.zeroNode(d));
}
this.rootNode = node;
else {
// If navigated to the right, then all the child nodes of the left node are part of the new tree.
// So re-bind new `node` with the existing left node of the parent.
node = new node_1.BranchNode(parentNodeStack[d].left, node);
}
}
// Done, return new root node
return node;
}
exports.Tree = Tree;
exports.treeZeroAfterIndex = treeZeroAfterIndex;
/**
* Returns true if the `index` at `depth` is a left node, false if it is a right node.
*
* Supports index up to `Number.MAX_SAFE_INTEGER`.
* In Eth2 case the biggest tree's index is 2**40 (VALIDATOR_REGISTRY_LIMIT)
*/
function isLeftNode(depthi, index) {
if (depthi > 31) {
// Javascript can only do bitwise ops with 32 bit numbers.
// Shifting left 1 by 32 wraps around and becomes 1.
// Get the high part of `index` and adjust depthi
const indexHi = (index / 2 ** 32) >>> 0;
const mask = 1 << (depthi - 32);
return (indexHi & mask) !== mask;
}
const mask = 1 << depthi;
return (index & mask) !== mask;
}
/**
* depth depthi gindexes indexes
* 0 1 1 0
* 1 0 2 3 0 1
* 2 - 4 5 6 7 0 1 2 3
*
* **Conditions**:
* - `from` and `to` must not be equal
*
* @param from Index
* @param to Index
*/
function findDiffDepthi(from, to) {
return (
// (0,0) -> 0 | (0,1) -> 1 | (0,2) -> 2
Math.ceil(Math.log2(-~(from ^ to))) -
// Must offset by one to match the depthi scale
1);
}

14

lib/zeroNode.d.ts
import { Node } from "./node";
export declare function zeroNode(depth: number): Node;
/**
* Return the `Node` at a specified height from the merkle tree made of "zero data"
* ```
* ...
* /
* x <- height 2
* / \
* x x <- height 1
* / \ / \
* 0x0 0x0 0x0 0x0 <- height 0
* ```
*/
export declare function zeroNode(height: number): Node;

22

lib/zeroNode.js

@@ -5,11 +5,23 @@ "use strict";

const node_1 = require("./node");
const zeroes = [new node_1.LeafNode(new Uint8Array(32))];
function zeroNode(depth) {
if (depth >= zeroes.length) {
for (let i = zeroes.length; i <= depth; i++) {
const zeroes = [node_1.LeafNode.fromZero()];
/**
* Return the `Node` at a specified height from the merkle tree made of "zero data"
* ```
* ...
* /
* x <- height 2
* / \
* x x <- height 1
* / \ / \
* 0x0 0x0 0x0 0x0 <- height 0
* ```
*/
function zeroNode(height) {
if (height >= zeroes.length) {
for (let i = zeroes.length; i <= height; i++) {
zeroes[i] = new node_1.BranchNode(zeroes[i - 1], zeroes[i - 1]);
}
}
return zeroes[depth];
return zeroes[height];
}
exports.zeroNode = zeroNode;

28

package.json
{
"name": "@chainsafe/persistent-merkle-tree",
"version": "0.3.7",
"version": "0.4.0",
"description": "Merkle tree implemented as a persistent datastructure",

@@ -36,26 +36,6 @@ "main": "lib/index.js",

"homepage": "https://github.com/ChainSafe/persistent-merkle-tree#readme",
"devDependencies": {
"@dapplion/benchmark": "^0.1.6",
"@types/chai": "^4.2.0",
"@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",
"eslint": "^7.14.0",
"eslint-plugin-import": "^2.22.1",
"eslint-plugin-no-only-tests": "^2.4.0",
"eslint-plugin-node": "^11.1.0",
"eslint-plugin-prettier": "^3.3.1",
"karma": "^4.3.0",
"mocha": "^8.3.0",
"nyc": "^14.1.1",
"prettier": "^2.2.1",
"ts-node": "^9.1.1",
"typescript": "^4.1.3"
"dependencies": {
"@chainsafe/as-sha256": "^0.3.0"
},
"dependencies": {
"@chainsafe/as-sha256": "^0.2.3"
}
"gitHead": "59065e6965a04d829d49dfaa870f237a38280c4e"
}

46

README.md

@@ -17,4 +17,4 @@ # Persistent Merkle Tree

const leaf = new LeafNode(Uint8Array.from([...]));
const otherLeaf = new LeafNode(Uint8Array.from([...]));
const leaf = LeafNode.fromRoot(Buffer.alloc(32, 0xaa));
const otherLeaf = LeafNode.fromRoot(Buffer.alloc(32, 0xbb));

@@ -65,3 +65,3 @@ const branch = new BranchNode(leaf, otherLeaf);

const rrr: Uint8Array = tree.getRoot(gindex); // the Uint8Array root at gindex
const subtree: Tree = tree.getSubtree(gindex); // the Tree wrapping the Node at gindex
const subtree: Tree = tree.getSubtree(gindex); // the Tree wrapping the Node at gindex. Updates to `subtree` will be propagated to `tree`

@@ -120,2 +120,42 @@ // A merkle proof for a gindex can be generated

#### Navigation by gindex or (depth, index)
Many tree methods allow navigation with a gindex. A gindex (or generalized index) describes a path through the tree, starting from the root and nagivating downwards.
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
It can also be interpreted as a bitstring, starting with "1", then appending "0" for each navigation left, or "1" for each navigation right.
```
1
/ \
10 11
/ \ / \
100 101 110 111
```
Alternatively, several tree methods, with names ending with `AtDepth`, allow navigation by (depth, index). Depth and index navigation works by first navigating down levels into the tree from the top, starting at 0 (depth), and indexing nodes from the left, starting at 0 (index).
```
0 <- depth 0
/ \
0 1 <- depth 1
/ \ / \
0 1 2 3 <- depth 2
```
#### Memory efficiency
As an implementation detail, nodes hold their values as a `HashObject` (a javascript object with `h0`, ... `h7` uint32 `number` values) internally, rather than as a 32 byte `Uint8Array`. Memory benchmarking shows that this results in a ~3x reduction in memory over `Uint8Array`. This optimization allows this library to practically scale to trees with millions of nodes.
#### Navigation efficiency
In performance-critical applications performing many reads and writes to trees, being smart with tree navigation is crucial. This library correctly provides tree navigation methods that handle several important optimized cases: multi-node get and set, and get-then-set operations.
## See also:

@@ -122,0 +162,0 @@

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc