func TestMerkleTreeConsistencyFuzz(t *testing.T) {
	data := makeFuzzTestData()
	for treeSize := int64(1); treeSize <= fuzzTestSize; treeSize++ {
		mt := makeEmptyTree()
		for l := int64(0); l < treeSize; l++ {
			mt.AddLeaf(data[l])
		}
		for j := 0; j < 8; j++ {
			snapshot2 := rand.Int63n(treeSize + 1)
			snapshot1 := rand.Int63n(snapshot2 + 1)
			c1 := mt.SnapshotConsistency(snapshot1, snapshot2)
			c2, err := referenceSnapshotConsistency(data[:snapshot2], snapshot2, snapshot1, mt.hasher, true)
			if err != nil {
				t.Fatalf("referenceSnapshotConsistency(): %v", err)
			}
			if len(c1) != len(c2) {
				t.Errorf("Different proof lengths: %d %d %d", treeSize, snapshot2,
					snapshot1)
			}
			for i := 0; i < len(c1); i++ {
				if !bytes.Equal(c1[i].Value.hash, c2[i]) {
					t.Errorf("Different proof: %d %d %d %d, %s, %s", treeSize,
						snapshot2, snapshot1, i, hex.EncodeToString(c1[i].Value.hash),
						hex.EncodeToString(c2[i]))
				}
			}
		}
	}
}
Make random proof queries and check against the reference implementation.
package inmemory
import (
	"bytes"
	"encoding/hex"
	"errors"
	"fmt"
	"math/rand"
	"testing"
	_ "github.com/golang/glog"
	"github.com/google/trillian/merkle/hashers"
	"github.com/google/trillian/merkle/rfc6962"
)
var fuzzTestSize = int64(256)
var emptyTreeHashValue = "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
var leafInputs = []string{
	"", "00", "10", "2021", "3031", "40414243",
	"5051525354555657", "606162636465666768696a6b6c6d6e6f",
}
var levelCounts = []int64{1, 2, 3, 3, 4, 4, 4, 4}
var rootsAtSize = []string{
	"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
	"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125",
	"aeb6bcfe274b70a14fb067a5e5578264db0fa9b51af5e0ba159158f329e06e77",
	"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
	"4e3bbb1f7b478dcfe71fb631631519a3bca12c9aefca1612bfce4c13a86264d4",
	"76e67dadbcdf1e10e1b74ddc608abd2f98dfb16fbce75277b5232a127f2087ef",
	"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c",
	"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328",
}
type pathTestVector struct {
	leaf       int64
	snapshot   int64
	pathLength int64
	testVector []string
}
var testPaths = []pathTestVector{
	{0, 0, 0, []string{""}},
	{1, 1, 0, []string{""}},
	{
		1,
		8,
		3,
		[]string{
			"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
			"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
			"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
		},
	},
	{
		6,
		8,
		3,
		[]string{
			"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
			"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
			"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
		},
	},
	{
		3,
		3,
		1,
		[]string{"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125"},
	},
	{
		2,
		5,
		3,
		[]string{
			"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
			"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
			"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
		},
	},
}
type proofTestVector struct {
	snapshot1   int64
	snapshot2   int64
	proofLength int64
	proof       []string
}
var testProofs = []proofTestVector{
	{1, 1, 0, []string{""}},
	{1, 8, 3, []string{
		"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
		"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
		"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
	}},
	{6, 8, 3, []string{
		"0ebc5d3437fbe2db158b9f126a1d118e308181031d0a949f8dededebc558ef6a",
		"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
		"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
	}},
	{2, 5, 2, []string{
		"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
		"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
	}},
}
func decodeHexStringOrPanic(hs string) []byte {
	data, err := hex.DecodeString(hs)
	if err != nil {
		panic(fmt.Errorf("failed to decode test data: %s", hs))
	}
	return data
}
func makeEmptyTree() *MerkleTree {
	return NewMerkleTree(rfc6962.DefaultHasher)
}
func makeFuzzTestData() [][]byte {
	var data [][]byte
	for s := int64(0); s < fuzzTestSize; s++ {
		data = append(data, make([]byte, 1))
		data[s][0] = byte(s)
	}
	return data
}
func getRootAsString(mt MerkleTree, leaf int64) string {
	node := mt.RootAtSnapshot(leaf)
	if node.hash == nil {
		return "<nil>"
	}
	return hex.EncodeToString(node.hash)
}
func downToPowerOfTwo(i int64) int64 {
	if i < 2 {
		panic(errors.New("requested downToPowerOf2 for value < 2"))
	}
	split := int64(2)
	for split < i {
		split <<= 1
	}
	return split >> 1
}
func referenceMerkleTreeHash(inputs [][]byte, treehasher hashers.LogHasher) ([]byte, error) {
	if len(inputs) == 0 {
		return treehasher.EmptyRoot(), nil
	}
	if len(inputs) == 1 {
		return treehasher.HashLeaf(inputs[0]), nil
	}
	split := downToPowerOfTwo(int64(len(inputs)))
	lhs, err := referenceMerkleTreeHash(inputs[:split], treehasher)
	if err != nil {
		return nil, err
	}
	rhs, err := referenceMerkleTreeHash(inputs[split:], treehasher)
	if err != nil {
		return nil, err
	}
	return treehasher.HashChildren(lhs, rhs), nil
}
func referenceMerklePath(inputs [][]byte, leaf int64, treehasher hashers.LogHasher) ([][]byte, error) {
	var path [][]byte
	inputLen := int64(len(inputs))
	if leaf > inputLen || leaf == 0 {
		return path, nil
	}
	if inputLen == 1 {
		return path, nil
	}
	split := downToPowerOfTwo(inputLen)
	var subpath [][]byte
	if leaf <= split {
		s, err := referenceMerklePath(inputs[:split], leaf, treehasher)
		if err != nil {
			return nil, err
		}
		subpath = s
		path = append(path, subpath...)
		refHash, err := referenceMerkleTreeHash(inputs[split:], treehasher)
		if err != nil {
			return nil, err
		}
		path = append(path, refHash)
	} else {
		s, err := referenceMerklePath(inputs[split:], leaf-split, treehasher)
		if err != nil {
			return nil, err
		}
		subpath = s
		path = append(path, subpath...)
		refHash, err := referenceMerkleTreeHash(inputs[:split], treehasher)
		if err != nil {
			return nil, err
		}
		path = append(path, refHash)
	}
	return path, nil
}
func referenceSnapshotConsistency(inputs [][]byte, snapshot2 int64,
	snapshot1 int64, treehasher hashers.LogHasher, haveRoot1 bool) ([][]byte, error) {
	var proof [][]byte
	if snapshot1 == 0 || snapshot1 > snapshot2 {
		return proof, nil
	}
	if snapshot1 == snapshot2 {
		if !haveRoot1 {
			refHash, err := referenceMerkleTreeHash(inputs[:snapshot1], treehasher)
			if err != nil {
				return nil, err
			}
			proof = append(proof, refHash)
		}
		return proof, nil
	}
	split := downToPowerOfTwo(snapshot2)
	var subproof [][]byte
	if snapshot1 <= split {
		s, err := referenceSnapshotConsistency(inputs[:split], split, snapshot1, treehasher, haveRoot1)
		if err != nil {
			return nil, err
		}
		subproof = s
		proof = append(proof, subproof...)
		h, err := referenceMerkleTreeHash(inputs[split:], treehasher)
		if err != nil {
			return nil, err
		}
		proof = append(proof, h)
	} else {
		s, err := referenceSnapshotConsistency(inputs[split:], snapshot2-split, snapshot1-split, treehasher, false)
		if err != nil {
			return nil, err
		}
		subproof = s
		proof = append(proof, subproof...)
		refHash, err := referenceMerkleTreeHash(inputs[:split], treehasher)
		if err != nil {
			return nil, err
		}
		proof = append(proof, refHash)
	}
	return proof, nil
}
func TestEmptyTreeIsEmpty(t *testing.T) {
	mt := makeEmptyTree()
	if mt.LevelCount() != 0 {
		t.Errorf("Empty tree had levels: %d", mt.LevelCount())
	}
	if mt.LeafCount() != 0 {
		t.Errorf("Empty tree had leaves: %d", mt.LeafCount())
	}
}
func TestEmptyTreeHash(t *testing.T) {
	actual := makeEmptyTree().CurrentRoot().hash
	actualStr := hex.EncodeToString(actual)
	if actualStr != emptyTreeHashValue {
		t.Errorf("Unexpected empty tree hash: %s", actualStr)
	}
}
func validateTree(mt *MerkleTree, l int64, t *testing.T) {
	if mt.LeafCount() != l+1 {
		t.Errorf("Incorrect leaf count %d, expecting %d", mt.LeafCount(), l+1)
	}
	if mt.LevelCount() != levelCounts[l] {
		t.Errorf("Incorrect leaf count %d, expecting %d", mt.LevelCount(),
			levelCounts[l])
	}
	if getRootAsString(*mt, l+1) != rootsAtSize[l] {
		t.Errorf("Incorrect root %d, got %s", l, getRootAsString(*mt, l+1))
	}
	if getRootAsString(*mt, 0) != emptyTreeHashValue {
		t.Errorf("Incorrect root(0) %d, got %s", l, getRootAsString(*mt, 0))
	}
	for j := int64(0); j <= l; j++ {
		if getRootAsString(*mt, j+1) != rootsAtSize[j] {
			t.Errorf("Incorrect root %d, %d, got %s", l, j, getRootAsString(*mt, j+1))
		}
	}
	for k := l + 1; k <= 8; k++ {
		if getRootAsString(*mt, k+1) != "<nil>" {
			t.Errorf("Got root for missing leaf %d, %d, %s", l, k,
				getRootAsString(*mt, k+1))
		}
	}
}
func TestBuildTreeBuildOneAtATime(t *testing.T) {
	mt := makeEmptyTree()
	for l := int64(0); l < 8; l++ {
		mt.AddLeaf(decodeHexStringOrPanic(leafInputs[l]))
		validateTree(mt, l, t)
	}
}
func TestBuildTreeBuildAllAtOnce(t *testing.T) {
	mt := makeEmptyTree()
	for l := 0; l < 3; l++ {
		mt.AddLeaf(decodeHexStringOrPanic(leafInputs[l]))
	}
	validateTree(mt, 2, t)
	for l := 3; l < 8; l++ {
		mt.AddLeaf(decodeHexStringOrPanic(leafInputs[l]))
	}
	validateTree(mt, 7, t)
}
func TestBuildTreeBuildTwoChunks(t *testing.T) {
	mt := makeEmptyTree()
	for l := 0; l < 8; l++ {
		mt.AddLeaf(decodeHexStringOrPanic(leafInputs[l]))
	}
	validateTree(mt, 7, t)
}
func TestDownToPowerOfTwoSanity(t *testing.T) {
	if downToPowerOfTwo(7) != 4 {
		t.Errorf("Down to power of 2 returned 7 -> %d", downToPowerOfTwo(7))
	}
	if downToPowerOfTwo(8) != 4 {
		t.Errorf("Down to power of 2 returned 8 -> %d", downToPowerOfTwo(8))
	}
	if downToPowerOfTwo(63) != 32 {
		t.Errorf("Down to power of 2 returned 63 -> %d", downToPowerOfTwo(63))
	}
	if downToPowerOfTwo(28973) != 16384 {
		t.Errorf("Down to power of 2 returned 63 -> %d", downToPowerOfTwo(28973))
	}
}
func TestReferenceMerklePathSanity(t *testing.T) {
	var data [][]byte
	mt := makeEmptyTree()
	for s := 0; s < 8; s++ {
		data = append(data, decodeHexStringOrPanic(leafInputs[s]))
	}
	for _, path := range testPaths {
		referencePath, err := referenceMerklePath(data[:path.snapshot], path.leaf, mt.hasher)
		if err != nil {
			t.Fatalf("referenceMerklePath(): %v", err)
		}
		if int64(len(referencePath)) != path.pathLength {
			t.Errorf("Mismatched path length: %d, %d: %v %v",
				len(referencePath), path.pathLength, path, referencePath)
		}
		for i := int64(0); i < path.pathLength; i++ {
			if !bytes.Equal(referencePath[i], decodeHexStringOrPanic(path.testVector[i])) {
				t.Errorf("Path mismatch: %s, %s", hex.EncodeToString(referencePath[i]),
					path.testVector[i])
			}
		}
	}
}
func TestMerkleTreeRootFuzz(t *testing.T) {
	data := makeFuzzTestData()
	for treeSize := int64(1); treeSize <= fuzzTestSize; treeSize++ {
		mt := makeEmptyTree()
		for l := int64(0); l < treeSize; l++ {
			mt.AddLeaf(data[l])
		}
		for j := int64(0); j < 8; j++ {
			snapshot := rand.Int63n(treeSize + 1)
			h1 := mt.RootAtSnapshot(snapshot).hash
			h2, err := referenceMerkleTreeHash(data[:snapshot], mt.hasher)
			if err != nil {
				t.Fatalf("referenceMerkleTreeHash(): %v", err)
			}
			if !bytes.Equal(h1, h2) {
				t.Errorf("Mismatched hash: %x, %x", h1, h2)
			}
		}
	}
}
func TestMerkleTreePathFuzz(t *testing.T) {
	data := makeFuzzTestData()
	for treeSize := int64(1); treeSize <= fuzzTestSize; treeSize++ {
		mt := makeEmptyTree()
		for l := int64(0); l < treeSize; l++ {
			mt.AddLeaf(data[l])
		}
		for j := 0; j < 8; j++ {
			snapshot := rand.Int63n(treeSize + 1)
			leaf := rand.Int63n(snapshot + 1)
			p1 := mt.PathToRootAtSnapshot(leaf, snapshot)
			p2, err := referenceMerklePath(data[:snapshot], leaf, mt.hasher)
			if err != nil {
				t.Fatalf("referenceMerklePath(): %v", err)
			}
			if len(p1) != len(p2) {
				t.Errorf("Different path lengths %v, %v", p1, p2)
			} else {
				for i := 0; i < len(p1); i++ {
					if !bytes.Equal(p1[i].Value.hash, p2[i]) {
						t.Errorf("Mismatched hash %d %d %d: %v, %v", snapshot, leaf, i,
							p1[i].Value.hash, p2[i])
					}
				}
			}
		}
	}
}