merkle.gno

 1package merkle
 2
 3import (
 4	"crypto/sha256"
 5)
 6
 7// HashFromByteSlices computes a Merkle tree where the leaves are the byte
 8// slice, in the provided order. It follows RFC-6962.
 9func HashFromByteSlices(items [][]byte) []byte {
10	switch len(items) {
11	case 0:
12		return emptyHash()
13	case 1:
14		return leafHash(items[0])
15	default:
16		// Find the split point (largest power of 2 <= len(items)).
17		length := len(items)
18		var k int
19		for k = 1; k < length; k <<= 1 {
20		}
21		k >>= 1
22
23		left := HashFromByteSlices(items[:k])
24		right := HashFromByteSlices(items[k:])
25		return innerHash(left, right)
26	}
27}
28
29var (
30	leafPrefix  = []byte{0x00}
31	innerPrefix = []byte{0x01}
32)
33
34// emptyHash returns sha256(<empty>)
35func emptyHash() []byte {
36	bz := sha256.Sum256([]byte{})
37	return bz[:]
38}
39
40// leafHash returns sha256(0x00 || leaf)
41func leafHash(leaf []byte) []byte {
42	bz := sha256.Sum256(append(leafPrefix, leaf...))
43	return bz[:]
44}
45
46// innerHash returns sha256(0x01 || left || right)
47func innerHash(left, right []byte) []byte {
48	bz := sha256.Sum256(append(innerPrefix, append(left, right...)...))
49	return bz[:]
50}