ledger

package
v0.0.0-...-bf905d0 Latest Latest
Warning

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

 Go to latest Published: Aug 27, 2026 License: AGPL-3.0 Imports: 10 Imported by: 0

Documentation

Overview

Package ledger is an authenticated key-value store: a versioned sparse Merkle tree (16-ary storage, binary hashing) over a pluggable KV backend.

One 32-byte root attests the entire logical data state. The root is encryption-independent: it commits to keyed plaintext hashes (HMAC-SHA-256 under a commitment key ck), never to the bytes at rest. At-rest confidentiality is the volume's job by default (a LUKS data partition inside a confidential VM, typically); an optional per-machine storage key (WithStorageKey) adds AES-256-GCM value encryption as a second layer. Replicas sharing ck compare state as (version, root) whatever each one does at rest.

This package is the Go port of the enclave-os-mini `enclave-os-merkle` crate. The commitment scheme, node hashing, record encodings and proof format are byte-identical: a Go store and a Rust store sharing ck produce the same root for the same logical data, and proofs verify across implementations.

Reads fail closed: any record that does not verify against the in-memory root (node hashes, GCM tags, value commitments) is an error, never data.

Index

Constants

View Source 
const HashSize = 32

HashSize is the size of every hash in the tree.

View Source 
const KeySize = 32

KeySize is the size of both the commitment key and the storage key.

Variables

View Source 
var HistoryKey = []byte("\x00immutable-ledger:history-head")

HistoryKey is the reserved logical key of the history-chain head leaf. It lives in the reserved system namespace: user batches cannot write it; reads return the current head.

Functions

This section is empty.

Types

type Backend 

type Backend interface {
	// Get returns the record at key, or (nil, false, nil) when absent.
	Get(key []byte) (value []byte, ok bool, err error)
	// WriteBatch applies all ops atomically: either every op lands or
	// none does. Atomicity is what makes commits crash-safe.
	WriteBatch(ops []BatchOp) error
	// Scan returns records in [start, end) in ascending key order, at
	// most limit entries (0 = unlimited). An empty end is unbounded.
	Scan(start, end []byte, limit uint32) ([]KV, error)
}

Backend is the storage surface the tree requires.

type BatchOp 

type BatchOp struct {
	Key    []byte
	Value  []byte
	Delete bool
}

BatchOp is one operation of an atomic write batch. A nil Value with Delete=false stores an empty record; set Delete for removals.

type Change 

type Change struct {
	Path    Hash
	Value   []byte
	Deleted bool
}

Change is one leaf-level difference between a version and its predecessor. Path is the tree position (the keyed hash of the logical key — logical keys are not recoverable); Value is the plaintext for puts and nil for deletes.

type Error 

type Error struct {
	Kind Kind
	Msg  string
	// Err carries the underlying backend error for KindBackend.
	Err error
}

Error is the ledger error type. Use errors.As / Error.Kind to classify.

func (*Error) Error 

func (e *Error) Error() string

func (*Error) Unwrap 

func (e *Error) Unwrap() error

type Fork 

type Fork struct {
	// contains filtered or unexported fields
}

Fork is a pending, uncommitted transaction over a Store.

func NewFork 

func NewFork(store *Store) *Fork

NewFork forks the store at its current (root, version).

func (*Fork) Delete 

func (f *Fork) Delete(key []byte)

Delete buffers a delete.

func (*Fork) Get 

func (f *Fork) Get(key []byte) (value []byte, ok bool, err error)

Get reads through the overlay, then the underlying store. ok reports whether the key is present.

func (*Fork) PendingOps 

func (f *Fork) PendingOps() int

PendingOps returns the number of buffered operations.

func (*Fork) Put 

func (f *Fork) Put(key, value []byte)

Put buffers an insert/overwrite.

func (*Fork) RootBefore 

func (f *Fork) RootBefore() (Hash, uint64)

RootBefore returns the state this fork is based on.

func (*Fork) Seal 

func (f *Fork) Seal() (*SealedFork, error)

Seal computes (rootAfter, versionAfter) without committing, and hands back the deterministic write-set. Fails closed if the store moved underneath the fork.

type Hash 

type Hash = [HashSize]byte

Hash is a 32-byte SHA-256 output. 

func HistoryLink(prevHead, prevRoot Hash, version uint64) Hash

HistoryLink computes the chain head written by the commit that produced version, from the previous head and previous root. Pure function; head_0 is all zeros.

func Placeholder 

func Placeholder() Hash

