A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus
Mixed-integer mathematical programming has been widely used to model and solve challenging optimization problems. One interesting feature of this technique is the ability to prove the optimality of the achieved solution, for many practical scenarios where a linear programming model can be devised. T...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Future Internet |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-5903/12/11/185 |
| _version_ | 1797549551784034304 |
|---|---|
| author | Vitor Nazário Coelho Rodolfo Pereira Araújo Haroldo Gambini Santos Wang Yong Qiang Igor Machado Coelho |
| author_facet | Vitor Nazário Coelho Rodolfo Pereira Araújo Haroldo Gambini Santos Wang Yong Qiang Igor Machado Coelho |
| author_sort | Vitor Nazário Coelho |
| collection | DOAJ |
| description | Mixed-integer mathematical programming has been widely used to model and solve challenging optimization problems. One interesting feature of this technique is the ability to prove the optimality of the achieved solution, for many practical scenarios where a linear programming model can be devised. This paper explores its use to model <i>very strong Byzantine adversaries</i>, in the context of distributed consensus systems. In particular, we apply the proposed technique to find challenging adversarial conditions on a state-of-the-art blockchain consensus: the Neo dBFT. Neo Blockchain has been using the dBFT algorithm since its foundation, but, due to the complexity of the algorithm, it is challenging to devise definitive algebraic proofs that guarantee safety/liveness of the system (and adjust for every change proposed by the community). Core developers have to manually devise and explore possible adversarial attacks scenarios as an exhaustive task. The proposed multi-objective model is intended to assist the search of possible faulty scenario, which includes three objective functions that can be combined as a maximization problem for testing one-block finality or a minimization problem for ensuring liveness. Automated graphics help developers to visually observe attack conditions and to quickly find a solution. This paper proposes an exact adversarial model that explores current limits for practical blockchain consensus applications such as dBFT, with ideas that can also be extended to other decentralized ledger technologies. |
| first_indexed | 2024-03-10T15:16:14Z |
| format | Article |
| id | doaj.art-d074447dc0cd494183ddaac702d1c19c |
| institution | Directory Open Access Journal |
| issn | 1999-5903 |
| language | English |
| last_indexed | 2024-03-10T15:16:14Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Future Internet |
| spelling | doaj.art-d074447dc0cd494183ddaac702d1c19c2023-11-20T18:56:53ZengMDPI AGFuture Internet1999-59032020-10-01121118510.3390/fi12110185A MILP Model for a Byzantine Fault Tolerant Blockchain ConsensusVitor Nazário Coelho0Rodolfo Pereira Araújo1Haroldo Gambini Santos2Wang Yong Qiang3Igor Machado Coelho4OptBlocks, Avenida Jo ao Pinheiro, 274 Sala 201-Lourdes, Belo Horizonte-MG 30130-186, BrazilGraduate Program in Computational Sciences (PPG-CComp), Universidade do Estado do Rio de Janeiro, Rua S ao Francisco Xavier, 524-Maracan a, Rio de Janeiro-RJ 20550-013, BrazilDepartment of Computer Science, Universidade Federal de Ouro Preto, Campus Morro do Cruzeiro, Ouro Preto-MG 35400-000, BrazilResearch & Development Department, Neo Global Development, 80, Zhengxue Rd, Shanghai 200082, ChinaInstitute of Computing, Universidade Federal Fluminense, Av. Gal. Milton Tavares de Souza, São Domingos, Niterói-RJ 24210-310, BrazilMixed-integer mathematical programming has been widely used to model and solve challenging optimization problems. One interesting feature of this technique is the ability to prove the optimality of the achieved solution, for many practical scenarios where a linear programming model can be devised. This paper explores its use to model <i>very strong Byzantine adversaries</i>, in the context of distributed consensus systems. In particular, we apply the proposed technique to find challenging adversarial conditions on a state-of-the-art blockchain consensus: the Neo dBFT. Neo Blockchain has been using the dBFT algorithm since its foundation, but, due to the complexity of the algorithm, it is challenging to devise definitive algebraic proofs that guarantee safety/liveness of the system (and adjust for every change proposed by the community). Core developers have to manually devise and explore possible adversarial attacks scenarios as an exhaustive task. The proposed multi-objective model is intended to assist the search of possible faulty scenario, which includes three objective functions that can be combined as a maximization problem for testing one-block finality or a minimization problem for ensuring liveness. Automated graphics help developers to visually observe attack conditions and to quickly find a solution. This paper proposes an exact adversarial model that explores current limits for practical blockchain consensus applications such as dBFT, with ideas that can also be extended to other decentralized ledger technologies.https://www.mdpi.com/1999-5903/12/11/185byzantine fault toleranceconsensusdistributed ledger technologyexact adversarial modelinteger programmingNeo Blockchain |
| spellingShingle | Vitor Nazário Coelho Rodolfo Pereira Araújo Haroldo Gambini Santos Wang Yong Qiang Igor Machado Coelho A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus Future Internet byzantine fault tolerance consensus distributed ledger technology exact adversarial model integer programming Neo Blockchain |
| title | A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus |
| title_full | A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus |
| title_fullStr | A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus |
| title_full_unstemmed | A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus |
| title_short | A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus |
| title_sort | milp model for a byzantine fault tolerant blockchain consensus |
| topic | byzantine fault tolerance consensus distributed ledger technology exact adversarial model integer programming Neo Blockchain |
| url | https://www.mdpi.com/1999-5903/12/11/185 |
| work_keys_str_mv | AT vitornazariocoelho amilpmodelforabyzantinefaulttolerantblockchainconsensus AT rodolfopereiraaraujo amilpmodelforabyzantinefaulttolerantblockchainconsensus AT haroldogambinisantos amilpmodelforabyzantinefaulttolerantblockchainconsensus AT wangyongqiang amilpmodelforabyzantinefaulttolerantblockchainconsensus AT igormachadocoelho amilpmodelforabyzantinefaulttolerantblockchainconsensus AT vitornazariocoelho milpmodelforabyzantinefaulttolerantblockchainconsensus AT rodolfopereiraaraujo milpmodelforabyzantinefaulttolerantblockchainconsensus AT haroldogambinisantos milpmodelforabyzantinefaulttolerantblockchainconsensus AT wangyongqiang milpmodelforabyzantinefaulttolerantblockchainconsensus AT igormachadocoelho milpmodelforabyzantinefaulttolerantblockchainconsensus |