URS Canonicalization Specification v0.1.0

Preamble

This document specifies the URS Canonicalization algorithms — the deterministic transformation rules that reduce any valid URS representation (URS §1–§5) to a canonical byte sequence suitable for hashing, content-addressing, identity binding, and cross-implementation comparison.

URS Canonicalization is a companion specification to the URS Formal Specification (v0.1.0). It depends on URS but URS does not depend on it — the URS data model is complete without canonicalization, but all constitutional verification (identity binding, provenance hashing, attestation chains) requires canonical form.

Relationship to URS: The URS spec defines canonical representation rules (§4): identity levels, graph equivalence, ordering, normalization, cycle handling, and per-kind rules. This specification defines the algorithms that implement those rules deterministically. The rules are frozen with URS; the algorithms may be revised independently (separate versioning).

Constitutional dependencies: URS §4 (Canonical Representation Rules), CORE-LD §7 (Invariants I1–I23, incl. I21–I23 in §7.5), URS §6 (Provenance).

Codec independence: This canonicalization algorithm is codec-agnostic. It operates on the URS representation graph, not on any serialized form. Every conforming CORE-LD encoding binding (JSON-CORE-LD, CBOR-CORE-LD, and future bindings) SHALL reference this canonicalization specification for hash computation and identity binding.

Alignment (July 31, 2026): this specification has been aligned to the CORE-LD v0.1.0 family — the DAG-JSON-LD / DAG-CBOR-LD codec drafts are superseded by the JSON-CORE-LD and CBOR-CORE-LD encoding bindings (CORE-LD §6.2), and the codec registry (§5.1) and DAG addressing mode (§5.3) are updated accordingly. The canonicalization algorithms (§2–§4) are unchanged by the alignment.

Status: Frozen-readiness — conformance suite verified (24 tests, test_urs_canonicalization.py, §8.5); formal freeze pending constitutional artifact compilation via UCF forge per the publishing directive.

Section 1: Canonical Form Definition

1.1 What Canonicalization Produces

URS Canonicalization transforms a URS representation graph into a canonical byte sequence — a deterministic, ordered sequence of bytes that satisfies:

1. Determinism: The same representation graph always produces the same canonical byte sequence (URS I21). 2. Structural identity preservation: Two structurally identical graphs (URS §4.1, L1) produce identical canonical byte sequences (URS I22). 3. Cycle safety: Graphs containing cycles serialize deterministically without infinite recursion (URS I23). 4. Codec independence: The canonical byte sequence does not depend on any particular serialization codec.

1.2 Canonical Form vs Canonical Serialization

A codec's canonical serialization SHALL decode to the canonical form defined here but MAY produce different bytes (different encoding, same structural identity).

Section 2: Normalization Algorithm

2.1 Algorithm Overview

The URS Canonicalization algorithm proceeds in six phases:

1. Entity enumeration — collect all Entities in the representation graph 2. Kind assignment — confirm each Entity's kind and derive its canonical properties 3. Identifier normalization — relabel all Local Identifiers to deterministic blank node labels 4. Property normalization — canonicalize all Property names and values 5. Graph normalization — canonicalize Link structure, Group membership, and containment 6. Ordering — apply canonical ordering to all unordered structures

2.2 Phase 1: Entity Enumeration

Enumerate all Entities reachable from the root Entity via Properties (Entity references), Links (source/target), and Group membership. The enumeration is a depth-first traversal starting from the root (URS I11), using canonical ordering rules at each level (URS §4.3) to ensure determinism.

Traversal order: 1. Visit root Entity 2. For each Property on the Entity (ordered by Property name), if the Property value references another Entity, visit that Entity 3. For each Link where this Entity is the source (ordered by Link type, then target Identifier), visit the target Entity 4. For each Group this Entity is a member of (ordered by Group Identifier), visit the Group Entity 5. For each member of a Group (ordered by canonical member order), visit the member Entity 6. Maintain a visited-Entity set. If an Entity has been visited, do not revisit (cycle termination)

2.3 Phase 2: Kind Assignment

For each Entity, confirm its Representation Kind is one of the five declared kinds (URS I1): entity, property, identifier, link, group.

Derive the canonical kind properties for each kind per URS §4.6:

CORE-LD alignment: in the CORE-LD family, kinds are expressed via @type on framed documents (JSON-CORE-LD §3.2, CBOR-CORE-LD §3.2), with kind retained as an alias for URS-kind documents:

2.4 Phase 3: Identifier Normalization

Local Identifier normalization follows a deterministic relabeling algorithm:

1. Collect all Local Identifiers in the graph. 2. Sort them by their first appearance in the Phase 1 depth-first traversal order. 3. Assign each a canonical blank node label: _:b0, _:b1, _:b2, ... in traversal order. 4. Replace all references to the original Local Identifier with the canonical label.

