Comprehensive Explanation

Provenance

Conceptual Definition

Provenance refers to the chronology of ownership, custody, and location of data or objects, providing contextual and circumstantial evidence for authenticity. The term originates from tracking the history of art objects and manuscripts but has expanded to encompass digital data management, where it represents the complete lifecycle documentation of information from creation through all transformations and transfers.

In digital systems, provenance serves three critical functions:

1. Authentication: Establishing the origin and creator of data
2. Integrity verification: Proving data has not been altered inappropriately
3. Chain of custody: Documenting all parties who have controlled or modified the data

Provenance is distinct from but complementary to authenticity. While authenticity proves who created data and that it hasn't been tampered with, provenance provides the historical context of that data's journey through various transformations and custodians. A newspaper story may have authentic provenance (verifiable publication history) without having veracity (truthfulness of content).

Historical Context

Traditional provenance systems relied on paper trails and trusted intermediaries to document custody chains. In physical supply chains, provenance was maintained through:

• Signed transfer documents
• Custody logs maintained by trusted parties
• Physical seals and tamper-evident packaging
• Regulatory oversight and auditing

These systems suffered from fundamental limitations:

• Centralized trust dependencies: Required faith in record-keeping authorities
• Forgery vulnerabilities: Paper documents could be falsified
• Incomplete records: Gaps in documentation broke the chain
• Non-verifiable claims: No cryptographic proof of custody transfers

In digital systems, early provenance approaches used:

• Database audit logs: Centralized records of data modifications
• Digital signatures: Cryptographic proof of specific operations
• Blockchain timestamping: Immutable records of data states
• Certificate chains: Hierarchical trust structures (PKI)

However, these approaches still required trust in infrastructure operators, lacked portability across systems, or couldn't efficiently handle complex data transformation chains.

KERI's Approach

Cryptographic Provenance Through ACDCs

KERI implements provenance through ACDC (Authentic Chained Data Container) structures that provide two coherent mechanisms:

1. Cryptographic Verification of Key States

KERI's Key Event Log (KEL) provides verifiable provenance for Autonomic Identifiers (AIDs) through:

• Inception events: Cryptographically bound origin of identifiers
• Rotation events: Verifiable key state transitions
• Interaction events: Anchored commitments to external data
• Pre-rotation: Forward commitments preventing unauthorized key changes

This creates an append-only, cryptographically chained log where every key state transition is verifiable back to the identifier's inception. The KEL serves as the provenance record for the identifier's control authority.

2. Credential Attestation Chains

ACDCs extend provenance to data through:

• SAID (Self-Addressing Identifier) binding: Each ACDC contains a cryptographic digest of its contents
• Issuer signatures: Non-repudiable commitments from AID controllers
• Edge chaining: Cryptographic links to prerequisite credentials
• Transaction Event Logs (TEL): Verifiable issuance and revocation states

Authentic Provenance Chains (APC)

The specification defines Authentic Provenance Chain (APC) as interlinked presentations of evidence that allow data to be tracked back to its origin in an objectively verifiable way. APCs are implemented through:

Directed Acyclic Graph (DAG) Structure

ACDCs form directed acyclic graphs where:

• Each ACDC is a graph fragment (node with properties)
• Edges reference other ACDCs through SAIDs
• Operators (I2I, DI2I, NI2I) define relationship semantics
• Acyclic property ensures finite traversal and prevents circular dependencies

This structure enables:

• Selective disclosure: Revealing only necessary provenance links
• Compact representation: SAIDs replace full credential content
• Verifiable expansion: Recipients can verify disclosed credentials match SAIDs
• Composable chains: Complex provenance relationships through graph composition

Proof-of-Authorship vs. Proof-of-Authority

KERI distinguishes two types of provenance:

1. Proof-of-Authorship: Verifiable chain establishing who originally created data
2. Proof-of-Authority: Verifiable chain establishing current rights and permissions over data

Example: An author (Terlalu Bonito) creates a book with an ACDC containing:

• Book data with anchoring digest
• Author's signature at publication date (proof-of-authorship)

When rights are sold to Liz Smiley:

• New ACDC establishes proof-of-authority transfer
• Original authorship remains verifiable
• Current control matches the ACDC chain

This separation enables delegation trees where authority can be transferred while maintaining verifiable authorship provenance.

End-to-End Provenance

KERI implements end-to-end provenance through:

Data Flow Transformations

Every data transformation must be provenanced using verifiable data items:

• Input ACDCs: Source credentials with SAIDs
• Transformation logic: Documented processing steps
• Output ACDCs: New credentials referencing inputs
• Operator semantics: Defined relationship types

This creates verifiable data supply chains where:

• Each transformation step is cryptographically bound
• Validators can verify the entire chain
• No trusted intermediaries are required
• Provenance is ambient verifiable (anyone, anywhere, anytime)

Decentralized Autonomic Data (DAD)

The Decentralized Autonomic Data concept establishes that authentic data must be:

• Self-identifying: Contains its own identifier (SAID)
• Self-certifying: Signature verifiable without external trust
• Self-securing: Maintains integrity through cryptographic binding

DAD items maintain provenance through:

• Signed at rest: Signatures preserved for future verification
• Key state at rest: KERI solves maintaining verifiable key state over time
• Persistent verification: No need to reconstruct verifiable structures

Graduated Disclosure and Privacy

KERI's provenance mechanisms support privacy-preserving disclosure:

Compact Disclosure

ACDCs can be presented with:

• SAIDs only: Minimal information leakage
• Selective expansion: Reveal only necessary provenance links
• Cryptographic commitments: Prove relationships without full disclosure

Chain-Link Confidentiality

Provenance chains can include:

• Usage constraints: Legal terms governing data use
• Downstream obligations: Requirements binding all recipients
• Contractual protections: Enforceable confidentiality agreements

This enables contractually protected disclosure where provenance is verifiable but data usage is legally constrained.

Practical Implications

Use Cases

Supply Chain Tracking

Physical supply chains can be digitally twinned through ACDC provenance:

• Each custody transfer creates a new ACDC
• Transformations (manufacturing, packaging) are documented
• Quality certifications chain to source materials
• End consumers verify complete provenance to origin

Credential Ecosystems

The vLEI (verifiable Legal Entity Identifier) ecosystem demonstrates provenance in practice:

• GLEIF Root: Establishes root of trust
• QVI Credentials: Delegated authority from GLEIF
• Legal Entity Credentials: Issued by QVIs
• Role Credentials: Chain to Legal Entity credentials

Each credential's provenance is verifiable back to GLEIF through the ACDC chain.

Data Transformation Pipelines

In analytics and IoT applications:

• Raw sensor data ACDCs establish origin
• Processing steps create derived ACDCs
• Aggregations reference source data
• Final reports maintain verifiable provenance to raw inputs

Benefits

Cryptographic Verifiability

• No trusted intermediaries required
• Mathematical proof of provenance integrity
• Tamper-evident structures detect unauthorized modifications
• Duplicity detection identifies conflicting claims

Portability

• Provenance chains are infrastructure-independent
• Can be verified without access to original issuance systems
• Support identifier portability across platforms
• Enable transfer off ledger from blockchain systems

Scalability

• Selective disclosure reduces bandwidth requirements
• SAID references enable compact representation
• Parallel verification of independent provenance branches
• Ambient verifiability distributes verification load

Privacy Protection

• Graduated disclosure reveals only necessary provenance
• Unlinkability through selective ACDC presentation
• Contractual protections govern downstream use
• Minimal disclosure principles supported

Trade-offs

Complexity

• Provenance chains can become deeply nested
• Graph traversal algorithms required for verification
• Schema composition increases implementation complexity
• Operator semantics require careful specification

Storage Requirements

• Complete provenance chains require storing all ACDCs
• Compact disclosure reduces storage but requires expansion for verification
• Caching strategies needed for frequently accessed chains
• Pruning policies must balance completeness with efficiency

Governance Challenges

• Schema evolution must maintain backward compatibility
• Revocation propagation through provenance chains
• Authority delegation requires clear governance frameworks
• Dispute resolution when provenance claims conflict

Veracity vs. Provenance

KERI provides secure attribution (who said what) but not veracity (whether claims are true):

• Provenance proves the chain of custody
• Truth determination requires additional governance
• Reputation systems needed for trust assessment
• Verifiers must evaluate claim validity independently

Conclusion

Provenance in KERI represents a fundamental shift from trust-based to verification-based data lineage. By combining cryptographic key management (KELs) with chained data containers (ACDCs), KERI enables end-to-end verifiable provenance without requiring trusted intermediaries. This approach supports the vision of an authentic web where all data maintains cryptographically verifiable provenance from origin through all transformations, enabling trust at internet scale through mathematical proof rather than institutional authority.