• Adversarial environments: Systems exposed to malicious actors
• Safety-critical applications: Where incorrect operation has severe consequences
• Decentralized networks: Where no central authority can enforce correct behavior

Practical Byzantine Fault Tolerance (pBFT), introduced by Miguel Castro and Barbara Liskov in 1999, represented a breakthrough by demonstrating that Byzantine fault tolerance could be achieved efficiently in asynchronous systems. pBFT showed that:

• BFT consensus could be practical with minimal performance overhead
• Systems could operate in asynchronous environments without strict timing assumptions
• High throughput could be maintained with only slight increases in latency

The pBFT algorithm operates through a three-phase protocol (pre-prepare, prepare, commit) that ensures all honest nodes agree on the ordering of operations, even when up to one-third of nodes are faulty. This work laid the foundation for modern BFT consensus mechanisms used in blockchain systems and distributed identity infrastructure.

KERI's Approach

KERI employs Byzantine fault tolerance principles through its witness coordination mechanism and KAACE (KERI Agreement Algorithm for Control Establishment), but with a distinctive architectural approach that differs from traditional BFT systems.

Witness-Based BFT Architecture

KERI's BFT implementation centers on witness pools—designated entities that verify, sign, and store key events for autonomic identifiers (AIDs). The witness architecture provides Byzantine fault tolerance through:

Threshold-Based Agreement: Controllers specify a witness threshold determining the minimum number of witness confirmations required for an event to be considered properly witnessed. This threshold must satisfy the relationship M >= N - F, where:

• N = total number of witnesses
• F = maximum number of potentially faulty witnesses
• M = minimum required confirmations (the ample number)

Independent Verification: Each witness independently validates key events before signing receipts, preventing a single compromised witness from corrupting the system.

Duplicity Detection: Rather than preventing Byzantine behavior, KERI's architecture makes duplicity evident. If a controller creates conflicting versions of key events, witnesses maintain immutable records that expose the inconsistency through ambient duplicity detection.

KAACE: Simplified BFT Consensus

KERI's Agreement Algorithm for Control Establishment (KAACE) represents what the KERI specification describes as "a simplification of PBFT-class algorithms." KAACE achieves consensus through:

Agreement Definition: Agreement on a key event occurs when:

1. Each witness observes the exact same version of the event
2. Each witness's receipt has been received by every other witness

Separation of Networks: KAACE introduces a novel architectural separation:

• Promulgation network: Witnesses exchange and verify event receipts
• Confirmation network: Watchers independently monitor for duplicity

This separation enables KERI to achieve safety without requiring liveness, making it suitable for decentralized, eventually-consistent identity systems.

Distinctive Properties

KERI's BFT approach is characterized by what KERI creator Samuel Smith describes as "what if PBFT and Stellar had a baby?" with these properties:

Present Properties:

• Safety guarantees: Prevents conflicting states from being accepted
• Complete decentralization: No central coordination required
• Portability: Works across different infrastructures
• Permissionless operation: No authorization required for participation

Deliberately Absent Properties:

• Liveness guarantees: Does not guarantee all operations eventually complete
• Total ordering: Does not require global ordering of all events

This trade-off reflects KERI's design philosophy: prioritizing duplicity detection and cryptographic verifiability over strict real-time consensus. By relaxing liveness and total ordering requirements, KERI achieves greater scalability and flexibility while maintaining the safety properties essential for secure identifier management.

Threshold of Accountable Duplicity (TOAD)

KERI implements BFT principles through the Threshold of Accountable Duplicity (TOAD)—a controller-declared threshold M indicating the minimum number of witness confirmations deemed sufficient for accountability. This threshold:

• Enables fault tolerance: System remains secure with up to F faulty witnesses
• Provides flexibility: Controllers can adjust security/availability trade-offs
• Supports accountability: Clear criteria for when controllers accept responsibility for events

Supermajority and Ample

KERI employs the concept of supermajority—a sufficient majority labeled as immune from certain attacks or faults. The ample number represents the minimum participants required to achieve supermajority, ensuring that:

• One and only one agreement can be reached on an event
• No accidental lockout occurs in multi-signature groups
• Byzantine resilience is maintained against malicious actors

The mathematical constraints ensure that the ample number provides genuine Byzantine fault tolerance:

• f >= 1 if n > 0 (at least one fault must be tolerated)
• n >= 3*f + 1 (total participants must exceed three times the fault threshold)
• (n + f + 1)/2 <= m <= n - f (ample number must be achievable yet sufficient)

