Proof-Carrying Knowledge

Query results that carry the evidence needed to re-derive them.

Most grounded systems answer a query and cite a source: “trust this, it was retrieved.” Kremis takes a different approach. A query result can carry a Verifiable Query Certificate (VQC) — an object that a third party re-executes against the same graph state to obtain the identical answer, offline, without trusting the server that produced it. Re-verification ties the result to state_hash, so the verifier needs a graph whose canonical export hashes to that value; the certificate is not a standalone proof in isolation.

A citation says this exists. A certificate says here is how to re-derive it.

The Verifiable Query Certificate

The certificate is a pure function of (graph state, query). It contains no timestamp, no randomness, and no floating-point value.

Field	Content
query	The query in canonical form
evidence_nodes	The minimal set of nodes the result depends on, sorted
evidence_edges	The minimal set of edges the result depends on, sorted
traversal_trace	The ordered, deterministic steps taken
state_hash	BLAKE3 hash of the canonical (KREX) export of the graph state
grounding	The honest verdict: fact, inference, or unknown

The grounding field is not omitted when the answer is absent — see Proof of Absence.

Reproducible by construction

Reproducibility here is structural, not a logging side effect. It follows from the same constraints documented in the Graph Engine:

• All core collections use BTreeMap — iteration order is deterministic, no HashMap anywhere in kremis-core.
• The canonical export (KREX, magic b"KREX", version 2, postcard) is bit-exact; the same state serializes to the same bytes.
• GET /hash returns a BLAKE3 hash over that canonical form.

Because the answer is a deterministic function of the serialized state, the certificate is too. Re-running it yields the same bytes.

Independent re-verification

A verifier does not need Kremis. Any implementation that reproduces the canonical KREX bytes for a given state can recompute the certificate and compare. Correctness is therefore falsifiable by anyone: a divergent implementation that produces different bytes proves a defect, the way a mismatched hash does.

The published certificate specification freezes this format and ships test vectors (a frozen graph, a set of queries, and the expected certificate bytes) so the property can be checked, not assumed.

Proof of absence

When a query has no answer, grounding is unknown. The certificate over an absent result, together with state_hash, is a verifiable assertion: the graph at this state does not contain X. A probabilistic retriever cannot demonstrate a negative; a complete, deterministic store can. Absence is treated as a first-class, certifiable result, not a silent empty response.

Scope and honesty

This page describes a verification substrate, not a retrieval engine. Kremis deliberately does not provide:

• ontology-constrained or LLM-based extraction (authoring is the caller’s job)
• vector or hybrid retrieval
• a temporal / bi-temporal model

These are out of scope by design, not pending features.

Related work

Deterministic, auditable knowledge graphs for agents are an active area: canonical-primitive APIs for auditable reasoning over temporal knowledge graphs (arXiv:2510.06002), cryptographic deletion receipts (ForgetAgent), and reproducible KG construction (OPTIMUS). These provide auditable logs or reproducible construction. Kremis differs on a narrow, checkable point: the query result itself is reproducible by construction and re-verifiable by an independent implementation, delivered as a single local binary over MCP.

The defensible claim is intentionally narrow and falsifiable: no combination of (reproducible-by-construction query results) + (independently re-verifiable certificate) + (proof of absence) + (single local binary over MCP) is covered by the work above. Overstating beyond this is a defect, the same as a wrong hash.