MerkleTree

import { MerkleTree } from "https://raw.githubusercontent.com/marigold-dev/tzstamp/0.3.4/tezos-merkle/mod.ts";

Appendable Tezos-style Merkle tree

Based on the Merkle tree implementation found within the Tezos source code.

The hashing algorithm is BLAKE2b with 32-byte digests. The last leaf is implicitly duplicated until the tree is perfect. The root of an empty tree is the BLAKE2b digest of no input.

Appends have a logarithmic time complexity.

class MerkleTree {

constructor({ deduplicate }?: MerkleTreeOptions);

private blocks: Uint8Array[];

private blockSet: Set<string>;

private readonly deduplicate: boolean;

private layers: Uint8Array[][];

get root(): Uint8Array;

get size(): number;

append(...blocks: Uint8Array[]): void;

has(block: Uint8Array): boolean;

path(index: number): Path;

*paths(): Generator<Path>;

}

§Constructors

new MerkleTree({ deduplicate }?: MerkleTreeOptions)

[src]

@param deduplicate

Deduplicate leaves. Defaults to false

§Properties

blocks: Uint8Array[]

[src]

blockSet: Set<string>

[src]

deduplicate: boolean

[src]

layers: Uint8Array[][]

[src]

root: Uint8Array readonly

[src]

Root hash

size: number readonly

[src]

The number of leaves included within the Merkle tree

§Methods

append(...blocks: Uint8Array[]): void

[src]

Appends data blocks to the Merkle tree.

const merkleTree = new MerkleTree();

merkleTree.append(
  new Uint8Array([ 1, 2 ]),
  new Uint8Array([ 3, 4 ]),
  new Uint8Array([ 5, 6 ]),
);

merkleTree.size; // 3

Merkle trees configured to deduplicate blocks will silently drop previously-included blocks:

const merkleTree = new MerkleTree({
  deduplicate: true,
});

merkleTree.append(
  new Uint8Array([ 1, 2 ]),
  new Uint8Array([ 1, 2 ]), // deduplicated
);

merkleTree.size; // 1

Appends have logarithmic time-complexity. Internally, the last leaf is implicitly duplicated until the tree is perfect.

@param blocks

Data blocks

has(block: Uint8Array): boolean

[src]

Checks if a block is included in the tree.

@param block

Data block

path(index: number): Path

[src]

Calculates the path from a leaf at the given index to the root hash. Throws RangeError if there is no leaf with the given index.

@param index

Index of the leaf.

paths(): Generator<Path>

[src]

Generates all leaf-to-root paths in the Merkle tree.