mroot

mroot
=====
Simple Merkle root calculator

Node or bundler

require('mroot')

import mroot from 'mroot'

Browser

import mroot from './mroot.mjs'

Usage

mroot(leaves, hasher, compat = false)

leaves your ordered Array or Set of already-hashed messages

hasher your pair-hashing function, e.g. (a, b) => sha256(a + b)

compat whether to pad each layer to an even number of nodes by duplicating the
last leaf, if necessary, for compatibility with Satoshi's Merkle tree
implementation in Bitcoin

Notes

1. Your leaves can be in whatever format you want (hex, buffer, array). They
never get touched except by your hasher.

2. If you have zero leaves, we throw an error. In Bitcoin, this returns the
256-bit representation of 1 (see merkle.cpp). You
need to handle this case.

3. If you only have one leaf, your hasher won't be called, so the root will be
your leaf itself, even with the Bitcoin compatibility option. You need to make
sure your leaf's type is acceptable as a root.

4. This "constant-space" algorithm mutates a shrinking internal array that
doesn't keep the whole tree in memory. (Other JS implementations optimize this
further by requiring you to concatenate all of your leaves into a mutable buffer
to avoid garbage collection of intermediate nodes?)

Examples

// Node
const crypto = require('crypto')
const sha256 = buf => crypto.createHash('sha256').update(buf).digest()
const hasher = (a, b) => sha256(Buffer.concat([a, b]))
const leaves = ['bwib', 'bwab', bwob'].map(Buffer.from).map(sha256)
const root = mroot(leaves, hasher)
console.log(root.toString('hex'))

Warnings on Merkle tree security

1. Each leaf must be externally validated, to protect against the second
preimage attack.

For example, given leaves A = "alice" and B = "bob", the
root of [A, B] is the same as the root of just [C], where C =
hash("alice") + hash("bob").

YOU SHOULD BE OK if you reject C (e.g. because it's actually a binary hash
blob and you were expecting a name) and you don't permanently flag the root
itself as invalid (preventing you from accepting the legitimate [A, B]).

https://crypto.stackexchange.com/questions/43430

2. Do not use the root as an HMAC if your hasher is vulnerable to
length-extension.

For example, for your shared secret key K and message M, the naive
signature sha256(K + M) can be used by anyone to make sha256(K + M + X)
to make it seem like you signed X as well.

YOU SHOULD BE OK if you don't use shared-secret cryptography or you stick to
strictly-formatted messages.

https://security.stackexchange.com/questions/20129

3. Do not use the Bitcoin compatibility option unless you handle the fact that
you will get the same root with a potentially invalid, duplicated last-pair
of leaves.

For example, the leaves [A, B, C] will have the same root as the leaves
[A, B, C, C]. If you earmark the root itself as invalid because you don't
like C being duplicated, then you might be tricked into rejecting
[A, B, C] as well.

https://bitcointalk.org/?topic=102395
https://github.com/bitcoin/bitcoin/blob/master/src/consensus/merkle.cpp

By Dylan Sharhon, 2020