merkle-tree-binary

Set of functions for creating Merkle Tree, proofs and verifying proofs using binary data.

This library doesn't hash original data, you have to specify hashes (or binary data of fixed size).

This implementation is vulnerable to a forgery attack (as a second pre-image attack), see these[1][2] crypto.stackexchange questions for an explanation. To avoid this vulnerability, you should pre-hash your leaves using a different hash function than the function provided such that H(x) != H'(x), alternatively you can record tree depth alongside root hash and check it during validation.

This implementation is vulnerable to a forgery attack (for an unbalanced Merkle Tree), wherein, in an unbalanced Merkle Tree, the last leaf node can be duplicated to create an artificial balanced tree, resulting in the same root hash. To avoid this vulnerability, do not accept unbalanced Merkle Trees in your application.

How to install

npm install merkle-tree-binary

How to use

TypeScript:

import {Tree} from 'merkle-tree-binary';

// Do stuff

Node.js:

var {Tree} = require('merkle-tree-binary')

// Do stuff

Browser:

requirejs(['merkle-tree-binary'], function ({Tree}) {
    // Do stuff
})

API

merkleTreeBinary.Tree(items : Uint8Array[], hashFunction : (input: Uint8Array) => Uint8Array) : merkleTreeBinary.Tree

Constructor, creates a tree object from items and using specified hash function (items should also be constant-size, like after some hash function).

merkleTreeBinary.Tree.getRoot() : Uint8Array

Returns Uint8Array root of Merkle Tree.

merkleTreeBinary.getProof(targetItem : Uint8Array) : Uint8Array

Generates a proof for targetItem in form of single compact binary string.

Binary string consists of blocks. Each block starts with 0 or 1 for left and right accordingly, where current hash should be inserted and followed by the other hash on the same level.

merkleTreeBinary.Tree.checkProof(root, proof, targetItem, hashFunction: (input: Uint8Array) => Uint8Array) : boolean

Static function on Tree class, checks whether proof generated by getProof() is correct or not.

Contribution

Feel free to create issues and send pull requests (for big changes create an issue first and link it from the PR), they are highly appreciated!

When reading LiveScript code make sure to configure 1 tab to be 4 spaces (GitHub uses 8 by default), otherwise code might be hard to read.

License

Zero-Clause BSD

https://opensource.org/licenses/0BSD

https://tldrlegal.com/license/bsd-0-clause-license