HashSize is the size of a Hash in bytes.
const HashSize = 32
func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error
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 CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error
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 FormatRecord(id int64, text []byte) (msg []byte, err error)
FormatRecord formats a record for serving to a client in a lookup response or data tile.
The encoded form is the record ID as a single number, then the text of the record, and then a terminating blank line. Record text must be valid UTF-8 and must not contain any ASCII control characters (those below U+0020) other than newline (U+000A). It must end in a terminating newline and not contain any blank lines.
func FormatTree(tree Tree) []byte
FormatTree formats a tree description for inclusion in a note.
The encoded form is three lines, each ending in a newline (U+000A):
go.sum database tree N Hash
where N is in decimal and Hash is in base64.
A future backwards-compatible encoding may add additional lines, which the parser can ignore. A future backwards-incompatible encoding would use a different first line (for example, "go.sum database tree v2").
func ParseRecord(msg []byte) (id int64, text, rest []byte, err error)
ParseRecord parses a record description at the start of text, stopping immediately after the terminating blank line. It returns the record id, the record text, and the remainder of text.
func ReadTileData(t Tile, r HashReader) ([]byte, error)
ReadTileData reads the hashes for tile t from r and returns the corresponding tile data.
func SplitStoredHashIndex(index int64) (level int, n int64)
SplitStoredHashIndex is the inverse of StoredHashIndex. That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
func StoredHashCount(n int64) int64
StoredHashCount returns the number of stored hashes that are expected for a tree with n records.
func StoredHashIndex(level int, n int64) int64
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.
A Hash is a hash identifying a log record or tree root.
type Hash [HashSize]byte
func HashFromTile(t Tile, data []byte, index int64) (Hash, error)
HashFromTile returns the hash at the given storage index, provided that t == TileForIndex(t.H, index) or a wider version, and data is t's tile data (of length at least t.W*HashSize).
func NodeHash(left, right Hash) Hash
NodeHash returns the hash for an interior tree node with the given left and right hashes.
func ParseHash(s string) (Hash, error)
ParseHash parses the base64-encoded string form of a hash.
func RecordHash(data []byte) Hash
RecordHash returns the content hash for the given record data.
func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error)
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 StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error)
StoredHashesForRecordHash is like StoredHashes but takes as its second argument RecordHash(data) instead of data itself.
func TreeHash(n int64, r HashReader) (Hash, error)
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 (h Hash) MarshalJSON() ([]byte, error)
MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.
func (h Hash) String() string
String returns a base64 representation of the hash for printing.
func (h *Hash) UnmarshalJSON(data []byte) error
UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.
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)
}
func TileHashReader(tree Tree, tr TileReader) HashReader
TileHashReader returns 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. Therefore, any hashes returned by the HashReader are already proven to be in the tree.
A HashReaderFunc is a function implementing HashReader.
type HashReaderFunc func([]int64) ([]Hash, error)
func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error)
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
func ProveRecord(t, n int64, r HashReader) (RecordProof, error)
ProveRecord returns the proof that the tree of size t contains the record with index n.
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 starting at offset N*(2**H). A complete tile lists 2**H hashes; a partial tile lists fewer. Note that a tile represents the entire subtree of height H with those hashes as the leaves. The levels above H*L can be reconstructed by hashing the leaves.
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, meaning W < 2**H. The NNN element is an encoding of N into 3-digit path elements. All but the last path element begins with an "x". For example, Tile{H: 3, L: 4, N: 1234067, W: 1}'s path is tile/3/4/x001/x234/067.p/1, and Tile{H: 3, L: 4, N: 1234067, W: 8}'s path is tile/3/4/x001/x234/067. See the Tile.Path method and the ParseTilePath function.
The special level L=-1 holds raw record data instead of hashes. In this case, the level encodes into a tile path as the path element "data" instead of "-1".
See also https://golang.org/design/25530-sumdb#checksum-database and https://research.swtch.com/tlog#tiling_a_log.
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)
}
func NewTiles(h int, oldTreeSize, newTreeSize int64) []Tile
NewTiles returns 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. (No tiles need to be published for a tree of size zero.)
If h ≤ 0, NewTiles panics.
func ParseTilePath(path string) (Tile, error)
ParseTilePath parses a tile coordinate path.
func TileForIndex(h int, index int64) Tile
TileForIndex returns the tile of fixed height h ≥ 1 and least width storing the given hash storage index.
If h ≤ 0, TileForIndex panics.
func (t Tile) Path() string
Path returns a tile coordinate path describing t.
A TileReader reads tiles from a go.sum database log.
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).
//
// An implementation of ReadTiles typically reads
// them from an on-disk cache or else from a remote
// tile server. Tile data downloaded from a server should
// be considered suspect and not saved into a persistent
// on-disk cache before returning from ReadTiles.
// When the client confirms the validity of the tile data,
// it will call SaveTiles to signal that they can be safely
// written to persistent storage.
// See also https://research.swtch.com/tlog#authenticating_tiles.
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 Tree is a tree description, to be signed by a go.sum database server.
type Tree struct {
N int64
Hash Hash
}
func ParseTree(text []byte) (tree Tree, err error)
ParseTree parses a formatted tree root description.
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
func ProveTree(t, n int64, h HashReader) (TreeProof, error)
ProveTree returns the proof that the tree of size t contains as a prefix all the records from the tree of smaller size n.