This allegory captures the essential challenge: achieving consensus when communication is unreliable and some participants may actively work against the system. The problem is particularly relevant to distributed computing systems where:

• Network messages may be delayed, duplicated, or lost
• Nodes may crash or behave erratically
• Malicious actors may attempt to disrupt consensus
• Different observers may see different system states

Evolution of Byzantine Agreement Protocols

Early Byzantine Agreement protocols were primarily theoretical, demonstrating that consensus was mathematically possible if fewer than one-third of nodes were faulty. However, these protocols were impractical for real-world systems due to high message complexity and computational overhead.

The breakthrough came with Practical Byzantine Fault Tolerance (pBFT), introduced by Miguel Castro and Barbara Liskov in 1999. pBFT demonstrated that Byzantine Agreement could be achieved with:

• High performance: Minimal overhead compared to non-Byzantine protocols
• Asynchronous operation: No reliance on synchronized clocks or bounded message delays
• Practical deployment: Suitable for real-world distributed systems

pBFT operates through a three-phase protocol:

1. Pre-prepare: A primary node proposes a value and broadcasts it
2. Prepare: Nodes verify the proposal and broadcast prepare messages
3. Commit: Once sufficient prepare messages are received, nodes broadcast commit messages and execute the operation

This protocol ensures that if 2f + 1 nodes (where f is the maximum number of faulty nodes) agree on an operation, all honest nodes will eventually execute it in the same order.

Alternative Byzantine Agreement Approaches

Beyond pBFT, several other Byzantine Agreement protocols have emerged:

Stellar Consensus Protocol (SCP): Uses federated Byzantine agreement where nodes choose their own "quorum slices" of trusted peers rather than relying on a global participant set. This enables more flexible trust models but requires careful quorum configuration.

Tendermint: Combines Byzantine Agreement with blockchain architecture, using a round-based voting protocol where validators take turns proposing blocks. Provides immediate finality once consensus is reached.

HotStuff: A leader-based Byzantine Agreement protocol that achieves linear message complexity (O(n) instead of O(n²) for pBFT), making it more scalable for large validator sets.

These protocols share the core Byzantine Agreement properties but make different trade-offs between performance, scalability, and flexibility.

KERI's Approach

KERI adopts a distinctive approach to Byzantine Agreement that prioritizes safety and decentralization while deliberately relaxing certain traditional consensus requirements. As KERI creator Samuel Smith characterizes it:

"What if PBFT and Stellar had a baby? that was missing liveness and total ordering but had safety and was completely decentralized, portable, and permission-less? It would be named KERI."

This characterization reveals KERI's consensus philosophy:

Properties KERI Inherits from Byzantine Agreement

Safety guarantees: KERI maintains the fundamental safety property of Byzantine Agreement—if honest witnesses agree on a key event, that agreement is cryptographically verifiable and cannot be undone. The system prevents conflicting states from being accepted as valid.

Byzantine fault tolerance: KERI's witness infrastructure can tolerate up to one-third of witnesses being faulty or malicious. The threshold of accountable duplicity (TOAD) mechanism ensures that as long as a sufficient number of honest witnesses confirm an event, the system maintains integrity.

Decoupling from resources: Like pBFT, KERI achieves consensus without requiring computational proof-of-work or financial proof-of-stake. Consensus depends on cryptographic verification and witness coordination rather than resource expenditure.

Properties KERI Deliberately Omits

Liveness guarantees: Traditional Byzantine Agreement protocols guarantee that the system will eventually make progress (reach consensus) even if some nodes are slow or temporarily unavailable. KERI does not provide this guarantee—if witnesses are unavailable, key events may not be confirmed immediately. However, this is acceptable for KERI's use case because:

• Identity operations do not require immediate global consensus
• Duplicity detection is more important than immediate finality
• Controllers can wait for witness availability before proceeding

Total ordering: Byzantine Agreement protocols typically ensure all nodes agree on a single, total ordering of all operations across the entire system. KERI does not require this—each AID has its own KEL with its own ordering, and there is no requirement for a global ordering across all identifiers. This enables:

• Scalability: No global synchronization bottleneck
• Portability: KELs can be verified independently without access to other identifiers' logs
• Parallelism: Multiple identifiers can evolve simultaneously without coordination

KERI's Agreement Algorithm for Control Establishment (KAACE)

KERI implements its Byzantine Agreement approach through KAACE (also known as KAWA), which establishes consensus among witnesses for a specific AID. The algorithm works as follows:

1. Event promulgation: The controller creates a key event and broadcasts it to the designated witness pool

2. Witness verification: Each witness independently verifies the event's cryptographic validity, including:

   • Signature verification against current authoritative keys
   • Hash chain integrity (linking to previous events)
   • Pre-rotation commitment verification
   • Threshold satisfaction

3. Receipt generation: Valid events receive receipts—cryptographic signatures from witnesses confirming they observed the event

4. Receipt exchange: Witnesses exchange receipts with each other, ensuring all witnesses observe the same event version

5. Agreement establishment: Agreement is achieved when each witness has received receipts from all other witnesses for the same event version

This process ensures that:

• All witnesses observe the identical event version
• Any attempt to present different event versions to different witnesses is detectable
• The controller cannot unilaterally change history after witnesses have confirmed an event

Separation of Promulgation and Confirmation

