[Colloquium] Computer Science Seminar

[Donna Brooms]

Juan A. Garay
Yahoo Labs

Wed., April 29th @ 3:00 pm
 
Title: “The Bitcoin Backbone Protocol: Analysis and Applications”
 
Abstract:
Bitcoin is the first and most popular decentralized cryptocurrency to date.In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin "backbone," and prove two of its fundamental  properties which we call "common prefix" and "chain quality" in the static  setting where the number of players remains fixed. Our proofs hinge on  appropriate and novel assumptions on the "hashing power" of the  adversary relative to network synchronicity; we show our results to be tight under high synchronization.
 
Next, we propose and analyze applications that can be built "on top'' of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a  public transaction ledger. Regarding BA, we observe hat Nakamoto's suggestion falls short of solving it, and present a simple alternative which works assuming that the adversary's hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin's operation as a cryptocurrency, in the sense that it guarantees the liveness and  persistence of committed  transactions. Based on this  notion 
we describe and analyze the Bitcoin system as well as a more elaborate BA protocol, proving them secure assuming high network synchronicity and that the adversary's hashing power is strictly less than 1/2, while the adversarial bound needed for security decreases  as the network desynchronizes.
 
This is joint work with Aggelos Kiayias (U. of Athens) and Nikos Leonardos (U. Paris Diderot -- Paris 7).
 
Bio: After receiving his PhD in Computer Science from Penn State in 1989, Juan A.  Garay 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. He is currently a Sr. Principal Research Scientist and Technical Lead for security and privacy research at Yahoo Labs. 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.
Host: Prof. Simon
(Refreshments will be served after the talk in Ry. 255 @ 4pm)


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150428/0fed845f/attachment-0002.htm 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Juan Garay.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 219967 bytes
Desc: not available
Url : http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150428/0fed845f/attachment-0001.bin 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20150428/0fed845f/attachment-0003.htm