How to Use Bitcoin to Incentivize Correct Computations

Speaker: Ranjit Kumaresan

Date: Wednesday, April 29, 2015

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-D507

Event Type:

Room Description:

Host: CSAIL Security Seminar

Contact: Frank Wang, frankw@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu

Reminder Subject: TALK: How to Use Bitcoin to Incentivize Correct Computations

Abstract
We study a model of incentivizing correct computations in a variety of cryptographic tasks. For each of these tasks we propose a formal model and design protocols satisfying our model's constraints in a hybrid model where parties have access to special ideal functionalities that enable monetary transactions. We summarize our results: -- *Verifiable computation.* We consider a setting where a delegator outsources computation to a worker who expects to get paid in return for delivering correct outputs. We design protocols that compile both public and private verification schemes to support the incentivization described above. -- *Secure computation with restricted leakage.* Building on the recent work of Huang et al. (Security and Privacy 2012), we show an efficient secure computation protocol that monetarily penalizes an adversary that attempts to learn one bit of information but gets detected in the process. -- *Fair secure computation.* Inspired by recent work, we consider a model of secure computation where a party that aborts after learning the output is monetarily penalized. We then propose an ideal transaction functionality \fml\ and show a constant-round realization on the Bitcoin network. Then, in the \fml-hybrid world we design a constant round protocol for secure computation in this model. -- *Non-interactive bounties.* We provide formal definitions and candidate realizations of non-interactive bounty mechanisms on the Bitcoin network which (1) allow a bounty maker to place a bounty for the solution of a hard problem by sending a single message, and (2) allow a bounty collector (unknown at the time of bounty creation) with the solution to claim the bounty, while (3) ensuring that the bounty maker can learn the solution whenever its bounty is collected, and (4) preventing malicious eavesdropping parties from both claiming the bounty as well as learning the solution. All our protocol realizations (except those realizing fair secure computation) rely on a special ideal functionality that is not currently supported in Bitcoin due to limitations imposed on Bitcoin scripts. Motivated by this, we propose {\em validation complexity} of a protocol, a formal complexity measure that captures the amount of computational effort required to validate Bitcoin transactions required to implement it in Bitcoin. Our protocols are also designed to take advantage of optimistic scenarios where participating parties behave honestly. Joint work with Iddo Bentov (Technion).

Bio
Ranjit Kumaresan is a postdoc at MIT CSAIL. Previously he did a postdoc at the Technion after graduating from the University of Maryland. His research interests are in cryptography,distributed algorithms, and theory of computation.

Research Areas:

Impact Areas:

See other events that are part of the CSAIL Security Seminar 2014/2015.

Created by Frank Wang Email at Tuesday, February 24, 2015 at 7:25 PM.