@truestamp/tree
This library provides a TypeScript/JavaScript API for creating Merkle trees, and validating Merkle inclusion proofs.
Data provided to create the tree is required to already be in binary form (Uint8Array) and all
internal operations are performed on binary data.
The library provides several encodings for Merkle inclusion proofs, any one of which is acceptable for validation.
This library doesn't hash original data, you have to provide hashed (or arbitrary binary data of fixed size). All SHA2 and SHA3 common hash functions, implemented in pure TypeScript, are exported for your convenience and are the same hash functions used internally.
The library performs extensive compile time (TypeScript), and run time, validation of the incoming and outgoing data to ensure correctness and safety at the possible expense of raw performance. That being said, it is still extremely fast, able to round-trip process a 1,000 item tree in about 20 milliseconds.
Security Notes
In order to help prevent the possibility of a second pre-image attack (see 1 2 3) the data leaf nodes provided to construct the tree are prefixed with a 0x00 byte. All inner nodes of the tree are prefixed with a 0x01 byte. These prefixes are also applied during the validation step.
An additional step that can be taken to avoid second pre-image attack vulnerability is to pre-hash your leaves using a different hash function (see 3) than the function provided to construct the tree so that H(x) != H'(x). For example, use sha3-256 to pre-hash the leaves, and use sha2-256 to construct the tree.
This implementation is potentially vulnerable to a forgery attack for an unbalanced Merkle Tree (see 4), wherein, in an unbalanced Merkle Tree, the last leaf node can be duplicated to create an artificially balanced tree. This can result in the same root hash. To avoid this vulnerability, do not construct an unbalanced Merkle Trees (where the length of the data array provided is not a power of 2). This library provides an optional requireBalanced configuration flag that will throw an Error if the data.length is not a power of 2.
Install
npm install @truestamp/treeSample Usage
Node.js:
const { Tree } = require('@truestamp/tree')
// import { Tree } from '@truestamp/tree';
// A sample data array with 8 elements of 32 bytes each.
// The data elements should be the same length as the output of the hash.
const data = [
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
new Uint8Array([
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
]),
]
// Construct the Merkle tree, the hash function name and options are optional.
const t = new Tree(data, 'sha256', { requireBalanced: true, debug: false })
// Get the root of the tree for later use
const r = t.root()
// For example purposes, pick (and store a verifiable copy) of
// one data element that will be verified.
// In the real world likely store a pristine copy of the data
// for later re-hashing and verification.
const d = data[4]
// Extract the Merkle inclusion proof for that data element to store
// alongside your pristine copy of the data.
// In the real world you'd likely do the same for every data element
// to store and later verify).
const p = t.proofObject(d)
// At any time in the future, verify your proof by providing
// the stored root, the proof, and the data. The last argument, the hash
// function name, is optional in this case since we're using the
// proof object encoding.
console.log('verified?', Tree.verify(r, p, d)) // returns true or falseA more detailed version of this example can be found in [examples/example.cjs].
API Documentation
The TypeScript API documentation for this project is generated and published upon each new release.
Performance
Using the example code on a MacBook Pro and the following size sample data sets of random elements and the Node.js crypto SHA-256 function:
1,000 data elements
- creates a tree in
13.03ms - extracts the Merkle root from the tree in
0.154ms - extracts a single Merkle inclusion proof in
3.42ms - verifies that proof in
1.15ms
1,000,000 data elements
- creates a tree in
3.490s - extracts the Merkle root from the tree in
0.204ms - extracts a single Merkle inclusion proof in
23.139ms - verifies that proof in
1.533ms
Truestamp Community Hub
Please see our Github organization's profile at github.com/truestamp for quick access to links related to these and other important topics.
- Filing Issues (bug reports & feedback)
- Community Discussions
- Security Reporting
- Code of Conduct
- Code Contributions
- Public roadmap
- Support
Legal
Copyright © 2019-2023 Truestamp Inc. All Rights Reserved.