Structural Constraints

The graph-fragment architecture imposes critical structural constraints:

DAG Requirement: All ACDC chains MUST form directed acyclic graphs. The specification explicitly states: "The set of ACDCs disclosed in a presentation exchange MUST be chained and form a directed acyclic graph (DAG) with at least one vertex and zero or more edges pointing to other vertices."

This constraint ensures:

• No circular dependencies in credential chains
• Deterministic traversal and verification order
• Prevention of infinite loops during validation
• Clear provenance chains from root to leaf credentials

Minimum Viable Fragment: A valid graph-fragment requires:

• At least one vertex (the ACDC itself)
• Zero or more edges (connections to other ACDCs)
• Cryptographic binding via SAIDs for all components

Data Format

Top-Level ACDC Structure

Graph-fragments are serialized as JSON, CBOR, or MGPK field maps with mandatory insertion-ordered fields. The normative top-level structure includes:

{
  "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): Protocol identification with regex-able format encoding version, serialization type, size
• d (SAID): Self-referential cryptographic digest serving as the node identifier
• u (UUID): Optional high-entropy nonce for privacy protection (distinguishes public vs private ACDCs)
• i (Issuer AID): Autonomic Identifier of the credential issuer
• ri (Registry Identifier): Optional link to TEL for issuance/revocation tracking
• s (Schema): SAID reference or embedded schema block defining credential structure
• a (Attribute): SAID reference or embedded attribute block (node properties)
• e (Edge): SAID reference or embedded edge block (graph connections)
• r (Rule): SAID reference or embedded rule block for logic and constraints

Edge Section Structure

The Edge section (e field) defines the graph-fragment's connections to other ACDCs. The specification provides detailed edge semantics:

Edge Types:

1. I2I (Issuer-to-Issuee): Default operator requiring the issuer of a child credential to be the issuee (subject) of the parent credential. This represents direct delegation chains.

2. NI2I (Not-Issuer-to-Issuee): Permissive operator allowing any identifier to chain a child credential to a parent regardless of relationship. Used for referencing or associating credentials without implying delegated authority.

3. DI2I (Delegated-Issuer-to-Issuee): Extends I2I to include formally recognized delegates, enabling security through the single responsibility pattern and reduced exposure of parent AID signing keys.

Edge Operators: The edge section supports logical operators for complex authorization logic:

"e": {
  "d": "EFH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZIl3MOA",
  "boss": {
    "o": "AND",
    "edges": [
      "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY",
      "EG71iheqcywJcnjtJtQIYPvAu6DZIl3MORH3dCdoFOLB"
    ]
  }
}

This structure enables:

• Unary operators: Operating on single edges
• M-ary operators: Operating on edge groups (AND, OR, NOT)
• Nested operators: Hierarchical logical expressions
• Weighted edges: Supporting threshold authorization schemes

Compact vs Full Variants

Graph-fragments support multiple disclosure levels through graduated disclosure:

Compact Variant: Uses SAIDs for all sections:

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

Full Variant: Expands all sections with complete content:

{
  "v": "ACDC10JSON00011c_",
  "d": "EAdXt3gIXOf2BBWNHdSXCJnFJL5OuQPyM5K0neuniccM",
  "i": "did:keri:EBkPreYpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDIPM",
  "s": {
    "d": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A",
    "$schema": "https://json-schema.org/draft/2020-12/schema",
    "type": "object",
    "properties": {...}
  },
  "a": {
    "d": "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY",
    "i": "did:keri:EpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDI",
    "dt": "2021-06-27T21:26:21.233257+00:00",
    "LEI": "254900OPPU84GM83MG36"
  },
  "e": {
    "d": "EFH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZIl3MOA",
    "qvi": {
      "n": "EpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDI",
      "s": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A"
    }
  }
}

The specification states: "An Issuer commitment via a signature to any variant of ACDC (compact, full, etc) makes a cryptographic commitment to the top-level section fields shared by all variants of that ACDC." This ensures that signing the compact variant provides integrity proof for the entire graph-fragment tree.

Operations

Fragment Creation

Creating a graph-fragment involves several cryptographic operations:

1. Schema Definition: Define the credential structure using JSON Schema:

{
  "$schema": "https://json-schema.org/draft/2020-12/schema",
  "type": "object",
  "properties": {
    "LEI": {"type": "string"},
    "issuanceDate": {"type": "string", "format": "date-time"}
  },
  "required": ["LEI"]
}

2. SAID Computation: Calculate self-addressing identifiers for all sections using the SAID protocol. The SAID is computed over the field map with the SAID field itself set to a dummy value, then replaced with the actual digest.

3. Attribute Population: Fill the attribute section with credential claims:

{
  "d": "EEveY4-9XgOcLxUderzwLIr9Bf7V_NHwY1lkFrn9y2PY",
  "i": "did:keri:EpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDI",
  "dt": "2021-06-27T21:26:21.233257+00:00",
  "LEI": "254900OPPU84GM83MG36"
}

4. Edge Definition: Specify connections to other ACDCs:

{
  "d": "EFH3dCdoFOLe71iheqcywJcnjtJtQIYPvAu6DZIl3MOA",
  "qvi": {
    "n": "EpZfFk66jpf3uFv7vklXKhzBrAqjsKAn2EDI",
    "s": "ED6jrVPTzlSkUPqGGeIZ8a8FWS7a6s4reAXRZOkogZ2A"
  }
}

5. Top-Level Assembly: Combine all sections with version string and issuer AID.

6. Signature Attachment: Sign the ACDC using CESR signature attachments bound to the issuer's KEL.

Fragment Verification

Verifying a graph-fragment requires multiple validation steps:

1. SAID Verification: Recompute all SAIDs and verify they match the provided values. This ensures content integrity.

2. Signature Verification: Validate the issuer's signature against their current key state from the KEL:

def verify_fragment(acdc, signature, issuer_kel):
    # Retrieve current key state
    key_state = issuer_kel.get_key_state(acdc['i'])
    
    # Verify signature
    if not key_state.verify(acdc['d'], signature):
        raise ValidationError("Invalid signature")
    
    # Verify all SAIDs
    for section in ['s', 'a', 'e', 'r']:
        if section in acdc:
            if not verify_said(acdc[section]):
                raise ValidationError(f"Invalid SAID in {section}")
    
    return True

3. Schema Validation: Validate the attribute section against the schema:

import jsonschema

def validate_against_schema(attributes, schema):
    try:
        jsonschema.validate(instance=attributes, schema=schema)
        return True
    except jsonschema.ValidationError as e:
        raise ValidationError(f"Schema validation failed: {e}")

4. Edge Validation: Verify edge semantics and operator logic:

def validate_edges(acdc, parent_acdc):
    edge_section = acdc.get('e', {})
    
    # Check I2I constraint
    if edge_section.get('operator') == 'I2I':
        if acdc['i'] != parent_acdc['a']['i']:
            raise ValidationError("I2I constraint violated")
    
    # Verify edge SAIDs point to valid ACDCs
    for edge_said in extract_edge_saids(edge_section):
        if not verify_acdc_exists(edge_said):
            raise ValidationError(f"Edge target {edge_said} not found")
    
    return True

5. DAG Validation: Ensure the fragment chain forms a valid DAG:

def validate_dag(acdc_chain):
    visited = set()
    rec_stack = set()
    
    def has_cycle(acdc_said):
        visited.add(acdc_said)
        rec_stack.add(acdc_said)
        
        acdc = retrieve_acdc(acdc_said)
        for edge_said in extract_edge_saids(acdc.get('e', {})):
            if edge_said not in visited:
                if has_cycle(edge_said):
                    return True
            elif edge_said in rec_stack:
                return True
        
        rec_stack.remove(acdc_said)
        return False
    
    for acdc in acdc_chain:
        if acdc['d'] not in visited:
            if has_cycle(acdc['d']):
                raise ValidationError("Cycle detected in ACDC chain")
    
    return True

Fragment Traversal

Traversing graph-fragments enables verification of credential chains:

Depth-First Traversal:

def traverse_fragment_dfs(root_said, visitor_func):
    visited = set()
    
    def dfs(acdc_said):
        if acdc_said in visited:
            return
        
        visited.add(acdc_said)
        acdc = retrieve_acdc(acdc_said)
        visitor_func(acdc)
        
        # Traverse edges
        for edge_said in extract_edge_saids(acdc.get('e', {})):
            dfs(edge_said)
    
    dfs(root_said)

Breadth-First Traversal:

from collections import deque

def traverse_fragment_bfs(root_said, visitor_func):
    visited = set()
    queue = deque([root_said])
    
    while queue:
        acdc_said = queue.popleft()
        
        if acdc_said in visited:
            continue
        
        visited.add(acdc_said)
        acdc = retrieve_acdc(acdc_said)
        visitor_func(acdc)
        
        # Enqueue edges
        for edge_said in extract_edge_saids(acdc.get('e', {})):
            if edge_said not in visited:
                queue.append(edge_said)

Fragment Composition

Graph-fragments can be composed into complex structures:

Chaining Fragments: Create delegation chains by linking ACDCs through edges:

{
  "root_acdc": {
    "d": "ERootSAID",
    "i": "did:keri:ERootIssuer",
    "e": {
      "delegate": {
        "n": "EDelegateSAID",
        "s": "ESchemaForDelegate"
      }
    }
  },
  "delegate_acdc": {
    "d": "EDelegateSAID",
    "i": "did:keri:EDelegateIssuer",
    "e": {
      "parent": {
        "n": "ERootSAID",
        "s": "ESchemaForRoot"
      }
    }
  }
}

Aggregating Fragments: Combine multiple ACDCs using logical operators:

{
  "d": "EAggregateACDC",
  "e": {
    "requirements": {
      "o": "AND",
      "edges": [
        "ECredential1SAID",
        "ECredential2SAID",
        {
          "o": "OR",
          "edges": [
            "ECredential3SAID",
            "ECredential4SAID"
          ]
        }
      ]
    }
  }
}

This enables complex authorization logic: "Require Credential1 AND Credential2 AND (Credential3 OR Credential4)".

Usage Context

IPEX Protocol Integration

Graph-fragments are exchanged using the IPEX (Issuance and Presentation Exchange) protocol. The specification states:

"A presentation exchange is an exchange that provides disclosure of one or more ACDCs between a Discloser and a Disclosee. The set of ACDCs disclosed in a presentation exchange MUST be chained and form a directed acyclic graph (DAG)."

IPEX messages carry graph-fragments with graduated disclosure:

{
  "v": "IPEX10JSON00011c_",
  "t": "exn",
  "d": "EMessageSAID",
  "i": "did:keri:EDiscloserAID",
  "p": "EPriorEventSAID",
  "dt": "2021-06-27T21:26:21.233257+00:00",
  "r": "/ipex/grant",
  "q": {},
  "a": {
    "acdc": "ECompactACDCSAID",
    "iss": "EIssuerAID",
    "anc": "EAnchorSAID"
  }
}

vLEI Ecosystem Implementation

The GLEIF vLEI ecosystem extensively uses graph-fragments for organizational credentials:

QVI Credential Chain:

GLEIF Root AID
  └─> GLEIF External Delegated AID (GEDA)
      └─> QVI Credential (graph-fragment)
          └─> Legal Entity Credential (graph-fragment)
              ├─> OOR Credential (graph-fragment)
              └─> ECR Credential (graph-fragment)

Each credential is a graph-fragment with edges pointing to parent credentials, forming a verifiable delegation chain from GLEIF's root authority to individual role credentials.

Example vLEI Graph-Fragment:

{
  "v": "ACDC10JSON00011c_",
  "d": "ELegalEntityCredSAID",
  "i": "did:keri:EQVIAID",
  "s": "ELegalEntitySchemaSAID",
  "a": {
    "d": "EAttributesSAID",
    "i": "did:keri:ELegalEntityAID",
    "LEI": "254900OPPU84GM83MG36",
    "legalName": "Example Corporation"
  },
  "e": {
    "d": "EEdgesSAID",
    "qvi": {
      "n": "EQVIAID",
      "s": "EQVICredentialSchemaSAID",
      "o": "I2I"
    }
  }
}

The edge section references the QVI credential using I2I operator, ensuring the Legal Entity credential issuer (QVI) is the issuee of the parent QVI authorization credential.

Authentic Data Supply Chains

Graph-fragments enable authentic data supply chains where data transformations maintain verifiable provenance:

Data Source ACDC (fragment)
  └─> Processing Step 1 ACDC (fragment)
      └─> Processing Step 2 ACDC (fragment)
          └─> Final Output ACDC (fragment)

Each transformation step is a graph-fragment that:

• References input data via edges
• Contains transformation metadata in attributes
• Maintains cryptographic binding to the processor's AID
• Enables end-to-end verification of the data pipeline

Knowledge Graph Construction

Graph-fragments serve as building blocks for verifiable knowledge graphs:

{
  "entity_acdc": {
    "d": "EEntitySAID",
    "a": {
      "type": "Organization",
      "name": "Example Corp"
    },
    "e": {
      "relationships": [
        {
          "predicate": "employs",
          "object": "EPersonSAID"
        },
        {
          "predicate": "locatedIn",
          "object": "ELocationSAID"
        }
      ]
    }
  }
}

This enables construction of semantic graphs with:

• Verifiable entity properties (attributes)
• Cryptographically bound relationships (edges)
• Provenance tracking for all assertions
• Privacy-preserving selective disclosure

Lifecycle Management

Graph-fragments have defined lifecycle stages:

1. Issuance: Fragment created and signed by issuer, anchored to TEL for revocation tracking

2. Active: Fragment is valid and can be presented/verified

3. Revoked: Issuer publishes revocation event to TEL, fragment becomes invalid

4. Expired: Time-based expiration (if specified in attributes) invalidates fragment

5. Superseded: New version of fragment issued, old version deprecated

The TEL provides the registry mechanism:

{
  "v": "TEL10JSON00011c_",
  "t": "iss",
  "d": "ETELEventSAID",
  "i": "ERegistryAID",
  "s": "0",
  "ri": "ERegistrySAID",
  "dt": "2021-06-27T21:26:21.233257+00:00",
  "a": {
    "acdc": "EFragmentSAID",
    "status": "issued"
  }
}

Revocation updates the status:

{
  "v": "TEL10JSON00011c_",
  "t": "rev",
  "d": "ERevocationEventSAID",
  "i": "ERegistryAID",
  "s": "1",
  "p": "ETELEventSAID",
  "ri": "ERegistrySAID",
  "dt": "2021-07-15T14:30:00.000000+00:00",
  "a": {
    "acdc": "EFragmentSAID",
    "status": "revoked"
  }
}

Scalability and Performance

Graph-fragments enable scalable verification through several mechanisms:

Selective Verification: Verifiers can validate specific fragments without processing entire graphs:

def verify_fragment_selective(fragment_said, required_depth=1):
    fragment = retrieve_acdc(fragment_said)
    verify_fragment(fragment)
    
    if required_depth > 0:
        for edge_said in extract_edge_saids(fragment.get('e', {})):
            verify_fragment_selective(edge_said, required_depth - 1)

Parallel Verification: Independent fragments can be verified concurrently:

import concurrent.futures

def verify_fragments_parallel(fragment_saids):
    with concurrent.futures.ThreadPoolExecutor() as executor:
        futures = [executor.submit(verify_fragment, said) 
                   for said in fragment_saids]
        results = [f.result() for f in concurrent.futures.as_completed(futures)]
    return all(results)

Caching: Verified fragments can be cached to avoid redundant verification:

class FragmentCache:
    def __init__(self):
        self.cache = {}
    
    def verify_cached(self, fragment_said):
        if fragment_said in self.cache:
            return self.cache[fragment_said]
        
        result = verify_fragment(fragment_said)
        self.cache[fragment_said] = result
        return result

The specification emphasizes that graph-fragments support the authentic web vision where "you can hop into the graph to verify any fragment of the graph" without requiring global state or complete graph traversal.

Security Considerations

Graph-fragments provide several security properties:

Cryptographic Integrity: SAIDs ensure tamper-evidence. Any modification to a fragment invalidates its SAID and breaks the cryptographic chain.

Non-Repudiation: Signatures bound to KELs provide non-repudiable proof of issuance. The issuer cannot deny creating the fragment.

Delegation Control: Edge operators (I2I, DI2I, NI2I) enforce delegation semantics, preventing unauthorized credential chains.

Privacy Protection: Graduated disclosure enables minimal information sharing. Compact variants reveal only SAIDs, not content.

Revocation Transparency: TEL-based revocation provides verifiable status without requiring online checks to centralized services.

The graph-fragment architecture thus provides a foundation for building verifiable, privacy-preserving, and scalable credential ecosystems that align with the authentic web vision of a globally verifiable data structure.

Interoperability

• Follow ACDC specification exactly for field ordering
• Support all three serialization formats
• Implement IPEX protocol for fragment exchange
• Ensure compatibility with KERI ecosystem tools
• Provide clear error messages for validation failures