research-article

Public Access

Revisiting the Power of Non-Equivocation in Distributed Protocols

Authors:

Naama Ben-David,

Benjamin Y. Chan,

Elaine ShiAuthors Info & Claims

PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

Pages 450 - 459

https://doi.org/10.1145/3519270.3538427

Published: 21 July 2022 Publication History

Abstract

Trusted hardware and new computing platforms such as RDMA naturally provide a non-equivocation abstraction. Previous works have shown that non-equivocation allows us to achieve tasks that otherwise would not have been possible in the plain model. In this paper, we are interested in understanding whether we can use non-equivocation to compile any asynchronous crash-fault protocol into one that tolerates the same number of Byzantine faults. Furthermore, we consider protocols with security and privacy guarantees that we must preserve under the compilation. Previous works have aimed to achieve a similar goal. However, we explain why the previous results in this area were incomplete. We then present a new compiler that achieves security and privacy, and does so while introducing only polynomial overhead over the underlying protocol (as compared to exponential overhead in previous results).

Supplementary Material

MP4 File (S9-T3.mp4)

Presentation video

Download
808.35 MB

References

[1]

Ittai Abraham, Marcos K Aguilera, and Dahlia Malkhi. Fast asynchronous consensus with optimal resilience. In International Symposium on Distributed Computing (DISC), pages 4--19. Springer, 2010.

[2]

Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra Marathe, and Igor Zablotchi. The impact of rdma on agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 409--418, 2019.

Digital Library

[3]

Marcos K Aguilera, Naama Ben-David, Rachid Guerraoui, Virendra J Marathe, Athanasios Xygkis, and Igor Zablotchi. Microsecond consensus for microsecond applications. In 14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20), pages 599--616, 2020.

[4]

Marcos K Aguilera and Sam Toueg. The correctness proof of ben-or's randomized consensus algorithm. Distributed Computing, 25(5):371--381, 2012.

[5]

Mohammed Alfatafta, Basil Alkhatib, Ahmed Alquraan, and Samer Al-Kiswany. Toward a generic fault tolerance technique for partial network partitioning. In 14th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 20), pages 351--368, 2020.

[6]

Michael Backes, Fabian Bendun, Ashish Choudhury, and Aniket Kate. Asynchronous mpc with a strict honest majority using non-equivocation. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 10--19, 2014.

Digital Library

[7]

Naama Ben-David and Kartik Nayak. Brief announcement: Classifying trusted hardware via unidirectional communication. 2021.

[8]

Michael Ben-Or. Another advantage of free choice (extended abstract) completely asynchronous agreement protocols. In ACM Symposium on Principles of Distributed Computing (PODC), pages 27--30, 1983.

[9]

Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 1--10, 1988.

Digital Library

[10]

Rishabh Bhadauria and Ashish Choudhury. Brief announcement: Asynchronous secure distributed computing with transferrable non-equivocation revisited. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 265--267, 2018.

Digital Library

[11]

Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, and Amit Sahai. Secure computation against adaptive auxiliary information. In Annual Cryptology Conference, pages 316--334. Springer, 2013.

[12]

Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130--143, 1987.

Digital Library

[13]

Ran Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Symposium on Foundations of Computer Science (FOCS), pages 136-- 145. IEEE, 2001.

[14]

Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multi-party secure computation. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, pages 494--503, 2002.

Digital Library

[15]

Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OSDI, volume 99, pages 173--186, 1999.

Digital Library

[16]

David Chaum, Claude Crépeau, and Ivan Damgard. Multiparty unconditionally secure protocols. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 11--19, 1988.

Digital Library

[17]

Byung-Gon Chun, Petros Maniatis, Scott Shenker, and John Kubiatowicz. Attested append-only memory: Making adversaries stick to their word. ACM SIGOPS Operating Systems Review, 41(6):189--204, 2007.

Digital Library

[18]

Allen Clement, Flavio Junqueira, Aniket Kate, and Rodrigo Rodrigues. On the (limited) power of non-equivocation. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 301--308, 2012.

Digital Library

[19]

B. A. Coan. A compiler that increases the fault tolerance of asynchronous protocols. IEEE Transactions on Computers, 37(12):1541--1553, 1988.

Digital Library

[20]

Ran Cohen. Asynchronous secure multiparty computation in constant time. In Public-Key Cryptography--PKC 2016, pages 183--207. Springer, 2016.

Digital Library

[21]

Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky. On the round complexity of randomized byzantine agreement. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

[22]

Miguel Correia, Giuliana S. Veronese, and Lau Cheuk Lung. Asynchronous byzantine consensus with 2f+1 processes. In Proceedings of the 2010 ACM Symposium on Applied Computing, SAC '10, page 475--480, 2010.

Digital Library

[23]

Danny Dolev. The byzantine generals strike again. Journal of algorithms, 3(1):14--30, 1982.

[24]

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM, 35(2), 1988.

Digital Library

[25]

Mattias Fitzi and Ueli Maurer. From partial consistency to global broadcast. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC '00, page 494--503, 2000.

Digital Library

[26]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In ACM symposium on Theory of computing (STOC), 1987.

