Skip to Content
DocsInternalsCanonicalization

Canonicalization

The fingerprint function relies on a canonicalization step to ensure deterministic hashing. This page describes the algorithm in detail.

The canonicalize Function

function canonicalize(value: unknown): unknown { if (value === null || value === undefined) return value; if (Array.isArray(value)) { const allStrings = value.every((v) => typeof v === "string"); const items = allStrings ? (value as string[]).slice().sort() : value; return items.map(canonicalize); } if (typeof value === "object") { const sorted: Record<string, unknown> = {}; for (const key of Object.keys(value as Record<string, unknown>).sort()) { sorted[key] = canonicalize((value as Record<string, unknown>)[key]); } return sorted; } return value; }

Rules

1. Null and undefined pass through

canonicalize(null) // → null canonicalize(undefined) // → undefined

2. Object keys are sorted

canonicalize({ z: 1, a: 2, m: 3 }) // → { a: 2, m: 3, z: 1 }

This is recursive — nested objects are also sorted:

canonicalize({ outer: { z: 1, a: 2 } }) // → { outer: { a: 2, z: 1 } }

3. All-string arrays are sorted

canonicalize(["charlie", "alpha", "bravo"]) // → ["alpha", "bravo", "charlie"]

4. Mixed arrays preserve order

canonicalize([3, 1, 2]) // → [3, 1, 2] (not all strings, order preserved) canonicalize(["a", 1, "b"]) // → ["a", 1, "b"] (not all strings)

5. Primitives pass through

canonicalize(42) // → 42 canonicalize("hello") // → "hello" canonicalize(true) // → true

Why Deep Clone First?

The fingerprint function calls structuredClone(obj) before canonicalization to avoid mutating the caller’s object. canonicalize sorts arrays in-place via .sort(), which would modify the original without cloning.

Why Sort String Arrays?

In distributed systems, the same set of items may arrive in different orders depending on which node responded first. Sorting ensures that ["a", "b"] and ["b", "a"] produce the same fingerprint — they represent the same logical set.

Non-string arrays are not sorted because their order may be semantically meaningful (e.g., processing steps, priority lists).

Typed canonical form v0.2

fingerprint(obj) above knows nothing about the schema, so it sorts every all-string array, including ones whose order matters. v0.2 adds a schema-aware canonical form, used by canonicalJson(value, schema) and typedFingerprint(value, schema).

The value is type-checked first (see Type System); then:

ValueCanonical form
record, variantobject; keys sorted; absent / undefined / null optional fields omitted
map<string,T>object; keys sorted
string[]array, items sorted (duplicates kept)
list<T>array, source order kept
intJSON integer, no exponent, no sign on zero (-0 → 0)
string, enumJSON string
booltrue / false

Sort order is by UTF-16 code units, which is JavaScript’s default sort() and the order v0.1 already uses. (It differs from code-point order only when comparing characters above U+FFFF with characters in U+E000–U+FFFF; implementations in other languages should compare UTF-16 encodings.)

Serialization is compact JSON: no whitespace, object keys written in sorted order, strings escaped as ECMAScript JSON.stringify does (\", \\, \b \f \n \r \t, other controls as \u00xx in lower-case hex, everything else literal, including non-ASCII).

Fingerprint = lower-case hex SHA-256 of the canonical JSON’s UTF-8 bytes. A short, versioned identifier is versionedId(name, fp) = name@ + the first 12 hex digits, for example rules-v0@5a316e4bf6d7.

The fingerprint covers the data, not the schema. If the schema identity must be part of the hash, put a discriminator in the data (an enum field such as "schema": "routing-snapshot" plus a schemaVersion int).

Relation to the v0.1 fingerprint

For a value that conforms to a v0.1 schema, typedFingerprint equals fingerprint, with one exception: map keys that look like array indices ("2", "10"). JSON.stringify writes such keys first, in numeric order, so v0.1 hashed {"2":…,"10":…}; canonical JSON writes them in sorted order, {"10":…,"2":…}. fingerprint and verify on v0.1 schemas are unchanged, so existing hashes stay valid.

Last updated on