1 // Package merkle rebuilds a block's merkle root from its transaction ids.
2 //
3 // A filter says a block mentions a script; the root is how the wallet knows the block it was
4 // handed is the block the header committed to. Without it, a gateway could answer a filter
5 // match with a block of its own invention, and the wallet would believe the outputs in it.
6 package merkle
7 8 import "crypto/sha256"
9 10 // Root computes a block's merkle root from its transaction ids, in wire order.
11 //
12 // Bitcoin's rule for an odd number of hashes at any level is to pair the last one with itself;
13 // getting that wrong produces a different root for every block with an odd count, which is
14 // most of them.
15 func Root(txids [][32]byte) ([32]byte, error) {
16 if len(txids) == 0 {
17 return [32]byte{}, ErrNoTransactions
18 }
19 20 level := make([][32]byte, len(txids))
21 copy(level, txids)
22 23 for len(level) > 1 {
24 if len(level)%2 == 1 {
25 level = append(level, level[len(level)-1])
26 }
27 28 next := make([][32]byte, 0, len(level)/2)
29 30 for index := 0; index < len(level); index += 2 {
31 next = append(next, hashPair(level[index], level[index+1]))
32 }
33 34 level = next
35 }
36 37 return level[0], nil
38 }
39 40 // hashPair is the double SHA-256 of two concatenated hashes.
41 func hashPair(left, right [32]byte) [32]byte {
42 pair := make([]byte, 0, 64)
43 pair = append(pair, left[:]...)
44 pair = append(pair, right[:]...)
45 46 first := sha256.Sum256(pair)
47 48 return sha256.Sum256(first[:])
49 }
50 51 // ErrNoTransactions is an empty block.
52 var ErrNoTransactions = errorString("merkle: a block has at least one transaction")
53 54 // errorString is a constant error with no formatting.
55 type errorString string
56 57 // Error renders the message.
58 func (e errorString) Error() string { return string(e) }
59