Digital Library

[27]

Damien Imbs, Michel Raynal, and Julien Stainer. Are byzantine failures really different from crash failures? In International Symposium on Distributed Computing, pages 215--229. Springer, 2016.

[28]

Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen. On the price of equivocation in byzantine agreement. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 309--318, 2012.

Digital Library

[29]

Ramakrishna Kotla, Lorenzo Alvisi, Mike Dahlin, Allen Clement, and Edmund Wong. Zyzzyva: speculative byzantine fault tolerance. In Proceedings of twentyfirst ACM SIGOPS symposium on Operating systems principles (SOSP), pages 45--58, 2007.

Digital Library

[30]

Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133--169, 1998.

Digital Library

[31]

Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382--401, 1982.

Digital Library

[32]

Dave Levin, John R Douceur, Jacob R Lorch, and Thomas Moscibroda. Trinc: Small trusted hardware for large distributed systems. In NSDI, volume 9, pages 1--14, 2009.

[33]

Chuanyou Li, Michel Hurfin, Yun Wang, and Lei Yu. Towards a restrained use of non-equivocation for achieving iterative approximate byzantine consensus. In 2016 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2016, Chicago, IL, USA, May 23--27, 2016, pages 710--719. IEEE Computer Society, 2016.

[34]

Mads Frederik Madsen and Søren Debois. On the subject of non-equivocation: Defining non-equivocation in synchronous agreement systems. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 159--168, 2020.

Digital Library

[35]

Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 31--42, 2016.

Digital Library

[36]

Gil Neiger and Sam Toueg. Automatically increasing the fault-tolerance of distributed systems. In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC '88, page 248--262, 1988.

Digital Library

[37]

Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In 2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 305--319, 2014.

Digital Library

[38]

Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228--234, 1980.

[39]

Luis F. G. Sarmenta, Marten van Dijk, Charles W. O'Donnell, Jonathan Rhodes, and Srinivas Devadas. Virtual monotonic counters and count-limited objects using a tpm without a trusted os. STC '06, page 27--42, 2006.

Digital Library

[40]

Luis F. G. Sarmenta, Marten van Dijk, Jonathan Rhodes, and Srinivas Devadas. Offline count-limited certificates. In Proceedings of the 2008 ACM Symposium on Applied Computing, SAC '08, page 2145--2152, 2008.

Digital Library

[41]

Alin Tomescu and Srinivas Devadas. Catena: Efficient non-equivocation via bitcoin. In 2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22--26, 2017, pages 393--409. IEEE Computer Society, 2017.

[42]

Marten van Dijk, Jonathan Rhodes, Luis F. G. Sarmenta, and Srinivas Devadas. Offline untrusted storage with immediate detection of forking and replay attacks. In Proceedings of the 2007 ACM Workshop on Scalable Trusted Computing, STC '07, page 41--48, 2007.

Digital Library

[43]

Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pages 162--167. IEEE, 1986.

Cited By

Aguilera MBen-David NGuerraoui RMurat AXygkis AZablotchi IAamodt TJerger NSwift M(2023)uBFT: Microsecond-Scale BFT using Disaggregated MemoryProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575732(862-877)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575732

Index Terms

Revisiting the Power of Non-Equivocation in Distributed Protocols
1. Security and privacy
  1. Security services
    1. Privacy-preserving protocols
2. Theory of computation
  1. Design and analysis of algorithms
    1. Distributed algorithms

Recommendations

On the (limited) power of non-equivocation
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

In recent years, there have been a few proposals to add a small amount of trusted hardware at each replica in a Byzantine fault tolerant system to cut back replication factors. These trusted components eliminate the ability for a Byzantine node to ...
Asynchronous MPC with a strict honest majority using non-equivocation
PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Multiparty computation (MPC) among n parties can tolerate up to t < n/2 active corruptions in a synchronous communication setting; however, in an asynchronous communication setting, the resiliency bound decreases to only t < n/3 active corruptions. We ...
Protocols for Multiparty Coin Toss with a Dishonest Majority

Coin-tossing protocols are protocols that generate a random bit with uniform distribution, although some corrupted parties might try to bias the output. These protocols are used as a building block in many cryptographic protocols. Cleve (Proc. of the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC'22: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing

July 2022

509 pages

ISBN:9781450392624

DOI:10.1145/3519270

General Chair:
Alessia Milani
Aix-Marseille University, France
,
Program Chair:
Philipp Woelfel
University of Calgary, Canada

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 July 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ONR
NSF

Conference

PODC '22

Sponsor:

PODC '22: ACM Symposium on Principles of Distributed Computing

July 25 - 29, 2022

Salerno, Italy

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
388
Total Downloads

Downloads (Last 12 months)168
Downloads (Last 6 weeks)24

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aguilera MBen-David NGuerraoui RMurat AXygkis AZablotchi IAamodt TJerger NSwift M(2023)uBFT: Microsecond-Scale BFT using Disaggregated MemoryProceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3575693.3575732(862-877)Online publication date: 27-Jan-2023
https://dl.acm.org/doi/10.1145/3575693.3575732

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents