tlog

Imports

Imports #

"bytes"
"encoding/base64"
"errors"
"fmt"
"strconv"
"strings"
"unicode/utf8"
"fmt"
"strconv"
"strings"
"crypto/sha256"
"encoding/base64"
"errors"
"fmt"
"math/bits"

Constants & Variables

HashSize const #

HashSize is the size of a Hash in bytes.

const HashSize = 32

emptyHash var #

emptyHash is the hash of the empty tree, per RFC 6962, Section 2.1. It is the hash of the empty string.

var emptyHash = Hash{...}

errMalformedRecord var #

var errMalformedRecord = *ast.CallExpr

errMalformedTree var #

var errMalformedTree = *ast.CallExpr

errProofFailed var #

var errProofFailed = *ast.CallExpr

pathBase const #

To limit the size of any particular directory listing, we encode the (possibly very large) number N by encoding three digits at a time. For example, 123456789 encodes as x123/x456/789. Each directory has at most 1000 each xNNN, NNN, and NNN.p children, so there are at most 3000 entries in any one directory.

const pathBase = 1000

treePrefix var #

var treePrefix = *ast.CallExpr

zeroPrefix var #

var zeroPrefix = []byte{...}

Type Aliases

Hash type #

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

type Hash [HashSize]byte

HashReaderFunc type #

A HashReaderFunc is a function implementing [HashReader].

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

RecordProof type #

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

TreeProof type #

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

Interfaces

HashReader interface #

A HashReader can read hashes for nodes in the log's tree structure.

type HashReader interface {
ReadHashes(indexes []int64) ([]Hash, error)
}

TileReader interface #

A TileReader reads tiles from a go.sum database log.

type TileReader interface {
Height() int
ReadTiles(tiles []Tile) (data [][]byte, err error)
SaveTiles(tiles []Tile, data [][]byte)
}

Structs

Tile struct #

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
L int
N int64
W int
}

Tree struct #

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

type Tree struct {
N int64
Hash Hash
}

badPathError struct #

type badPathError struct {
path string
}

tileHashReader struct #

type tileHashReader struct {
tree Tree
tr TileReader
}

Functions

CheckRecord function #

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 CheckRecord(p RecordProof, t int64, th Hash, n int64, h Hash) error

CheckTree function #

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 CheckTree(p TreeProof, t int64, th Hash, n int64, h Hash) error

Error method #

func (e *badPathError) Error() string

FormatRecord function #

FormatRecord formats a record for serving to a client in a lookup response. 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. Responses to data tiles consist of concatenated formatted records from each of which the first line, with the record ID, is removed.

func FormatRecord(id int64, text []byte) (msg []byte, err error)

FormatTree function #

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 FormatTree(tree Tree) []byte

HashFromTile function #

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 HashFromTile(t Tile, data []byte, index int64) (Hash, error)

MarshalJSON method #

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

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

NewTiles function #

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 NewTiles(h int, oldTreeSize int64, newTreeSize int64) []Tile

NodeHash function #

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

func NodeHash(left Hash, right Hash) Hash

ParseHash function #

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

func ParseHash(s string) (Hash, error)

ParseRecord function #

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 ParseRecord(msg []byte) (id int64, text []byte, rest []byte, err error)

ParseTilePath function #

ParseTilePath parses a tile coordinate path.

func ParseTilePath(path string) (Tile, error)

ParseTree function #

ParseTree parses a formatted tree root description.

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

Path method #

Path returns a tile coordinate path describing t.

func (t Tile) Path() string

ProveRecord function #

ProveRecord returns the proof that the tree of size t contains the record with index n.

func ProveRecord(t int64, n int64, r HashReader) (RecordProof, error)

ProveTree function #

ProveTree returns the proof that the tree of size t contains as a prefix all the records from the tree of smaller size n.

func ProveTree(t int64, n int64, h HashReader) (TreeProof, error)

ReadHashes method #

func (f HashReaderFunc) ReadHashes(indexes []int64) ([]Hash, error)

ReadHashes method #

func (r *tileHashReader) ReadHashes(indexes []int64) ([]Hash, error)

ReadTileData function #

ReadTileData reads the hashes for tile t from r and returns the corresponding tile data.

func ReadTileData(t Tile, r HashReader) ([]byte, error)

RecordHash function #

RecordHash returns the content hash for the given record data.

func RecordHash(data []byte) Hash

SplitStoredHashIndex function #

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

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

