immutable-ledger

An authenticated key-value store for Go: a versioned sparse Merkle tree (16-ary storage, binary hashing) over any storage backend, where one 32-byte root attests the entire logical data state.

This is the Go port of the Merkle store from Enclave OS (Mini), for confidential workloads that run as containers (Intel TDX confidential VMs, typically) rather than as SGX enclaves. The commitment scheme, record encodings and proof format are byte-identical to the Rust implementation: a Go store and a Rust store sharing the commitment key produce the same root for the same logical data, and proofs verify across implementations (enforced by compat_test.go, whose vectors are generated by the Rust reference).

Properties

• Verified reads, fail closed. A value is returned only after every node on its path hashes up to the in-memory root, its AES-256-GCM tag verifies, and its plaintext re-derives the committed value hash. Stale data, dropped keys and resurrected deletes are errors, never wrong answers.
• Encryption-independent root. The root commits to keyed plaintext hashes (HMAC-SHA-256 under a commitment key ck), never to the bytes at rest. Two stores sharing ck compare entire datasets as one (version, root) pair, whatever each one does at rest.
• One key by default. Confidentiality at rest is the volume's job — in a confidential VM the backend sits on an attested, LUKS-encrypted data partition, and adding a second application-level key on top buys little. Deployments that do want defence in depth pass WithStorageKey(sk) to add AES-256-GCM value encryption under a per-machine key; the roots and proofs are identical in both modes.
• Atomic commits. A batch of puts and deletes lands as one atomic backend write (new nodes, values, stale marks, root record and an encrypted checkpoint); the in-memory root only advances after the backend confirms.
• Proofs of presence and absence. Compact binary sparse-Merkle proofs, verifiable by a pure function against just the root — no store, no backend, no trust in whoever served the proof.
• Versioned history with deliberate pruning. Commits are immutable copy-on-write versions; Prune/RetainRecent delete history against a retention window at cost proportional to garbage.
• Transaction forks. Run logic against a read-through overlay, seal it as (root_before, write_set, root_after), and apply it atomically — the previewed root is exactly what the commit produces.

Usage

import ledger "github.com/Privasys/immutable-ledger/ledger"

// ck: the dataset's commitment key, shared by replicas of the same
// logical dataset. In a confidential deployment it comes from an
// attested key release (an Enclave Vaults credential), never from disk.
store, err := ledger.OpenOrCreate(backend, ck)

root, version, err := store.PutBatch([]ledger.Op{
    ledger.Put([]byte("alice"), []byte("1000")),
    ledger.Put([]byte("bob"), []byte("250")),
})
// Anchor (root, version) externally when an anchor is available.

value, ok, err := store.Get([]byte("alice"))

proof, err := store.Prove([]byte("alice"))
ok, err = store.VerifyValue(&root, []byte("alice"), []byte("1000"), proof)

The store talks to storage through the three-method Backend interface (point get, atomic write batch, ascending scan). backend/pebble ships a production adapter over Pebble (pure Go); MemBackend ships for tests. The core ledger package itself depends only on the standard library.

The store is single-writer and not safe for concurrent use; wrap it in a mutex at the application layer (the SQL layer below does this for you).

SQL

sqlledger runs MySQL-dialect SQL over the ledger, using go-mysql-server (Apache-2.0) as the query engine — embedded in-process only, by design: the application remains the sole boundary in front of its data, and there is deliberately no network listener.

store, _ := sqlledger.Open(led, backend, "app")
eng := sqlledger.NewEngine(store)
ctx := eng.NewContext(context.Background())

eng.Exec(ctx, `CREATE TABLE accounts (id BIGINT PRIMARY KEY, name VARCHAR(64), balance DOUBLE)`)
eng.Exec(ctx, `INSERT INTO accounts VALUES (1, 'alice', 100.5)`)
rows, _ := eng.Exec(ctx, `SELECT name, balance FROM accounts WHERE id = 1`)

