Design note: canonical hashing — hand-rolled & streaming

Status: accepted. This explains a choice that is easy to second-guess later, so it is written down and committed.

The problem

Two independent implementations of Ledvar must produce byte-identical hashes for the same node — otherwise the whole protocol falls apart (SPEC §2, §6). To hash a node we turn its path/content into one exact byte string (the canonical form) and feed it to SHA-256. If two implementations build that string even one byte differently (key order, whitespace, string escaping), the hashes diverge.

The SPEC fixes the recipe as JCS (RFC 8785) with protocol rules: object keys sorted, value-sets sorted and de-duplicated, no insignificant whitespace, and — crucially — every value is a string, so JCS number canonicalization (the hard part of the standard) never applies to us.

The decision: hand-rolled, not a JCS crate

We build the canonical bytes ourselves (crates/ledvar-core/src/canon.rs) instead of pulling a general JCS/serde_jcs crate. Why:

1. Our subset is tiny. Path = array of strings; content = map of string → set of strings. The only non-trivial part is JSON string escaping (~20 lines). A general JCS library carries machinery for numbers/floats/nesting we never use.
2. Dependency-light. ledvar-core is embedded by every higher layer; its only deps are serde (wire model) and sha2 (hashing). Fewer moving parts to trust and audit.
3. Exact control. The bytes are defined by our code and pinned by the golden conformance vectors. A third-party crate could change behavior across versions and silently shift our hashes.
4. Performance — see below.

The safety net is the golden vectors (conformance/): if the canonicalizer is ever wrong, those tests fail immediately.

Performance: streaming, zero intermediate allocation

The library is on the hot path (a gateway may hash every node of every snapshot from a whole fleet), so hashing must be cheap.

• Input parsing is not part of hashing. A YAML/XML/proto reader parses directly into the in-memory model — there is no “convert to JSON” step.
• Hashing streams. SHA-256 is incremental, so we feed the canonical bytes straight into the hasher as we walk the (already sorted) BTreeMap/ BTreeSet — punctuation, then JSON-escaped strings — with no intermediate String allocation. The “JSON-ness” of the canonical form is just the shape of the bytes; there is no JSON parser in the hashing path.
• The same escaping routine is parameterised over a Sink, so the inspection path (canon command / Node::canonical_*) reuses it to materialise the string into a buffer — without slowing the hashing path.
• BTreeMap/BTreeSet pay the ordering/de-duplication cost once on construction; hashing then iterates already-canonical and is O(bytes).

This is also why hand-rolled wins on performance: a JCS crate typically builds a String first (an allocation per hash); we never do.

String escaping (the one fiddly part)

Per RFC 8785 / RFC 8259, only these are escaped inside a JSON string: " → \", \ → \\, and the control characters U+0000..=U+001F — using the short forms \b \t \n \f \r where defined, otherwise \u00XX. Everything else, including all multi-byte UTF-8, is emitted verbatim. Byte-wise iteration is safe because every escaped character is single-byte ASCII and UTF-8 continuation bytes are all ≥ 0x80.

Ordering of non-BMP characters (resolved)

We rely on Rust’s BTreeMap/BTreeSet, which order by Unicode scalar value (code point) = UTF-8 byte order. JCS (RFC 8785) instead sorts by UTF-16 code unit. The two are identical across the entire Basic Multilingual Plane — all ASCII and essentially every realistic key/value — and diverge only for supplementary characters (U+10000 and above, e.g. some emoji) used as a key or set element.

Resolved: SPEC §6.1 was amended to specify code-point ordering as a deliberate, documented departure from JCS — matching what this implementation already does, so spec and impl agree. The node-astral* conformance vectors pin the difference (the test fails if the ordering ever regresses to UTF-16). This is no longer a release blocker.