Skip to main content
SpringerLink
Log in

A Two-Hop Neighborhood Based Berserk Detection Algorithm for Probabilistic Model of Consensus in Distributed Ledger Systems

  • Conference paper
  • First Online:
Computational Collective Intelligence (ICCCI 2023)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 14162))

Included in the following conference series:

  • 537 Accesses

Abstract

Emerging distributed ledger technologies are often not based on Proof of Work (PoW) or Proof of Stake (PoS) consensus protocols. The lightweight protocols, based on the voter model, are typically used for handling contention. However, such protocols are fraught with a particular type of Byzantine adversary known as Berserk adversaries who intend to break the consensus. The existing method of Berserk detection involves the exchange of signatures. This in turn requires key servers, subject to a single point of failure. This paper investigates a new method of Berserk detection. Unlike most of the existing deterministic detection methodologies, the proposed method does not use signatures for the detection of Berserk behavior. The proposed solution is based on two-hop neighborhood opinion information gathering and detects Berserk nodes with some degree of certitude. We also try to ensure that the proposed approach detects most of the Berserk nodes and at the same time keeps the number of false detections marginal.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 89.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 119.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    https://github.com/DeepanjanMitra/NewBerserkDetectionMethod.git refer to this repository to find the simulation and data used for evaluation.

References

  1. Nakamoto, S., Bitcoin, A.: A peer-to-peer electronic cash system. Bitcoin (2008). https://bitcoin.org/bitcoin.pdf

  2. Buterin, V.: Ethereum white paper. GitHub Repository 1, 22–23 (2013)

    Google Scholar 

  3. Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139–147. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-48071-4_10

    Chapter  Google Scholar 

  4. Saleh, F.: Blockchain without waste: proof-of-stake. Rev. Financ. Stud. 34(3), 1156–1190 (2021)

    Article  MathSciNet  Google Scholar 

  5. Chauhan, A., Malviya, O.P., Verma, M., der Singh Mor, T.: Blockchain and scalability. In: 2018 IEEE International Conference on Software Quality, Reliability and Security Companion (QRS-C), pp. 122–128. IEEE (2018)

    Google Scholar 

  6. Chen, P., Zhiqiang, L., Zhen, L., Long, Yu.: Research on scalability of blockchain technology: problems and methods. J. Comput. Res. Dev. 55(10), 2099 (2018)

    Google Scholar 

  7. Holley, R.A., Liggett, T.M., et al.: Ergodic theorems for weakly inter- acting infinite systems and the voter model. Ann. Probab. 3(4), 643–663 (1975)

    Article  MATH  Google Scholar 

  8. Bracha, G.: Asynchronous Byzantine agreement protocols. Inf. Comput. 75(2), 130–143 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  9. Feldman, P., Micali, S.: An optimal probabilistic algorithm for synchronous Byzantine agreement. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) ICALP 1989. LNCS, vol. 372, pp. 341–378. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0035770

    Chapter  Google Scholar 

  10. Mitra, D., Cortesi, A., Chaki, N.: ALEA: an anonymous leader election algorithm for synchronous distributed systems. In: Choraś, M., Choraś, R.S., Kurzyński, M., Trajdos, P., Pejaś, J., Hyla, T. (eds.) CORES/IP &C/ACS -2021. LNNS, vol. 255, pp. 46–58. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-81523-3_5

    Chapter  Google Scholar 

  11. Friedman, R., Mostefaoui, A., Raynal, M.: Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems. IEEE Trans. Dependable Secure Comput. 2(1), 46–56 (2005)

    Article  Google Scholar 

  12. Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382–401 (1982). https://doi.org/10.1145/357172.357176

    Article  MATH  Google Scholar 

  13. Marano, S., Matta, V., Tong, L.: Distributed detection in the presence of Byzantine attacks. IEEE Trans. Signal Process. 57(1), 16–29 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  14. Ayday, E., Fekri, F.: An iterative algorithm for trust management and adversary detection for delay-tolerant networks. IEEE Trans. Mob. Comput. 11(9), 1514–1531 (2011)

    Article  Google Scholar 

  15. Dong, Y., et al.: Secure distributed on-device learning networks with byzantine adversaries. IEEE Netw. 33(6), 180–187 (2019)

    Article  Google Scholar 

  16. Kailkhura, B., et al.: Distributed Bayesian detection in the presence of Byzantine data. IEEE Trans. Signal Process. 63(19), 5250–5263 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  17. Popov, Serguei, Buchanan, William J.: FPC-BI: fast probabilistic consensus within Byzantine infrastructures. J. Parallel Distrib. Comput. 147, 77–86 (2021). https://doi.org/10.1016/j.jpdc.2020.09.002. ISSN 0743-7315

    Article  Google Scholar 

  18. Capossele, A., Müller, S., Penzkofer, A.: Robustness and efficiency of voting consensus protocols within byzantine infrastructures. Blockchain Res. Appl. 2(1), 100007 (2021). https://doi.org/10.1016/j.bcra.2021.100007. ISSN 2096-7209

    Article  Google Scholar 

  19. Popov, S., et al.: The coordicide, pp. 1–30 (2020)

    Google Scholar 

  20. Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-x_21

    Chapter  Google Scholar 

  21. Kokoris Kogias, E., Malkhi, D., Spiegelman, A.: Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security (CCS 2020), pp. 1751–1767. ACM, New York (2020). https://doi.org/10.1145/3372297.3423364

  22. Das, S., Yurek, T., Xiang, Z., Miller, A., Kokoris-Kogias, L., Ren, L.: Practical asynchronous distributed key generation. In: 2022 IEEE Symposium on Security and Privacy (SP), San Francisco, CA, USA, pp. 2518–2534 (2022). https://doi.org/10.1109/SP46214.2022.9833584

  23. Mahato, P., Saha, S., Chayan, S., Shaghil, M.: Consensus-based, fast and energy-efficient multi-robot task allocation. Robot. Auton. Syst. 159, 104270 (2023). https://doi.org/10.1016/j.robot.2022.104270. ISSN 0921-8890

    Article  Google Scholar 

  24. Olfati-Saber, R., Shamma, J.S.: Consensus filters for sensor networks and distributed sensor fusion. In: Proceedings of the 44th IEEE Conference on Decision and Control. IEEE (2005)

    Google Scholar 

  25. Bonomi, S., Del Pozzo, A., Potop-Butucaru, M., Tixeuil, S.: Approximate agreement under mobile Byzantine faults. Theor. Comput. Sci. 758, 17–29 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  26. Gorbunov, S., Wee, H.: Digital signatures for consensus. Cryptology ePrint Archive (2019)

    Google Scholar 

  27. Tseng, Y.-M., Jan, J.-K., Chien, H.-Y.: Digital signature with message recovery using self-certified public keys and its variants. Appl. Math. Comput. 136(2–3), 203–214 (2003)

    MathSciNet  MATH  Google Scholar 

  28. Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998)

    Article  MATH  Google Scholar 

