layout

Documentation

Overview

Package layout contains routines for specifying the path layout of Tessera logs, which is really to say that it provides functions to calculate paths used by the tlog-tiles API.

Index

• Constants
• func EntriesPath(n uint64, p uint8) string
• func EntriesPathForLogIndex(seq, logSize uint64) string
• func NWithSuffix(l, n uint64, p uint8) string
• func NodeCoordsToTileAddress(treeLevel, treeIndex uint64) (uint64, uint64, uint, uint64)
• func ParseTileIndexPartial(index string) (uint64, uint8, error)
• func ParseTileLevel(level string) (uint64, error)
• func ParseTileLevelIndexPartial(level, index string) (uint64, uint64, uint8, error)
• func PartialTileSize(level, index, logSize uint64) uint8
• func Range(from, N, treeSize uint64) iter.Seq[RangeInfo]
• func TilePath(tileLevel, tileIndex uint64, p uint8) string
• type RangeInfo

Examples

• EntriesPath
• NodeCoordsToTileAddress
• ParseTileLevelIndexPartial
• TilePath

Constants

const (
	// TileHeight is the maximum number of levels Merkle tree levels a tile represents.
	// This is fixed at 8 by tlog-tile spec.
	TileHeight = 8
	// TileWidth is the maximum number of hashes which can be present in the bottom row of a tile.
	TileWidth = 1 << TileHeight
	// EntryBundleWidth is the maximum number of entries which can be present in an EntryBundle.
	// This is defined to be the same as the width of the node tiles by tlog-tile spec.
	EntryBundleWidth = TileWidth
)

const (
	// CheckpointPath is the location of the file containing the log checkpoint.
	CheckpointPath = "checkpoint"
)

Functions

func EntriesPath

func EntriesPath(n uint64, p uint8) string

EntriesPath returns the local path for the nth entry bundle. p denotes the partial tile size, or 0 if the tile is complete.

Example

package main

import (
	"fmt"

	"github.com/transparency-dev/tessera/api/layout"
)

func main() {
	entriesPath := layout.EntriesPath(1234067, 8)
	fmt.Printf("entries path: %s", entriesPath)
}

Output:

entries path: tile/entries/x001/x234/067.p/8

func EntriesPathForLogIndex

func EntriesPathForLogIndex(seq, logSize uint64) string

EntriesPathForLogIndex builds the local path at which the leaf with the given index lives in. Note that this will be an entry bundle containing up to 256 entries and thus multiple indices can map to the same output path. The logSize is required so that a partial qualifier can be appended to tiles that would contain fewer than 256 entries.

func NWithSuffix

func NWithSuffix(l, n uint64, p uint8) string

NWithSuffix returns a tiles-spec "N" path, with a partial suffix if p > 0.

func NodeCoordsToTileAddress

func NodeCoordsToTileAddress(treeLevel, treeIndex uint64) (uint64, uint64, uint, uint64)

NodeCoordsToTileAddress returns the (TileLevel, TileIndex) in tile-space, and the (NodeLevel, NodeIndex) address within that tile of the specified tree node co-ordinates.

Example

package main

import (
	"fmt"

	"github.com/transparency-dev/tessera/api/layout"
)

func main() {
	var treeLevel, treeIndex uint64 = 8, 123456789
	tileLevel, tileIndex, nodeLevel, nodeIndex := layout.NodeCoordsToTileAddress(treeLevel, treeIndex)
	fmt.Printf("tile level: %d, tile index: %d, node level: %d, node index: %d", tileLevel, tileIndex, nodeLevel, nodeIndex)
}

Output:

tile level: 1, tile index: 482253, node level: 0, node index: 21

func ParseTileIndexPartial

func ParseTileIndexPartial(index string) (uint64, uint8, error)

ParseTileIndexPartial takes index in string, validates and returns the index and width in uint64.

func ParseTileLevel

func ParseTileLevel(level string) (uint64, error)

ParseTileLevel takes level in string, validates and returns the level in uint64.

func ParseTileLevelIndexPartial

func ParseTileLevelIndexPartial(level, index string) (uint64, uint64, uint8, error)

ParseTileLevelIndexPartial takes level and index in string, validates and returns the level, index and width in uint64.

Examples: "/tile/0/x001/x234/067" means level 0 and index 1234067 of a full tile. "/tile/0/x001/x234/067.p/8" means level 0, index 1234067 and width 8 of a partial tile.

Example

package main

import (
	"fmt"

	"github.com/transparency-dev/tessera/api/layout"
)

func main() {
	level, index, width, _ := layout.ParseTileLevelIndexPartial("0", "x001/x234/067.p/8")
	fmt.Printf("level: %d, index: %d, width: %d", level, index, width)
}

Output:

level: 0, index: 1234067, width: 8

func PartialTileSize

func PartialTileSize(level, index, logSize uint64) uint8

PartialTileSize returns the expected number of leaves in a tile at the given tile level and index within a tree of the specified logSize, or 0 if the tile is expected to be fully populated.

func Range

func Range(from, N, treeSize uint64) iter.Seq[RangeInfo]

Range returns an iterator over a list of RangeInfo structs which describe the bundles/tiles necessary to cover the specified range of individual entries/hashes `[from, min(from+N, treeSize) )`.

If from >= treeSize or N == 0, the returned iterator will yield no elements.

func TilePath

func TilePath(tileLevel, tileIndex uint64, p uint8) string

TilePath builds the path to the subtree tile with the given level and index in tile space. If p > 0 the path represents a partial tile.

Example

package main

import (
	"fmt"

	"github.com/transparency-dev/tessera/api/layout"
)

func main() {
	tilePath := layout.TilePath(0, 1234067, 8)
	fmt.Printf("tile path: %s", tilePath)
}

Output:

tile path: tile/0/x001/x234/067.p/8

Types

type RangeInfo

type RangeInfo struct {
	// Index is the index of the entry bundle/tile in the tree.
	Index uint64
	// Partial is the partial size of the bundle/tile, or zero if a full bundle/tile is expected.
	Partial uint8
	// First is the offset into the entries contained by the bundle/tile at which the range starts.
	First uint
	// N is the number of entries, starting at First, which are covered by the range.
	N uint
}

RangeInfo describes a specific range of elements within a particular bundle/tile.

Usage:

bundleRaw, ... := fetchBundle(..., ri.Index, ri.Partial")
bundle, ... := parseBundle(bundleRaw)
elements := bundle.Entries[ri.First : ri.First+ri.N]