IDEAS home Printed from https://ideas.repec.org/a/gam/jftint/v12y2020i11p185-d436505.html
   My bibliography  Save this article

A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus

Author

Listed:
  • Vitor Nazário Coelho

    (OptBlocks, Avenida Jo ao Pinheiro, 274 Sala 201-Lourdes, Belo Horizonte-MG 30130-186, Brazil)

  • Rodolfo Pereira Araújo

    (Graduate 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, Brazil)

  • Haroldo Gambini Santos

    (Department of Computer Science, Universidade Federal de Ouro Preto, Campus Morro do Cruzeiro, Ouro Preto-MG 35400-000, Brazil)

  • Wang Yong Qiang

    (Research & Development Department, Neo Global Development, 80, Zhengxue Rd, Shanghai 200082, China)

  • Igor Machado Coelho

    (Institute of Computing, Universidade Federal Fluminense, Av. Gal. Milton Tavares de Souza, São Domingos, Niterói-RJ 24210-310, Brazil)

Abstract

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 very strong Byzantine adversaries , 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.

Suggested Citation

  • Vitor Nazário Coelho & Rodolfo Pereira Araújo & Haroldo Gambini Santos & Wang Yong Qiang & Igor Machado Coelho, 2020. "A MILP Model for a Byzantine Fault Tolerant Blockchain Consensus," Future Internet, MDPI, vol. 12(11), pages 1-18, October.
    • Handle: RePEc:gam:jftint:v:12:y:2020:i:11:p:185-:d:436505
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1999-5903/12/11/185/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1999-5903/12/11/185/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    2. Coelho, Vitor N. & Coelho, Igor M. & Coelho, Bruno N. & Cohen, Miri Weiss & Reis, Agnaldo J.R. & Silva, Sidelmo M. & Souza, Marcone J.F. & Fleming, Peter J. & Guimarães, Frederico G., 2016. "Multi-objective energy storage power dispatching using plug-in vehicles in a smart-microgrid," Renewable Energy, Elsevier, vol. 89(C), pages 730-742.
    3. Igor M. Coelho & Vitor N. Coelho & Rodolfo P. Araujo & Wang Yong Qiang & Brett D. Rhodes, 2020. "Challenges of PBFT-Inspired Consensus for Blockchain and Enhancements over Neo dBFT," Future Internet, MDPI, vol. 12(8), pages 1-20, July.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Uttam Ghosh & Deepak Tosh & Nawab Muhammad Faseeh Qureshi & Ali Kashif Bashir & Al-Sakib Khan Pathan & Zhaolong Ning, 2022. "Cyber-Physical Systems: Prospects, Challenges and Role in Software-Defined Networking and Blockchains," Future Internet, MDPI, vol. 14(12), pages 1-2, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Martello, Silvano & Pisinger, David & Toth, Paolo, 2000. "New trends in exact algorithms for the 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 325-332, June.
    2. Iida, Hiroshi, 2011. "How to solve the collapsing subset-sum problem revisited," ビジネス創造センターディスカッション・ペーパー (Discussion papers of the Center for Business Creation) 10252/4432, Otaru University of Commerce.
    3. Viet Anh Nguyen & Fan Zhang & Shanshan Wang & Jose Blanchet & Erick Delage & Yinyu Ye, 2021. "Robustifying Conditional Portfolio Decisions via Optimal Transport," Papers 2103.16451, arXiv.org, revised Apr 2024.
    4. Herweg, Fabian & Müller, Daniel, 2008. "The Optimality of Simple Contracts: Moral Hazard and Loss Aversion," Bonn Econ Discussion Papers 17/2008, University of Bonn, Bonn Graduate School of Economics (BGSE).
    5. Mhand Hifi & Slim Sadfi & Abdelkader Sbihi, 2004. "An Exact Algorithm for the Multiple-choice Multidimensional Knapsack Problem," Post-Print halshs-03322716, HAL.
    6. B. Golany & N. Goldberg & U. Rothblum, 2015. "Allocating multiple defensive resources in a zero-sum game setting," Annals of Operations Research, Springer, vol. 225(1), pages 91-109, February.
    7. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2020. "On the difficulty of budget allocation in claims problems with indivisible items of different prices," ThE Papers 20/09, Department of Economic Theory and Economic History of the University of Granada..
    8. Teresa Estañ & Natividad Llorca & Ricardo Martínez & Joaquín Sánchez-Soriano, 2021. "On the Difficulty of Budget Allocation in Claims Problems with Indivisible Items and Prices," Group Decision and Negotiation, Springer, vol. 30(5), pages 1133-1159, October.
    9. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    10. Jooken, Jorik & Leyman, Pieter & De Causmaecker, Patrick, 2023. "Features for the 0-1 knapsack problem based on inclusionwise maximal solutions," European Journal of Operational Research, Elsevier, vol. 311(1), pages 36-55.
    11. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    12. Christoph Buchheim & Dorothee Henke & Jannik Irmai, 2022. "The Stochastic Bilevel Continuous Knapsack Problem with Uncertain Follower’s Objective," Journal of Optimization Theory and Applications, Springer, vol. 194(2), pages 521-542, August.
    13. Thomas, Dimitrios & D’Hoop, Gaspard & Deblecker, Olivier & Genikomsakis, Konstantinos N. & Ioakimidis, Christos S., 2020. "An integrated tool for optimal energy scheduling and power quality improvement of a microgrid under multiple demand response schemes," Applied Energy, Elsevier, vol. 260(C).
    14. Cedric A. Lehmann & Christiane B. Haubitz & Andreas Fügener & Ulrich W. Thonemann, 2022. "The risk of algorithm transparency: How algorithm complexity drives the effects on the use of advice," Production and Operations Management, Production and Operations Management Society, vol. 31(9), pages 3419-3434, September.
    15. Zheng, Yingying & Jenkins, Bryan M. & Kornbluth, Kurt & Træholt, Chresten, 2018. "Optimization under uncertainty of a biomass-integrated renewable energy microgrid with energy storage," Renewable Energy, Elsevier, vol. 123(C), pages 204-217.
    16. Rahman, Syed & Khan, Irfan Ahmed & Khan, Ashraf Ali & Mallik, Ayan & Nadeem, Muhammad Faisal, 2022. "Comprehensive review & impact analysis of integrating projected electric vehicle charging load to the existing low voltage distribution system," Renewable and Sustainable Energy Reviews, Elsevier, vol. 153(C).
    17. Yanhong Feng & Xu Yu & Gai-Ge Wang, 2019. "A Novel Monarch Butterfly Optimization with Global Position Updating Operator for Large-Scale 0-1 Knapsack Problems," Mathematics, MDPI, vol. 7(11), pages 1-31, November.
    18. Taylan İlhan & Seyed M. R. Iravani & Mark S. Daskin, 2011. "TECHNICAL NOTE---The Adaptive Knapsack Problem with Stochastic Rewards," Operations Research, INFORMS, vol. 59(1), pages 242-248, February.
    19. M. Eric Johnson & Margaret L. Brandeau, 1999. "Design of an Automated Shop Floor Material Handling System with Inventory Considerations," Operations Research, INFORMS, vol. 47(1), pages 65-80, February.
    20. Altay, Nezih & Robinson Jr., Powell E. & Bretthauer, Kurt M., 2008. "Exact and heuristic solution approaches for the mixed integer setup knapsack problem," European Journal of Operational Research, Elsevier, vol. 190(3), pages 598-609, November.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jftint:v:12:y:2020:i:11:p:185-:d:436505. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.