@truestamp/tree

@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 ³) 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 ⁴), 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/tree

Sample 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 false

A 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.

Footnotes

1. Attacking Merkle Trees With a Second Pre-image Attack ↩

2. Merkle tree second pre-image attack ↩

3. What is the purpose of using different hash functions for the leaves and internals of a hash tree? ↩ ↩²

4. Bitcoin Forum > Bitcoin > Bitcoin Discussion > [Full Disclosure] CVE-2012-2459 (block merkle calculation exploit) ↩