How to Use Bitcoin to Incentivize Correct Computations
http://www.cs.technion.ac.il/~ranjit/papers/incentives.pdfABSTRACT
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 incentivizations 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 F?
ML and show a
constant-round realization on the Bitcoin network. Then, in
the F?
ML-hybrid world we design a constant round protocol
for secure computation in this model.
Noninteractive bounties. We provide formal definitions and
candidate realizations of noninteractive 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 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 make use of optimistic scenarios where participating parties behave
honestly.
