Blockchain Alternatives: Technologies like IOTA's Tangle and Hedera Hashgraph use DAG structures instead of linear chains, allowing parallel transaction processing while maintaining causal ordering.

Citation Networks: Academic papers form DAGs where edges represent citations—papers can only cite previously published work, naturally creating acyclic structures.

In traditional Public Key Infrastructure (PKI), certificate chains form tree structures (a special case of DAGs) where:

• Root Certificate Authorities sit at the top
• Intermediate CAs form middle layers
• End-entity certificates are leaves
• Each certificate is signed by exactly one parent

However, traditional PKI certificate chains have significant limitations:

• Centralized trust: Root CAs are single points of failure
• Rigid hierarchies: Tree structures don't support complex delegation patterns
• No key rotation: Certificate revocation requires external infrastructure
• Limited expressiveness: Cannot represent multi-party authorizations or threshold schemes

KERI's Approach

KERI leverages DAG structures in two primary contexts:

ACDCs as DAG Fragments

Authentic Chained Data Containers (ACDCs) are explicitly designed as labeled property graph fragments that form DAGs when chained together. Each ACDC represents:

A single vertex with:

• Node properties (the credential's attributes)
• Metadata (issuer, schema, timestamps)
• Cryptographic commitments (SAIDs)

Zero or more directed edges to other ACDCs via the edges section (e field), where each edge:

• Points to another ACDC by its SAID
• Specifies the relationship type through edge operators (I2I, DI2I, NI2I)
• May include logical operators (AND, OR, NOT) for complex authorization logic
• Carries edge properties (metadata about the relationship)

The ACDC specification mandates that disclosed ACDCs in a presentation exchange MUST form a DAG with:

• At least one vertex (minimum one credential)
• Zero or more edges (credentials may be standalone or chained)
• No cycles (preventing circular credential dependencies)

This DAG structure enables:

Verifiable Credential Chains: A Legal Entity vLEI credential chains to a QVI credential, which chains to GLEIF's root credential, forming a verifiable path of authority.

Selective Disclosure: A verifier can request specific subgraphs of the credential DAG, receiving only the credentials and edges necessary to verify particular claims.

Graduated Disclosure: Credentials can be presented in compact form (SAIDs only) initially, with full details disclosed progressively as trust relationships develop.

Complex Authorization Patterns: Multi-party authorizations, threshold schemes, and conditional delegations can be expressed through edge operators and logical combinations.

Delegation Trees as DAGs

KERI delegation creates hierarchical structures where:

• A delegator AID authorizes a delegate AID
• Delegates can themselves become delegators (nested delegation)
• The resulting structure forms a delegation tree (a special DAG)

Key properties:

Cooperative Delegation: Both delegator and delegate must cryptographically commit to the delegation through seals in their respective KELs.

Revocability: Delegators can revoke delegations through rotation events, pruning branches of the delegation tree.

Bivalent Security: The delegation DAG enables bivalent key management where:

• Root identifiers use high-security key management
• Leaf identifiers may use more convenient but less secure methods
• Compromise of leaves doesn't compromise the root
• Recovery flows from root to leaves through the delegation structure

Scalability: Organizations can create delegation hierarchies matching their operational structure, with each branch independently managed.

Verification Algorithms

The DAG structure enables efficient verification through topological traversal:

1. Identify the root(s): Find credentials with no incoming edges (self-signed or root authority credentials)
2. Topological sort: Order credentials such that all dependencies are verified before dependents
3. Traverse in order: Verify each credential's cryptographic integrity and check that referenced credentials (edges) are valid
4. Terminate: The acyclic property guarantees traversal completes in finite time

This approach provides O(V + E) complexity where V is vertices (credentials) and E is edges (references), making verification computationally tractable even for large credential graphs.

Duplicity Detection

The DAG structure supports duplicity detection by:

• Enabling comparison of different versions of credential graphs
• Detecting inconsistencies in credential chains
• Identifying conflicting authorizations or revocations
• Providing ambient verifiability—anyone can verify the graph structure

Practical Implications

Use Cases

vLEI Credential Ecosystem: The GLEIF vLEI implementation creates a five-level DAG:

1. GLEIF Root (no dependencies)
2. QVI Credentials (depend on GLEIF)
3. Legal Entity Credentials (depend on QVI)
4. Authorization Credentials (depend on LE)
5. Role Credentials (depend on Authorization)

Each credential cryptographically chains to its parent through edge SAIDs, forming a verifiable DAG from any role credential back to GLEIF's root authority.

Supply Chain Provenance: ACDCs can model supply chain transformations as a DAG where:

• Raw materials are root vertices
• Manufacturing steps are intermediate vertices with edges to inputs
• Final products are leaves
• Each vertex contains attestations about quality, custody, and transformations

The DAG structure naturally represents bill-of-materials relationships and enables verification of complete provenance chains.

Multi-Party Authorizations: Complex business processes requiring multiple approvals can be modeled as DAGs where:

• Each approval is a vertex (an ACDC)
• Edges represent dependencies ("approval B requires approval A")
• Logical operators express requirements ("need 3 of 5 approvals")
• The final authorization vertex has edges to all required approvals

Benefits

Guaranteed Termination: Verification algorithms always complete because DAG traversal is finite. This prevents denial-of-service attacks through circular credential chains.

Flexible Relationships: Unlike tree structures, DAGs support:

• Multiple parents (a credential can chain to multiple authorizing credentials)
• Shared dependencies (multiple credentials can reference the same parent)
• Complex authorization logic through edge operators

Selective Verification: Verifiers can validate specific subgraphs without processing the entire credential ecosystem, improving privacy and efficiency.

Cryptographic Integrity: Each edge is a SAID reference, creating cryptographic binding between credentials. Tampering with any credential breaks the chain.

Scalability: DAG structures enable:

• Parallel verification of independent branches
• Distributed storage (different parties hold different subgraphs)
• Incremental disclosure (reveal graph structure progressively)

Trade-offs

Complexity: DAG-based credential systems are more complex than simple certificate chains:

• Verification requires graph traversal algorithms
• Presentation logic must handle partial graph disclosure
• Storage and indexing require graph database capabilities

Correlation Risk: The graph structure itself can leak information:

• Edge patterns may reveal organizational structures
• Shared parent credentials create correlation points
• Mitigation requires careful use of selective disclosure and compact variants

Coordination Overhead: Creating credential DAGs requires:

• Multiple parties to coordinate issuance
• Agreement on edge semantics and operators
• Governance frameworks to manage the graph structure

Storage Requirements: Full DAG verification may require:

• Storing or retrieving multiple credentials
• Maintaining graph indexes for efficient traversal
• Caching frequently-accessed subgraphs

Despite these trade-offs, the DAG structure is fundamental to ACDC's ability to provide verifiable, chainable, privacy-preserving credentials that support complex real-world authorization and delegation patterns while maintaining cryptographic integrity and enabling efficient verification.

• Streaming verification that doesn't load entire graph into memory
• Lazy loading of credentials as needed during traversal
• Pruning of verified subgraphs to reduce memory footprint