tlog

package
v0.0.2 Latest Latest
Warning

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

Go to latest
Published: Apr 29, 2019 License: BSD-3-Clause Imports: 9 Imported by: 0

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

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

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

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 height h ≥ 1 and least width storing the given hash storage index.

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL