Documentation
¶
Overview ¶
Package tiles implements https://c2sp.org/tlog-tiles.
Entry tiles contain up to 256 MTCLogEntry objects and are stored as compressed entry bundles.
Hash tiles contain up to 256 32-byte SHA-256 hashes, concatenated. The tile represents up to 8 layers of the Merkle Tree, but only the bottom-most of those layers is actually stored. Higher layers are calculated from the tile contents as needed.
Invariants:
- Tiles in storage are never empty.
- Tiles in storage are immutable.
- A hash is only appended to a tile when it will be permanent. Equivalently: only the hashes of complete subtrees are appended to a tile.
- Any hash stored in a level L tile is equal to MTH(c), where c is a list of exactly 256 hashes stored in a child tile at level L-1 (for L > 0).
Index ¶
Constants ¶
This section is empty.
Variables ¶
var ErrTileExists = errors.New("tile exists")
ErrTileExists is returned when trying to write a tile that already exists in storage.
Functions ¶
This section is empty.
Types ¶
type Frontier ¶
type Frontier struct {
// contains filtered or unexported fields
}
Frontier contains all the tiles on the right edge of the tree, which may be partial or empty (but not full). It keeps track of which tiles have been modified and need to be written to storage.
When a tile becomes full, it gets moved into a holding list of tiles that are not on the right edge but need to be written and its MTH gets appended to the tile above it.
The zero value of Frontier represents an empty tree. Empty trees cannot be loaded or flushed.
Frontier is not safe for concurrent access.
func LoadFrontier ¶
func LoadFrontier(ctx context.Context, s3c simpleS3, treeSize int64, prefix string) (*Frontier, error)
LoadFrontier loads the current frontier from storage, given the current tree size.
Succeeds only if all the frontier tiles for that tree size exist in storage.
func (*Frontier) AppendEntry ¶
func (f *Frontier) AppendEntry(mtcle *entry.MTCLogEntry) error
AppendEntry appends a single MTCLogEntry to the entries tile and a corresponding hash to the level-0 hashes tile, updating any higher levels as needed.
On error, the Frontier is unchanged.
func (*Frontier) Flush ¶
Flush writes all dirty tiles to storage and clears their dirty status.
If it errors partway, dirty status is not reset but subsequent flushes will likely fail (duplicate writes).
Errors if the tree is empty.
Source Files