The algorithm activates whenever:

• A controller publishes a new establishment event (inception or rotation)
• Witnesses must coordinate to provide receipts
• Validators need to verify the authoritative key state
• Duplicity must be detected across the witness network

Key Participants

KAACE involves three primary roles:

1. Controller: Creates key events and initiates the agreement process by promulgating receipted events to witnesses
2. Witnesses: Designated entities that observe events, create receipts, and exchange receipts with other witnesses to establish agreement
3. 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:

1. Generates the event with appropriate cryptographic primitives
2. Signs the event with current authoritative keys
3. Creates its own receipt of the event
4. Prepares the receipted event for promulgation

This initial controller receipt establishes the controller's commitment to the specific event version.

Step 2: Event Promulgation to Witnesses

The controller promulgates (broadcasts) the receipted event to all designated witnesses in its witness pool. This promulgation:

• Delivers the identical event version to each witness
• Includes the controller's receipt as proof of authorship
• Initiates the witness coordination phase
• Establishes the first-seen timestamp at each witness

The promulgation network operates from the controller's locus-of-control, representing the controller's authority to publish authoritative key events.

Step 3: Witness Receipt Creation

Each witness independently:

1. Validates the event structure and cryptographic signatures
2. Verifies the event chains correctly to previous events in the KEL
3. Checks that the event satisfies the current threshold requirements
4. Creates its own receipt by signing the event digest
5. Records the event and receipt in its local storage

Witness receipts serve as cryptographic attestations that the witness observed a specific version of the event at a specific time.

Step 4: Receipt Exchange Among Witnesses

This is the critical coordination phase where witnesses exchange receipts with each other. Each witness:

1. Promulgates its receipt to all other witnesses in the pool
2. Receives receipts from other witnesses
3. Validates received receipts cryptographically
4. Stores receipts from other witnesses
5. Tracks which witnesses have provided receipts

The exchange continues until each witness has received receipts from all other witnesses (or until timeout/failure conditions are met).

Step 5: Agreement State Achievement

A state of agreement is reached when:

• Every witness in the set has witnessed the same version of the event
• Every witness's receipt has been promulgated to every other witness
• The controller and witness set collectively create verifiable control authority

This state represents immune agreement - a supermajority consensus that guarantees at most one agreement occurs despite potentially faulty witnesses.

Step 6: Validator Confirmation

Validators (operating in the confirmation network) independently:

1. Query witnesses for the event and associated receipts
2. Verify that sufficient witnesses agree on the event version
3. Check that the ample threshold is satisfied
4. Detect any duplicity by comparing versions across witnesses
5. 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:

Digital Signatures: All events and receipts must be signed using non-repudiable digital signatures. The algorithm requires:

• Controller signatures on events using current authoritative keys
• Witness signatures on receipts using witness identifier keys
• Cryptographic strength of approximately 128 bits minimum

Hash Chaining: Events must be cryptographically chained through:

• Backward chaining via digests of previous events
• Forward chaining via digests of pre-rotated keys
• SAID (Self-Addressing Identifier) mechanisms for content integrity

Threshold Cryptography: The algorithm supports:

• Multi-signature schemes with configurable thresholds
• Weighted thresholds for heterogeneous witness pools
• Ample calculations ensuring Byzantine fault tolerance

Timing Considerations

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
• Configure witness endpoints via OOBI
• Maintain witness pool through rotation events
• Balance security, availability, and cost

Error Handling

KAACE must handle several failure modes:

Witness Failures:

• Unavailable witnesses (network failures, downtime)
• Faulty witnesses (Byzantine behavior, compromise)
• Slow witnesses (delayed receipt generation)
• Malicious witnesses (deliberate duplicity)

Network Failures:

• Partitions preventing receipt exchange
• Message loss or corruption
• Denial-of-service attacks
• Eclipse attacks on witness communication

Duplicity Detection:

• Conflicting event versions from controller
• Inconsistent receipts from witnesses
• First-seen rule violations
• Forked KEL detection

Usage Patterns

Typical Scenarios

Identifier Inception: When creating a new AID:

1. Controller generates inception event with initial keys
2. Controller designates witness pool in inception configuration
3. Controller promulgates inception event to witnesses
4. Witnesses coordinate to establish initial key state
5. Validators can immediately verify the new identifier

Key Rotation: When rotating keys:

1. Controller creates rotation event with new keys and next key digests
2. Controller promulgates to existing witness pool
3. Witnesses verify rotation satisfies pre-rotation commitments
4. Agreement establishes new authoritative key state
5. Old keys become stale, new keys become current

Witness Pool Rotation: When changing witnesses:

1. Controller creates rotation event with new witness configuration
2. Both old and new witnesses must participate
3. Agreement requires coordination across both witness sets
4. Successful rotation transfers authority to new witnesses

Delegation: When delegating authority:

1. Delegator creates delegation event
2. Delegate creates delegated inception event
3. Both events must achieve witness agreement
4. 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

Comparison to Other Consensus Mechanisms

KAACE differs fundamentally from:

Blockchain Consensus (Proof-of-Work, Proof-of-Stake):

• No global ledger required
• No mining or staking mechanisms
• No transaction fees
• 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."

Duplicity Detection

KAACE enables ambient duplicity detection through:

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.

Partial Agreement:

• Handle cases where some witnesses are unavailable
• Determine if partial agreement meets threshold
• Decide whether to proceed or abort
• Log partial agreement scenarios for analysis

Network Partitions:

• Detect network partition scenarios
• Implement partition recovery procedures
• Avoid split-brain situations
• Reconcile state after partition heals

Performance Optimization

Caching: Implement intelligent caching:

• Cache verified key states at validators
• Cache witness receipts to reduce queries
• Invalidate cache on new events
• Use TTL for cache expiration

Batching: Batch operations where possible:

• Batch receipt exchanges
• Batch validator queries
• Batch event processing
• Balance latency vs. throughput

Monitoring: Implement comprehensive monitoring:

• Receipt exchange latency
• Witness availability metrics
• Agreement success rates
• Duplicity detection events

Security Considerations

Witness Selection: Choose witnesses carefully:

• Verify witness identity through OOBI
• Assess witness security practices
• Evaluate witness availability history
• Consider witness incentive alignment

Key Management: Protect witness keys:

• Use HSM or TEE for witness keys
• Implement key rotation for witness identifiers
• Secure key backup and recovery
• Monitor for key compromise indicators

Attack Mitigation:

• Rate limit witness queries to prevent DoS
• Implement authentication for witness APIs
• Use TLS for all witness communication
• Deploy DDoS protection for witness endpoints

Testing Requirements

Unit Tests: Test individual components:

• Ample calculation with various n and f values
• Receipt generation and verification
• Event validation logic
• Duplicity detection algorithms

Integration Tests: Test witness coordination:

• Receipt exchange between witnesses
• Agreement achievement scenarios
• Partial agreement handling
• Network failure recovery

Chaos Testing: Test failure scenarios:

• Random witness failures
• Network partitions
• Byzantine witness behavior
• Timing attacks

Compliance and Governance

vLEI Requirements: For vLEI ecosystem:

• Minimum 5 witnesses with KAACE threshold
• 18-month backward compatibility for spec versions
• Documented witness selection criteria
• Audit logging of all witness operations

Documentation: Maintain comprehensive documentation:

• Witness pool configuration rationale
• Threshold calculation methodology
• Incident response procedures
• Security audit results