Download references

Acknowledgment

Work partially supported by SERICS (PE00000014) under the PNRR MUR program funded by the EU - NGEU, iNEST-Interconnected NordEst Innovation Ecosystem funded by PNRR (Mission 4.2, Investment 49 1.5) NextGeneration EU - Project ID: ECS 00000043, Research project on Formal Method Based Security Evaluation funded by M/s Keysight Technologies, USA and Research project on Connected Smart Health Services for Rural India under the cluster IoT Research funded by DST, Government of India.

Author information

Authors and Affiliations

  1. University of Calcutta, Kolkata, India

    Deepanjan Mitra & Nabendu Chaki

  2. Ca’ Foscari University, Venice, Italy

    Agostino Cortesi

Authors
  1. Deepanjan Mitra
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Agostino Cortesi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nabendu Chaki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deepanjan Mitra .

Editor information

Editors and Affiliations

  1. Wrocław University of Science and Technology, Wrocław, Poland

    Ngoc Thanh Nguyen

  2. Eötvös Loránd University, Budapest, Hungary

    János Botzheim

  3. Eötvös Loránd University, Budapest, Hungary

    László Gulyás

  4. Universidad Complutense de Madrid, Madrid, Spain

    Manuel Núñez

  5. Vrije Universiteit Amsterdam, Amsterdam, The Netherlands

    Jan Treur

  6. Universität Münster, Münster, Germany

    Gottfried Vossen

  7. Wrocław University of Science and Technology, Wrocław, Poland

    Adrianna Kozierkiewicz

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Mitra, D., Cortesi, A., Chaki, N. (2023). A Two-Hop Neighborhood Based Berserk Detection Algorithm for Probabilistic Model of Consensus in Distributed Ledger Systems. In: Nguyen, N.T., et al. Computational Collective Intelligence. ICCCI 2023. Lecture Notes in Computer Science(), vol 14162. Springer, Cham. https://doi.org/10.1007/978-3-031-41456-5_29

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-41456-5_29

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-41455-8

  • Online ISBN: 978-3-031-41456-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation