Ledvar Protocol Specification

• Version: 0.1.0 (DRAFT)
• Protocol MAJOR: 0
• Status: Draft — definition phase. The data model and canonical form are not yet frozen.

1. Introduction

Ledvar is an open protocol for representing the state of a system as a canonical, content-addressed tree, so that two such trees can later be compared — exactly and reproducibly — to reveal what changed.

The protocol defines nouns, not verbs: what a piece of state is, and how it is hashed. It does not define what to do with it. Checking, comparing, storing, alerting and displaying are the business of implementations built on the protocol. Ledvar is deliberately the smallest thing that lets independent implementations agree — and nothing more.

It is encoding-agnostic — carry the data as JSON, YAML, XML, Protocol Buffers, or a binary packing (§8) — and domain-blind: it never knows whether a node describes a firewall rule, a virtual machine’s specs, a cloud permission, or a financial transaction. Any program, in any language, that produces the same hashes from the same input speaks Ledvar.

The name: a ledger is a book of record kept by adding, never erasing — every entry preserved so the past stays legible. A system’s state, kept the same way, is what Ledvar reads. (The name is a backronym — Ledger · Every · Diff · Versioned · Append-only · Recorded.)

Comparison (the “diff”) is not part of this specification. Turning hashes into “what changed” is a forced consequence of the data model, not something the protocol prescribes. Its representation is an optional companion standard, DIFF.md — see §7.

2. Conventions

The key words MUST, MUST NOT, SHOULD, MAY are interpreted as in RFC 2119. An implementation is any program that consumes or produces the data model and computes the hashes defined here.

3. Scope

This specification defines (normative): the data model; node identity and content hashing (the canonical form); well-formedness; protocol versioning; conformance.

Out of scope:

• comparison / diff — a forced consequence of the data model; its representation is the optional companion DIFF.md;
• the wire transport;
• the serialization format used for transport or storage (§8);
• storage durability and history retention;
• the meaning of any path or value;
• alerting, suppression, access control, authentication.

4. Data model

4.1 Snapshot

A Snapshot is one observation of some state at a point in time.

Snapshot-level fields are metadata. They do NOT participate in any hash.

4.2 Node

A Node is identity + content.

• path is ordered and significant, and MUST be unique within a Snapshot. A different path is a different node. The hierarchy that paths look like (["etc","ssh"] “above” ["etc","ssh","sshd_config"]) is a naming convention only — it carries no semantics. Nodes are independent: there is no subtree hash, a parent’s hash does not depend on its children, and removing ["etc","ssh"] does not affect ["etc","ssh","sshd_config"]. (This is deliberately not a Merkle tree.)
• content maps each attribute name to a set of string values. A scalar is a one-element set; a multi-valued attribute (a list of grants, a list of ports) is a larger set. Defaults to empty.
• labels and refs are pure annotation: never hashed.

Content or label? — the one question. Both can hold arbitrary strings, so the only thing that decides where a value goes is hashing: should a change to it count as drift?

• Yes — it is part of the observed state → content. Changing it changes the content_hash, so it surfaces as a modification.
• No — it is a human note about the node → labels. It is never hashed, so editing it is never drift; it is there to show up in a document or UI.

Example — a firewall node with an open port someone wants to explain:

{
  "path": ["firewall", "0.0.0.0:3306"],
  "content": { "state": ["open"], "proto": ["tcp"] },
  "labels":  { "description": "Open for the API-X integration DB tests" }
}

The port being open is state — it lives in content, and a change is drift. The human description is annotation — it rides in labels, appears in a doc or front-end, and re-wording it never raises an alert.

And the mirror case — a VM whose cloud tag you do want to watch, next to a private note you do not:

{
  "path": ["vms", "i-123"],
  "content": { "cpu": ["4"], "mem_gb": ["16"], "cloud_tag": ["prod-api"] },
  "labels":  { "description": "provisioned for the Q3 migration" }
}

Same kind of text in both places, decided only by consequence: rename the cloud_tag and it is drift — it is part of the VM’s real state; reword the description label and nothing fires. The firewall and the VM together are the whole rule in one picture: content is what is true, labels is what is noted.

4.3 Ref

