* Faculty       * Staff       * Students & Alumni       * Committees       * Contact       * Institute Directory
* Undergraduate Program       * Graduate Program       * Courses       * Institute Catalog      
* Undergraduate       * Graduate       * Institute Admissions: Undergraduate | Graduate      
* Colloquia       * Seminars       * News       * Events       * Institute Events      
* Overview       * Lab Manual       * Institute Computing      
No Menu Selected

* News


Blockchain-based Consensus

Speaker: Dr. Juan Garay
Yahoo! Research

March 10, 2016 - 1:00 p.m. to 2:00 p.m.
Location: The Bruggeman Conference Center, Center for Biotechnology & Interdisciplinary Studies
Hosted By: Dr. Vassilis Zikas (x2609)


Distributed consensus (aka Byzantine agreement [Pease, Shostak & Lamport, 1980]) is one of the fundamental problems in fault-tolerant distributed computing and cryptographic protocols. It requires correct participants to reach agreement on initially held values despite the arbitrary behavior of some of them, with an additional requirement that if all the correct participants start off with the same value, then that must be the decision value. The problem has been studied extensively in both the unconditional (no assumptions are made about the computational power of the adversary) and cryptographic settings, and efficient (i.e., polynomial-time) solutions exist tolerating the optimal number of misbehaving parties and running in the optimal number of rounds, on networks with pairwise authenticated channels.

In many interesting, non-traditional scenarios, however, such as "peer-to-peer" networks, where parties come and go as they please and there are no prior relations among them, such infrastructure (authenticated channels, public-key infrastructure) is unavailable, thus raising the question whether anything "interesting" can be achieved. In this talk we answer this question in the affirmative, presenting two new probabilistic consensus protocols based on "proofs of work" (POWs, aka "moderately hard functions," "cryptographic puzzles" [Dwork & Naor, 1992]), the technology underlying Bitcoin, the first and most popular decentralized cryptocurrency to date. The first protocol works assuming the adversary's hashing power is bounded by 1/3 of the network's total hashing power. The second consensus protocol is more elaborate, relies on the notion of robust transaction ledgers, which capture the essence of Bitcoin's operation as a cryptocurrency, and works assuming the adversary's hashing power is strictly less than 1/2.


Juan Garay is currently a Sr. Principal Research Scientist and Technical Lead for security and privacy research at Yahoo Research. Previously, after receiving his PhD in Computer Science from Penn State, he was a postdoc at the Weizmann Institute of Science, and held research positions at the IBM T.J. Watson Research Center, Bell Labs, and AT&T Labs--Research. His research interests include both foundational and applied aspects of cryptography and information security. He has published extensively in the areas of cryptography, network security, distributed computing, and algorithms, and is the recipient of over two dozen patents. Recently, he was the program co-chair for Crypto 2013 and 2014, the discipline's premier conference.

Last updated: February 23, 2016