npm package discovery and stats viewer.

Discover Tips

  • General search

    [free text search, go nuts!]

  • Package details

    pkg:[package-name]

  • User packages

    @[username]

Sponsor

Optimize Toolset

I’ve always been into building performant and accessible sites, but lately I’ve been taking it extremely seriously. So much so that I’ve been building a tool to help me optimize and monitor the sites that I build to make sure that I’m making an attempt to offer the best experience to those who visit them. If you’re into performant, accessible and SEO friendly sites, you might like it too! You can check it out at Optimize Toolset.

About

Hi, 👋, I’m Ryan Hefner  and I built this site for me, and you! The goal of this site was to provide an easy way for me to check the stats on my npm packages, both for prioritizing issues and updates, and to give me a little kick in the pants to keep up on stuff.

As I was building it, I realized that I was actually using the tool to build the tool, and figured I might as well put this out there and hopefully others will find it to be a fast and useful way to search and browse npm packages as I have.

If you’re interested in other things I’m working on, follow me on Twitter or check out the open source projects I’ve been publishing on GitHub.

I am also working on a Twitter bot for this site to tweet the most popular, newest, random packages from npm. Please follow that account now and it will start sending out packages soon–ish.

Open Software & Tools

This site wouldn’t be possible without the immense generosity and tireless efforts from the people who make contributions to the world and share their work via open source initiatives. Thank you 🙏

© 2024 – Pkg Stats / Ryan Hefner

@guildofweavers/merkle

v0.3.12

Published

Merkle tree and other data structures

Downloads

24

Readme

Merkle

Merkle tree and other data structures.

Install

$ npm install @guildofweavers/merkle --save

Example

import { MerkleTree, createHash } from '@guildofweavers/merkle';

// create an array of values to put into a tree
const values = [
    Buffer.from('a'),
    Buffer.from('b'),
    Buffer.from('c'),
    Buffer.from('d')
];

// create a Merkle tree
const hash = createHash('sha256');
const tree = MerkleTree.create(values, hash);

// create a proof for the second position in the tree (value 'b')
const proof = tree.prove(1);
console.log(proof[0].toString()); // 'b'

// verify the proof
const result = MerkleTree.verify(tree.root, 1, proof, hash);
console.log(result); // true

API

You can find complete API definitions in merkle.d.ts. Here is a quick overview of the provided functionality:

Creating Merkle trees

You can create a Merkle Tree from a list of values:

  • static create(values: Buffer[] | Vector, hash: Hash): MerkleTree
  • static createAsync(values: Buffer[] | Vector, hash: Hash): Promise<MerkleTree>

The meaning of the parameters is as follows:

| Parameter | Description | | --------- | ----------- | | values | Values that will form the leaves of the Merkle tree. If provided as an array of Buffer objects, all buffers are assumed to have the same length (otherwise, bad things will happen). Can also be provided as an object that complies with Vector interface, or as a single Buffer object. | | valueSize | If values are provided as a single Buffer, this parameter specifies length of a single value (in bytes). | | hash | A hash object that will be used to hash values and internal nodes. |

Note: async method is currently just a placeholder. All it does is call the sync version and returns the result.

Creating Merkle proofs

Once you have a tree, you can use it to prove that a value is located at a certain index like so:

  • prove(index: number): Buffer[] The returned proof is an array which has the values as the first element, and nodes comprising the proof as all other elements.

You can also create a proof for many indexes at the same time:

  • proveBatch(indexes: number[]): BatchMerkleProof The resulting proof is compressed. So, if you need to prove membership of multiple values, this is a much more efficient approach.

Batch proof has the following form:

interface BatchMerkleProof {
    values  : Buffer[];
    nodes   : Buffer[][];
    depth   : number;
}

where, values are the leaves located at the indexes covered by the proof, nodes are the internal nodes that form the actual proof, and depth is the depth of the source tree.

Verifying Merkle proofs

