• Issuers: Must canonicalize ACDC structures before computing SAIDs and signing
• Verifiers: Must canonicalize received data structures to recompute digests and verify signatures
• Witnesses: Canonicalize key events before creating receipts
• Parsers: Must apply canonical ordering rules when deserializing data structures

Process Flow

Canonicalization for SAID Generation

The most critical canonicalization workflow in KERI is the SAID generation process, which requires careful ordering to handle the self-referential nature of SAIDs:

Step 1: Data Structure Population

• Populate all fields in the data structure (e.g., ACDC credential)
• Insert a placeholder value (typically # characters) where the SAID will eventually reside
• The placeholder must be exactly the length of the final SAID (e.g., 44 characters for Blake3-256 with CESR encoding)

Step 2: Canonical Serialization

• Apply insertion-order preservation for field maps (JSON objects)
• The order of fields must match the schema-defined order, not lexicographic (alphabetical) order
• For ACDCs, the canonical field order is defined by the JSON Schema document
• Nested structures must recursively apply canonical ordering
• Array elements maintain their positional order

Step 3: Identifiable Basis Creation

• The canonically serialized data with placeholder becomes the identifiable basis
• This representation is the input to the cryptographic hash function
• The identifiable basis must be byte-exact reproducible across all implementations

Step 4: Cryptographic Digest Computation

• Apply the specified hash algorithm (e.g., Blake3-256, SHA-256) to the identifiable basis
• The hash algorithm is indicated by the CESR derivation code
• The raw hash bytes are then encoded using CESR encoding

Step 5: SAID Embedding

• Replace the placeholder in the identifiable basis with the computed SAID
• This creates the saidified data - the final canonical form
• The SAID is now cryptographically bound to the content

Canonicalization for Verification

When verifying a SAID or signature, the process reverses:

Step 1: Extract Claimed SAID

• Parse the received data structure
• Extract the SAID value from its designated field
• Note the CESR derivation code to determine the hash algorithm

Step 2: Reconstruct Identifiable Basis

• Replace the SAID value with the original placeholder
• Apply canonical serialization rules to the structure
• This recreates the identifiable basis that was originally hashed

Step 3: Recompute Digest

• Apply the same hash algorithm to the reconstructed identifiable basis
• Encode the result using CESR

Step 4: Compare

• Byte-compare the recomputed SAID with the claimed SAID
• Equality proves the data has not been tampered with
• Inequality indicates corruption or malicious modification

State Changes During Canonicalization

Canonicalization involves several critical state transitions:

1. Raw Data → Ordered Data: Field maps are reordered according to canonical rules
2. Ordered Data → Serialized Bytes: The structure is converted to a byte sequence
3. Serialized Bytes → Digest: Cryptographic hashing produces a fixed-length digest
4. Digest → Encoded SAID: CESR encoding adds derivation code and produces the final SAID

Decision Points

Implementers must make several critical decisions:

Serialization Format Selection:

• JSON (human-readable, widely supported)
• CBOR (compact binary, efficient)
• MGPK (MessagePack, alternative binary)
• All formats must produce equivalent canonical forms

Hash Algorithm Selection:

• Blake3-256 (recommended for performance and security)
• SHA-256 (widely supported, slower)
• SHA3-256 (alternative, different security properties)
• The choice is encoded in the CESR derivation code

Ordering Strategy:

• Schema-defined order (required for ACDCs)
• Insertion order (for general field maps)
• Never lexicographic (alphabetical ordering is explicitly forbidden)

Technical Requirements

Cryptographic Requirements

Hash Function Properties:

• Must be collision-resistant: Computationally infeasible to find two inputs producing the same hash
• Must be pre-image resistant: Cannot derive input from hash output
• Must be deterministic: Same input always produces same output
• Should be post-quantum resistant (Blake3 provides better quantum resistance than SHA-256)

Encoding Requirements:

• CESR encoding must prepend derivation codes
• Derivation codes indicate the cryptographic algorithm used
• Encoded output must be URL-safe Base64 compatible
• Length must be deterministic based on hash algorithm

Signature Compatibility:

• Canonicalized data must be signable with Ed25519, ECDSA, or other supported signature schemes
• Signature verification must use the same canonical form
• Multi-signature schemes must apply canonicalization before each signature

Timing Considerations

Performance Constraints:

• Canonicalization must be efficient for real-time credential presentation
• Large ACDC structures with nested credentials require recursive canonicalization
• Caching canonical forms can improve performance but risks using stale data

Ordering Guarantees:

• Field ordering must be deterministic across all implementations
• Programming language differences (e.g., Python dict ordering vs. JavaScript object ordering) must not affect canonical output
• Serialization libraries must preserve insertion order or implement explicit ordering

Concurrency Considerations:

• Canonicalization is stateless and can be parallelized
• Multiple threads can canonicalize different data structures simultaneously
• No locking or synchronization required for the canonicalization process itself

Error Handling

Invalid Input Detection:

• Missing required fields: Canonicalization should fail if required fields are absent
• Type mismatches: Fields must match expected types (string, number, object, array)
• Invalid SAID placeholders: Placeholder length must match expected SAID length

Serialization Failures:

• Circular references: Data structures with cycles cannot be canonicalized
• Unsupported types: Some language-specific types (e.g., Python sets) have no canonical JSON representation
• Encoding errors: Non-UTF-8 strings may cause serialization failures

Verification Failures:

• SAID mismatch: Recomputed SAID doesn't match claimed SAID
• Unknown derivation codes: Unrecognized CESR codes indicate unsupported algorithms
• Malformed structures: Data that doesn't conform to expected schema

Recovery Strategies:

• Reject invalid data: Most errors should result in rejection
• Graceful degradation: Unknown optional fields can be ignored
• Detailed error reporting: Provide specific information about canonicalization failures for debugging

Usage Patterns

ACDC Schema Canonicalization

One of the most critical canonicalization use cases is schema SAIDification. ACDC schemas must be canonicalized to compute their SAIDs, which are then embedded in credentials to cryptographically bind credentials to their schemas.

Typical Workflow:

1. Author JSON Schema with empty $id fields ("") at all levels
2. Recursively canonicalize from innermost blocks outward
3. Compute SAID for each nested schema block
4. Embed computed SAIDs into parent blocks
5. Continue until top-level schema SAID is computed
6. Publish schema with all SAIDs embedded

Example Pattern:

{
  "$id": "",
  "$schema": "http://json-schema.org/draft-07/schema#",
  "type": "object",
  "properties": {
    "attributes": {
      "$id": "",
      "type": "object",
      "properties": {
        "name": {"type": "string"},
        "age": {"type": "number"}
      }
    }
  }
}

After canonicalization and SAID computation:

{
  "$id": "EBNaNu-M9P5cgrnfl2Fvymy4E_jvxxyjb70PRtiANlJy",
  "$schema": "http://json-schema.org/draft-07/schema#",
  "type": "object",
  "properties": {
    "attributes": {
      "$id": "EDj-Pm8CNw80aA5djaobjhM__eFeAZIIkgo1-nfkB7M1",
      "type": "object",
      "properties": {
        "name": {"type": "string"},
        "age": {"type": "number"}
      }
    }
  }
}

Credential Issuance Canonicalization

When issuing ACDC credentials, canonicalization ensures the credential structure is verifiable:

Issuance Steps:

1. Populate credential fields in schema-defined order
2. Insert SAID placeholder in the d field
3. Canonicalize the entire credential structure
4. Compute SAID over canonical form
5. Embed SAID in the d field
6. Sign the canonical form with issuer's private key
7. Attach signature using CESR encoding

Best Practice: Always validate that the credential conforms to its schema before canonicalization to catch structural errors early.

Presentation Exchange Canonicalization

During IPEX (Issuance and Presentation Exchange) flows, both compact and full disclosure variants require canonicalization:

Compact Disclosure:

• Only SAIDs of undisclosed sections are included
• Canonicalization ensures SAIDs are computed consistently
• Verifier can request full disclosure of specific sections

Selective Disclosure:

• Individual attributes are blinded using SAIDs
• Each selectively disclosable attribute has its own canonical form
• Disclosure reveals canonical attribute blocks

Full Disclosure:

• Complete credential structure is canonicalized
• Verifier recomputes SAIDs to verify integrity
• All nested structures must maintain canonical ordering

Integration Considerations

Programming Language Differences:

• Python: Use dict with insertion order (Python 3.7+)
• JavaScript/TypeScript: Use Object or Map with insertion order
• Rust: Use IndexMap or LinkedHashMap for ordered maps
• Go: Use ordered map libraries (standard map is unordered)

Serialization Library Selection:

• Choose libraries that support insertion-order preservation
• Avoid libraries that automatically sort keys alphabetically
• Test round-trip serialization/deserialization to verify ordering

Schema Validation Integration:

• Validate structure before canonicalization
• Use JSON Schema validators that preserve field order
• Ensure validators don't reorder fields during validation

Caching Strategies:

• Cache canonical forms of frequently used schemas
• Invalidate cache when schemas are updated
• Be cautious with caching credentials (they may contain time-sensitive data)

Error Propagation:

• Canonicalization errors should propagate to calling code
• Provide detailed error messages for debugging
• Log canonicalization failures for security monitoring

Common Pitfalls

Lexicographic Ordering Mistake:

• Wrong: Sorting fields alphabetically
• Correct: Using schema-defined or insertion order
• This is the most common canonicalization error in KERI implementations

Placeholder Length Mismatch:

• Wrong: Using arbitrary placeholder length
• Correct: Placeholder must exactly match final SAID length (44 chars for Blake3-256)

Nested Structure Ordering:

• Wrong: Only ordering top-level fields
• Correct: Recursively applying canonical ordering to all nested structures

Serialization Format Inconsistency:

• Wrong: Mixing JSON and CBOR without proper conversion
• Correct: Using consistent serialization format throughout a workflow

Whitespace Handling:

• Wrong: Including formatting whitespace in canonical form
• Correct: Using compact serialization without unnecessary whitespace

Performance Optimization

Lazy Canonicalization:

• Only canonicalize when needed (e.g., before signing or verification)
• Don't canonicalize data that won't be cryptographically processed

Incremental Canonicalization:

• For large structures, canonicalize sections independently
• Combine canonical sections to form complete structure

Parallel Processing:

• Canonicalize independent data structures in parallel
• Use worker threads for large batch operations

Memory Management:

• Stream large data structures rather than loading entirely into memory
• Use generators/iterators for processing large credential sets

Relationship to KERI Security Model

Canonicalization is foundational to KERI's security architecture:

Self-Certification: SAIDs computed over canonical forms enable self-certifying identifiers that don't require external registries

Duplicity Detection: Canonical forms ensure that different representations of the same event can be detected, enabling duplicity detection in KELs

End-Verifiability: Canonical serialization enables end-verifiable data structures where any party can independently verify integrity

Composability: CESR's composability property depends on canonical encoding of primitives

Authentic Chaining: ACDC chains rely on canonical SAIDs to cryptographically link credentials

Without deterministic canonicalization, none of KERI's core security properties would be achievable. It is the invisible foundation that makes cryptographic verifiability practical across heterogeneous systems.

JSON Serialization: Use compact format without whitespace:

json.dumps(data, separators=(',', ':'))  # No spaces

Programming Language Considerations

Python (3.7+):

• dict maintains insertion order by default
• Use json.dumps() with separators=(',', ':') for compact output
• OrderedDict is no longer necessary but can be used for clarity

JavaScript/TypeScript:

• Object property order is insertion order (ES2015+)
• Use JSON.stringify() for serialization
• Be aware of numeric key sorting behavior

Rust:

• Use IndexMap or LinkedHashMap for ordered maps
• Standard HashMap is unordered and unsuitable
• serde_json preserves order with appropriate map types

Go:

• Standard map is unordered
• Use third-party ordered map libraries
• Consider using structs with explicit field ordering

Performance Optimization

Caching Strategies:

• Cache canonical forms of frequently used schemas
• Invalidate cache when schemas are updated
• Be cautious with credential caching (may contain time-sensitive data)

Lazy Evaluation:

• Only canonicalize when needed (before signing/verification)
• Don't canonicalize data that won't be cryptographically processed

Parallel Processing:

• Canonicalize independent structures in parallel
• Use worker threads for batch operations
• Canonicalization is stateless and thread-safe

Error Handling

Validation Before Canonicalization:

• Validate structure against schema before canonicalization
• Check for required fields, type correctness
• Fail fast on structural errors

Detailed Error Messages:

• Report which field caused canonicalization failure
• Include expected vs. actual types
• Provide context for debugging (e.g., path to problematic field)

Security Considerations:

• Log canonicalization failures for security monitoring
• Reject data with SAID mismatches immediately
• Don't expose internal implementation details in error messages

Testing Requirements

Test Cases:

1. Round-trip testing: Serialize → Deserialize → Serialize should produce identical output
2. Cross-implementation testing: Same data canonicalized by different implementations should match
3. Edge cases: Empty objects, deeply nested structures, large arrays
4. Negative tests: Invalid placeholders, missing fields, type mismatches
5. Performance tests: Large credentials, batch processing

Test Vectors: Use official KERI test vectors to verify implementation correctness. Document 14 references test implementations in the qvi-software repository.

Integration with KERI Components

KEL Integration: Key events must be canonically serialized before signing. The KEL verification process recomputes digests over canonical forms.

ACDC Integration: Credentials must maintain canonical ordering throughout their lifecycle: issuance, presentation, verification.

CESR Integration: CESR primitives are canonically encoded. The composability property depends on canonical representation.

IPEX Integration: Presentation exchanges require canonicalization for both compact and full disclosure variants.

Common Pitfalls

1. Lexicographic Ordering: Never sort fields alphabetically. This is the most common canonicalization error.

2. Whitespace Handling: Don't include formatting whitespace in canonical forms. Use compact serialization.

3. Placeholder Length: Ensure placeholder exactly matches final SAID length (44 chars for Blake3-256).

4. Nested Structure Ordering: Apply canonical ordering recursively to all nested structures, not just top-level.

5. Serialization Format Mixing: Use consistent serialization format throughout a workflow. Don't mix JSON and CBOR without proper conversion.

6. Caching Stale Data: Invalidate cached canonical forms when underlying data changes.

7. Type Coercion: Ensure numeric types are preserved (don't convert integers to strings during serialization).

Debugging Techniques

Diff Canonical Forms: When SAID verification fails, diff the expected and actual canonical forms to identify discrepancies.

Hex Dump Comparison: For binary formats, hex dump both forms to identify byte-level differences.

Field Order Inspection: Print field order before and after canonicalization to verify ordering logic.

Hash Intermediate Steps: Log intermediate values (identifiable basis, hash bytes, encoded SAID) to isolate where the process diverges.

Security Implications

Malleability Prevention: Canonical serialization prevents attackers from creating alternative representations of signed data that would produce different signatures.

Duplicity Detection: Canonical forms enable detection of conflicting representations of the same event in KELs.

Replay Attack Prevention: Combined with timestamps and nonces, canonical forms help prevent replay attacks.

Side-Channel Resistance: Deterministic canonicalization reduces timing side-channels in cryptographic operations.