Placeholder is the hash standing in for any empty subtree, at every height. It is also the root of an empty store.

type KV 

type KV struct {
	Key   []byte
	Value []byte
}

KV is one scanned record.

type Kind 

type Kind int

Kind classifies a ledger error. Every integrity failure is Corrupted and fails closed: the store never silently returns data that did not verify against the in-memory root. 

const (
	// KindBackend: the storage backend returned an error.
	KindBackend Kind = iota + 1
	// KindCorrupted: a record failed hash verification, decoding or
	// decryption. Either storage was tampered with or it is damaged.
	KindCorrupted
	// KindMissing: a record that must exist is missing (e.g. a node
	// referenced by its parent, or a root record for a requested version).
	KindMissing
	// KindInvalid: invalid input from the caller.
	KindInvalid
)

type Leaf 

type Leaf struct {
	Path  Hash
	Value []byte
}

Leaf is one exported (path, value) pair.

type MemBackend 

type MemBackend struct {
	// contains filtered or unexported fields
}

MemBackend is an in-memory Backend for tests: it counts reads (I/O-complexity assertions) and can tamper with stored records (fail-closed assertions).

func NewMemBackend 

func NewMemBackend() *MemBackend

NewMemBackend returns an empty in-memory backend.

func (*MemBackend) Get 

func (b *MemBackend) Get(key []byte) ([]byte, bool, error)

Get implements Backend.

func (*MemBackend) Keys 

func (b *MemBackend) Keys() [][]byte

Keys returns all record keys (for tamper sweeps).

func (*MemBackend) Len 

func (b *MemBackend) Len() int

Len returns the number of records stored.

func (*MemBackend) Reads 

func (b *MemBackend) Reads() int

Reads returns the number of point reads served since construction or the last ResetReads.

func (*MemBackend) Remove 

func (b *MemBackend) Remove(key []byte) bool

Remove deletes a record outright (storage "loses" data).

func (*MemBackend) ResetReads 

func (b *MemBackend) ResetReads()

ResetReads zeroes the read counter.

func (*MemBackend) Scan 

func (b *MemBackend) Scan(start, end []byte, limit uint32) ([]KV, error)

Scan implements Backend.

func (*MemBackend) Tamper 

func (b *MemBackend) Tamper(key []byte) bool

Tamper flips one bit of the record at key. Returns false if absent.

func (*MemBackend) WriteBatch 

func (b *MemBackend) WriteBatch(ops []BatchOp) error

WriteBatch implements Backend.

type Op 

type Op struct {
	Key    []byte
	Value  []byte
	Delete bool
}

Op is one operation of a PutBatch: a put (Value, possibly empty) or a delete. Use Put and Del to construct.

func Del 

func Del(key []byte) Op

Del builds a delete op.

func Put 

func Put(key, value []byte) Op

Put builds an insert/overwrite op.

type Option 

type Option func(*storeOptions)

Option configures a store at construction.

func WithHistoryChain 

func WithHistoryChain() Option

WithHistoryChain makes every commit extend a hash chain over the root lineage, stored in a reserved leaf so each root commits to the entire sequence of roots before it (see audit.go for the audit workflow). Choose at Create — the setting is persisted and the chain changes what roots a given history produces, so it cannot be toggled later. Passing it to Open/OpenLatest asserts the store was created with the chain (open fails otherwise).

func WithStorageKey 

func WithStorageKey(sk [KeySize]byte) Option

WithStorageKey enables at-rest encryption of value records and the checkpoint under a per-machine storage key (AES-256-GCM), as a second layer on top of whatever encrypts the volume. Without it, value bytes are stored plaintext in the backend and confidentiality at rest is the volume's job. The root is a pure function of the logical data and the commitment key in BOTH modes, so replicas and proofs are unaffected by this choice — but the two modes write different value-record bytes, so one store's backend must always be opened in the mode that wrote it.

type Proof 

type Proof struct {
	// Leaf is the terminal leaf found by the descent, if any.
	Leaf *ProofLeaf
	// Siblings holds sibling hashes, bottom-up (deepest first).
	Siblings []Hash
}

Proof proves presence or absence of one path at one root.

func DecodeProof 

func DecodeProof(data []byte) (*Proof, error)

DecodeProof is the strict decoder of Encode's format.

func (*Proof) Encode 

func (p *Proof) Encode() []byte

Encode packs the proof as `[u8 flags(bit0 = has_leaf)] (path 32 ‖ vh 32)? [u16 LE count] siblings*32`.

