// Package merkle rebuilds a block's merkle root from its transaction ids.
//
// A filter says a block mentions a script; the root is how the wallet knows the block it was
// handed is the block the header committed to. Without it, a gateway could answer a filter
// match with a block of its own invention, and the wallet would believe the outputs in it.
package merkle

import "crypto/sha256"

// Root computes a block's merkle root from its transaction ids, in wire order.
//
// Bitcoin's rule for an odd number of hashes at any level is to pair the last one with itself;
// getting that wrong produces a different root for every block with an odd count, which is
// most of them.
func Root(txids [][32]byte) ([32]byte, error) {
	if len(txids) == 0 {
		return [32]byte{}, ErrNoTransactions
	}

	level := make([][32]byte, len(txids))
	copy(level, txids)

	for len(level) > 1 {
		if len(level)%2 == 1 {
			level = append(level, level[len(level)-1])
		}

		next := make([][32]byte, 0, len(level)/2)

		for index := 0; index < len(level); index += 2 {
			next = append(next, hashPair(level[index], level[index+1]))
		}

		level = next
	}

	return level[0], nil
}

// hashPair is the double SHA-256 of two concatenated hashes.
func hashPair(left, right [32]byte) [32]byte {
	pair := make([]byte, 0, 64)
	pair = append(pair, left[:]...)
	pair = append(pair, right[:]...)

	first := sha256.Sum256(pair)

	return sha256.Sum256(first[:])
}

// ErrNoTransactions is an empty block.
var ErrNoTransactions = errorString("merkle: a block has at least one transaction")

// errorString is a constant error with no formatting.
type errorString string

// Error renders the message.
func (e errorString) Error() string { return string(e) }