Simple Merkle root calculator
Node or bundler
require('mroot')
import mroot from 'mroot'
Browser
<script src="mroot.js"></script>
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
-
Your leaves can be in whatever format you want (hex, buffer, array). They never get touched except by your hasher.
-
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.
-
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.
-
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
-
Each leaf must be externally validated, to protect against the second preimage attack.
For example, given leaves
A = "alice"
andB = "bob"
, the root of[A, B]
is the same as the root of just[C]
, whereC = 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]
). -
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 messageM
, the naive signaturesha256(K + M)
can be used by anyone to makesha256(K + M + X)
to make it seem like you signedX
as well.YOU SHOULD BE OK if you don't use shared-secret cryptography or you stick to strictly-formatted messages.
-
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 likeC
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