Revision History for: Byzantine Agreement
- 2025-06-24 at 21:23 by JuliaM
Functionality Description
Byzantine agreement[1,2] is a classical problem concerned with reaching agreement on a single bit of data in a network of $n$ players, out of which $t$ players may be faulty. Each player starts with an input bit $b_{i}$ and the objective is that all non-faulty players output the same bit $d$ (agreement), under the constraint that $d=b_{i}$ for some node $i$ (validity).
The difficulty of this task depends on the failure model of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding, etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.Classical Analogues
No content has been added to this section, yet!
Real-world Use Cases
-
Cryptocurrencies and Blockchain Protocols
Bitcoin, Ethereum (PoW/PoS models): Use variants of BA for reaching consensus on the blockchain state, although not traditional BA. Tendermint, HotStuff, PBFT-based blockchains (e.g., Cosmos, Diem): These rely directly on classical Byzantine Fault Tolerant (BFT) protocols. Algorand also uses a cryptographic sortition + BA protocol (BA⋆) to select committees and finalise blocks. -
Permissioned Distributed Ledgers: Hyperledger Fabric OR IBM Blockchain use PBFT-style consensus mechanisms. These systems operate in enterprise settings where nodes are known but still not fully trusted, making BA protocols essential.
- Fault-Tolerant Systems in Safety- and Mission-Critical Computing: Byzantine fault tolerance (BFT) is used in safety- and mission-critical computing systems, such as aerospace, automotive, and industrial control, to ensure reliable operation despite arbitrary faults or malicious behaviour. These systems often rely on message redundancy, self-checking components, and consensus logic to detect and mask faults. To guarantee that these mechanisms provide sufficient fault coverage, they must be rigorously tested using specialised tools like fault injectors that simulate complex Byzantine failures. This form of BFT emphasises physical reliability and provable system safety over cryptographic guarantees.
Properties
A Byzantine Agreement protocol is formally defined to satisfy the criteria of agreement, validity and termination. The agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if:
- Agreement: Every non-faulty player outputs the same bit $d$.
- Validity: The agreement value $d$ is proposed by at least one node, i.e. $d=b_{i}$ for some node $i$.
- Termination: The protocol will eventually terminate.
In Byzantine Agreement, node failures are modelled as Byzantine Failures. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.
Further Information
- Agreement problems are also studied in weaker failure models, such as crash-failures.
- Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
- It is known that no unconditionally secure classical protocol can solve Byzantine Agreement if the number of failures $t>n/3$, while computationally secure classical protocols can solve the problem for any $t<n$.
References
[1] Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” In Concurrency: the works of leslie lamport, pp. 203-226. 2019.
[2] Ben-Or, Michael, and Avinatan Hassidim. “Fast quantum byzantine agreement.” In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 481-485. 2005. -
- 2025-05-15 at 11:00 by JuliaM
Functionality Description
Byzantine agreement[1,2] is a classical problem concerned with reaching agreement on a single bit of data in a network of $n$ players, out of which $t$ players may be faulty. Each player starts with an input bit $b_{i}$ and the objective is that all non-faulty players output the same bit $d$ (agreement), under the constraint that $d=b_{i}$ for some node $i$ (validity).
The difficulty of this task depends on the failure model of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding, etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.Protocols
No protocols implement this functionality yet.
Classical Analogues
No content has been added to this section, yet!
Real-world Use Cases
-
Cryptocurrencies and Blockchain Protocols
Bitcoin, Ethereum (PoW/PoS models): Use variants of BA for reaching consensus on the blockchain state, although not traditional BA. Tendermint, HotStuff, PBFT-based blockchains (e.g., Cosmos, Diem): These rely directly on classical Byzantine Fault Tolerant (BFT) protocols. Algorand also uses a cryptographic sortition + BA protocol (BA⋆) to select committees and finalise blocks. -
Permissioned Distributed Ledgers: Hyperledger Fabric OR IBM Blockchain use PBFT-style consensus mechanisms. These systems operate in enterprise settings where nodes are known but still not fully trusted, making BA protocols essential.
- Fault-Tolerant Systems in Safety- and Mission-Critical Computing: Byzantine fault tolerance (BFT) is used in safety- and mission-critical computing systems, such as aerospace, automotive, and industrial control, to ensure reliable operation despite arbitrary faults or malicious behaviour. These systems often rely on message redundancy, self-checking components, and consensus logic to detect and mask faults. To guarantee that these mechanisms provide sufficient fault coverage, they must be rigorously tested using specialised tools like fault injectors that simulate complex Byzantine failures. This form of BFT emphasises physical reliability and provable system safety over cryptographic guarantees.
Properties
A Byzantine Agreement protocol is formally defined to satisfy the criteria of agreement, validity and termination. The agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if:
- Agreement: Every non-faulty player outputs the same bit $d$.
- Validity: The agreement value $d$ is proposed by at least one node, i.e. $d=b_{i}$ for some node $i$.
- Termination: The protocol will eventually terminate.
In Byzantine Agreement, node failures are modelled as Byzantine Failures. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.
Further Information
- Agreement problems are also studied in weaker failure models, such as crash-failures.
- Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
- It is known that no unconditionally secure classical protocol can solve Byzantine Agreement if the number of failures $t>n/3$, while computationally secure classical protocols can solve the problem for any $t<n$.
References
[1] Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” In Concurrency: the works of leslie lamport, pp. 203-226. 2019.
[2] Ben-Or, Michael, and Avinatan Hassidim. “Fast quantum byzantine agreement.” In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 481-485. 2005. -
- 2025-05-15 at 10:31 by Mina Doosti
Functionality Description
Byzantine agreement[1,2] is a classical problem concerned with reaching agreement on a single bit of data in a network of $n$ players, out of which $t$ players may be faulty. Each player starts with an input bit $b_{i}$ and the objective is that all non-faulty players output the same bit $d$ (agreement), under the constraint that $d=b_{i}$ for some node $i$ (validity).
The difficulty of this task depends on the failure model of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding, etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.Classical Analogues
Real-world Use Cases
-
Cryptocurrencies and Blockchain Protocols
Bitcoin, Ethereum (PoW/PoS models): Use variants of BA for reaching consensus on the blockchain state, although not traditional BA. Tendermint, HotStuff, PBFT-based blockchains (e.g., Cosmos, Diem): These rely directly on classical Byzantine Fault Tolerant (BFT) protocols. Algorand also uses a cryptographic sortition + BA protocol (BA⋆) to select committees and finalise blocks. -
Permissioned Distributed Ledgers: Hyperledger Fabric OR IBM Blockchain use PBFT-style consensus mechanisms. These systems operate in enterprise settings where nodes are known but still not fully trusted, making BA protocols essential.
- Fault-Tolerant Systems in Safety- and Mission-Critical Computing: Byzantine fault tolerance (BFT) is used in safety- and mission-critical computing systems, such as aerospace, automotive, and industrial control, to ensure reliable operation despite arbitrary faults or malicious behaviour. These systems often rely on message redundancy, self-checking components, and consensus logic to detect and mask faults. To guarantee that these mechanisms provide sufficient fault coverage, they must be rigorously tested using specialised tools like fault injectors that simulate complex Byzantine failures. This form of BFT emphasises physical reliability and provable system safety over cryptographic guarantees.
Properties
A Byzantine Agreement protocol is formally defined to satisfy the criteria of agreement, validity and termination. The agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if:
- Agreement: Every non-faulty player outputs the same bit $d$.
- Validity: The agreement value $d$ is proposed by at least one node, i.e. $d=b_{i}$ for some node $i$.
- Termination: The protocol will eventually terminate.
In Byzantine Agreement, node failures are modelled as Byzantine Failures. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.
Future Information
- Agreement problems are also studied in weaker failure models, such as crash-failures.
- Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
- It is known that no unconditionally secure classical protocol can solve Byzantine Agreement if the number of failures $t>n/3$, while computationally secure classical protocols can solve the problem for any $t<n$.
References
[1] Lamport, Leslie, Robert Shostak, and Marshall Pease. “The Byzantine generals problem.” In Concurrency: the works of leslie lamport, pp. 203-226. 2019.
[2] Ben-Or, Michael, and Avinatan Hassidim. “Fast quantum byzantine agreement.” In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 481-485. 2005. -