target selector grammar is non-normative in MAJOR 0. refs are pure annotation and are never hashed (§4.2), so the selector syntax does not affect conformance — two implementations can hash identically while resolving target differently. The exact grammar (how a path-based selector addresses another node) is therefore left unspecified and reserved for a future companion specification; do not rely on a particular syntax across implementations until it is pinned. Resolving target (e.g. for the “orphan/dependency” convenience) is a resolver concern, not a core-protocol one. Concretely — and non-normatively — two shapes are already in use for different contexts: the examples here select within one document by the target node’s path joined with / (e.g. mydb/config:max_connections points at the node ["mydb","config:max_connections"]), while the Ledvar reference gateway, which partitions data by provider, uses a cross-provider <provider>:<path> form (e.g. files:/etc/secret.cnf, expanded from an ideal’s depends_on). That two forms already coexist is exactly why the grammar is reserved rather than fixed; a future companion may unify them.

4.4 Everything is a string

Every value in content is a string. The protocol never carries native numbers, booleans, or null inside content, and never interprets a value’s type.

This is deliberate. It removes all cross-language disagreement over number/float/boolean canonicalization — the most common way independent hash implementations diverge (is 4 equal to 4.0? does 0600 keep its leading zero? how is a float rendered?).

An implementation MAY accept or expose richer types at its edges — parsing input, rendering output, answering queries — but it MUST reduce every value to its string form before hashing. Reading "200" as an integer, or "Medium" as a severity, is meaning, and meaning lives in higher layers, not in the protocol.

5. Identity and content hashing

The protocol computes exactly two values, both derived properties of a node:

• identity_key(node) = HASH(canonical(path)) — which node this is. Two nodes are the same node iff they share an identity_key.
• content_hash(node) = HASH(canonical(content)) — what the node currently is. Two nodes are equal iff they share a content_hash.

labels and refs MUST NOT affect either hash. Re-tagging or re-linking a node is organization, not change.

These two hashes are the whole of what Ledvar standardizes about a node. Everything anyone does later — comparing, storing, displaying — is built on them.

Choosing a good path is the most consequential modeling decision a collector makes. For practical guidance — identity stability, representing order, value normalization — see the non-normative GUIDE.md.

6. Canonical form and hashing

Transport and storage MAY use any format (§8). Hashing MUST NOT. So that hashes are byte-identical across all implementations, the exact bytes that are hashed are defined here.

This is an internal hashing step, not a transport rule. The canonical form is a transient representation: an implementation reads a node from whatever format it arrived in (XML, Protocol Buffers, YAML…) into its in-memory model, builds the canonical byte string only to feed SHA-256, and discards it. Nothing is ever stored or transmitted as canonical JSON because of this rule — an XML-based implementation does not embed JSON in its XML. JSON is used here only because it is a simple, debuggable, universally implementable recipe for turning a value into deterministic bytes; another canonical encoding (e.g. canonical CBOR) would serve the same role. The recipe is fixed only so that every implementation agrees on the bytes.

6.1 Canonical encoding

The canonical encoding of a value is a JSON serialization built by the rules below. It is JSON (RFC 8259) and, for whitespace and string escaping, follows the JSON Canonicalization Scheme (JCS, RFC 8785) — with one deliberate departure from JCS: ordering is by Unicode code point, not by UTF-16 code unit (see the note below). The rules:

1. A set of strings is encoded as a JSON array whose elements are sorted ascending by Unicode code point (equivalently: by their UTF-8 byte sequence) and de-duplicated. The same code-point ordering applies to object keys.
2. A path is encoded as a JSON array of its segments in order — paths are NOT sorted, because order is identity.
3. content is encoded as a JSON object keyed by attribute name, keys sorted ascending by code point, with no insignificant whitespace. Because every value is a string, number canonicalization never applies.
4. Strings are escaped minimally (RFC 8259 §7, as JCS specifies): only ", \, and the control characters U+0000–U+001F are escaped (\b \t \n \f \r where defined, otherwise \u00xx with lowercase hex digits — \u001f, never \u001F); every other character — including all multi-byte text — is emitted verbatim. Ordering (rule 1) is over the raw string values, before this escaping is applied.

All output bytes are UTF-8.

