KAACE (KERI Agreement Algorithm for Control Establishment) is a Byzantine Fault Tolerant consensus algorithm that enables witnesses to reach agreement on key events by ensuring each witness observes identical event versions and all witness receipts are exchanged, thereby establishing verifiable control authority over an identifier through coordinated witness consensus.
Related Concepts
No related concepts available
Comprehensive Explanation
KERI Agreement Algorithm for Control Establishment (KAACE)
Process Definition
KAACE (also written as KA2CE or KA<sup>2</sup>CE) is KERI's fundamental consensus mechanism for establishing agreement about key events among witnesses. The algorithm solves the critical problem of distributed agreement in KERI's decentralized architecture without requiring blockchain-style global consensus or total ordering of events.
What KAACE Accomplishes
KAACE enables control establishment - the verifiable determination of who has authoritative control over an autonomic identifier (AID) at any point in time. This is achieved through coordinated witness agreement on the key event log (KEL) that records all key management operations for an identifier.
The algorithm ensures that:
Unique agreement: At most one valid agreement occurs, or none at all
Duplicity detection: Conflicting versions of events are detectable
Byzantine fault tolerance: The system remains secure despite potentially faulty witnesses
Accountability: Controllers can be held responsible for agreed-upon key states
When KAACE is Used
KAACE operates in indirect mode, where identifiers require high availability and persistent verifiability even when the is offline. This contrasts with , where controllers and validators communicate directly without witness infrastructure.
Implementation Notes
Critical Implementation Requirements
Witness Infrastructure
Persistent Storage: Witnesses MUST maintain persistent storage for:
Complete KELs for all witnessed identifiers
All receipts (both self-generated and received from other witnesses)
Validators need to verify the authoritative key state
Duplicity must be detected across the witness network
Key Participants
KAACE involves three primary roles:
Controller: Creates key events and initiates the agreement process by promulgating receipted events to witnesses
Witnesses: Designated entities that observe events, create receipts, and exchange receipts with other witnesses to establish agreement
Validators: Entities that verify the agreed-upon key state by examining witness receipts and detecting potential duplicity
Process Flow
The KAACE algorithm follows a carefully orchestrated sequence that separates control between the controller's promulgation network (witnesses) and the validator's confirmation network (watchers).
Step 1: Controller Receipt Generation
The process begins when the controller creates a new key event (typically an inception event or rotation event). The controller:
Detect any duplicity by comparing versions across witnesses
Establish the authoritative key state based on witness consensus
Validators operate from their own locus-of-control, making independent trust decisions without requiring controller permission or witness coordination.
Technical Requirements
Cryptographic Requirements
KAACE depends on several cryptographic mechanisms:
KAACE deliberately sacrifices liveness for safety and decentralization:
No Liveness Guarantee: Unlike traditional consensus algorithms, KAACE does not guarantee that agreement will eventually occur. The algorithm ensures that if agreement occurs, it is unique, but agreement may fail entirely if:
Insufficient witnesses are available
Network partitions prevent receipt exchange
Witnesses provide conflicting receipts
Asynchronous Operation: The algorithm operates asynchronously:
No global clock synchronization required
Witnesses process events independently
Receipt exchange proceeds at network speed
Validators query witnesses on-demand
Timeout Handling: Implementations must handle:
Receipt exchange timeouts
Witness unavailability
Partial agreement scenarios
Recovery from transient failures
Witness Pool Configuration
The algorithm requires careful witness pool configuration:
Minimum Pool Size: According to vLEI governance requirements, witness pools must have:
Minimum of 5 witnesses for production systems
Sufficient diversity to prevent collusion
Geographic and organizational distribution
Threshold Calculation: The TOAD (Threshold of Accountable Duplicity) determines:
Minimum number of confirming witnesses (M)
Maximum tolerable faulty witnesses (F)
Relationship: M >= N - F where N is total witnesses
Ample constraint: (N + F + 1)/2 <= M <= N - F
Witness Selection: Controllers must:
Choose witnesses with appropriate security properties
Controller creates rotation event with new witness configuration
Both old and new witnesses must participate
Agreement requires coordination across both witness sets
Successful rotation transfers authority to new witnesses
Delegation: When delegating authority:
Delegator creates delegation event
Delegate creates delegated inception event
Both events must achieve witness agreement
Cryptographic seals link delegator and delegate KELs
Best Practices
Witness Pool Design:
Use geographically distributed witnesses to prevent regional failures
Select witnesses with independent infrastructure to avoid common-mode failures
Implement monitoring to detect witness unavailability
Plan for witness rotation to maintain security over time
Threshold Configuration:
Set thresholds using ample calculations to ensure Byzantine fault tolerance
Balance security (higher thresholds) with availability (lower thresholds)
Consider weighted thresholds for heterogeneous witness pools
Document threshold rationale for governance compliance
Duplicity Prevention:
Implement first-seen policies at witnesses
Use cryptographic commitments (pre-rotation) to prevent key compromise attacks
Deploy watchers to monitor for duplicity across the network
Establish incident response procedures for detected duplicity
Performance Optimization:
Use efficient serialization (CESR) to minimize message size
Implement receipt caching to reduce redundant queries
Deploy witness proxies for high-availability scenarios
Monitor receipt exchange latency to detect network issues
Integration Considerations
Application Integration:
Applications should query multiple witnesses to verify agreement
Implement timeout handling for witness unavailability
Cache verified key states to reduce witness queries
Handle partial agreement scenarios gracefully
Infrastructure Integration:
Witness services require persistent storage for KELs and receipts
Implement API endpoints for receipt queries (KAPI)
Support OOBI resolution for witness discovery
Integrate with monitoring systems for operational visibility
Governance Integration:
Document witness selection criteria for compliance
Implement audit logging of witness operations
Establish SLAs for witness availability
Define incident response procedures for witness failures
Algorithmic Innovation
KAACE represents a novel simplification of PBFT-class algorithms with unique characteristics:
Relationship to Byzantine Fault Tolerance
KAACE inherits Byzantine fault tolerance properties from PBFT (Practical Byzantine Fault Tolerance) but simplifies the algorithm by:
Eliminating Total Ordering: Unlike blockchain consensus, KAACE does not require global ordering of all events across all identifiers. Each KEL maintains its own linear ordering, but KELs are independent.
Separating Networks: KAACE introduces a novel separation of control using:
Promulgation networks (witnesses) for distributed consensus
Confirmation networks (watchers) for independent verification
This separation is described as "what if PBFT and Stellar had a baby" - combining PBFT's safety properties with Stellar's network separation approach.
Properties Trade-offs
Sacrificed Properties:
Liveness: No guarantee that agreement will occur
Total Ordering: No global event ordering across identifiers
Maintained Properties:
Safety: Guarantees at most one agreement or none
Decentralization: No central authority required
Portability: Identifiers work across any infrastructure
Permissionless: No gatekeepers for identifier creation
Per-identifier consensus instead of global consensus
Traditional BFT (PBFT, Raft):
No leader election
No view changes
No global membership
Simpler message patterns
Stellar Consensus Protocol:
Similar network separation concept
Different trust model (quorum slices vs. witness pools)
Different use case (payments vs. key management)
Security Properties
KAACE provides several critical security guarantees:
Immune Agreement
The algorithm ensures immune agreement - a supermajority consensus that is immune to certain attacks:
Protection Against:
Dead attacks: Attacks on stale key states cannot affect current state
Live attacks: Compromise of current keys cannot forge pre-rotated keys
Duplicity: Conflicting versions are detectable by validators
Byzantine witnesses: Up to F faulty witnesses can be tolerated
Formal Guarantee: "Satisfaction of this constraint guarantees that at most one sufficient agreement occurs or none at all despite a dishonest controller but where at most F of the witnesses are potentially faulty."
First-Seen Rule: Honest witnesses maintain immutable first-seen copies of events, making duplicity evident when:
Controller publishes conflicting versions
Witnesses provide inconsistent receipts
Validators compare versions across witnesses
Watcher Networks: Independent watchers monitor for duplicity by:
Querying multiple witnesses
Comparing event versions
Detecting inconsistencies
Alerting on discovered duplicity
Attack Resistance
The algorithm resists several attack vectors:
Sybil Attacks: Prevented by:
Controller designation of specific witnesses
Cryptographic witness identifiers
Threshold requirements for agreement
Eclipse Attacks: Mitigated by:
Multiple independent witnesses
Geographic distribution
Watcher network monitoring
Compromise Recovery: Enabled by:
Pre-rotation of keys
Witness coordination for rotations
Cryptographic commitments to next keys
Implementation Considerations
Implementing KAACE requires careful attention to:
Witness Infrastructure:
Persistent storage for KELs and receipts
Network connectivity for receipt exchange
Cryptographic key management for witness identities
API endpoints for validator queries
Controller Software:
Event generation and signing
Witness pool management
Receipt collection and verification
Timeout and error handling
Validator Software:
Multi-witness querying
Receipt verification
Duplicity detection
Key state caching
Monitoring and Operations:
Witness availability monitoring
Receipt exchange latency tracking
Duplicity alert systems
Incident response procedures
KAACE represents a fundamental innovation in distributed consensus, enabling KERI's vision of truly self-sovereign, portable identifiers with cryptographic security guarantees.