Rows and the catalogue are ordinary ledger entries: the root attests the whole database, identical SQL histories produce identical roots, and Store.VerifiedGet returns any row together with its inclusion proof and the (root, version) it was read at (absence comes with an absence proof). Ordered scans and secondary indexes come from a derived keyspace next to the ledger — a materialisation, rebuilt automatically whenever it disagrees with the ledger's version; row content is always re-read and verified through the ledger.

Supported today: CREATE/DROP/RENAME/TRUNCATE TABLE (a primary key is required), INSERT/UPDATE/DELETE, SELECT with joins, aggregation, window functions, CTEs, ORDER BY and LIMIT, secondary and unique indexes (CREATE/DROP INDEX), AUTO_INCREMENT, multi-statement transactions (below), and the type set INT/BIGINT (signed and unsigned), FLOAT/DOUBLE, CHAR/VARCHAR/TEXT, BINARY/VARBINARY/BLOB, DATETIME/TIMESTAMP, BOOLEAN. Foreign keys, DECIMAL/JSON/ENUM columns, non-binary collations and column defaults are not yet supported.

Transactions

Without an explicit transaction, statements run in autocommit: each DML statement is one atomic ledger commit. BEGIN … COMMIT (with ROLLBACK, savepoints and SET autocommit = 0) buffers a multi-statement transaction in the session: later statements read their transaction's earlier writes through every path (point lookups, scans, indexes), other sessions see nothing until commit, and COMMIT applies the whole write-set as one atomic ledger commit — a transaction is exactly one ledger version, the root history only ever contains committed states, and a crash mid-transaction needs no recovery because nothing reached storage. DDL commits directly and implicitly commits the surrounding transaction (as in MySQL).

Concurrency is optimistic: the transaction records the committed row each write was based on, and commit re-validates the write-set (rows and unique indexes) if other work committed in between. A transaction whose touched rows changed underneath it fails with ErrTxnConflict and is rolled back — retry it. Keys a transaction only read are not tracked, so write skew across transactions is possible; serialise such transactions in the application if it matters.

Auditable history

WithHistoryChain() (a Create-time choice) makes every commit extend a hash chain over the root lineage, stored in a reserved leaf — so the current root commits to every root before it. Storage cannot rewrite or fork history between two audits and stay consistent with the live root. On top of it, ChangesAt extracts what any version changed (a structural diff, cost proportional to the change), and VerifyHistory confirms the recorded root sequence from any anchored (version, head) pair up to the live state.

The intended workflow is audit, sign, prune: at each audit (an owner-side or delegated audit — content verification requires the commitment key), verify the chain from the previous signed anchor, review the transitions as needed, sign the new (root, version, head), then Prune the audited range. Pruning physically removes superseded and deleted values, chain segment included — the signed anchor stands in for the discarded history, and the audit cadence bounds how long deleted data can persist. Third parties without the key can still verify root lineage and fork evidence, but not contents. See docs/auditing.md for the full model and the exact link function.

Freshness model and limits

Live reads are bound to the in-memory root: storage cannot roll back or forge state while the process runs. On restart, OpenLatest resumes from an authenticated checkpoint written atomically with every commit (HMAC under a ck-derived key, or AES-256-GCM when a storage key is configured) and refuses storage that does not verify against it. A backend that replays an old checkpoint together with a matching old store is not locally detectable — anchor Root() externally (a monitoring system, a transparency log, a vault) to narrow that residual, or replicate and compare roots to close it. Historical reads (GetAt, ProveAt) authenticate content against the stored root record for that version; the version-to-root binding for history is backend-held, so history is strongest for roots the caller anchored.

Performance

Measured figures and how to reproduce them: docs/benchmarks.md. In short: batched writes are CPU-bound on commitment hashing at roughly 5–7k rows/s per core, single-statement commits are fsync-bound, reads and proofs sit in the 100–300 µs band through the whole stack, and scans pay ~150 µs per row for verified re-reads.

Licence

AGPL-3.0 — see LICENSE.