Package tlog implements a tamper-evident log used in the Go module go.sum database server.
import "golang.org/x/mod/sumdb/tlog"The tlog package implements a transparent, append-only log structure compatible with Certificate Transparency (RFC 6962). It provides cryptographic proofs that:
The log uses a Merkle tree structure where each node's hash is computed from its children, providing tamper-evident properties.
const HashSize = 32HashSize is the size of a Hash in bytes (SHA-256).
type Hash [HashSize]byteA Hash is a hash identifying a log record or tree root.
func RecordHash(data []byte) HashReturns the content hash for the given record data.
func NodeHash(left, right Hash) HashReturns the hash for an interior tree node with the given left and right hashes.
func ParseHash(s string) (Hash, error)Parses the base64-encoded string form of a hash.
func TreeHash(n int64, r HashReader) (Hash, error)Computes the hash for the root of the tree with n records, using the HashReader to obtain previously stored hashes. Makes a single call to ReadHashes requesting at most 1 + log₂ n hashes.
func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error)Returns the hashes that must be stored when writing record n with the given data. The result will have at most 1 + log₂ n hashes.
func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error)Like StoredHashes but takes as its second argument RecordHash(data) instead of data itself.
func HashFromTile(t Tile, data []byte, index int64) (Hash, error)Returns the hash at the given storage index from tile data.
func (h Hash) String() stringReturns a base64 representation of the hash for printing.
func (h Hash) MarshalJSON() ([]byte, error)
func (h *Hash) UnmarshalJSON(data []byte) errorMarshals/unmarshals the hash as JSON string containing base64-encoded hash.
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 HashReader can read hashes for nodes in the log's tree structure.
func TileHashReader(tree Tree, tr TileReader) HashReaderReturns a HashReader that satisfies requests by loading tiles of the given tree. The returned HashReader checks that loaded tiles are valid for the given tree.
type HashReaderFunc func([]int64) ([]Hash, error)A HashReaderFunc is a function implementing HashReader.
func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error)type Tree struct {
N int64
Hash Hash
}A Tree is a tree description, to be signed by a go.sum database server.
type Tile struct {
H int // height of tile (1 ≤ H ≤ 30)
L int // level in tiling (-1 ≤ L ≤ 63)
N int64 // number within level (0 ≤ N, unbounded)
W int // width of tile (1 ≤ W ≤ 2**H; 2**H is complete tile)
}A Tile is a description of a transparency log tile. A tile of height H at level L offset N lists W consecutive hashes at level H*L of the tree.
Each Tile can be encoded as a "tile coordinate path" of the form tile/H/L/NNN[.p/W]. The .p/W suffix is present only for partial tiles. The NNN element is an encoding of N into 3-digit path elements with "x" prefix except for the last element.
Examples:
tile/3/4/x001/x234/067.p/1 - Tile{H: 3, L: 4, N: 1234067, W: 1}tile/3/4/x001/x234/067 - Tile{H: 3, L: 4, N: 1234067, W: 8} (complete)The special level L=-1 holds raw record data and encodes as "data" instead of "-1".
func TileForIndex(h int, index int64) TileReturns the tile of fixed height h ≥ 1 and least width storing the given hash storage index.
func NewTiles(h int, oldTreeSize, newTreeSize int64) []TileReturns the coordinates of the tiles of height h ≥ 1 that must be published when publishing from a tree of size newTreeSize to replace a tree of size oldTreeSize.
func ParseTilePath(path string) (Tile, error)Parses a tile coordinate path.
func (t Tile) Path() stringReturns a tile coordinate path describing t.
type TileReader interface {
// Height returns the height of the available tiles.
Height() int
// ReadTiles returns the data for each requested tile.
// If ReadTiles returns err == nil, it must also return
// a data record for each tile (len(data) == len(tiles))
// and each data record must be the correct length
// (len(data[i]) == tiles[i].W*HashSize).
ReadTiles(tiles []Tile) (data [][]byte, err error)
// SaveTiles informs the TileReader that the tile data
// returned by ReadTiles has been confirmed as valid
// and can be saved in persistent storage (on disk).
SaveTiles(tiles []Tile, data [][]byte)
}A TileReader reads tiles from a go.sum database log.
type RecordProof []HashA RecordProof is a verifiable proof that a particular log root contains a particular record. RFC 6962 calls this a "Merkle audit path."
func ProveRecord(t, n int64, r HashReader) (RecordProof, error)Returns the proof that the tree of size t contains the record with index n.
func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) errorVerifies that p is a valid proof that the tree of size t with hash th has an n'th record with hash h.
type TreeProof []HashA 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."
func ProveTree(t, n int64, h HashReader) (TreeProof, error)Returns the proof that the tree of size t contains as a prefix all the records from the tree of smaller size n.
func CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) errorVerifies 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 StoredHashIndex(level int, n int64) int64Maps the tree coordinates (level, n) to a dense linear ordering for hash storage.
func SplitStoredHashIndex(index int64) (level int, n int64)Inverse of StoredHashIndex. That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
func StoredHashCount(n int64) int64Returns the number of stored hashes expected for a tree with n records.
func FormatRecord(id int64, text []byte) (msg []byte, err error)Formats a record for serving to a client in a lookup response. The encoded form is the record ID as a single number, then the text of the record, and then a terminating blank line.
func ParseRecord(msg []byte) (id int64, text, rest []byte, err error)Parses a record description at the start of text.
func FormatTree(tree Tree) []byteFormats a tree description for inclusion in a note. The encoded form is three lines:
go.sum database tree
N
Hashfunc ParseTree(text []byte) (tree Tree, err error)Parses a formatted tree root description.
func ReadTileData(t Tile, r HashReader) ([]byte, error)Reads the hashes for tile t from r and returns the corresponding tile data.
package main
import (
"fmt"
"log"
"golang.org/x/mod/sumdb/tlog"
)
func main() {
// Create a simple hash reader
hashes := make(map[int64]tlog.Hash)
// Add some record hashes
for i := int64(0); i < 10; i++ {
data := []byte(fmt.Sprintf("record %d", i))
recordHash := tlog.RecordHash(data)
// Store hashes for this record
stored, _ := tlog.StoredHashes(i, data, tlog.HashReaderFunc(func(indexes []int64) ([]tlog.Hash, error) {
result := make([]tlog.Hash, len(indexes))
for i, idx := range indexes {
result[i] = hashes[idx]
}
return result, nil
}))
for j, h := range stored {
idx := tlog.StoredHashIndex(0, i) + int64(j)
hashes[idx] = h
}
}
// Compute tree hash
reader := tlog.HashReaderFunc(func(indexes []int64) ([]tlog.Hash, error) {
result := make([]tlog.Hash, len(indexes))
for i, idx := range indexes {
result[i] = hashes[idx]
}
return result, nil
})
treeHash, err := tlog.TreeHash(10, reader)
if err != nil {
log.Fatal(err)
}
fmt.Printf("Tree hash (10 records): %s\n", treeHash)
}package main
import (
"fmt"
"log"
"golang.org/x/mod/sumdb/tlog"
)
func main() {
// Assume we have a hash reader with stored hashes
reader := getHashReader() // Implementation not shown
// Generate proof that record 5 is in tree of size 10
proof, err := tlog.ProveRecord(10, 5, reader)
if err != nil {
log.Fatal(err)
}
// Get tree hash
treeHash, _ := tlog.TreeHash(10, reader)
// Get record hash
recordData := []byte("record 5")
recordHash := tlog.RecordHash(recordData)
// Verify proof
err = tlog.CheckRecord(proof, 10, treeHash, 5, recordHash)
if err != nil {
log.Fatal("Proof verification failed:", err)
}
fmt.Println("Record proof verified successfully")
}package main
import (
"fmt"
"golang.org/x/mod/sumdb/tlog"
)
func main() {
// Create a tile
tile := tlog.Tile{
H: 8, // height
L: 0, // level
N: 0, // number
W: 256, // width (complete tile)
}
// Get tile path
path := tile.Path()
fmt.Printf("Tile path: %s\n", path)
// Parse tile path back
parsed, err := tlog.ParseTilePath(path)
if err != nil {
panic(err)
}
fmt.Printf("Parsed: H=%d L=%d N=%d W=%d\n", parsed.H, parsed.L, parsed.N, parsed.W)
// Get tiles needed for tree growth
tiles := tlog.NewTiles(8, 0, 1000)
fmt.Printf("Tiles needed: %d\n", len(tiles))
for _, t := range tiles {
fmt.Printf(" %s\n", t.Path())
}
}package main
import (
"fmt"
"log"
"golang.org/x/mod/sumdb/tlog"
)
func main() {
// Create a tree
tree := tlog.Tree{
N: 1000,
Hash: tlog.RecordHash([]byte("root")),
}
// Format for signing
formatted := tlog.FormatTree(tree)
fmt.Printf("Formatted tree:\n%s\n", string(formatted))
// Parse back
parsed, err := tlog.ParseTree(formatted)
if err != nil {
log.Fatal(err)
}
fmt.Printf("Parsed: N=%d, Hash=%s\n", parsed.N, parsed.Hash)
}package main
import (
"fmt"
"log"
"golang.org/x/mod/sumdb/tlog"
)
func main() {
reader := getHashReader() // Implementation not shown
// Prove that tree of size 5 is prefix of tree of size 10
proof, err := tlog.ProveTree(10, 5, reader)
if err != nil {
log.Fatal(err)
}
// Get both tree hashes
hash5, _ := tlog.TreeHash(5, reader)
hash10, _ := tlog.TreeHash(10, reader)
// Verify proof
err = tlog.CheckTree(proof, 10, hash10, 5, hash5)
if err != nil {
log.Fatal("Tree proof verification failed:", err)
}
fmt.Println("Tree consistency verified")
}Tiles organize hashes in a hierarchical structure:
Complete tiles have W = 2^H. Partial tiles have W < 2^H and include .p/W in their path.
Once a record is added, it cannot be removed or modified. The log can only grow.
Any modification to past records changes the tree hash, which is signed and can be detected.
Clients can verify:
Use StoredHashIndex for efficient linear storage:
for i := int64(0); i < n; i++ {
hashes := tlog.StoredHashes(i, data[i], reader)
for j, h := range hashes {
idx := tlog.StoredHashIndex(0, i) + int64(j)
storage[idx] = h
}
}Read multiple hashes at once:
indexes := []int64{0, 1, 2, 3, 4}
hashes, err := reader.ReadHashes(indexes)The tree provides:
Always verify proofs:
if err := tlog.CheckRecord(proof, treeSize, treeHash, recordIndex, recordHash); err != nil {
// Do not trust the record
return err
}