Documentation

Overview

    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.

    Index

    Constants

    View Source
    const HashSize = 32

      HashSize is the size of a Hash in bytes.

      Variables

      This section is empty.

      Functions

      func CheckRecord

      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

        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

          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

            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

              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

                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

                  func SplitStoredHashIndex(index int64) (level int, n int64)

                    SplitStoredHashIndex is the inverse of StoredHashIndex. That is, SplitStoredHashIndex(StoredHashIndex(level, n)) == level, n.

                    func StoredHashCount

                    func StoredHashCount(n int64) int64

                      StoredHashCount returns the number of stored hashes that are expected for a tree with n records.

                      func StoredHashIndex

                      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.

                        Types

                        type Hash

                        type Hash [HashSize]byte

                          A Hash is a hash identifying a log record or tree root.

                          func HashFromTile

                          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

                            func NodeHash(left, right Hash) Hash

                              NodeHash returns the hash for an interior tree node with the given left and right hashes.

                              func ParseHash

                              func ParseHash(s string) (Hash, error)

                                ParseHash parses the base64-encoded string form of a hash.

                                func RecordHash

                                func RecordHash(data []byte) Hash

                                  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

                                        func (h Hash) MarshalJSON() ([]byte, error)

                                          MarshalJSON marshals the hash as a JSON string containing the base64-encoded hash.

                                          func (Hash) String

                                          func (h Hash) String() string

                                            String returns a base64 representation of the hash for printing.

                                            func (*Hash) UnmarshalJSON

                                            func (h *Hash) UnmarshalJSON(data []byte) error

                                              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

                                                  type HashReaderFunc func([]int64) ([]Hash, error)

                                                    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".

                                                          See also https://golang.org/design/25530-sumdb#checksum-database and https://research.swtch.com/tlog#tiling_a_log.

                                                          func NewTiles

                                                          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, TileForIndex panics.

                                                            func ParseTilePath

                                                            func ParseTilePath(path string) (Tile, error)

                                                              ParseTilePath parses a tile coordinate path.

                                                              func TileForIndex

                                                              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 (Tile) Path

                                                                func (t Tile) Path() string

                                                                  Path returns a tile coordinate path describing t.

                                                                  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).
                                                                  	//
                                                                  	// 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 TileReader reads tiles from a go.sum database log.

                                                                    type Tree

                                                                    type Tree struct {
                                                                    	N    int64
                                                                    	Hash Hash
                                                                    }

                                                                      A Tree is a tree description, to be signed by a go.sum database server.

                                                                      func ParseTree

                                                                      func ParseTree(text []byte) (tree Tree, err error)

                                                                        ParseTree parses a formatted tree root description.

                                                                        type TreeProof

                                                                        type TreeProof []Hash

                                                                          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.”

                                                                          func ProveTree

                                                                          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.