Graph-Based Implementation

The KERI documentation explicitly states: "The persistent data structure is a graph." This reveals that ACDCs implement persistent data structures as directed acyclic graphs (DAGs), where:

• Nodes represent individual ACDCs with their attribute data
• Edges represent cryptographic references (via SAIDs) between ACDCs
• Acyclicity ensures finite traversal and prevents circular dependencies
• Immutability means the graph structure is append-only, with new nodes and edges added but never modified

This graph-based architecture enables complex credential chains, delegation hierarchies, and proof-of-authority relationships while maintaining cryptographic verifiability at every node.

Data Format

ACDC as the Primary Persistent Data Structure

The Authentic Chained Data Container (ACDC) serves as the canonical implementation of persistent data structures in the KERI ecosystem. ACDCs are structured as ordered nested field maps (key-value mappings) with specific requirements:

Top-Level Structure

Each ACDC contains normative top-level fields that establish its identity and integrity:

{
  "v": "ACDC10JSON00011c_",
  "d": "EAdXt3gIXOf2BBWNHdSXCJnFJL5OuQPyM5K0neuniccM",
  "u": "0ABghkDaG7OY1wjaDAE0qHcg",
  "i": "did:keri:EBkPreYpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDIPM",
  "ri": "did:keri:ECmRy7xMwsxUelUauaXtMxTfPAMPAI6FkekeolOjkggt",
  "s": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A",
  "a": "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY",
  "e": "EFH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZIl3MOA",
  "r": "EG71iheqcywJcnjtJtQIYPvAu6DZIl3MORH3dCdoFOLB"
}

Field Definitions:

• v (Version String): Regex-parsable format encoding protocol version, serialization type (JSON/CBOR/MGPK/CESR), size, and terminator
• d (SAID): Self-Addressing Identifier—a cryptographic digest of the entire ACDC that serves as both identifier and integrity proof
• u (UUID): High-entropy pseudorandom nonce that acts as a "salty nonce" to prevent rainbow table attacks on the SAID
• i (Issuer AID): Autonomic Identifier of the credential issuer, rooted in KERI's verifiable key state
• ri (Registry ID): Reference to the Transaction Event Log (TEL) registry for issuance/revocation tracking
• s (Schema): SAID of the JSON Schema or the schema itself
• a (Attributes): SAID of the attribute block or the uncompacted attributes
• e (Edges): SAID of edge block or the edges themselves, forming the property graph
• r (Rules): SAID of Ricardian contract clauses or the rules themselves

Insertion-Ordered Field Maps

The ACDC specification mandates insertion-ordered field maps for canonical serialization. This ordering requirement is critical because:

• Reproducible serialization is essential for SAID computation
• Round-trip serialization/deserialization must not alter field order
• Modern programming languages support ordered dictionaries/hash tables that maintain insertion order
• Lexicographic (alphabetical) ordering is explicitly NOT required

This design choice prioritizes implementation simplicity and compatibility with existing data structures over arbitrary ordering schemes.

Compact vs. Uncompacted Variants

ACDCs support multiple disclosure levels through variant representations:

Compact Variant: Only SAIDs are disclosed for sections, providing minimal information leakage:

{
  "v": "ACDC10JSON00011c_",
  "d": "EAdXt3gIXOf2BBWNHdSXCJnFJL5OuQPyM5K0neuniccM",
  "i": "did:keri:EBkPreYpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDIPM",
  "s": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A",
  "a": "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY"
}

Uncompacted Variant: Full attribute blocks are disclosed:

{
  "v": "ACDC10JSON00011c_",
  "d": "EAdXt3gIXOf2BBWNHdSXCJnFJL5OuQPyM5K0neuniccM",
  "i": "did:keri:EBkPreYpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDIPM",
  "s": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A",
  "a": {
    "d": "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY",
    "i": "did:keri:EpDA1n-WiBA0A8YOqnKrB-wWQYYC49i5zY_qrIZIicQg",
    "dt": "2021-06-09T17:35:54.169967+00:00",
    "LEI": "254900OPPU84GM83MG36",
    "personLegalName": "John Doe",
    "officialRole": "Chief Executive Officer"
  }
}

