In this Series;Verified, we’re talking with Reihaneh Safavi-Naini, a computer science professor with the University of Calgary. Reihaneh is the coauthor of numerous white papers, notably “Smart Contracts for Incentivized Outsourcing of Computation,” with Alptekin Küpçü; “Game-theoretic Analysis of An Incentivized Verifiable Computation System,” with Mahmudun Nabi, Sepideh Avizheh, and Muni Venkateswarlu Kumaramangalam; and “Verifiable Computation using Smart Contracts” with Sepideh Avizheh, Mahmudun Nabi, and Muni Venkateswarlu K. We are thrilled to discuss Reihaneh’s research and developments in the world of verifiable computation and smart contracts.
Welcome, Reihaneh! Please tell us about yourself.
I am a professor of computer science at the University of Calgary in Canada. My research interest is in cryptography and its application to information security.
In the last few years, one of my main research interests has been the application of distributed ledger technology, in particular smart contracts in security systems.
Can you tell us more about smart contracts in relation to incentivized outsourcing?
Smart contracts are programs that have a few important properties. Firstly, their execution can be seen as trusted; that is, each line of the program has been executed by many computing nodes and the result has been agreed upon (through a consensus algorithm), and so we can trust that the result is correct. Secondly, they are transparent. That is, their code and execution can be seen by everyone and so everyone “knows” what they are doing. They also have access to coins (through wallets) and can exchange them automatically when certain conditions hold. Smart contract computation, however, is expensive because it is done many times (all nodes that are part of the consensus algorithm).
In outsourcing computational tasks, a problem giver needs a solution to a computational task — say processing a large data set — and wants to hire computing nodes or “contractors” to perform this task for a fee. The problem giver also wants to be sure that the received result is correct without redoing the computation themselves. An immediate idea is to send the computation to a smart contract. This, however, is not feasible for large computations because of cost. One can, however, use smart contracts as a trusted and transparent third party to manage the process of outsourcing: recruit contractors to do the task and pay the agreed upon fees, and run algorithms that would identify misbehaviour of contractors and issue fines and rewards. This last role is very important in incentivizing participation and correct behaviour of contractors.
Through your game-theoretic analysis, you showed modifications of incentivizing systems that improve the system’s correctness guarantee. Can you expand on your results?
The goal of incentivised outsourcing computation systems is to design computation systems that provide correctness guarantee. In many cases, these systems use the idea of replication of computation to achieve their goal. That is, they use the following simple and powerful idea: if multiple computing nodes independently do the same computation and obtain the same result, there is a very high chance that the result is correct. To analyse these systems, one can assume that the contractors are rational entities and use appropriate incentivization to “encourage” correct computation. Game theoretic analysis is used to evaluate the effectiveness of incentivization systems.
Our work has been on the analysis and design of incentivization systems that use a smart contract to manage the outsourcing. We have done a couple of things. Firstly, we showed that using smart contracts in incentivized systems, even those with provable cryptographic security, is subtle, and direct translation of a secure system to a smart contract-based system can completely break the security of the system. We also showed how to design an incentivized mechanism for a replicated outsourcing system that uses two contractors to guarantee correctness of the computation. Our analysis shows that it is possible to design a reward and fine mechanism for which the Nash equilibrium of the outsourcing game is obtained when the two contractors perform the computation correctly.
What were the obstacles that first led you to explore smart contracts as a method for managing incentivization of computation outsourcing? What new obstacles do you foresee evolving with implementation?
Smart contracts had been used in incentivized outsourcing of computation not only in theory but also in real working systems such as Truebit. My interest has been on the game theoretic analysis of these systems. This analysis, however, becomes more complex as the number of replication increases and with it the reward and fine mechanism becomes more complex.
As an example, extending the result of the two-party outsourcing system that we talked about (achieving Nash equilibrium) to the multiparty case is currently an open problem. The main implementation challenge is that our analysis uses some assumptions about the environment and behaviour of the contractors that may not hold in practice. For example, in the analysis of the two contractor systems, we have used estimated values for parameters of a blockchain system that can be challenging to estimate in practice. And of course in all smart contract based systems, keeping computation and communication of the smart contract low is a challenge.
What real world applications do you think would most benefit from this system?
Outsourcing is going to grow as we use more and more data and complex applications and services that run on them. Examples are learning algorithms and analytics. A very nice property of incentivised outsourcing by replication is their generality and flexibility that allows us to use them for almost any computation. This is in stark contrast with verifiable computation systems that are designed for specific computations.
How does Truebit fit within the scope of your use for smart contracts?
Truebit is an example of an incentivized computation system that provides correctness guarantee by replicating the computation, and uses smart contracts as a trusted third party for managing the computation, incentivization of contractors, and transfer of coins. Truebit incentivization mechanism is complex and hard to analyse formally. Of course there have been plenty of semi-formal analysis and arguments for the security of Truebit. And other security systems, having been up and running for some length of time without major breaks, would be in support of its security.