StoredHashCount function #

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

func StoredHashCount(n int64) int64

StoredHashIndex function #

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.

func StoredHashIndex(level int, n int64) int64

StoredHashes function #

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 StoredHashes(n int64, data []byte, r HashReader) ([]Hash, error)

StoredHashesForRecordHash function #

StoredHashesForRecordHash is like [StoredHashes] but takes as its second argument RecordHash(data) instead of data itself.

func StoredHashesForRecordHash(n int64, h Hash, r HashReader) ([]Hash, error)

String method #

String returns a base64 representation of the hash for printing.

func (h Hash) String() string

TileForIndex function #

TileForIndex returns the tile of fixed height h ≥ 1 and least width storing the given hash storage index. If h ≤ 0, [TileForIndex] panics.

func TileForIndex(h int, index int64) Tile

TileHashReader function #

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.

func TileHashReader(tree Tree, tr TileReader) HashReader

TreeHash function #

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 TreeHash(n int64, r HashReader) (Hash, error)

UnmarshalJSON method #

UnmarshalJSON unmarshals a hash from JSON string containing the a base64-encoded hash.

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

isValidRecordText function #

isValidRecordText reports whether text is syntactically valid record text.

func isValidRecordText(text []byte) bool

leafProof function #

leafProof constructs the proof that leaf n is contained in the subtree with leaves [lo, hi). It returns any leftover hashes as well. See https://tools.ietf.org/html/rfc6962#section-2.1.1

func leafProof(lo int64, hi int64, n int64, hashes []Hash) (RecordProof, []Hash)

leafProofIndex function #

leafProofIndex builds the list of indexes needed to construct the proof that leaf n is contained in the subtree with leaves [lo, hi). It appends those indexes to need and returns the result. See https://tools.ietf.org/html/rfc6962#section-2.1.1

func leafProofIndex(lo int64, hi int64, n int64, need []int64) []int64

maxpow2 function #

maxpow2 returns k, the maximum power of 2 smaller than n, as well as l = log₂ k (so k = 1<

func maxpow2(n int64) (k int64, l int)

runRecordProof function #

runRecordProof runs the proof p that leaf n is contained in the subtree with leaves [lo, hi). Running the proof means constructing and returning the implied hash of that subtree.

func runRecordProof(p RecordProof, lo int64, hi int64, n int64, leafHash Hash) (Hash, error)

runTreeProof function #

runTreeProof runs the sub-proof p related to the subtree containing records [lo, hi), where old is the hash of the old tree with n records. Running the proof means constructing and returning the implied hashes of that subtree in both the old and new tree.

func runTreeProof(p TreeProof, lo int64, hi int64, n int64, old Hash) (Hash, Hash, error)

subTreeHash function #

subTreeHash computes the hash for the subtree containing records [lo, hi), assuming that hashes are the hashes corresponding to the indexes returned by subTreeIndex(lo, hi). It returns any leftover hashes.

func subTreeHash(lo int64, hi int64, hashes []Hash) (Hash, []Hash)

subTreeIndex function #

subTreeIndex returns the storage indexes needed to compute the hash for the subtree containing records [lo, hi), appending them to need and returning the result. See https://tools.ietf.org/html/rfc6962#section-2.1

func subTreeIndex(lo int64, hi int64, need []int64) []int64

tileForIndex function #

tileForIndex returns the tile of height h ≥ 1 storing the given hash index, which can be reconstructed using tileHash(data[start:end]).

func tileForIndex(h int, index int64) (t Tile, start int, end int)

tileHash function #

tileHash computes the subtree hash corresponding to the (2^K)-1 hashes in data.

func tileHash(data []byte) Hash

tileParent function #

tileParent returns t's k'th tile parent in the tiles for a tree of size n. If there is no such parent, tileParent returns Tile{}.

func tileParent(t Tile, k int, n int64) Tile

treeProof function #

treeProof constructs the sub-proof related to the subtree containing records [lo, hi). It returns any leftover hashes as well. See https://tools.ietf.org/html/rfc6962#section-2.1.2.

func treeProof(lo int64, hi int64, n int64, hashes []Hash) (TreeProof, []Hash)

treeProofIndex function #

treeProofIndex builds the list of indexes needed to construct the sub-proof related to the subtree containing records [lo, hi). See https://tools.ietf.org/html/rfc6962#section-2.1.2.

func treeProofIndex(lo int64, hi int64, n int64, need []int64) []int64

Generated with Arrow