KERI introduces a novel architectural separation:

Promulgation network: The witness pool designated by the controller, responsible for initial event confirmation and receipt generation. This network provides the Byzantine Agreement mechanism for establishing key state.

Confirmation network: Watchers selected by validators, who independently monitor for duplicity by comparing event logs from multiple sources. This network provides additional security through ambient verification.

This separation enables KERI to achieve safety without requiring liveness or total ordering:

• The promulgation network (witnesses) provides immediate cryptographic confirmation
• The confirmation network (watchers) provides ongoing duplicity detection
• Neither network requires global coordination across all identifiers

Benefits of KERI's Byzantine Agreement Approach

Complete decentralization: No central authority or coordination point exists. Each AID operates independently with its own witness configuration.

Portability: KELs are self-contained and can be verified anywhere without requiring access to specific infrastructure. An identifier can move between platforms while maintaining verifiable continuity.

Permission-less operation: Anyone can create an AID, select witnesses, and participate in the system without authorization from gatekeepers.

Scalability: By eliminating global ordering requirements, KERI avoids the scalability bottlenecks that plague traditional Byzantine Agreement systems. Each identifier's consensus is independent.

Eventual consistency: While KERI does not guarantee immediate liveness, it provides strong eventual consistency—once witnesses agree on an event, that agreement is permanent and verifiable by anyone.

Practical Implications

Use Cases for Byzantine Agreement in Identity Systems

Byzantine Agreement is particularly valuable for decentralized identity systems because:

Trust in adversarial environments: Identity systems must operate across organizational boundaries where participants may have conflicting interests. Byzantine Agreement enables consensus without requiring trust in any single party.

Resistance to compromise: Even if some witnesses are compromised or malicious, the system maintains integrity as long as fewer than one-third are faulty. This provides robust security for high-stakes identity operations.

Verifiable history: Byzantine Agreement ensures that once consensus is reached, the agreed-upon history cannot be retroactively altered. This is critical for identity systems where past authorizations and delegations must remain verifiable.

Decentralized control: Byzantine Agreement eliminates single points of failure and control, enabling truly self-sovereign identity where no central authority can revoke or modify identifiers.

Benefits of Byzantine Agreement

Security without central authority: Byzantine Agreement provides cryptographic security guarantees without requiring trust in centralized infrastructure. This enables decentralized systems to achieve security levels comparable to centralized systems.

Fault tolerance: Systems can continue operating correctly even when some nodes fail, are compromised, or act maliciously. This resilience is essential for critical infrastructure.

Flexibility: Different Byzantine Agreement protocols offer different trade-offs, allowing system designers to choose approaches that match their specific requirements for performance, scalability, and trust models.

Formal guarantees: Byzantine Agreement protocols provide mathematically provable security properties, enabling rigorous analysis of system behavior under various failure scenarios.

Trade-offs and Limitations

Performance overhead: Byzantine Agreement protocols require multiple rounds of message exchange, increasing latency compared to non-Byzantine protocols. pBFT requires O(n²) messages for n participants, though newer protocols like HotStuff reduce this to O(n).

Scalability challenges: Traditional Byzantine Agreement protocols struggle with large participant sets due to message complexity. This limits the number of validators that can participate directly in consensus.

Liveness vs. safety trade-off: In asynchronous networks (where message delays are unbounded), Byzantine Agreement protocols must choose between guaranteed liveness and guaranteed safety. Most practical protocols prioritize safety, accepting that progress may stall if network conditions are poor.

Configuration complexity: Byzantine Agreement systems require careful configuration of participant sets, thresholds, and network parameters. Incorrect configuration can compromise security or availability.

Assumption requirements: While Byzantine Agreement makes minimal assumptions about node behavior, it does assume:

• Cryptographic primitives are secure
• Fewer than one-third of nodes are faulty
• Messages eventually arrive (in asynchronous models)
• Nodes can verify message authenticity

Violating these assumptions can compromise system security.

KERI's Trade-offs

KERI's approach to Byzantine Agreement makes specific trade-offs:

Sacrifices liveness for portability: By not guaranteeing liveness, KERI enables identifiers to be truly portable and independent. This is acceptable for identity use cases where immediate finality is less critical than long-term verifiability.

Sacrifices total ordering for scalability: By not requiring global ordering, KERI achieves horizontal scalability—adding more identifiers does not increase the consensus burden on the system.

Requires witness availability: While KERI does not guarantee liveness, practical operation requires witnesses to be available when controllers need to perform key operations. Controllers must choose reliable witnesses or configure sufficient redundancy.

Depends on duplicity detection: KERI's security model assumes that duplicitous behavior will eventually be detected through ambient verification. This requires validators to actively monitor for conflicting event logs.

These trade-offs reflect KERI's design philosophy: prioritize the properties essential for decentralized identity (security, portability, scalability) while relaxing properties that are less critical for this use case (immediate liveness, global ordering).

Security Assumptions

Implementations must maintain Byzantine Agreement security assumptions:

• Cryptographic strength: Use cryptographically secure signature schemes and hash functions
• Witness independence: Ensure witnesses are independently operated to prevent correlated failures
• Network reliability: While KERI tolerates network delays, witnesses must eventually receive and process events
• Threshold enforcement: Strictly enforce witness thresholds—accepting events with insufficient receipts compromises Byzantine fault tolerance