type ProofLeaf 

type ProofLeaf struct {
	Path Hash
	Vh   Hash
}

ProofLeaf is the terminal leaf (path, vh) found by a proof's descent.

type PruneStats 

type PruneStats struct {
	// StaleEntries is the count of stale-index entries processed (and removed).
	StaleEntries int
	// RecordsDeleted is the count of node + value records deleted.
	RecordsDeleted int
	// RootRecordsDeleted is the count of root records deleted.
	RootRecordsDeleted int
}

PruneStats reports what a Prune call removed.

type SealedFork 

type SealedFork struct {
	RootBefore    Hash
	VersionBefore uint64
	RootAfter     Hash
	VersionAfter  uint64
	// Ops is the deterministic write-set (key-ordered).
	Ops []Op
}

SealedFork is the state transition a transaction proposes.

func (*SealedFork) IsNoop 

func (sf *SealedFork) IsNoop() bool

IsNoop reports whether this transaction is a no-op (empty or ineffective write-set).

type Store 

type Store struct {
	// contains filtered or unexported fields
}

Store is the authenticated KV store. Single writer: it is not safe for concurrent use; wrap it in a mutex at the application layer.

func Create 

func Create(backend Backend, commitmentKey [KeySize]byte, opts ...Option) (*Store, error)

Create builds a fresh, empty store (version 0, placeholder root).

func Open 

func Open(backend Backend, commitmentKey [KeySize]byte, root Hash, version uint64, opts ...Option) (*Store, error)

Open opens an existing store at a trusted (root, version) checkpoint (e.g. one anchored externally). It verifies the backend actually holds that root before returning; fails closed otherwise.

func OpenLatest 

func OpenLatest(backend Backend, commitmentKey [KeySize]byte, opts ...Option) (*Store, error)

OpenLatest opens at the checkpoint record the store itself maintains, written atomically inside every commit batch and authenticated: AES-256-GCM under the storage key when one is configured, otherwise an HMAC under a key derived from the commitment key. Storage cannot forge it — at worst it can replay an old checkpoint together with a matching old store, the documented restart-replay residual. Prefer anchoring Root() externally when an extra anchor is available.

func OpenOrCreate 

func OpenOrCreate(backend Backend, commitmentKey [KeySize]byte, opts ...Option) (*Store, error)

OpenOrCreate opens an existing store, or creates a fresh one if no checkpoint exists yet.

func (*Store) Backend 

func (s *Store) Backend() Backend

Backend exposes the underlying backend (tests, diagnostics).

func (*Store) ChangesAt 

func (s *Store) ChangesAt(version uint64) ([]Change, error)

ChangesAt extracts what the commit producing version changed, by structural diff against the predecessor: subtrees with equal hashes are skipped, so the cost is proportional to the change, not the store. The reserved history leaf is omitted (verify it with VerifyHistory instead). Works on any store, chained or not, for any unpruned version.

func (*Store) Get 

func (s *Store) Get(key []byte) (value []byte, ok bool, err error)

Get returns the value for key at the current version. ok reports whether the key is present (an empty value is a value).

func (*Store) GetAt 

func (s *Store) GetAt(version uint64, key []byte) (value []byte, ok bool, err error)

GetAt returns the value for key at a historical version.

Content is authenticated against the stored root record for that version; the version→root binding for history is backend-held, so history is strongest for roots the caller pinned externally.

func (*Store) HistoryEnabled 

func (s *Store) HistoryEnabled() bool

HistoryEnabled reports whether this store maintains the chain.

func (*Store) HistoryHead 

func (s *Store) HistoryHead() (Hash, uint64, error)

HistoryHead returns the current chain head and the version it covers (zeros before the first chained commit). Anchor all three of (root, version, head) at each audit.

func (*Store) HistoryHeadAt 

func (s *Store) HistoryHeadAt(version uint64) (Hash, error)

HistoryHeadAt returns the chain head recorded at a historical version (the same freshness caveat as GetAt; version 0 is the all-zero genesis head).

func (*Store) PinVersion 

func (s *Store) PinVersion(version *uint64)

PinVersion pins a version against pruning (a snapshot is being served from it). Pass nil to release the pin.

func (*Store) PreviewBatch 

func (s *Store) PreviewBatch(ops []Op) (Hash, uint64, error)

PreviewBatch computes the (root, version) this batch WOULD produce, without committing anything. The tree math is pure, so a later PutBatch with the same ops from the same state produces exactly this result. This is what a transaction Fork uses to seal rootAfter.

