tlog

package
v0.18.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 14, 2024 License: BSD-3-Clause Imports: 9 Imported by: 15

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

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, NewTiles 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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.