sumdb/tlog/tlog.go - mod - Git at Google

 // Copyright 2019 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.

 // Package tlog implements a tamper-evident log
 // used in the Go module go.sum database server.
 //
 // This package follows the design of Certificate Transparency (RFC 6962)
 // and its proofs are compatible with that system.
 // See TestCertificateTransparency.
 package tlog

 import (
 	"crypto/sha256"
 	"encoding/base64"
 	"errors"
 	"fmt"
 	"math/bits"
 )

 // A Hash is a hash identifying a log record or tree root.
 type Hash [HashSize]byte

 // HashSize is the size of a Hash in bytes.
 const HashSize = 32

 // String returns a base64 representation of the hash for printing.
 func (h Hash) String() string {
 	return base64.StdEncoding.EncodeToString(h[:])
 }

 // MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.
 func (h Hash) MarshalJSON() ([]byte, error) {
 	return []byte(`"` + h.String() + `"`), nil
 }

 // UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.
 func (h *Hash) UnmarshalJSON(data []byte) error {
 	if len(data) != 1+44+1 || data[0] != '"' || data[len(data)-2] != '=' || data[len(data)-1] != '"' {
 		return errors.New("cannot decode hash")
 	}

 	// As of Go 1.12, base64.StdEncoding.Decode insists on
 	// slicing into target[33:] even when it only writes 32 bytes.
 	// Since we already checked that the hash ends in = above,
 	// we can use base64.RawStdEncoding with the = removed;
 	// RawStdEncoding does not exhibit the same bug.
 	// We decode into a temporary to avoid writing anything to *h
 	// unless the entire input is well-formed.
 	var tmp Hash
 	n, err := base64.RawStdEncoding.Decode(tmp[:], data[1:len(data)-2])
 	if err != nil || n != HashSize {
 		return errors.New("cannot decode hash")
 	}
 	*h = tmp
 	return nil
 }

 // ParseHash parses the base64-encoded string form of a hash.
 func ParseHash(s string) (Hash, error) {
 	data, err := base64.StdEncoding.DecodeString(s)
 	if err != nil || len(data) != HashSize {
 		return Hash{}, fmt.Errorf("malformed hash")
 	}
 	var h Hash
 	copy(h[:], data)
 	return h, nil
 }

 // maxpow2 returns k, the maximum power of 2 smaller than n,
 // as well as l = log₂ k (so k = 1<<l).
 func maxpow2(n int64) (k int64, l int) {
 	l = 0
 	for 1<<uint(l+1) < n {
 		l++
 	}
 	return 1 << uint(l), l
 }

 var zeroPrefix = []byte{0x00}

 // RecordHash returns the content hash for the given record data.
 func RecordHash(data []byte) Hash {
 	// SHA256(0x00 || data)
 	// https://tools.ietf.org/html/rfc6962#section-2.1
 	h := sha256.New()
 	h.Write(zeroPrefix)
 	h.Write(data)
 	var h1 Hash
 	h.Sum(h1[:0])
 	return h1
 }

 // NodeHash returns the hash for an interior tree node with the given left and right hashes.
 func NodeHash(left, right Hash) Hash {
 	// SHA256(0x01 || left || right)
 	// https://tools.ietf.org/html/rfc6962#section-2.1
 	// We use a stack buffer to assemble the hash input
 	// to avoid allocating a hash struct with sha256.New.
 	var buf [1 + HashSize + HashSize]byte
 	buf[0] = 0x01
 	copy(buf[1:], left[:])
 	copy(buf[1+HashSize:], right[:])
 	return sha256.Sum256(buf[:])
 }

 // For information about the stored hash index ordering,
 // see section 3.3 of Crosby and Wallach's paper
 // "Efficient Data Structures for Tamper-Evident Logging".
 // https://www.usenix.org/legacy/event/sec09/tech/full_papers/crosby.pdf

 // StoredHashIndex maps the tree coordinates (level, n)
 // to a dense linear ordering that can be used for hash storage.
 // Hash storage implementations that store hashes in sequential
 // storage can use this function to compute where to read or write
 // a given hash.
 func StoredHashIndex(level int, n int64) int64 {
 	// Level L's n'th hash is written right after level L+1's 2n+1'th hash.
 	// Work our way down to the level 0 ordering.
 	// We'll add back the original level count at the end.
 	for l := level; l > 0; l-- {
 		n = 2*n + 1
 	}

 	// Level 0's n'th hash is written at n+n/2+n/4+... (eventually n/2ⁱ hits zero).
 	i := int64(0)
 	for ; n > 0; n >>= 1 {
 		i += n
 	}

 	return i + int64(level)
 }

 // SplitStoredHashIndex is the inverse of [StoredHashIndex].
 // That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
 func SplitStoredHashIndex(index int64) (level int, n int64) {
 	// Determine level 0 record before index.
 	// StoredHashIndex(0, n) < 2*n,
 	// so the n we want is in [index/2, index/2+log₂(index)].
 	n = index / 2
 	indexN := StoredHashIndex(0, n)
 	if indexN > index {
 		panic("bad math")
 	}
 	for {
 		// Each new record n adds 1 + trailingZeros(n) hashes.
 		x := indexN + 1 + int64(bits.TrailingZeros64(uint64(n+1)))
 		if x > index {
 			break
 		}
 		n++
 		indexN = x
 	}
 	// The hash we want was committed with record n,
 	// meaning it is one of (0, n), (1, n/2), (2, n/4), ...
 	level = int(index - indexN)
 	return level, n >> uint(level)
 }

 // StoredHashCount returns the number of stored hashes
 // that are expected for a tree with n records.
 func StoredHashCount(n int64) int64 {
 	if n == 0 {
 		return 0
 	}
 	// The tree will have the hashes up to the last leaf hash.
 	numHash := StoredHashIndex(0, n-1) + 1
 	// And it will have any hashes for subtrees completed by that leaf.
 	for i := uint64(n - 1); i&1 != 0; i >>= 1 {
 		numHash++
 	}
 	return numHash
 }

 // StoredHashes returns the hashes that must be stored when writing
 // record n with the given data. The hashes should be stored starting
 // at StoredHashIndex(0, n). The result will have at most 1 + log₂ n hashes,
 // but it will average just under two per call for a sequence of calls for n=1..k.
 //
 // StoredHashes may read up to log n earlier hashes from r
 // in order to compute hashes for completed subtrees.
 func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error) {
 	return StoredHashesForRecordHash(n, RecordHash(data), r)
 }

 // StoredHashesForRecordHash is like [StoredHashes] but takes
 // as its second argument RecordHash(data) instead of data itself.
 func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error) {
 	// Start with the record hash.
 	hashes := []Hash{h}

 	// Build list of indexes needed for hashes for completed subtrees.
 	// Each trailing 1 bit in the binary representation of n completes a subtree
 	// and consumes a hash from an adjacent subtree.
 	m := int(bits.TrailingZeros64(uint64(n + 1)))
 	indexes := make([]int64, m)
 	for i := 0; i < m; i++ {
 		// We arrange indexes in sorted order.
 		// Note that n>>i is always odd.
 		indexes[m-1-i] = StoredHashIndex(i, n>>uint(i)-1)
 	}

 	// Fetch hashes.
 	old, err := r.ReadHashes(indexes)
 	if err != nil {
 		return nil, err
 	}
 	if len(old) != len(indexes) {
 		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(old))
 	}

 	// Build new hashes.
 	for i := 0; i < m; i++ {
 		h = NodeHash(old[m-1-i], h)
 		hashes = append(hashes, h)
 	}
 	return hashes, nil
 }

 // A HashReader can read hashes for nodes in the log's tree structure.
 type HashReader interface {
 	// ReadHashes returns the hashes with the given stored hash indexes
 	// (see StoredHashIndex and SplitStoredHashIndex).
 	// ReadHashes must return a slice of hashes the same length as indexes,
 	// or else it must return a non-nil error.
 	// ReadHashes may run faster if indexes is sorted in increasing order.
 	ReadHashes(indexes []int64) ([]Hash, error)
 }

 // A HashReaderFunc is a function implementing [HashReader].
 type HashReaderFunc func([]int64) ([]Hash, error)

 func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error) {
 	return f(indexes)
 }

 // emptyHash is the hash of the empty tree, per RFC 6962, Section 2.1.
 // It is the hash of the empty string.
 var emptyHash = Hash{
 	0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14,
 	0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
 	0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c,
 	0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
 }

 // TreeHash computes the hash for the root of the tree with n records,
 // using the HashReader to obtain previously stored hashes
 // (those returned by StoredHashes during the writes of those n records).
 // TreeHash makes a single call to ReadHash requesting at most 1 + log₂ n hashes.
 func TreeHash(n int64, r HashReader) (Hash, error) {
 	if n == 0 {
 		return emptyHash, nil
 	}
 	indexes := subTreeIndex(0, n, nil)
 	hashes, err := r.ReadHashes(indexes)
 	if err != nil {
 		return Hash{}, err
 	}
 	if len(hashes) != len(indexes) {
 		return Hash{}, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
 	}
 	hash, hashes := subTreeHash(0, n, hashes)
 	if len(hashes) != 0 {
 		panic("tlog: bad index math in TreeHash")
 	}
 	return hash, nil
 }

 // subTreeIndex returns the storage indexes needed to compute
 // the hash for the subtree containing records [lo, hi),
 // appending them to need and returning the result.
 // See https://tools.ietf.org/html/rfc6962#section-2.1
 func subTreeIndex(lo, hi int64, need []int64) []int64 {
 	// See subTreeHash below for commentary.
 	for lo < hi {
 		k, level := maxpow2(hi - lo + 1)
 		if lo&(k-1) != 0 {
 			panic("tlog: bad math in subTreeIndex")
 		}
 		need = append(need, StoredHashIndex(level, lo>>uint(level)))
 		lo += k
 	}
 	return need
 }

 // subTreeHash computes the hash for the subtree containing records [lo, hi),
 // assuming that hashes are the hashes corresponding to the indexes
 // returned by subTreeIndex(lo, hi).
 // It returns any leftover hashes.
 func subTreeHash(lo, hi int64, hashes []Hash) (Hash, []Hash) {
 	// Repeatedly partition the tree into a left side with 2^level nodes,
 	// for as large a level as possible, and a right side with the fringe.
 	// The left hash is stored directly and can be read from storage.
 	// The right side needs further computation.
 	numTree := 0
 	for lo < hi {
 		k, _ := maxpow2(hi - lo + 1)
 		if lo&(k-1) != 0 || lo >= hi {
 			panic("tlog: bad math in subTreeHash")
 		}
 		numTree++
 		lo += k
 	}

 	if len(hashes) < numTree {
 		panic("tlog: bad index math in subTreeHash")
 	}

 	// Reconstruct hash.
 	h := hashes[numTree-1]
 	for i := numTree - 2; i >= 0; i-- {
 		h = NodeHash(hashes[i], h)
 	}
 	return h, hashes[numTree:]
 }

 // A RecordProof is a verifiable proof that a particular log root contains a particular record.
 // RFC 6962 calls this a “Merkle audit path.”
 type RecordProof []Hash

 // ProveRecord returns the proof that the tree of size t contains the record with index n.
 func ProveRecord(t, n int64, r HashReader) (RecordProof, error) {
 	if t < 0 || n < 0 || n >= t {
 		return nil, fmt.Errorf("tlog: invalid inputs in ProveRecord")
 	}
 	indexes := leafProofIndex(0, t, n, nil)
 	if len(indexes) == 0 {
 		return RecordProof{}, nil
 	}
 	hashes, err := r.ReadHashes(indexes)
 	if err != nil {
 		return nil, err
 	}
 	if len(hashes) != len(indexes) {
 		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
 	}

 	p, hashes := leafProof(0, t, n, hashes)
 	if len(hashes) != 0 {
 		panic("tlog: bad index math in ProveRecord")
 	}
 	return p, nil
 }

 // leafProofIndex builds the list of indexes needed to construct the proof
 // that leaf n is contained in the subtree with leaves [lo, hi).
 // It appends those indexes to need and returns the result.
 // See https://tools.ietf.org/html/rfc6962#section-2.1.1
 func leafProofIndex(lo, hi, n int64, need []int64) []int64 {
 	// See leafProof below for commentary.
 	if !(lo <= n && n < hi) {
 		panic("tlog: bad math in leafProofIndex")
 	}
 	if lo+1 == hi {
 		return need
 	}
 	if k, _ := maxpow2(hi - lo); n < lo+k {
 		need = leafProofIndex(lo, lo+k, n, need)
 		need = subTreeIndex(lo+k, hi, need)
 	} else {
 		need = subTreeIndex(lo, lo+k, need)
 		need = leafProofIndex(lo+k, hi, n, need)
 	}
 	return need
 }

 // leafProof constructs the proof that leaf n is contained in the subtree with leaves [lo, hi).
 // It returns any leftover hashes as well.
 // See https://tools.ietf.org/html/rfc6962#section-2.1.1
 func leafProof(lo, hi, n int64, hashes []Hash) (RecordProof, []Hash) {
 	// We must have lo <= n < hi or else the code here has a bug.
 	if !(lo <= n && n < hi) {
 		panic("tlog: bad math in leafProof")
 	}

 	if lo+1 == hi { // n == lo
 		// Reached the leaf node.
 		// The verifier knows what the leaf hash is, so we don't need to send it.
 		return RecordProof{}, hashes
 	}

 	// Walk down the tree toward n.
 	// Record the hash of the path not taken (needed for verifying the proof).
 	var p RecordProof
 	var th Hash
 	if k, _ := maxpow2(hi - lo); n < lo+k {
 		// n is on left side
 		p, hashes = leafProof(lo, lo+k, n, hashes)
 		th, hashes = subTreeHash(lo+k, hi, hashes)
 	} else {
 		// n is on right side
 		th, hashes = subTreeHash(lo, lo+k, hashes)
 		p, hashes = leafProof(lo+k, hi, n, hashes)
 	}
 	return append(p, th), hashes
 }

 var errProofFailed = errors.New("invalid transparency proof")

 // CheckRecord verifies that p is a valid proof that the tree of size t
 // with hash th has an n'th record with hash h.
 func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error {
 	if t < 0 || n < 0 || n >= t {
 		return fmt.Errorf("tlog: invalid inputs in CheckRecord")
 	}
 	th2, err := runRecordProof(p, 0, t, n, h)
 	if err != nil {
 		return err
 	}
 	if th2 == th {
 		return nil
 	}
 	return errProofFailed
 }

 // runRecordProof runs the proof p that leaf n is contained in the subtree with leaves [lo, hi).
 // Running the proof means constructing and returning the implied hash of that
 // subtree.
 func runRecordProof(p RecordProof, lo, hi, n int64, leafHash Hash) (Hash, error) {
 	// We must have lo <= n < hi or else the code here has a bug.
 	if !(lo <= n && n < hi) {
 		panic("tlog: bad math in runRecordProof")
 	}

 	if lo+1 == hi { // m == lo
 		// Reached the leaf node.
 		// The proof must not have any unnecessary hashes.
 		if len(p) != 0 {
 			return Hash{}, errProofFailed
 		}
 		return leafHash, nil
 	}

 	if len(p) == 0 {
 		return Hash{}, errProofFailed
 	}

 	k, _ := maxpow2(hi - lo)
 	if n < lo+k {
 		th, err := runRecordProof(p[:len(p)-1], lo, lo+k, n, leafHash)
 		if err != nil {
 			return Hash{}, err
 		}
 		return NodeHash(th, p[len(p)-1]), nil
 	} else {
 		th, err := runRecordProof(p[:len(p)-1], lo+k, hi, n, leafHash)
 		if err != nil {
 			return Hash{}, err
 		}
 		return NodeHash(p[len(p)-1], th), nil
 	}
 }

 // A TreeProof is a verifiable proof that a particular log tree contains
 // as a prefix all records present in an earlier tree.
 // RFC 6962 calls this a “Merkle consistency proof.”
 type TreeProof []Hash

 // ProveTree returns the proof that the tree of size t contains
 // as a prefix all the records from the tree of smaller size n.
 func ProveTree(t, n int64, h HashReader) (TreeProof, error) {
 	if t < 1 || n < 1 || n > t {
 		return nil, fmt.Errorf("tlog: invalid inputs in ProveTree")
 	}
 	indexes := treeProofIndex(0, t, n, nil)
 	if len(indexes) == 0 {
 		return TreeProof{}, nil
 	}
 	hashes, err := h.ReadHashes(indexes)
 	if err != nil {
 		return nil, err
 	}
 	if len(hashes) != len(indexes) {
 		return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
 	}

 	p, hashes := treeProof(0, t, n, hashes)
 	if len(hashes) != 0 {
 		panic("tlog: bad index math in ProveTree")
 	}
 	return p, nil
 }

 // treeProofIndex builds the list of indexes needed to construct
 // the sub-proof related to the subtree containing records [lo, hi).
 // See https://tools.ietf.org/html/rfc6962#section-2.1.2.
 func treeProofIndex(lo, hi, n int64, need []int64) []int64 {
 	// See treeProof below for commentary.
 	if !(lo < n && n <= hi) {
 		panic("tlog: bad math in treeProofIndex")
 	}

 	if n == hi {
 		if lo == 0 {
 			return need
 		}
 		return subTreeIndex(lo, hi, need)
 	}

 	if k, _ := maxpow2(hi - lo); n <= lo+k {
 		need = treeProofIndex(lo, lo+k, n, need)
 		need = subTreeIndex(lo+k, hi, need)
 	} else {
 		need = subTreeIndex(lo, lo+k, need)
 		need = treeProofIndex(lo+k, hi, n, need)
 	}
 	return need
 }

 // treeProof constructs the sub-proof related to the subtree containing records [lo, hi).
 // It returns any leftover hashes as well.
 // See https://tools.ietf.org/html/rfc6962#section-2.1.2.
 func treeProof(lo, hi, n int64, hashes []Hash) (TreeProof, []Hash) {
 	// We must have lo < n <= hi or else the code here has a bug.
 	if !(lo < n && n <= hi) {
 		panic("tlog: bad math in treeProof")
 	}

 	// Reached common ground.
 	if n == hi {
 		if lo == 0 {
 			// This subtree corresponds exactly to the old tree.
 			// The verifier knows that hash, so we don't need to send it.
 			return TreeProof{}, hashes
 		}
 		th, hashes := subTreeHash(lo, hi, hashes)
 		return TreeProof{th}, hashes
 	}

 	// Interior node for the proof.
 	// Decide whether to walk down the left or right side.
 	var p TreeProof
 	var th Hash
 	if k, _ := maxpow2(hi - lo); n <= lo+k {
 		// m is on left side
 		p, hashes = treeProof(lo, lo+k, n, hashes)
 		th, hashes = subTreeHash(lo+k, hi, hashes)
 	} else {
 		// m is on right side
 		th, hashes = subTreeHash(lo, lo+k, hashes)
 		p, hashes = treeProof(lo+k, hi, n, hashes)
 	}
 	return append(p, th), hashes
 }

 // CheckTree verifies that p is a valid proof that the tree of size t with hash th
 // contains as a prefix the tree of size n with hash h.
 func CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error {
 	if t < 1 || n < 1 || n > t {
 		return fmt.Errorf("tlog: invalid inputs in CheckTree")
 	}
 	h2, th2, err := runTreeProof(p, 0, t, n, h)
 	if err != nil {
 		return err
 	}
 	if th2 == th && h2 == h {
 		return nil
 	}
 	return errProofFailed
 }

 // runTreeProof runs the sub-proof p related to the subtree containing records [lo, hi),
 // where old is the hash of the old tree with n records.
 // Running the proof means constructing and returning the implied hashes of that
 // subtree in both the old and new tree.
 func runTreeProof(p TreeProof, lo, hi, n int64, old Hash) (Hash, Hash, error) {
 	// We must have lo < n <= hi or else the code here has a bug.
 	if !(lo < n && n <= hi) {
 		panic("tlog: bad math in runTreeProof")
 	}

 	// Reached common ground.
 	if n == hi {
 		if lo == 0 {
 			if len(p) != 0 {
 				return Hash{}, Hash{}, errProofFailed
 			}
 			return old, old, nil
 		}
 		if len(p) != 1 {
 			return Hash{}, Hash{}, errProofFailed
 		}
 		return p[0], p[0], nil
 	}

 	if len(p) == 0 {
 		return Hash{}, Hash{}, errProofFailed
 	}

 	// Interior node for the proof.
 	k, _ := maxpow2(hi - lo)
 	if n <= lo+k {
 		oh, th, err := runTreeProof(p[:len(p)-1], lo, lo+k, n, old)
 		if err != nil {
 			return Hash{}, Hash{}, err
 		}
 		return oh, NodeHash(th, p[len(p)-1]), nil
 	} else {
 		oh, th, err := runTreeProof(p[:len(p)-1], lo+k, hi, n, old)
 		if err != nil {
 			return Hash{}, Hash{}, err
 		}
 		return NodeHash(p[len(p)-1], oh), NodeHash(p[len(p)-1], th), nil
 	}
 }
	// Copyright 2019 The Go Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style
	// license that can be found in the LICENSE file.

	// Package tlog implements a tamper-evident log
	// used in the Go module go.sum database server.
	//
	// This package follows the design of Certificate Transparency (RFC 6962)
	// and its proofs are compatible with that system.
	// See TestCertificateTransparency.
	package tlog

	import (
	"crypto/sha256"
	"encoding/base64"
	"errors"
	"fmt"
	"math/bits"
	)

	// A Hash is a hash identifying a log record or tree root.
	type Hash [HashSize]byte

	// HashSize is the size of a Hash in bytes.
	const HashSize = 32

	// String returns a base64 representation of the hash for printing.
	func (h Hash) String() string {
	return base64.StdEncoding.EncodeToString(h[:])
	}

	// MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.
	func (h Hash) MarshalJSON() ([]byte, error) {
	return []byte(`"` + h.String() + `"`), nil
	}

	// UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.
	func (h *Hash) UnmarshalJSON(data []byte) error {
	if len(data) != 1+44+1 \|\| data[0] != '"' \|\| data[len(data)-2] != '=' \|\| data[len(data)-1] != '"' {
	return errors.New("cannot decode hash")
	}

	// As of Go 1.12, base64.StdEncoding.Decode insists on
	// slicing into target[33:] even when it only writes 32 bytes.
	// Since we already checked that the hash ends in = above,
	// we can use base64.RawStdEncoding with the = removed;
	// RawStdEncoding does not exhibit the same bug.
	// We decode into a temporary to avoid writing anything to *h
	// unless the entire input is well-formed.
	var tmp Hash
	n, err := base64.RawStdEncoding.Decode(tmp[:], data[1:len(data)-2])
	if err != nil \|\| n != HashSize {
	return errors.New("cannot decode hash")
	}
	*h = tmp
	return nil
	}

	// ParseHash parses the base64-encoded string form of a hash.
	func ParseHash(s string) (Hash, error) {
	data, err := base64.StdEncoding.DecodeString(s)
	if err != nil \|\| len(data) != HashSize {
	return Hash{}, fmt.Errorf("malformed hash")
	}
	var h Hash
	copy(h[:], data)
	return h, nil
	}

	// maxpow2 returns k, the maximum power of 2 smaller than n,
	// as well as l = log₂ k (so k = 1<<l).
	func maxpow2(n int64) (k int64, l int) {
	l = 0
	for 1<<uint(l+1) < n {
	l++
	}
	return 1 << uint(l), l
	}

	var zeroPrefix = []byte{0x00}

	// RecordHash returns the content hash for the given record data.
	func RecordHash(data []byte) Hash {
	// SHA256(0x00 \|\| data)
	// https://tools.ietf.org/html/rfc6962#section-2.1
	h := sha256.New()
	h.Write(zeroPrefix)
	h.Write(data)
	var h1 Hash
	h.Sum(h1[:0])
	return h1
	}

	// NodeHash returns the hash for an interior tree node with the given left and right hashes.
	func NodeHash(left, right Hash) Hash {
	// SHA256(0x01 \|\| left \|\| right)
	// https://tools.ietf.org/html/rfc6962#section-2.1
	// We use a stack buffer to assemble the hash input
	// to avoid allocating a hash struct with sha256.New.
	var buf [1 + HashSize + HashSize]byte
	buf[0] = 0x01
	copy(buf[1:], left[:])
	copy(buf[1+HashSize:], right[:])
	return sha256.Sum256(buf[:])
	}

	// For information about the stored hash index ordering,
	// see section 3.3 of Crosby and Wallach's paper
	// "Efficient Data Structures for Tamper-Evident Logging".
	// https://www.usenix.org/legacy/event/sec09/tech/full_papers/crosby.pdf

	// StoredHashIndex maps the tree coordinates (level, n)
	// to a dense linear ordering that can be used for hash storage.
	// Hash storage implementations that store hashes in sequential
	// storage can use this function to compute where to read or write
	// a given hash.
	func StoredHashIndex(level int, n int64) int64 {
	// Level L's n'th hash is written right after level L+1's 2n+1'th hash.
	// Work our way down to the level 0 ordering.
	// We'll add back the original level count at the end.
	for l := level; l > 0; l-- {
	n = 2*n + 1
	}

	// Level 0's n'th hash is written at n+n/2+n/4+... (eventually n/2ⁱ hits zero).
	i := int64(0)
	for ; n > 0; n >>= 1 {
	i += n
	}

	return i + int64(level)
	}

	// SplitStoredHashIndex is the inverse of [StoredHashIndex].
	// That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
	func SplitStoredHashIndex(index int64) (level int, n int64) {
	// Determine level 0 record before index.
	// StoredHashIndex(0, n) < 2*n,
	// so the n we want is in [index/2, index/2+log₂(index)].
	n = index / 2
	indexN := StoredHashIndex(0, n)
	if indexN > index {
	panic("bad math")
	}
	for {
	// Each new record n adds 1 + trailingZeros(n) hashes.
	x := indexN + 1 + int64(bits.TrailingZeros64(uint64(n+1)))
	if x > index {
	break
	}
	n++
	indexN = x
	}
	// The hash we want was committed with record n,
	// meaning it is one of (0, n), (1, n/2), (2, n/4), ...
	level = int(index - indexN)
	return level, n >> uint(level)
	}

	// StoredHashCount returns the number of stored hashes
	// that are expected for a tree with n records.
	func StoredHashCount(n int64) int64 {
	if n == 0 {
	return 0
	}
	// The tree will have the hashes up to the last leaf hash.
	numHash := StoredHashIndex(0, n-1) + 1
	// And it will have any hashes for subtrees completed by that leaf.
	for i := uint64(n - 1); i&1 != 0; i >>= 1 {
	numHash++
	}
	return numHash
	}

	// StoredHashes returns the hashes that must be stored when writing
	// record n with the given data. The hashes should be stored starting
	// at StoredHashIndex(0, n). The result will have at most 1 + log₂ n hashes,
	// but it will average just under two per call for a sequence of calls for n=1..k.
	//
	// StoredHashes may read up to log n earlier hashes from r
	// in order to compute hashes for completed subtrees.
	func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error) {
	return StoredHashesForRecordHash(n, RecordHash(data), r)
	}

	// StoredHashesForRecordHash is like [StoredHashes] but takes
	// as its second argument RecordHash(data) instead of data itself.
	func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error) {
	// Start with the record hash.
	hashes := []Hash{h}

	// Build list of indexes needed for hashes for completed subtrees.
	// Each trailing 1 bit in the binary representation of n completes a subtree
	// and consumes a hash from an adjacent subtree.
	m := int(bits.TrailingZeros64(uint64(n + 1)))
	indexes := make([]int64, m)
	for i := 0; i < m; i++ {
	// We arrange indexes in sorted order.
	// Note that n>>i is always odd.
	indexes[m-1-i] = StoredHashIndex(i, n>>uint(i)-1)
	}

	// Fetch hashes.
	old, err := r.ReadHashes(indexes)
	if err != nil {
	return nil, err
	}
	if len(old) != len(indexes) {
	return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(old))
	}

	// Build new hashes.
	for i := 0; i < m; i++ {
	h = NodeHash(old[m-1-i], h)
	hashes = append(hashes, h)
	}
	return hashes, nil
	}

	// A HashReader can read hashes for nodes in the log's tree structure.
	type HashReader interface {
	// ReadHashes returns the hashes with the given stored hash indexes
	// (see StoredHashIndex and SplitStoredHashIndex).
	// ReadHashes must return a slice of hashes the same length as indexes,
	// or else it must return a non-nil error.
	// ReadHashes may run faster if indexes is sorted in increasing order.
	ReadHashes(indexes []int64) ([]Hash, error)
	}

	// A HashReaderFunc is a function implementing [HashReader].
	type HashReaderFunc func([]int64) ([]Hash, error)

	func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error) {
	return f(indexes)
	}

	// emptyHash is the hash of the empty tree, per RFC 6962, Section 2.1.
	// It is the hash of the empty string.
	var emptyHash = Hash{
	0xe3, 0xb0, 0xc4, 0x42, 0x98, 0xfc, 0x1c, 0x14,
	0x9a, 0xfb, 0xf4, 0xc8, 0x99, 0x6f, 0xb9, 0x24,
	0x27, 0xae, 0x41, 0xe4, 0x64, 0x9b, 0x93, 0x4c,
	0xa4, 0x95, 0x99, 0x1b, 0x78, 0x52, 0xb8, 0x55,
	}

	// TreeHash computes the hash for the root of the tree with n records,
	// using the HashReader to obtain previously stored hashes
	// (those returned by StoredHashes during the writes of those n records).
	// TreeHash makes a single call to ReadHash requesting at most 1 + log₂ n hashes.
	func TreeHash(n int64, r HashReader) (Hash, error) {
	if n == 0 {
	return emptyHash, nil
	}
	indexes := subTreeIndex(0, n, nil)
	hashes, err := r.ReadHashes(indexes)
	if err != nil {
	return Hash{}, err
	}
	if len(hashes) != len(indexes) {
	return Hash{}, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
	}
	hash, hashes := subTreeHash(0, n, hashes)
	if len(hashes) != 0 {
	panic("tlog: bad index math in TreeHash")
	}
	return hash, nil
	}

	// subTreeIndex returns the storage indexes needed to compute
	// the hash for the subtree containing records [lo, hi),
	// appending them to need and returning the result.
	// See https://tools.ietf.org/html/rfc6962#section-2.1
	func subTreeIndex(lo, hi int64, need []int64) []int64 {
	// See subTreeHash below for commentary.
	for lo < hi {
	k, level := maxpow2(hi - lo + 1)
	if lo&(k-1) != 0 {
	panic("tlog: bad math in subTreeIndex")
	}
	need = append(need, StoredHashIndex(level, lo>>uint(level)))
	lo += k
	}
	return need
	}

	// subTreeHash computes the hash for the subtree containing records [lo, hi),
	// assuming that hashes are the hashes corresponding to the indexes
	// returned by subTreeIndex(lo, hi).
	// It returns any leftover hashes.
	func subTreeHash(lo, hi int64, hashes []Hash) (Hash, []Hash) {
	// Repeatedly partition the tree into a left side with 2^level nodes,
	// for as large a level as possible, and a right side with the fringe.
	// The left hash is stored directly and can be read from storage.
	// The right side needs further computation.
	numTree := 0
	for lo < hi {
	k, _ := maxpow2(hi - lo + 1)
	if lo&(k-1) != 0 \|\| lo >= hi {
	panic("tlog: bad math in subTreeHash")
	}
	numTree++
	lo += k
	}

	if len(hashes) < numTree {
	panic("tlog: bad index math in subTreeHash")
	}

	// Reconstruct hash.
	h := hashes[numTree-1]
	for i := numTree - 2; i >= 0; i-- {
	h = NodeHash(hashes[i], h)
	}
	return h, hashes[numTree:]
	}

	// A RecordProof is a verifiable proof that a particular log root contains a particular record.
	// RFC 6962 calls this a “Merkle audit path.”
	type RecordProof []Hash

	// ProveRecord returns the proof that the tree of size t contains the record with index n.
	func ProveRecord(t, n int64, r HashReader) (RecordProof, error) {
	if t < 0 \|\| n < 0 \|\| n >= t {
	return nil, fmt.Errorf("tlog: invalid inputs in ProveRecord")
	}
	indexes := leafProofIndex(0, t, n, nil)
	if len(indexes) == 0 {
	return RecordProof{}, nil
	}
	hashes, err := r.ReadHashes(indexes)
	if err != nil {
	return nil, err
	}
	if len(hashes) != len(indexes) {
	return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
	}

	p, hashes := leafProof(0, t, n, hashes)
	if len(hashes) != 0 {
	panic("tlog: bad index math in ProveRecord")
	}
	return p, nil
	}

	// leafProofIndex builds the list of indexes needed to construct the proof
	// that leaf n is contained in the subtree with leaves [lo, hi).
	// It appends those indexes to need and returns the result.
	// See https://tools.ietf.org/html/rfc6962#section-2.1.1
	func leafProofIndex(lo, hi, n int64, need []int64) []int64 {
	// See leafProof below for commentary.
	if !(lo <= n && n < hi) {
	panic("tlog: bad math in leafProofIndex")
	}
	if lo+1 == hi {
	return need
	}
	if k, _ := maxpow2(hi - lo); n < lo+k {
	need = leafProofIndex(lo, lo+k, n, need)
	need = subTreeIndex(lo+k, hi, need)
	} else {
	need = subTreeIndex(lo, lo+k, need)
	need = leafProofIndex(lo+k, hi, n, need)
	}
	return need
	}

	// leafProof constructs the proof that leaf n is contained in the subtree with leaves [lo, hi).
	// It returns any leftover hashes as well.
	// See https://tools.ietf.org/html/rfc6962#section-2.1.1
	func leafProof(lo, hi, n int64, hashes []Hash) (RecordProof, []Hash) {
	// We must have lo <= n < hi or else the code here has a bug.
	if !(lo <= n && n < hi) {
	panic("tlog: bad math in leafProof")
	}

	if lo+1 == hi { // n == lo
	// Reached the leaf node.
	// The verifier knows what the leaf hash is, so we don't need to send it.
	return RecordProof{}, hashes
	}

	// Walk down the tree toward n.
	// Record the hash of the path not taken (needed for verifying the proof).
	var p RecordProof
	var th Hash
	if k, _ := maxpow2(hi - lo); n < lo+k {
	// n is on left side
	p, hashes = leafProof(lo, lo+k, n, hashes)
	th, hashes = subTreeHash(lo+k, hi, hashes)
	} else {
	// n is on right side
	th, hashes = subTreeHash(lo, lo+k, hashes)
	p, hashes = leafProof(lo+k, hi, n, hashes)
	}
	return append(p, th), hashes
	}

	var errProofFailed = errors.New("invalid transparency proof")

	// CheckRecord verifies that p is a valid proof that the tree of size t
	// with hash th has an n'th record with hash h.
	func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error {
	if t < 0 \|\| n < 0 \|\| n >= t {
	return fmt.Errorf("tlog: invalid inputs in CheckRecord")
	}
	th2, err := runRecordProof(p, 0, t, n, h)
	if err != nil {
	return err
	}
	if th2 == th {
	return nil
	}
	return errProofFailed
	}

	// runRecordProof runs the proof p that leaf n is contained in the subtree with leaves [lo, hi).
	// Running the proof means constructing and returning the implied hash of that
	// subtree.
	func runRecordProof(p RecordProof, lo, hi, n int64, leafHash Hash) (Hash, error) {
	// We must have lo <= n < hi or else the code here has a bug.
	if !(lo <= n && n < hi) {
	panic("tlog: bad math in runRecordProof")
	}

	if lo+1 == hi { // m == lo
	// Reached the leaf node.
	// The proof must not have any unnecessary hashes.
	if len(p) != 0 {
	return Hash{}, errProofFailed
	}
	return leafHash, nil
	}

	if len(p) == 0 {
	return Hash{}, errProofFailed
	}

	k, _ := maxpow2(hi - lo)
	if n < lo+k {
	th, err := runRecordProof(p[:len(p)-1], lo, lo+k, n, leafHash)
	if err != nil {
	return Hash{}, err
	}
	return NodeHash(th, p[len(p)-1]), nil
	} else {
	th, err := runRecordProof(p[:len(p)-1], lo+k, hi, n, leafHash)
	if err != nil {
	return Hash{}, err
	}
	return NodeHash(p[len(p)-1], th), nil
	}
	}

	// A TreeProof is a verifiable proof that a particular log tree contains
	// as a prefix all records present in an earlier tree.
	// RFC 6962 calls this a “Merkle consistency proof.”
	type TreeProof []Hash

	// ProveTree returns the proof that the tree of size t contains
	// as a prefix all the records from the tree of smaller size n.
	func ProveTree(t, n int64, h HashReader) (TreeProof, error) {
	if t < 1 \|\| n < 1 \|\| n > t {
	return nil, fmt.Errorf("tlog: invalid inputs in ProveTree")
	}
	indexes := treeProofIndex(0, t, n, nil)
	if len(indexes) == 0 {
	return TreeProof{}, nil
	}
	hashes, err := h.ReadHashes(indexes)
	if err != nil {
	return nil, err
	}
	if len(hashes) != len(indexes) {
	return nil, fmt.Errorf("tlog: ReadHashes(%d indexes) = %d hashes", len(indexes), len(hashes))
	}

	p, hashes := treeProof(0, t, n, hashes)
	if len(hashes) != 0 {
	panic("tlog: bad index math in ProveTree")
	}
	return p, nil
	}

	// treeProofIndex builds the list of indexes needed to construct
	// the sub-proof related to the subtree containing records [lo, hi).
	// See https://tools.ietf.org/html/rfc6962#section-2.1.2.
	func treeProofIndex(lo, hi, n int64, need []int64) []int64 {
	// See treeProof below for commentary.
	if !(lo < n && n <= hi) {
	panic("tlog: bad math in treeProofIndex")
	}

	if n == hi {
	if lo == 0 {
	return need
	}
	return subTreeIndex(lo, hi, need)
	}

	if k, _ := maxpow2(hi - lo); n <= lo+k {
	need = treeProofIndex(lo, lo+k, n, need)
	need = subTreeIndex(lo+k, hi, need)
	} else {
	need = subTreeIndex(lo, lo+k, need)
	need = treeProofIndex(lo+k, hi, n, need)
	}
	return need
	}

	// treeProof constructs the sub-proof related to the subtree containing records [lo, hi).
	// It returns any leftover hashes as well.
	// See https://tools.ietf.org/html/rfc6962#section-2.1.2.
	func treeProof(lo, hi, n int64, hashes []Hash) (TreeProof, []Hash) {
	// We must have lo < n <= hi or else the code here has a bug.
	if !(lo < n && n <= hi) {
	panic("tlog: bad math in treeProof")
	}

	// Reached common ground.
	if n == hi {
	if lo == 0 {
	// This subtree corresponds exactly to the old tree.
	// The verifier knows that hash, so we don't need to send it.
	return TreeProof{}, hashes
	}
	th, hashes := subTreeHash(lo, hi, hashes)
	return TreeProof{th}, hashes
	}

	// Interior node for the proof.
	// Decide whether to walk down the left or right side.
	var p TreeProof
	var th Hash
	if k, _ := maxpow2(hi - lo); n <= lo+k {
	// m is on left side
	p, hashes = treeProof(lo, lo+k, n, hashes)
	th, hashes = subTreeHash(lo+k, hi, hashes)
	} else {
	// m is on right side
	th, hashes = subTreeHash(lo, lo+k, hashes)
	p, hashes = treeProof(lo+k, hi, n, hashes)
	}
	return append(p, th), hashes
	}

	// CheckTree verifies that p is a valid proof that the tree of size t with hash th
	// contains as a prefix the tree of size n with hash h.
	func CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error {
	if t < 1 \|\| n < 1 \|\| n > t {
	return fmt.Errorf("tlog: invalid inputs in CheckTree")
	}
	h2, th2, err := runTreeProof(p, 0, t, n, h)
	if err != nil {
	return err
	}
	if th2 == th && h2 == h {
	return nil
	}
	return errProofFailed
	}

	// runTreeProof runs the sub-proof p related to the subtree containing records [lo, hi),
	// where old is the hash of the old tree with n records.
	// Running the proof means constructing and returning the implied hashes of that
	// subtree in both the old and new tree.
	func runTreeProof(p TreeProof, lo, hi, n int64, old Hash) (Hash, Hash, error) {
	// We must have lo < n <= hi or else the code here has a bug.
	if !(lo < n && n <= hi) {
	panic("tlog: bad math in runTreeProof")
	}

	// Reached common ground.
	if n == hi {
	if lo == 0 {
	if len(p) != 0 {
	return Hash{}, Hash{}, errProofFailed
	}
	return old, old, nil
	}
	if len(p) != 1 {
	return Hash{}, Hash{}, errProofFailed
	}
	return p[0], p[0], nil
	}

	if len(p) == 0 {
	return Hash{}, Hash{}, errProofFailed
	}

	// Interior node for the proof.
	k, _ := maxpow2(hi - lo)
	if n <= lo+k {
	oh, th, err := runTreeProof(p[:len(p)-1], lo, lo+k, n, old)
	if err != nil {
	return Hash{}, Hash{}, err
	}
	return oh, NodeHash(th, p[len(p)-1]), nil
	} else {
	oh, th, err := runTreeProof(p[:len(p)-1], lo+k, hi, n, old)
	if err != nil {
	return Hash{}, Hash{}, err
	}
	return NodeHash(p[len(p)-1], oh), NodeHash(p[len(p)-1], th), nil
	}
	}