Practical Implications

Security Benefits

Byzantine fault tolerance in KERI provides critical security properties:

Malicious Witness Resistance: Up to one-third of witnesses can be compromised without affecting system integrity. Honest witnesses maintain correct records that expose any duplicitous behavior.

Network Partition Tolerance: The system continues operating correctly even when network partitions prevent some witnesses from communicating, as long as sufficient honest witnesses remain reachable.

Duplicity Evidence: Rather than preventing Byzantine behavior in real-time, KERI makes it cryptographically evident, enabling post-facto accountability and dispute resolution.

Operational Trade-offs

Availability vs. Consistency: KERI's BFT approach prioritizes eventual consistency over immediate availability. Events may not be immediately confirmed across all witnesses, but once confirmed, they are cryptographically verifiable.

Witness Selection: Controllers must carefully select witness pools, balancing:

• Geographic distribution: Reducing common-mode failures
• Organizational diversity: Preventing collusion
• Reliability: Ensuring witnesses remain available
• Trust relationships: Selecting witnesses with appropriate incentives

Threshold Configuration: Setting witness thresholds involves trade-offs:

• Higher thresholds: Greater security but reduced availability
• Lower thresholds: Faster confirmation but increased vulnerability
• Optimal configuration: Typically M = N - F where F is the expected maximum faults

Use Cases

Enterprise Identity Systems: Organizations can deploy witness pools with known security properties, providing Byzantine fault tolerance for critical identity operations without blockchain overhead.

Federated Governance: Multiple organizations can jointly witness identifiers, with BFT properties ensuring no single organization can unilaterally compromise the system.

High-Stakes Credentials: Legal entity identifiers (like GLEIF's vLEI) benefit from BFT witness networks that provide cryptographic proof of credential issuance and revocation state.

Eclipse Attack Mitigation

The KERI documentation identifies eclipse attacks as the primary attack vector against KERI systems. Byzantine fault tolerance provides defense through:

Watcher Networks: Independent watchers monitor witness behavior, detecting inconsistencies that might indicate eclipse attacks.

Distributed Witnesses: Geographic and organizational distribution of witnesses makes it difficult for attackers to isolate or compromise sufficient witnesses to execute an eclipse attack.

Ambient Verification: Anyone can verify key event logs against multiple witnesses, making sustained eclipse attacks detectable through ambient duplicity detection.

Performance Characteristics

KERI's BFT approach achieves:

Low Latency: Witness confirmation typically completes in seconds, not minutes or hours like blockchain consensus.

High Throughput: Each identifier's key event log is independent, enabling parallel processing without global consensus bottlenecks.

Minimal Overhead: Witness coordination requires only cryptographic signature verification, not computational puzzles or stake-based voting.

Scalability: The system scales horizontally as each identifier maintains its own witness pool, avoiding the global state synchronization challenges of traditional BFT systems.

Conclusion

Byzantine Fault Tolerance in KERI represents a pragmatic adaptation of classical BFT principles to the specific requirements of decentralized identifier systems. By focusing on duplicity detection rather than duplicity prevention, and by separating promulgation from confirmation networks, KERI achieves the safety guarantees of Byzantine fault tolerance while maintaining the scalability, portability, and permissionless operation essential for internet-scale identity infrastructure. The witness-based architecture provides cryptographically verifiable consensus without the performance penalties or infrastructure dependencies of traditional blockchain-based BFT systems, making it particularly well-suited for enterprise and regulatory use cases like the GLEIF vLEI ecosystem.

Ambient Verification: Enable public watcher networks that allow anyone to verify identifier state, maximizing duplicity detection coverage.

Performance Optimization

Parallel Verification: Witnesses can verify events in parallel, reducing confirmation latency.

Asynchronous Operation: KERI's BFT model operates asynchronously, avoiding the synchronization overhead of traditional BFT systems.

Caching: Implement witness receipt caching to reduce redundant verification operations.

Batch Processing: Group multiple events for batch verification when appropriate to improve throughput.

Security Considerations

Witness Compromise Detection: Monitor witness behavior for signs of compromise:

• Inconsistent receipts across witnesses
• Delayed or missing receipts
• Receipts for events not seen by other witnesses

Rotation Strategy: Periodically rotate witness pools to limit the impact of long-term compromises.

Audit Trails: Maintain comprehensive logs of witness receipts and watcher observations for forensic analysis.

Incident Response: Establish procedures for responding to detected Byzantine behavior, including witness replacement and identifier recovery mechanisms.