immutable-ledger

README

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, ORDER BY and LIMIT, secondary and unique indexes (CREATE/DROP INDEX), AUTO_INCREMENT, and the type set INT/BIGINT (signed and unsigned), FLOAT/DOUBLE, CHAR/VARCHAR/TEXT, BINARY/VARBINARY/BLOB, DATETIME/TIMESTAMP, BOOLEAN. Statements run in autocommit (each DML statement is one atomic ledger commit); multi-statement transactions, foreign keys, DECIMAL/JSON/ENUM columns, non-binary collations and column defaults are not yet supported.

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.