Once you have a proof, you can verify it against a tree root like so:

  • static verify(root: Buffer, index: number, proof: Buffer[], hash: Hash): boolean This will return true if the value located at the first position in the proof array is indeed located at the specified index in the tree.

For the batched version use:

  • static verifyBatch(root: Buffer, indexes: number[], proof: BatchMerkleProof, hash: Hash): boolean Similarly to single-index version, this will return true if the values in proof.values are indeed located at the specified indexes in the tree.

Hash

A Hash object is required when creating Merkle trees and when verifying Merkle proofs. Internally, it is used for hashing of all values and tree nodes. To create a Hash object, you can use createHash() function:

  • createHash(algorithm: string, useWasm?: boolean): Hash Creates a Hash object for the specified algorithm. If useWasm is set to true, will try to instantiate a WebAssembly-optimized version of the algorithm. If WASM optimization is not available for the specified algorithm, Node's native implementation will be used.

  • createHash(algorithm: string, wasmOptions: WasmOptions): Hash Tries to create a WebAssembly-optimized Hash object for the specified algorithm and pass the provided options to it. If WASM optimization is not available for the specified algorithm, Node's native implementation will be used.

Currently, the following hash algorithms are supported:

| Algorithm | WASM-optimized | | ---------- | :------------: | | sha256 | no | | blake2s256 | yes |

Hash objects returned from createHash() function will have the following form:

interface Hash {
    readonly algorithm  : HashAlgorithm;
    readonly digestSize : number;

    digest(value: Buffer): Buffer;
    merge(a: Buffer, b: Buffer): Buffer;
}

where, digest(value) hashes the provided value, and merge(a,b) hashes a concatenation of values a and b.

Performance

Some very informal benchmarks run on Intel Core i5-7300U @ 2.60GHz (single thread) for generating a tree out of 220 32-byte values:

| Hash Algorithm | Native JS | WASM (external) | WASM (internal) | | -------------- | --------- | --------------- | ---------------- | | sha256 | 3.5 sec | N/A | N/A | | blake2s256 | 3.2 sec | 750 ms | 650 ms |

The difference between external and internal cases for WASM is that in the internal case, values from which the tree is to be built are already in WASM memory, while in the external case, they need to be copied into WASM memory.

Note: while WebAssembly-optimized version of Blake2s algorithm is much faster at hashing small values (i.e. 32-256 bytes), it is slower at hashing large values. For example, when hashing 1KB values, Node's native implementation is about 50% faster.

Batch proof compression

When you generate batch proofs, the proofs are compressed by removing redundant nodes. The table below shows an approximate size of batch proof for a given number of indexes against trees of a given size.

| Tree leaves | 32 indexes | 64 indexes | 128 indexes | 256 indexes | | :------------: | ------------: | ------------: | ------------: | ------------: | | 210 | 5.2 KB (47%) | 8.6 KB (39%) | 13.4 KB (30%) | 20.1 KB (23%) | | 212 | 7.0 KB (54%) | 12.4 KB (48%) | 20.6 KB (40%) | 34.0 KB (33%) | | 214 | 9.2 KB (61%) | 16.2 KB (54%) | 28.6 KB (48%) | 49.3 KB (41%) | | 216 | 11.0 KB (65%) | 20.3 KB (60%) | 36.5 KB (54%) | 65.2 KB (48%) | | 218 | 13.1 KB (69%) | 24.5 KB (63%) | 44.6 KB (59%) | 81.0 KB (53%) | | 220 | 15.1 KB (72%) | 28.4 KB (68%) | 52.5 KB (63%) | 96.8 KB (58%) |

The percentages next to proof sizes are ratios of the batch proof size to a naive proof size. For example, if you generate a batch proof for 32 indexes against a tree of 210 leaves, your proof will be about 5.2 KB, and that will be 47% of 32 individual proofs against the same tree.

References

  • Wikipedia article on Merkle trees.
  • Batch proof/verification use a variation of the Octopus algorithm from this paper.

License

MIT © 2019 Guild of Weavers