An issuer's signature on the compact variant provides a cryptographic commitment to the entire tree of possible uncompacted variants, as all variants share the same top-level SAID.

Encoding Formats

ACDCs support multiple serialization formats while maintaining the persistent data structure properties:

• JSON: Human-readable text format
• CBOR: Compact binary format (Concise Binary Object Representation)
• MGPK: MessagePack binary format
• CESR: Composable Event Streaming Representation for streaming applications

All formats must preserve insertion order and support the canonical ordering requirements for SAID computation.

Size and Constraints

Field Label Constraints: ACDC uses compact single-character field labels (v, d, i, s, a, e, r) for efficiency in resource-constrained environments like IoT devices and supply chain applications.

SAID Length: SAIDs are fixed-length based on the cryptographic hash algorithm:

• Blake3-256: 44 characters in CESR Base64 encoding
• SHA-256: 44 characters in CESR Base64 encoding
• SHA3-256: 44 characters in CESR Base64 encoding

UUID Length: The u field contains a 128-bit UUID encoded as 24 characters in CESR Base64.

Operations

Creation and Initialization

SAID Generation Protocol

Creating a persistent data structure in ACDC follows a precise algorithm to generate the self-addressing identifier:

1. Populate Data Structure: Fully populate all fields, using a placeholder string (typically # characters) for the SAID field d
2. Canonicalize: Transform the data into canonical form (the "identifiable basis") to ensure consistent hashing
3. Compute Digest: Apply the chosen cryptographic hash function (Blake3-256, SHA-256, etc.) to the identifiable basis
4. CESR Encode: Encode the digest using CESR, which prepends a derivation code indicating the algorithm
5. Embed SAID: Replace the placeholder with the computed SAID to create the final "saidified data"

This process creates a mutually tamper-evident relationship where any modification to either the identifier or the content can be cryptographically detected.

Issuer Signature

Once the ACDC structure is created with its SAID, the issuer signs the structure using their KERI-based Autonomic Identifier:

1. Key State Verification: The issuer's current authoritative keys are determined from their Key Event Log (KEL)
2. Signature Generation: The issuer signs the ACDC using their current signing keys
3. Signature Attachment: The signature is attached to the ACDC as CESR-encoded cryptographic material
4. Immutability Establishment: Once signed, the ACDC becomes immutable—any change would invalidate the signature

Updates and Modifications

Immutability Principle

The fundamental principle of persistent data structures in ACDC is: signed content cannot be modified. This creates several important operational characteristics:

No In-Place Updates: Unlike traditional database records that can be updated in place, ACDCs cannot be modified after signing. Any change requires creating a new ACDC with a new SAID.

Version Chains: Updates are represented by creating new ACDCs that reference previous versions through edge relationships:

{
  "v": "ACDC10JSON00011c_",
  "d": "NEW_SAID_FOR_UPDATED_VERSION",
  "i": "did:keri:EBkPreYpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDIPM",
  "e": {
    "d": "EDGE_BLOCK_SAID",
    "supersedes": {
      "n": "PREVIOUS_VERSION_SAID",
      "s": "SCHEMA_SAID"
    }
  },
  "a": {
    "d": "ATTRIBUTE_BLOCK_SAID",
    "updatedField": "new value",
    "unchangedField": "same value"
  }
}

Revocation via TEL: Rather than deleting or modifying ACDCs, their validity status is managed through Transaction Event Logs (TELs):

• Issuance Events: Record when an ACDC is issued
• Revocation Events: Record when an ACDC is revoked
• TEL Anchoring: TEL events are anchored to the issuer's KEL, creating a verifiable chain of authority

This approach maintains the immutability of the ACDC itself while providing a mechanism for status management.

Graduated Disclosure Updates

ACDCs support progressive disclosure through multiple variants:

Compact → Partial Disclosure: Revealing selected sections while keeping others as SAIDs Partial → Full Disclosure: Expanding all sections to show complete attribute data Selective Disclosure: Unbundling specific attributes from the selective disclosure array

Each disclosure level represents a different view of the same underlying persistent data structure, all cryptographically bound to the same root SAID.

Verification and Validation

SAID Verification

Verifying a persistent data structure involves confirming the SAID correctly identifies the content:

1. Extract SAID: Retrieve the d field value from the ACDC
2. Canonicalize: Transform the ACDC into canonical form
3. Replace SAID: Substitute the SAID with the original placeholder to reconstruct the identifiable basis
4. Recompute Digest: Hash the reconstructed identifiable basis using the algorithm indicated by the CESR derivation code
5. Compare: Verify the computed digest matches the embedded SAID

Equality proves the ACDC has not been tampered with since the SAID was generated.

Signature Verification

Verifying the issuer's signature requires:

1. Issuer AID Resolution: Retrieve the issuer's KEL from witnesses or watchers
2. Key State Determination: Determine the authoritative keys at the time of ACDC issuance
3. Signature Extraction: Extract the attached CESR-encoded signature(s)
4. Cryptographic Verification: Verify the signature(s) using the issuer's public key(s)
5. Threshold Satisfaction: Confirm sufficient signatures for multi-sig scenarios

Chain Verification

For ACDCs that form chains through edge relationships:

1. Edge Traversal: Follow edge references (SAIDs) to linked ACDCs
2. Recursive Verification: Verify each linked ACDC's SAID and signatures
3. Schema Compliance: Confirm each ACDC conforms to its declared schema
4. Operator Logic: Evaluate edge operators (I2I, DI2I, NI2I) to validate authorization chains
5. Root-of-Trust: Trace the chain back to a trusted root issuer

This recursive verification process ensures the entire credential graph maintains integrity.

Usage Context

KERI Protocol Integration

Persistent data structures in ACDC are fundamentally integrated with KERI's key management infrastructure:

Key Event Logs (KELs): The KEL itself is a persistent data structure—an append-only, cryptographically chained log of key events. Each event in the KEL is immutable once signed, providing the foundation for verifiable key state.

Transaction Event Logs (TELs): TELs extend the persistent data structure pattern to credential lifecycle management, tracking issuance and revocation states without modifying the underlying ACDCs.

Autonomic Identifiers (AIDs): AIDs serve as the issuer identifiers in ACDCs, with their control authority established through the persistent data structure of the KEL.

vLEI Ecosystem Implementation

The GLEIF vLEI (verifiable Legal Entity Identifier) ecosystem provides a production implementation of persistent data structures:

Credential Hierarchy: vLEI credentials form a DAG where:

• GLEIF Root AID issues QVI (Qualified vLEI Issuer) credentials
• QVIs issue Legal Entity credentials
• Legal Entities issue OOR (Official Organizational Role) and ECR (Engagement Context Role) credentials

Each credential is an immutable ACDC, with the entire hierarchy forming a verifiable persistent data structure.

Schema Registry: vLEI maintains a registry of credential schemas, each identified by a SAID. The schemas themselves are persistent data structures—once published, they cannot be modified, only superseded by new versions with new SAIDs.

Lifecycle Management

Creation Phase:

1. Schema selection and validation
2. Attribute population
3. SAID generation
4. Issuer signature
5. TEL issuance event

Active Phase:

1. Presentation to verifiers
2. Graduated disclosure as needed
3. Chain verification
4. Status checking via TEL

Revocation Phase:

1. TEL revocation event (ACDC remains unchanged)
2. Verifiers check TEL before accepting presentations
3. Historical validity preserved for audit purposes

Related Structures

Key Event Logs (KELs): Provide the authoritative key state for ACDC issuers. KELs are themselves persistent data structures with append-only, cryptographically chained events.

Transaction Event Logs (TELs): Manage credential lifecycle status. TELs are persistent data structures anchored to KELs, tracking issuance and revocation without modifying ACDCs.

JSON Schemas: Define the structure and validation rules for ACDCs. Schemas are identified by SAIDs and form part of the persistent data structure ecosystem.

Ricardian Contracts: Legal language embedded in the r (rules) field of ACDCs. These contracts are persistent—once signed, they cannot be altered, providing legal certainty.

Security Properties

Duplicity Detection

The immutability of persistent data structures enables duplicity detection—the ability to detect when an issuer creates conflicting versions of credentials:

Internal Consistency: A single ACDC is internally consistent if its SAID correctly identifies its content. Any tampering breaks this consistency.

External Consistency: Multiple copies of an ACDC with the same SAID must be identical. If different content exists with the same SAID, duplicity is evident.

Witness/Watcher Networks: KERI's infrastructure of witnesses and watchers maintains copies of KELs and can detect if an issuer attempts to create conflicting versions of events or credentials.

Cryptographic Strength

Persistent data structures in ACDC rely on cryptographic hash functions with specific security properties:

Collision Resistance: It must be computationally infeasible to find two different inputs that produce the same SAID. This ensures each unique ACDC has a unique identifier.

Pre-image Resistance: Given a SAID, it must be computationally infeasible to find the original content. This protects against rainbow table attacks (mitigated further by the UUID nonce).

Second Pre-image Resistance: Given an ACDC and its SAID, it must be computationally infeasible to find different content with the same SAID.

KERI supports multiple hash algorithms (Blake3-256, SHA-256, SHA3-256) with approximately 128 bits of cryptographic strength, providing post-quantum security for hash-based commitments.

Privacy Considerations

Selective Disclosure: The persistent data structure design enables privacy-preserving disclosure patterns where only necessary attributes are revealed, with the rest remaining as cryptographic commitments (SAIDs).

Unlinkability: The UUID nonce in each ACDC prevents correlation through SAID analysis. Different presentations of the same credential data can use different UUIDs, producing different SAIDs.

Chain-Link Confidentiality: Contractual restrictions can be embedded in the rules section, creating legal obligations for recipients to protect disclosed information.

Performance Characteristics

Concurrency Benefits

The immutability of persistent data structures provides significant concurrency advantages:

Lock-Free Reads: Multiple parties can read and verify ACDCs simultaneously without coordination or locking mechanisms.

Distributed Verification: Verifiers can independently validate ACDCs without contacting the issuer or any central authority.

Caching: Immutable ACDCs can be safely cached indefinitely—once verified, they never need re-verification unless key state changes.

Storage Efficiency

Structural Sharing: Multiple ACDCs can reference the same schemas, edge blocks, and attribute blocks through SAIDs, enabling efficient storage through deduplication.

Compact Variants: The ability to store only SAIDs for sections reduces storage requirements while maintaining verifiability.

Graduated Disclosure: Issuers can store full ACDCs while distributing compact variants, reducing bandwidth and storage requirements for recipients.

Comparison with Traditional Approaches

vs. Mutable Databases

Traditional CRUD (Create, Read, Update, Delete) databases allow in-place modification of records. This creates several challenges for verifiable credentials:

Verification Complexity: Verifiers must trust the database hasn't been tampered with, requiring complex audit logs and access controls.

Temporal Ambiguity: It's unclear which version of a record was valid at a given time without extensive versioning infrastructure.

Signature Invalidation: Modifying signed data invalidates signatures, requiring re-signing and breaking the chain of trust.

Persistent data structures eliminate these issues through immutability—what is signed remains signed and verifiable indefinitely.

vs. Blockchain

Blockchains provide immutability through distributed consensus, but with significant trade-offs:

Scalability: Blockchains require global consensus, limiting throughput. Persistent data structures in ACDC scale horizontally—each issuer manages their own credentials independently.

Privacy: Blockchain data is typically public. ACDCs support graduated disclosure and selective revelation.

Governance: Blockchains require shared governance of the consensus mechanism. KERI's persistent data structures are autonomic—each controller governs their own identifiers and credentials.

Performance: Blockchain writes require consensus latency. ACDC creation is instantaneous, with verification being the only distributed operation.

Future Directions

Post-Quantum Considerations

The persistent data structure design in ACDC is inherently post-quantum resistant for hash-based commitments:

Hash Function Agility: CESR's derivation codes enable algorithm migration. As quantum computers threaten current hash functions, new algorithms can be adopted without changing the fundamental architecture.

Pre-rotation Protection: KERI's pre-rotation mechanism uses hash commitments to future keys, providing quantum resistance even if current signing keys are compromised.

Signature Algorithm Migration: While digital signatures may require post-quantum algorithms (e.g., CRYSTALS-Dilithium), the persistent data structure pattern remains valid—only the signature primitives change.

Scalability Enhancements

Sharding: Large credential graphs could be sharded across multiple storage systems, with each shard maintaining its persistent data structure properties.

Compression: Advanced compression techniques could reduce storage requirements while maintaining the ability to reconstruct canonical forms for verification.

Incremental Verification: Techniques for verifying only changed portions of credential chains could improve performance for large graphs.

Interoperability

W3C VC Integration: ACDCs can be transformed into W3C Verifiable Credentials through unidirectional or bidirectional transformations, enabling interoperability with existing VC ecosystems.

DID Method Integration: The did:keri and did:webs DID methods provide standard interfaces to KERI-based persistent data structures.

Legacy System Bridges: Adapters can translate between traditional mutable credential systems and ACDC's persistent data structures, enabling gradual migration.

Conclusion

Persistent data structures in KERI/ACDC represent a fundamental architectural pattern that enables verifiable, immutable, and distributable credentials. By borrowing concepts from functional programming and applying them to cryptographic identity systems, ACDC achieves properties that are difficult or impossible in traditional mutable database architectures:

• Verifiability: Any party can independently verify credential integrity
• Immutability: Signed content cannot be altered without detection
• Concurrency: Multiple parties can safely read and verify simultaneously
• Scalability: Horizontal scaling through independent issuer management
• Privacy: Graduated disclosure without compromising verifiability

These properties make persistent data structures the foundation for building trustworthy, decentralized credential ecosystems that can operate at internet scale without relying on centralized authorities or shared infrastructure.

Index by SAID: Primary index should be by SAID for O(1) lookup. Secondary indexes by issuer AID, schema SAID, or attribute values enable efficient queries.

Security Best Practices

UUID Generation: The u field MUST use cryptographically secure random number generation. Weak UUIDs enable correlation attacks.

Key State Verification: Always verify the issuer's key state from their KEL before trusting signatures. Cached key state may be stale.

Duplicity Detection: Implement watcher networks or witness verification to detect if issuers create conflicting ACDCs with the same SAID.

Schema Validation: Verify ACDCs conform to their declared schemas. Schema violations may indicate malicious or buggy issuers.

Interoperability

Multiple Serialization Formats: Support JSON, CBOR, and MGPK serialization. All formats must produce identical SAIDs for the same content.

CESR Streaming: For high-performance applications, use CESR streaming format which enables efficient parsing and pipelining.

W3C VC Compatibility: Provide transformation functions to convert ACDCs to/from W3C Verifiable Credentials for ecosystem interoperability.

Error Handling

SAID Mismatch: If computed SAID doesn't match embedded SAID, the ACDC has been tampered with—reject immediately.

Signature Failure: If signature verification fails, either the ACDC was modified or signed with wrong keys—reject and log for security monitoring.

Schema Violation: If ACDC doesn't conform to schema, treat as malformed—reject and potentially blacklist issuer.

Missing Dependencies: If referenced ACDCs (via edge SAIDs) are unavailable, either fetch them or defer verification until available.