Constitutional Identifiers are never normalized. They are preserved verbatim (URS §4.4).

Cross-context Identifiers are resolved to their canonical form within their declaring context before comparison (URS §4.4).

Normalization invariant: After normalization, two structurally identical representations that differ only in their original Local Identifier names will have identical normalized forms.

2.5 Phase 4: Property Normalization

Property name normalization: 1. Property names are normalized to Unicode NFC (Normalization Form Canonical Composition). 2. After NFC normalization, Property names are compared as byte sequences.

Property value normalization:

2.6 Phase 5: Graph Normalization

Link normalization: 1. Source: replaced with the source Entity's canonical Identifier. 2. Target: replaced with the target Entity's canonical Identifier. 3. Link Type: normalized to NFC string. 4. Link Properties: normalized per §2.5. 5. Link ordering: primary by Link Type (byte-ordered), then by target Identifier (byte-ordered), then by canonical hash of Link Properties.

Group normalization: 1. Variant declared explicitly (Set, Sequence, or Map). 2. Set members: normalized by replacing each member reference with the member's canonical Identifier. Duplicates removed. Members ordered by canonical Identifier (byte-ordered). 3. Sequence members: normalized by replacing each member reference with the member's canonical Identifier. Order preserved as declared. 4. Map entries: normalized by replacing each value reference with the entry's canonical Identifier. Keys ordered by byte-ordered UTF-8. 5. Nested Groups normalized recursively.

2.7 Phase 6: Ordering

Apply canonical ordering per URS §4.3:

1. Properties within an Entity — ordered lexicographically by normalized Property name (UTF-8 byte order). 2. Links from a single source Entity — ordered by Link type (byte-ordered), then target Identifier (byte-ordered), then Link Properties hash. 3. Set members — ordered by canonical Identifier (byte-ordered). 4. Sequence members — order preserved as declared. 5. Map entries — ordered by key (byte-ordered UTF-8). 6. At document/representation level — provenance fields ordered: Representer, Timestamp, Authority, RepresentationContext, PriorState (if present).

Section 3: Content-Addressing Model

3.1 Canonical Byte Sequence

After normalization (Phases 1–6), the canonical representation graph is serialized to a canonical byte sequence:

1. Serialize each Entity as an ordered key-value structure (key-order determined by Phase 6). 2. Serialize the complete graph as an ordered array of Entities, ordered by their canonical Identifier (byte-ordered). 3. Output as a deterministic byte sequence using the URS Canonical Binary Format (defined below).

3.2 URS Canonical Binary Format

The canonical binary format is a minimal, deterministic binary encoding designed specifically for URS canonicalization. It is NOT a general-purpose serialization — it exists solely to produce the canonical byte sequence for hashing and identity binding.

Key ordering in maps: Byte-ordered by the key's serialized bytes. This is deterministic by construction.

Empty structures: An empty array is 0x50 0x00. An empty map is 0x60 0x00.

3.3 Content Identifier (CHash)

The Content Hash (CHash) of a URS representation is:

CHash = multihash(SHA-256(canonical_byte_sequence))

Where:

• `canonical_byte_sequence` is the output of §3.1
• `SHA-256` produces 32 bytes
• `multihash` wraps the hash in the standard multihash format: ` `

Multihash parameters (default):

• Hash function: SHA-256 (multihash code `0x12`)
• Digest length: 32 bytes
• Full multihand: `0x12 0x20` + 32 bytes = 34 bytes total

Multihash code registry (for URS Canonicalization):

3.4 Structural Identifier (SID)

The Structural Identifier (SID) is the CHash of the structural identity (L1) of a representation — excluding all provenance, authority, and constitutional identity metadata. This enables content-addressed identification of "what the data is" independently of "who asserted it."

Two representations that differ only in their provenance but have identical structural content will share the same SID but have different CHashes.

Identity-level alignment with CORE-LD (CORE-LD §3.1):

The exclusion sets are intentionally different: SID operates at the representation level (provenance removed), while the L2 content hash is defined per encoding binding and additionally strips the @context declaration for encoding-agnostic identity. All three are computed by the same normalization pipeline (§2) and serialized per §3.1–3.2.

Section 4: Canonical Hash Computation

4.1 Hash Binding

URS uses canonical hashes for three binding purposes:

4.2 Hash Computation Steps

To compute the CHash of a URS representation:

1. Extract the representation graph from the root Entity 2. Normalize the graph per §2 (Phases 1–6) 3. Serialize the normalized graph to canonical binary format per §3.1–3.2 4. Hash the byte sequence with SHA-256 per §3.3 5. Wrap in multihash per §3.3

The resulting 34-byte value is the CHash.

