Fair Protocols for Verifiable Computations Using Bitcoin and Ethereum

Abstract

Outsourcing a computation has been a major research area in cryptography. A delegatorDoutsources a computation to a workerW, who expects to get paid in return for delivering correct outputs. The delegator has to verify the output returned, to guard against malicious or malfunctioning worker. The worker may not trust the delegator to pay for computations performed by him. Blockchain systems like Bitcoin and Ethereum offer public verifiability of transactions generated in their networks. These transactions are of the form of a set of opcodes in Bitcoins or initiate execution of a contract in Ethereum, thus offering execution of small programs publicly. A fair protocol for verifiable computation between two parties$D$and$W$must provide the following guarantee: (1) Fast verification: The work performed to verify the correctness of output of a function is less than the work performed to compute function. (2) Pay to learn output: W obtains pay from D iff D received the correct output of the computation from W. In this work, we design two ideal functionalities$\mathcal{F}_{CRR}^{\ast}$for single worker case and$\mathcal{F}_{CCRR}^{\ast}$for multiple workers case. Existing methods do not allow Mutual revocation of deposit transaction which reduces the cost of script execution. Our ideal functionalities offer mutual revocation of the deposit transaction made byD. We show the realization of our ideal functionality$\mathcal{F}_{CRR}^{\ast}$in Bitcoin, and we also discuss fair protocols for verifiable computations of GCD of two large numbers and optimization problems. As our final work, we show a fair protocol for proof-based verifiable computing schemes.