func (*Store) Prove 

func (s *Store) Prove(key []byte) (*Proof, error)

Prove proves presence or absence of key at the current root.

func (*Store) ProveAt 

func (s *Store) ProveAt(version uint64, key []byte) (*Proof, error)

ProveAt proves presence or absence of key at a historical version (same freshness caveat as GetAt).

func (*Store) Prune 

func (s *Store) Prune(beforeVersion uint64) (PruneStats, error)

Prune deletes storage needed only by versions strictly before beforeVersion: stale records that died at or before it, and root records below it. Afterwards GetAt/ProveAt keep working for every version >= beforeVersion and fail with a KindMissing error below it. The live tree is never touched — both node and value records are versioned and never rewritten, so stale targets are deleted blindly.

Costs are proportional to accumulated garbage, not store size. Idempotent; safe to re-run after a partial failure.

func (*Store) PutBatch 

func (s *Store) PutBatch(ops []Op) (Hash, uint64, error)

PutBatch applies a batch of operations as one commit. Later ops win over earlier ops on the same key. Returns the new (root, version).

If the batch changes nothing (deletes of absent keys, overwrites with identical values), no commit happens and the current (root, version) is returned unchanged.

func (*Store) RestoreLeaves 

func (s *Store) RestoreLeaves(leaves []Leaf) (Hash, uint64, error)

RestoreLeaves inserts plaintext values addressed by PATH (not logical key) — the snapshot-restore path. One atomic commit; returns the new (root, version).

func (*Store) RetainRecent 

func (s *Store) RetainRecent(window uint64) (PruneStats, error)

RetainRecent prunes so that (at least) the last window versions stay readable: Prune(version - window), clamped at zero.

func (*Store) Root 

func (s *Store) Root() (Hash, uint64)

Root returns the current (root, version). Anchor this pair externally after every commit when an anchor is available.

func (*Store) RootAt 

func (s *Store) RootAt(version uint64) (Hash, error)

RootAt returns the root hash recorded for a historical version (same freshness caveat as GetAt).

func (*Store) SetCacheCapacity 

func (s *Store) SetCacheCapacity(capacity int)

SetCacheCapacity resizes the node cache (0 disables). Clears current contents.

func (*Store) SnapshotLeaves 

func (s *Store) SnapshotLeaves(version uint64, startAfter *Hash, max int) (leaves []Leaf, done bool, err error)

SnapshotLeaves collects up to max leaves of the tree at version, in path order, starting strictly after startAfter (nil = from the start). Each value is read, decrypted and commitment-verified (fail-closed). done is false when more leaves remain.

Chunked iteration re-descends only the resume path (subtrees entirely at or below startAfter are skipped by nibble comparison), so a full scan costs O(n) total.

func (*Store) StampVersion 

func (s *Store) StampVersion(version uint64) error

StampVersion is the snapshot-restore epilogue: stamp the store at version (>= the current build version), writing the root record and checkpoint for it, and duplicating the root NODE record at the stamped version so a later Open(root, version) resolves. Interior node records keep their (smaller) build versions, which child references tolerate (each carries its own version).

func (*Store) VerifyAbsent 

func (s *Store) VerifyAbsent(root *Hash, key []byte, proof *Proof) (bool, error)

VerifyAbsent checks a proof claiming key is absent at root.

func (*Store) VerifyHistory 

func (s *Store) VerifyHistory(fromVersion uint64, fromHead Hash) error

VerifyHistory confirms that the recorded root sequence from (fromVersion, fromHead) to the live state is the unique lineage the current root commits to: it recomputes the chain over the stored root records and compares the result with the live, root-bound head. fromVersion 0 with a zero fromHead verifies from genesis; otherwise pass a previously anchored (version, head) pair. Fails if any root record in the range was pruned — audit before pruning.

func (*Store) VerifyValue 

func (s *Store) VerifyValue(root *Hash, key, value []byte, proof *Proof) (bool, error)

VerifyValue checks a proof claiming key = value against root. (false, nil) = the proof is valid but proves something else (absence, or a different value).

type Verified 

type Verified struct {
	// Present reports whether the path holds a value at the root.
	Present bool
	// Vh is the value commitment when Present.
	Vh Hash
}

Verified is what a valid proof establishes about the proven path.

func Verify 

func Verify(root, path *Hash, proof *Proof) (Verified, error)

Verify checks proof for path against root.

It returns the established statement, or an error if the proof does not recompute root (or is malformed). Pure function.

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.