4.3 SID Computation

Same steps as CHash, but with provenance fields (§6.1 provenance record) removed from the representation graph before normalization and serialization.

Section 5: Codec Identifiers

5.1 Standard Codec Identifiers

Each URS codec SHALL be assigned a canonical codec identifier used in content addressing and cross-codec interop. The registry is maintained as part of this specification.

Active codecs (CORE-LD family, v0.1.0):

Historical codecs (superseded, retained on record):

The active CORE-LD bindings use the standard multicodec codes (dag-json 0x0129, dag-cbor 0x71) for DAG-addressed use — no prototype codes needed. A DAG address (§5.3) therefore reads identically whether produced by IPLD tooling or a URS implementation for the same underlying document.

5.2 Codec Identifier Resolution

Given a codec identifier CID and a canonical byte sequence CBS (from §3.1), a codec's canonical serialization is:

Serialize(CID, CBS) → codec-specific bytes

A conforming codec SHALL guarantee:

Decompress(codec_bytes) → CBS → CHash → matches declared CHash

5.3 DAG Addressing Mode

CORE-LD §6.2 defines addressing modes as an axis of the dimensional architecture: [Addr]-[Encoding]-[Profile]-LD. The DAG addressing mode makes a CORE-LD document content-addressed: its address is derived entirely from its canonical bytes, independent of location.

Address construction (byte form):

DAG address = <multicodec codec varint> ++ <multihash>

where <multihash> is the CHash (§3.3) of the representation. For CBOR-CORE-LD documents this is 0x71 ++ 0x12 0x20 ++ <32 bytes>; for JSON-CORE-LD documents 0xA9 0x02 ++ 0x12 0x20 ++ <32 bytes> (dag-json varint). The text form is multibase z-prefixed base58btc of the same bytes (CIDv1-style; a version varint 0x01 precedes the codec when full IPLD CID compatibility is required).

Properties:

1. Content-derived — the address changes iff the canonical bytes change (I21, I22). Provenance edits → different CHash → different address; structural-only edits likewise. 2. Label-stable (canonicalization level) — Local Identifier relabeling (§2.4) is applied before hashing, so two representations differing only in _: label names share the same CHash, and hence the same canonicalization-level DAG address. Binding-level block addresses (CBOR-CORE-LD §5.2 L2 over the framed document's canonical CBOR, IPLD-style) hash the actual block bytes and are label-sensitive — the _: labels are part of the block. C6 (§7) defines the conversion between the two domains. 3. Codec-distinct — the codec varint disambiguates the encoding; a JSON-CORE-LD and a CBOR-CORE-LD document with the same logical content carry different addresses. 4. Resolution — within a DAG-addressed document, entity references resolve via @id; references outside the document resolve to other DAG addresses (external links).

Addressing mode composition: DAG-JSON-LD and DAG-CBOR-LD (CORE-LD §6.2 naming) denote the DAG-addressed forms of the JSON-CORE-LD and CBOR-CORE-LD bindings respectively — the naming is inherited from the historical codec drafts, the addressing rules from this section.

Section 6: Cycle Handling in Canonicalization

6.1 Cycle Detection

The canonicalization algorithm MUST detect cycles during the Phase 1 traversal. Detection uses a visited-Entity map (by canonical Identifier). When an Entity is encountered that is already in the visited set, a cycle is recorded rather than recursing.

6.2 Cycle Documentation in Canonical Form

A cycle in the canonical form is recorded as:

[cycle:
  [0]: Entity canonical Identifier
  [1]: Link type that forms the back-edge
  [2]: Source Entity canonical Identifier (cycle origin)
  [3]: Link chain (array of [source, link type, target] tuples)
]

The cycle structure ensures deterministic serialization without infinite recursion (URS I23).

6.3 Self-Containing Group Detection

A Group that contains itself directly or transitively (URS I10) is invalid and MUST cause canonicalization to fail with an error. This is detected during Phase 1 traversal: if a Group Entity appears in its own membership chain, canonicalization halts.

Section 7: Invariants

This specification contributes the following invariants beyond the CORE-LD invariants I1–I23:

C1–C5 map to the CORE-LD canonicalization invariants (I21 determinism, I22 structural identity → same hash, I23 cycle-safe serialization; CORE-LD §7.5). C6 fixes the relationship between the binding-level hashes (defined over canonical JSON/CBOR bytes) and the canonicalization-level CHash (defined over the URS Canonical Binary): different byte forms, same structural identity — each is independently reproducible, and §5.2 resolution converts between them.

Section 8: Examples

8.1 Minimal Entity Normalization

Before normalization (with local identifiers):

Root Entity (Local: "_:myDevice")
  Properties:
    - name: "Device-001"
    - type: "sensor"
  Identifier: "_:myDevice"

After normalization:

Root Entity (Local: "_:b0")
  Properties:
    - name: "Device-001"
    - type: "sensor"
  Identifier: "_:b0"

Canonical byte sequence (hex):

50 01                                # array(1) — the graph, one entity
  60 02                              # map(2) — entity sections
    30 0A 49 64 65 6E 74 69 66 69 65 72   # text(10) "Identifier"
    30 04 5F 3A 62 30                     # text(4) "_:b0" — canonical blank label
    30 0A 50 72 6F 70 65 72 74 69 65 73   # text(10) "Properties"
    60 02                                 # map(2) — two properties
      30 04 6E 61 6D 65                   # text(4) "name"
      30 0A 44 65 76 69 63 65 2D 30 30 31 # text(10) "Device-001"
      30 04 74 79 70 65                   # text(4) "type"
      30 06 73 65 6E 73 6F 72             # text(6) "sensor"

The byte sequence above is the verified output of the reference implementation (canonicalize in urs_canonicalization.py); the conformance suite extracts this block and asserts byte-equality with the implementation output (§8.5).

8.2 Graph with Two Entities and a Link

Before normalization:

Entity A (Local: "_:node1")
  Properties: name = "Server"
  Links: → B via "connectsTo"

Entity B (Local: "_:node2")
  Properties: name = "Database"
  Links: → A via "connectsTo"  (cycle)

After normalization:

Entity _:b0
  Properties: name = "Server"
  Links: [connectsTo → _:b1]

Entity _:b1
  Properties: name = "Database"
  Links: [connectsTo → _:b0]
  Cycle: [_:b1, connectsTo, _:b0, [[_:b0, connectsTo, _:b1]]]

8.3 CHash Calculation

Given the normalized representation from 8.1, the canonical byte sequence is:

50 01 60 02 30 0A 49 64 65 6E 74 69 66 69 65 72 30 04 5F 3A 62 30 30 0A 50 72 6F 70 65 72 74 69 65 73 60 02 30 04 6E 61 6D 65 30 0A 44 65 76 69 63 65 2D 30 30 31 30 04 74 79 70 65 30 06 73 65 6E 73 6F 72

(68 bytes — the verified output of canonicalize(); array wrapper 0x50 0x01 per §3.1, string markers 0x30 per the §2.3 format table.)

CHash = SHA-256(above bytes) = 12 20 28 5F F6 81 25 8D 69 FF F5 B1 42 15 43 5A 41 95 B1 79 E0 DD DE 44 5F 04 A1 05 B9 F1 FE 3E 4F A3 (34 bytes: multihash 0x12 SHA-256, 0x20 length 32, 32-byte digest).

8.4 DAG Address Computation

Given the CHash from §8.3 (0x12 0x20 ++ <32 digest bytes>), the DAG address of the document as CBOR-CORE-LD is:

dag-cbor varint:  0x71
multihash:        0x12 0x20 <32 digest bytes>
address (bytes):  0x71 0x12 0x20 <32 digest bytes>     (35 bytes)
address (text):   z + base58btc(above 35 bytes)       (multibase z)

The same document addressed as JSON-CORE-LD carries the dag-json varint 0xA9 0x02 instead — codec-distinct addresses for the same logical content (§5.3 property 3).

8.5 Conformance Suite

The reference suite is test_urs_canonicalization.py (24 tests, all passing), exercising:

• C1 — determinism (repeated canonicalization byte-identical), non-canonical-input rejection (opaque integer map keys)
• C2 — relabel-stability (structurally identical docs differing only in `_:` label names canonicalize identically), opaque group-Map entry keys correctly treated as structural (relabeling changes them → different canonical form)
• C3 — cycle-safe serialization (deterministic bytes, cycle structure documented per §6.2, cycle record format byte-matched to the §8.2 example), self-containing Group rejection (I10 halt)
• C4 — `canonicalHash` declaration consistency (match → pass, mismatch → fail)
• C5 — binding round-trip: canonical JSON (JSON-CORE-LD §5.1) → CBOR-CORE-LD encode → canonicalize → byte-identical to direct canonicalization
• C6 — CBOR-CORE-LD L2/L3 hash stability and provenance-exclusion semantics (documents differing only in provenance share L2, differ at L3)
• §8.1/§8.3 examples — hex block extracted from the spec markdown and asserted byte-equal to `canonicalize()` output; CHash asserted byte-equal to the spec's documented digest

The suite reuses the CORE-LD family fixtures (test_cbor_core_ld.EXAMPLES, profile_conformance.build_doc) and the deterministic CBOR encoder (cbor_core_ld.py) for the C5/C6 binding checks.

Section 9: Constitutional Layer

Doctrine Position

End of URS Canonicalization Specification v0.1.0