-
Notifications
You must be signed in to change notification settings - Fork 1
/
mroot.mjs
40 lines (31 loc) · 1.19 KB
/
mroot.mjs
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
32
33
34
35
36
37
38
39
40
export default
/*
Merkle Root calculator
leaves: ordered array or set of pre-hashed messages
hasher: concatenates and hashes pair; (A, B) => hash(A + B)
compat: bitcoin compatibility option (self-pairs remainder leaf)
*/
function mroot (leaves, hasher, compat = false) {
if (!leaves.length && !leaves.size) throw Error('No leaves')
if (typeof hasher !== 'function') throw Error('No hasher')
// Make a working array from the leaves
const nodes = Array.from(leaves)
// Continue, combining pairs, until there's one node left
while (nodes.length > 1) {
// Bitcoin-compatibility option (duplicates odd man out)
const oddity = nodes[nodes.length - 1]
if (compat && nodes.length % 2) nodes.push(oddity)
const half = nodes.length / 2
const pairs = Math.trunc(half)
for (let i = 0; i < pairs; i++) {
const nodeA = nodes[2 * i ]
const nodeB = nodes[2 * i + 1]
const node = hasher(nodeA, nodeB)
nodes[i] = node // shrinks the array by half each round
}
// Trim the array and, if present, promote the odd man out
nodes.length = pairs
if (!compat && half % 1) nodes.push(oddity)
}
return nodes[0] // root, last remaining node
}