Document Open Access Logo

Moving Participants Turtle Consensus

Authors Stavros Nikolaou, Robbert van Renesse

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.20.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Stavros Nikolaou
Robbert van Renesse

Cite AsGet BibTex

Stavros Nikolaou and Robbert van Renesse. Moving Participants Turtle Consensus. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.20

Abstract

We present Moving Participants Turtle Consensus (MPTC), an asynchronous consensus protocol for crash and Byzantine-tolerant distributed systems. MPTC uses various moving target defense strategies to tolerate certain Denial-of-Service (DoS) attacks issued by an adversary capable of compromising a bounded portion of the system. MPTC supports on the fly reconfiguration of the consensus strategy as well as of the processes executing this strategy when solving the problem of agreement. It uses existing cryptographic techniques to ensure that reconfiguration takes place in an unpredictable fashion thus eliminating the adversary’s advantage on predicting protocol and execution-specific information that can be used against the protocol. We implement MPTC as well as a State Machine Replication protocol and evaluate our design under different attack scenarios. Our evaluation shows that MPTC approximates best case scenario performance even under a well-coordinated DoS attack.
Keywords
  • Consensus
  • adaptation
  • moving target defense

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Dan Alistarh, James Aspnes, Valerie King, and Jared Saia. Communication-efficient randomized consensus. In Fabian Kuhn, editor, Distributed Computing - 28th International Symposium, DISC 2014, Austin, TX, USA, October 12-15, 2014. Proceedings, volume 8784 of Lecture Notes in Computer Science, pages 61-75. Springer, 2014. Google Scholar
  2. Tuomas Aura, Pekka Nikander, and Jussipekka Leiwo. DOS-resistant authentication with client puzzles. In Security Protocols, volume 2133 of Lecture Notes in Computer Science, pages 170-177. Springer Berlin Heidelberg, 2001. URL: http://dx.doi.org/10.1007/3-540-44810-1_22.
  3. Michael Ben-Or. Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In Proc. of the 2nd Annual ACM Symp. on Principles of Distributed Computing, PODC'83, pages 27-30, New York, NY, USA, 1983. ACM. URL: http://dx.doi.org/10.1145/800221.806707.
  4. Christian Cachin, Klaus Kursawe, Anna Lysyanskaya, and Reto Strobl. Asynchronous verifiable secret sharing and proactive cryptosystems. In in Proc. 9th ACM Conference on Computer and Communications Security (CCS, pages 88-97. ACM Press, 2002. Google Scholar
  5. Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in Constantinople: Practical asynchronous Byzantine agreement using cryptography. Journal of Cryptology, 18(3):219-246, 2005. URL: http://dx.doi.org/10.1007/s00145-005-0318-0.
  6. Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. Paxos made live: An engineering perspective. In Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, PODC'07, pages 398-407, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1281100.1281103.
  7. Tushar Deepak Chandra, Vassos Hadzilacos, and Sam Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4):685-722, July 1996. URL: http://dx.doi.org/10.1145/234533.234549.
  8. Tushar Deepak Chandra and Sam Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225-267, March 1996. URL: http://dx.doi.org/10.1145/226643.226647.
  9. Bernadette Charron-Bost and André Schiper. The Heard-Of model: computing in distributed systems with benign faults. Distributed Computing, 22(1):49-71, 2009. URL: http://dx.doi.org/10.1007/s00446-009-0084-6.
  10. Benny Chor, Amos Israeli, and Ming Li. Wait-free consensus using asynchronous hardware. SIAM J. Comput., 23(4):701-712, August 1994. URL: http://dx.doi.org/10.1137/S0097539790192635.
  11. Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making Byzantine fault tolerant systems tolerate Byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, NSDI'09, pages 153-168, Berkeley, CA, USA, 2009. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=1558977.1558988.
  12. Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In The 28th Annual Symposium on Foundations of Computer Science, pages 427-438, Oct 1987. URL: http://dx.doi.org/10.1109/SFCS.1987.4.
  13. Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, April 1985. URL: http://dx.doi.org/10.1145/3149.214121.
  14. Xianjun Geng and Andrew B. Whinston. Defeating distributed denial of service attacks. IT Professional, 2(4):36-42, Jul 2000. URL: http://dx.doi.org/10.1109/6294.869381.
  15. Amir Herzberg, Stanislaw Jarecki, Hugo Krawczyk, and Moti Yung. Proactive secret sharing or: How to cope with perpetual leakage. In Proc. of the 15th Annual Int. Cryptology Conf. on Advances in Cryptology, CRYPTO'95, pages 339-352, London, UK, 1995. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=646760.706016.
  16. Jafar Haadi Jafarian, Ehab Al-Shaer, and Qi Duan. Openflow random host mutation: Transparent moving target defense using software defined networking. In Proc. of the 1st Workshop on Hot Topics in Software Defined Networks, pages 127-132. ACM, 2012. URL: http://dx.doi.org/10.1145/2342441.2342467.
  17. Sherif. M. Khattab, Chatree Sangpachatanaruk, Rami Melhem, Daniel Mosse, and Taieb Znati. Proactive server roaming for mitigating denial-of-service attacks. In International Conference on Information Technology: Research and Education (ITRE 2003), pages 286-290, Aug 2003. URL: http://dx.doi.org/10.1109/ITRE.2003.1270623.
  18. Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133-169, May 1998. URL: http://dx.doi.org/10.1145/279227.279229.
  19. Leslie Lamport, Dahlia Malkhi, and Lidong Zhou. Vertical Paxos and primary-backup replication. In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC'09, pages 312-313, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1582716.1582783.
  20. Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, CCS'16, pages 17-30, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2976749.2978389.
  21. Yanhua Mao, Flavio P. Junqueira, and Keith Marzullo. Mencius: Building efficient replicated state machines for WANs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI'08, pages 369-384, Berkeley, CA, USA, 2008. USENIX Association. URL: http://dl.acm.org/citation.cfm?id=1855741.1855767.
  22. Stavros Nikolaou and Robbert van Renesse. Turtle consensus: Moving target defense for consensus. In Proceedings of the 16th Annual Middleware Conference, Middleware'15, pages 185-196, New York, NY, USA, 2015. ACM. URL: http://dx.doi.org/10.1145/2814576.2814811.
  23. Stavros Nikolaou and Robbert van Renesse. Moving Participants Turtle Consensus. Technical report, Cornell University, November 2016. URL: http://arxiv.org/abs/1611.03562.
  24. Rafail Ostrovsky and Moti Yung. How to withstand mobile virus attacks (extended abstract). In Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, PODC'91, pages 51-59, New York, NY, USA, 1991. ACM. URL: http://dx.doi.org/10.1145/112600.112605.
  25. Adi Shamir. How to share a secret. Commun. ACM, 22(11):612-613, November 1979. URL: http://dx.doi.org/10.1145/359168.359176.
  26. Victor Shoup. Practical threshold signatures. In Proc. of the 19th Int. Conf. on Theory and Application of Cryptographic Techniques, pages 207-220, Berlin, Heidelberg, 2000. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=1756169.1756190.
  27. Brian White, Jay Lepreau, Leigh Stoller, Robert Ricci, Shashi Guruprasad, Mac Newbold, Mike Hibler, Chad Barb, and Abhijeet Joglekar. An integrated experimental environment for distributed systems and networks. In Proc. of the 5th Symp. on Operating Systems Design and Implementation (OSDI'02), pages 255-270, Boston, MA, December 2002. Usenix. Google Scholar
  28. Lidong Zhou, Fred B. Schneider, and Robbert van Renesse. APSS: Proactive secret sharing in asynchronous systems. ACM Trans. Inf. Syst. Secur., 8(3):259-286, August 2005. URL: http://dx.doi.org/10.1145/1085126.1085127.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact