![Meet Socket at BlackHat and DEF CON in Las Vegas](https://cdn.sanity.io/images/cgdhsj6q/production/4a3876139ffd3878bb3e7800a14cf4044245dca7-1080x834.jpg?w=400&fit=max&auto=format)
Security News
Meet Socket at BlackHat and DEF CON in Las Vegas
Come meet the Socket team at BlackHat and DEF CON! We're sponsoring some fun networking events and we would love to see you there.
@chainsafe/persistent-merkle-tree
Advanced tools
Package description
@chainsafe/persistent-merkle-tree is a JavaScript library that provides efficient and persistent data structures based on Merkle trees. It is designed to be used in blockchain and other applications where data integrity and efficient updates are crucial.
Creating a Merkle Tree
This feature allows you to create a Merkle Tree from an array of leaf nodes. The code sample demonstrates how to create a tree with two leaves and print the root hash.
const { Tree, LeafNode } = require('@chainsafe/persistent-merkle-tree');
const leaves = [new LeafNode(Buffer.from('a')), new LeafNode(Buffer.from('b'))];
const tree = new Tree(leaves);
console.log(tree.root);
Updating a Merkle Tree
This feature allows you to update a specific node in the Merkle Tree. The code sample demonstrates how to update the second leaf node and print the new root hash.
const { Tree, LeafNode } = require('@chainsafe/persistent-merkle-tree');
const leaves = [new LeafNode(Buffer.from('a')), new LeafNode(Buffer.from('b'))];
const tree = new Tree(leaves);
const newLeaf = new LeafNode(Buffer.from('c'));
tree.setNode(1, newLeaf);
console.log(tree.root);
Proof Generation and Verification
This feature allows you to generate and verify Merkle proofs. The code sample demonstrates how to create a proof for the first leaf node and verify its validity.
const { Tree, LeafNode, createProof, verifyProof } = require('@chainsafe/persistent-merkle-tree');
const leaves = [new LeafNode(Buffer.from('a')), new LeafNode(Buffer.from('b'))];
const tree = new Tree(leaves);
const proof = createProof(tree, 0);
const isValid = verifyProof(tree.root, proof, leaves[0]);
console.log(isValid);
merkletreejs is a popular library for creating and verifying Merkle Trees in JavaScript. It supports various hash algorithms and is widely used in blockchain applications. Compared to @chainsafe/persistent-merkle-tree, merkletreejs is more focused on general-purpose Merkle Tree operations and may not offer the same level of persistence and efficiency optimizations.
merkle-tools is another JavaScript library for working with Merkle Trees. It provides functionalities for creating trees, generating proofs, and verifying proofs. While it offers similar features to @chainsafe/persistent-merkle-tree, it may not be as optimized for persistent data structures and efficient updates.
Readme
A binary merkle tree implemented as a persistent data structure.
// LeafNode and BranchNode are used to build nodes in a tree
// Nodes may not be changed once initialized
import {LeafNode, BranchNode} from "@chainsafe/persistent-merkle-tree";
const leaf = new LeafNode(Uint8Array.from([...]));
const otherLeaf = new LeafNode(Uint8Array.from([...]));
const branch = new BranchNode(leaf, otherLeaf);
// The `root` property returns the merkle root of a Node
const r: Uint8Array = branch.root; // == hash(leaf.root, otherLeaf.root));
// The `isLeaf` method returns true if the Node is a LeafNode
branch.isLeaf() === false;
leaf.isLeaf() === true;
// Well-known zero nodes are provided
import {zeroNode} from "@chainsafe/persistent-merkle-tree";
// 0x0
const zero0 = zeroNode(0);
// hash(0, 0)
const zero1 = zeroNode(1);
// hash(hash(0, 0), hash(0, 0))
const zero1 = zeroNode(2);
// Tree provides a mutable wrapper around a "root" Node
import {Tree} from "@chainsafe/persistent-merkle-tree";
const tree = new Tree(zeroNode(10));
// `rootNode` property returns the root Node of a Tree
const rootNode: Node = tree.rootNode;
// `root` property returns the merkle root of a Tree
const rr: Uint8Array = tree.root;
// A Tree is navigated by Gindex
const gindex = BigInt(...);
const n: Node = tree.getNode(gindex); // the Node at gindex
const rrr: Uint8Array = tree.getRoot(gindex); // the Uint8Array root at gindex
const subtree: Tree = tree.getSubtree(gindex); // the Tree wrapping the Node at gindex
// A merkle proof for a gindex can be generated
const proof: Uint8Array[] = tree.getSingleProof(gindex);
// Multiple types of proofs are supported through the `getProof` interface
// For example, a multiproof for multiple gindices can be generated like so
import {ProofType} from "@chainsafe/persistent-merkle-tree";
const gindices: BigInt[] = [...];
const proof: Proof = tree.getProof({
type: ProofType.treeOffset,
gindices,
});
// `Proof` objects can be used to recreate `Tree` objects
// These `Tree` objects can be navigated as usual for all nodes contained in the proof
// Navigating to unknown/unproven nodes results in an error
const partialTree: Tree = Tree.createFromProof(proof);
const unknownGindex: BigInt = ...;
gindices.includes(unknownGindex) // false
partialTree.getRoot(unknownGindex) // throws
When dealing with large datasets, it is very expensive to merkleize them in their entirety. In cases where large datasets are remerkleized often between updates and additions, using ephemeral structures for intermediate hashes results in significant duplicated work, as many intermediate hashes will be recomputed and thrown away on each merkleization. In these cases, maintaining structures for the entire tree, intermediate nodes included, can mitigate these issues and allow for additional usecases (eg: proof generation). This implementation also uses the known immutability of nodes to share data between common subtrees across different versions of the data.
The tree is represented as a linked tree of Node
s, currently either BranchNode
s or LeafNode
s.
A BranchNode
has a left
and right
child Node
, and a root
, 32 byte Uint8Array
.
A LeafNode
has a root
.
The root
of a Node
is not computed until requested, and cached thereafter.
Any update to a tree (either to a leaf or intermediate node) is performed as a rebinding that yields a new, updated tree that maximally shares data between versions. Garbage collection allows memory from unused nodes to be eventually reclaimed.
A Tree
object wraps Node
and provides an API for tree navigation and transparent rebinding on updates.
https://github.com/protolambda/remerkleable
This repo was audited by Least Authority as part of this security audit, released 2020-03-23. Commit 8b5ad7
verified in the report.
Apache-2.0
FAQs
Merkle tree implemented as a persistent datastructure
We found that @chainsafe/persistent-merkle-tree demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 6 open source maintainers collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Come meet the Socket team at BlackHat and DEF CON! We're sponsoring some fun networking events and we would love to see you there.
Security News
Learn how Socket's 'Non-Existent Author' alert helps safeguard your dependencies by identifying npm packages published by deleted accounts. This is one of the fastest ways to determine if a package may be abandoned.
Security News
In July, the Python Software Foundation mounted a quick response to address a leaked GitHub token, elected new board members, and added more members to the team supporting PSF and PyPI infrastructure.