Documentation
¶
Overview ¶
Package tlog implements a tamper-evident log used in the Go module go.sum database server.
This package is part of a DRAFT of what the go.sum database server will look like. Do not assume the details here are final!
This package follows the design of Certificate Transparency (RFC 6962) and its proofs are compatible with that system. See TestCertificateTransparency.
Index ¶
- Constants
- func CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error
- func CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error
- func FormatRecord(id int64, text []byte) (msg []byte, err error)
- func FormatTree(tree Tree) []byte
- func ParseRecord(msg []byte) (id int64, text, rest []byte, err error)
- func ReadTileData(t Tile, r HashReader) ([]byte, error)
- func SplitStoredHashIndex(index int64) (level int, n int64)
- func StoredHashCount(n int64) int64
- func StoredHashIndex(level int, n int64) int64
- type Hash
- func HashFromTile(t Tile, data []byte, index int64) (Hash, error)
- func NodeHash(left, right Hash) Hash
- func ParseHash(s string) (Hash, error)
- func RecordHash(data []byte) Hash
- func StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error)
- func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error)
- func TreeHash(n int64, r HashReader) (Hash, error)
- type HashReader
- type HashReaderFunc
- type RecordProof
- type Tile
- type TileReader
- type Tree
- type TreeProof
Constants ¶
const HashSize = 32
HashSize is the size of a Hash in bytes.
Variables ¶
This section is empty.
Functions ¶
func CheckRecord ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
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 ¶
SplitStoredHashIndex is the inverse of StoredHashIndex. That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.
func StoredHashCount ¶
StoredHashCount returns the number of stored hashes that are expected for a tree with n records.
func StoredHashIndex ¶
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.
Types ¶
type Hash ¶
A Hash is a hash identifying a log record or tree root.
func HashFromTile ¶
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 ¶
NodeHash returns the hash for an interior tree node with the given left and right hashes.
func RecordHash ¶
RecordHash returns the content hash for the given record data.
func StoredHashes ¶
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 ¶
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 ¶
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. The tree of size zero is defined to have an all-zero Hash.
func (Hash) MarshalJSON ¶
MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.
func (*Hash) UnmarshalJSON ¶
UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.
type HashReader ¶
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 ¶
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.
type HashReaderFunc ¶
A HashReaderFunc is a function implementing HashReader.
func (HashReaderFunc) ReadHashes ¶
func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error)
type RecordProof ¶
type RecordProof []Hash
A RecordProof is a verifiable proof that a particular log root contains a particular record. RFC 6962 calls this a “Merkle audit path.”
func ProveRecord ¶
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.
type Tile ¶
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 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 Tile's 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".
func NewTiles ¶
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.)
func ParseTilePath ¶
ParseTilePath parses a tile coordinate path.
func TileForIndex ¶
TileForIndex returns the tile of height h ≥ 1 and least width storing the given hash storage index.
type TileReader ¶
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.
Source Files