No Unicode normalization — deliberate. The protocol compares and hashes the exact Unicode scalar values it is given; it performs no normalization (NFC, NFD, NFKC, NFKD). Two strings a human reads as identical but that are encoded as different code-point sequences — e.g. “café” as caf + U+00E9 (NFC) versus caf + e + U+0301 (NFD) — are different values and hash differently. This keeps the canonical form a pure function of its input, free of any Unicode-version dependency. Making equivalent forms compare equal (e.g. normalizing filenames to NFC) is a producer (collector) concern, not the protocol’s — see GUIDE.md §5.

Why code point (UTF-8 byte order), not UTF-16? Two different things are at play. Ordering — the sequence keys and set elements appear in — is compared by Unicode code point, which is identical to comparing the strings’ UTF-8 bytes. This is the natural ordering of many languages’ sorted string collections (Rust BTreeMap/BTreeSet, Go, Python 3’s str…), so those get it right for free — but Java and C# do NOT: their native string comparison (String.compareTo, String.CompareOrdinal, a TreeMap’s natural order) sorts by UTF-16 code unit, the very same trap as JavaScript. In any UTF-16-native language (JavaScript, Java, C#…) you MUST sort by the UTF-8 byte sequences — do not use the built-in string comparator. JCS itself inherited JavaScript’s UTF-16 collation; Ledvar’s canonical form deliberately departs from JCS here, because UTF-16 ordering would force every UTF-16-native implementation into an unnatural extra step that is easy to get wrong. The output — the bytes fed to SHA-256 — is always UTF-8; first you sort, then you encode. The two orderings differ only for characters outside the Basic Multilingual Plane: an astral character (e.g. an emoji) becomes a surrogate pair in UTF-16 whose first unit (U+D800– U+DBFF) sorts it before high-BMP characters like ff (U+FB00), whereas by code point it sorts after them. For ASCII and all BMP text the two are identical; the node-astral* conformance vectors pin exactly this difference.

6.2 Hash

HASH(x) = the lowercase hexadecimal SHA-256 of the UTF-8 bytes of canonical(x).

6.3 Worked example

path     ["catalog","sku:AX-42"]
canonical ["catalog","sku:AX-42"]
identity_key  40b6af8764108d36606126606c42d3e396a9e0778d7ad6a38e6bdc5804f6ad0c

content  { tags: {sale, featured, sale}, price_brl: {149.90} }
canonical {"price_brl":["149.90"],"tags":["featured","sale"]}
content_hash  63c1529881beb90df3a9865bea9cafe9bf1b4701932e0aa22ce980b7a387c5a2

(A retail product — the canonical form sorts the tags set, drops the duplicate sale, and orders the keys price_brl before tags. The mechanism is the same for any domain; see the cross-domain vectors in examples/.)

Full vectors: examples/CONFORMANCE.md.

6.4 Two structural properties

Two safety properties fall out of the canonical form for free; they are noted here so implementations do not accidentally break them:

• No separator injection. A path is canonicalized as a JSON array with each segment quoted and escaped — ["a","b"] — never as its segments joined by a separator. So a segment that itself contains the separator, a quote, or a backslash cannot forge a different identity: ["a/b"], ["a","b"] and ["a\",\"b"] all canonicalize distinctly. (A naïve join("/") identity would not have this property.)
• Domain separation between the two hashes. canonical(path) is always a JSON array (starts with [) and canonical(content) is always a JSON object (starts with {). The two pre-image spaces are therefore disjoint: no input to identity_key can collide with an input to content_hash, even though both use the same SHA-256.

7. Why comparison is out of scope

Given two snapshots, comparing them is pure set logic over the hashes of §5:

• a node in both with the same content_hash is unchanged;
• in both with a different content_hash, modified;
• only in the newer, added;
• only in the older, removed;
• with no prior snapshot, a baseline (cold start).

There is no sixth case. Because the outcome is fully determined by the data model, the protocol does not prescribe how to compute it — any correct implementation reaches the same answer, the way any two people dividing the same numbers get the same quotient.

What does benefit from a shared standard is the representation of a computed comparison, so that one component can produce it and another can read it with the same vocabulary. That representation is the optional companion standard, DIFF.md — the way JSON Patch (RFC 6902) is a separate standard from JSON itself. An implementation MAY adopt it, define its own, or never store comparisons at all and recompute them on demand. The core protocol requires none of this.

8. Serialization (non-normative)

Any format that can represent the data model may carry a Snapshot over a transport or into storage: JSON, YAML, XML, Protocol Buffers, a binary packing, etc. The choice is the implementation’s, and is a readability-vs-performance trade-off the protocol takes no position on. See examples/ for the same node in several formats.

The only place a single encoding is mandated is §6, and only for the bytes that are hashed.

9. Well-formedness

A Snapshot is well-formed iff:

• protocol_version parses as MAJOR.MINOR.PATCH — each of MAJOR, MINOR, PATCH is 0 or a non-zero digit followed by digits (no leading zeros), with no pre-release or build suffix (1.2.0, not 1.2.0-rc1 nor 01.2.0) — and its MAJOR is one the implementation supports (§10);
• every required field is present; an empty tree ([]) is well-formed — it is an empty scope, not an error (guarding against a producer that emits an empty tree on failure is a producer concern, see GUIDE.md §6);
• every value in content, every attribute name, and every path segment is a string in the serialization — a non-string (a JSON number, boolean, null, object, or array) is ill-formed. Reducing a richer input type to its string form (§4.4) is the producer’s job, done before serializing; a consumer that receives a non-string value rejects the document, it does not coerce it (there is no agreed string form of 200.0);
• every node path is non-empty and unique within the Snapshot, and every path segment is itself non-empty ([""], or any path containing an empty segment, is ill-formed);
• every attribute name is non-empty ({"":["x"]} is ill-formed), and each maps to a non-empty set — an attribute present with an empty set of values is ill-formed (encode “no value” by omitting the attribute, not by an empty set, and not by an empty name);
• no object the protocol interprets contains a duplicate key — this covers attribute names in content (the canonical model is a map from name to a set; two entries for the same name have no defined meaning and would not round-trip), labels, refs, and the snapshot/node structure itself. An unrecognized field is ignored wholesale — its interior is not inspected — so a duplicate key inside an ignored field is out of scope (to “ignore” a field is to not process it, not to validate it and then discard; requiring every implementation to strict-parse the interior of fields it does not read would be both surprising and unenforceable across parsers). Note: default JSON parsers silently collapse duplicate keys (last-wins), so enforcing this on interpreted objects needs a strict parser (see the note below);
• every string that is hashed — every path segment, every attribute name, and every value in content — is a valid sequence of Unicode scalar values (i.e. valid UTF-8 with no unpaired surrogate). A value that cannot be expressed as such (an unpaired UTF-16 surrogate; a raw byte sequence that is not valid UTF-8, such as some Linux filenames) is ill-formed and MUST be encoded by the producer before it becomes a value (see the note below);
• every string elsewhere in the document — labels names and values, refs fields, and the metadata strings (origin_id, provider_name, fingerprint, parent_origin_id) — is also a valid sequence of Unicode scalar values. The previous rule covers strings that are hashed; this extends it to the rest, so a well-formed Snapshot is always representable. A lone surrogate in a label is never hashed, yet it makes the whole document unparseable by a strict UTF-8 reader (e.g. Rust’s serde_json), so a Snapshot carrying one is ill-formed;
• content, when present, is an object (a map). Omitting it denotes a node with no attributes (it canonicalizes to {}); an explicit content: null, or a content that is any non-object, is ill-formed — “no attributes” is expressed by omission, never by null (as with the empty set);
• metadata is typed: labels, if present, maps string names to string values ({"env":42} is ill-formed, exactly as a non-string content value is); timestamp is an integer count of seconds within signed 64-bit range — a value with a non-zero fractional part (…000.5) or out of that range is ill-formed, as is a quoted string (§4.1). Because JSON number tokens do not distinguish N from N.0 uniformly across parsers (a strict int64 reader rejects 1718800000.0 at parse; a JavaScript reader accepts it as the integer 1718800000), a producer MUST serialize timestamp as a bare integer literal — no decimal point, no exponent. The N.0 and integral-exponent forms (1718800000e0) are not emitted by a conforming producer, so whether a consumer accepts or rejects them is unspecified and either conforms; only a non-zero fractional part, or a value out of int64 range, is unambiguously ill-formed. A ref, if present, carries a string relation and a string target (§4.3);
• an unrecognized field MUST be ignored, not rejected — this is what lets a later MINOR add a field without breaking an older reader. This leniency is only for unknown fields; a known field that is malformed is still ill-formed by the rules above.

Well-formedness is a property, not an operation — but it is not optional. An implementation MUST NOT hash an ill-formed Snapshot: doing so yields identity_key/content_hash values that no other conforming implementation reproduces, so refusing ill-formed input is part of conformance (§11), not an extra. When and how it detects ill-formedness — refusing at parse time, or in a later validation pass — is its own concern; both conform.

An implementation MAY impose resource limits — a maximum path-segment length, node count, value size, or total document size — to bound memory and time. On exceeding a limit it MUST reject the Snapshot rather than truncate, sample, or partially hash it: a truncated Snapshot hashes to a different value than the whole, the exact divergence this specification exists to prevent.

Upper-layer note (for producers/collectors). The last three rules pin decisions that would otherwise be made silently — and differently — by each implementation, the kind a prose-only reader must not have to guess:

• An empty attribute set must not exist. A producer whose native map preserves an empty-set key (e.g. a Rust BTreeMap<String, BTreeSet<String>>) must drop it before serializing; one whose multimap silently discards it already complies. A consumer that receives a serialized empty set rejects the document as ill-formed — it does not silently repair it to {}. Producer or consumer, no valid path leads to hashing an empty set (this matches §9 and the rejection listed in examples/CONFORMANCE.md §2b).
• Duplicate attribute names cannot survive: reject them, do not merge. In JSON this needs a strict parser — JSON.parse / json.loads silently collapse duplicate keys (last-wins) before you can see them, so an implementation using the default parser would hash a document these rules say to reject. Use a parser that surfaces duplicates at the deserialization boundary (Python’s object_pairs_hook, a streaming/event parser, a strict decoder). The same caution applies to any format whose default parser silently coalesces duplicate keys.
• A value that is not valid Unicode (a non-UTF-8 filename byte sequence, an unpaired surrogate) must be turned into a valid string before it enters content — hex or base64 is the usual choice (see GUIDE.md §8). Whether to encode it, or to skip the node and log the error, is a collector (upper-layer) decision, not a protocol one — the protocol only requires that whatever reaches a hash is valid Unicode.

10. Protocol versioning

protocol_version is MAJOR.MINOR.PATCH. Only MAJOR is contract-significant. The current MAJOR is 0. An implementation MUST reject a Snapshot whose MAJOR differs from the one it supports.

A MAJOR bump may change the data model or the canonical hashing form — it begins a new, incompatible hash universe. MINOR and PATCH changes MUST NOT change any hash.

During MAJOR 0 (draft), this stability guarantee does not yet apply. The “MINOR and PATCH MUST NOT change any hash” rule holds from MAJOR ≥ 1 onward. While the protocol is at MAJOR 0 the data model and canonical form are still being finalized (§12), so a MINOR bump within 0.x MAY change the canonical form and therefore hashes — but a PATCH within 0.x MUST NOT: during 0.x, any hash-affecting change MUST be released as a MINOR bump, never a PATCH. That discipline (a 0.x PATCH is text/examples/typo only, hashes intact) is exactly what makes the MINOR-pinning rule below sufficient — without it, a 0.1.0 reader could accept a 0.1.1 that silently moved the canonical form. Hash stability begins the moment a non-zero MAJOR is published, and that MAJOR’s canonical form is then permanent.

Consequently, while MAJOR is 0 an implementation MUST also reject a Snapshot whose MINOR differs from the one it implements. During 0.x the exact MINOR is contract-significant, precisely because a MINOR bump may have moved the canonical form — without this, a 0.1 reader would silently accept a 0.2 Snapshot whose hashes belong to a different universe. From MAJOR ≥ 1 onward this extra check falls away and only MAJOR gates compatibility, per the rule above.

11. Conformance

An implementation conforms to this core specification iff, for every vector in examples/CONFORMANCE.md, it computes the listed identity_key and content_hash exactly, and it refuses every ill-formed Snapshot — it MUST NOT hash one (§9). The reject-* vectors in examples/CONFORMANCE.md §2b are the machine-checkable form of that second half. Conformance is therefore exactly two things — reproduce every listed hash, and never produce a hash for ill-formed input — and nothing beyond those two. (The optional companion DIFF.md defines its own, separate conformance for those who adopt it.)

12. Status

Draft, MAJOR 0. The data model and canonical form are still open to change. Once a non-zero MAJOR is published, the canonical hashing form is permanent for that MAJOR.