Sourav Das (Department of Computer Science and Engineering, Indian Institute of Technology Delhi), Vinay Joseph Ribeiro (Department of Computer Science and Engineering, Indian Institute of Technology Delhi), Abhijeet Anand (Department of Computer Science and Engineering, Indian Institute of Technology Delhi)

One major shortcoming of permissionless blockchains such as Bitcoin and Ethereum is that they are unsuitable for running Computationally Intensive smart Contracts (CICs). This prevents such blockchains from running Machine Learning algorithms, Zero-Knowledge proofs, etc. which may need non-trivial computation.

In this paper, we present YODA, which is to the best of our knowledge the first solution for efficient computation of CICs in permissionless blockchains with guarantees for a threat model with both Byzantine and selfish nodes. YODA selects one or more execution sets (ES) via Sortition to execute a particular CIC off-chain. One key innovation is the MultI-Round Adaptive Consensus using Likelihood Estimation (MiRACLE) algorithm based on sequential hypothesis testing. MiRACLE allows the execution sets to be small thus making YODA efficient while ensuring correct CIC execution with high probability. It adapts the number of ES sets automatically depending on the concentration of Byzantine nodes in the system and is optimal in terms of the expected number of ES sets used in certain scenarios. Through a suite of economic incentives and technical mechanisms such as the novel Randomness Inserted Contract Execution (RICE) algorithm, we force selfish nodes to behave honestly. We also prove that the honest behavior of selfish nodes is an approximate Nash Equilibrium. We present the system design and details of YODA and prove the security properties of MiRACLE and RICE. Our prototype implementation built on top of Ethereum demonstrates the ability of YODA to run CICs with orders of magnitude higher gas per unit time as well as total gas requirements than Ethereum currently supports. It also demonstrates the low overheads of RICE.

View More Papers

Cybercriminal Minds: An investigative study of cryptocurrency abuses in...

Seunghyeon Lee (KAIST, S2W LAB Inc.), Changhoon Yoon (S2W LAB Inc.), Heedo Kang (KAIST), Yeonkeun Kim (KAIST), Yongdae Kim (KAIST), Dongsu Han (KAIST), Sooel Son (KAIST), Seungwon Shin (KAIST, S2W LAB Inc.)

Read More

Stealthy Adversarial Perturbations Against Real-Time Video Classification Systems

Shasha Li (University of California Riverside), Ajaya Neupane (University of California Riverside), Sujoy Paul (University of California Riverside), Chengyu Song (University of California Riverside), Srikanth V. Krishnamurthy (University of California Riverside), Amit K. Roy Chowdhury (University of California Riverside), Ananthram Swami (United States Army Research Laboratory)

Read More

Privacy Attacks to the 4G and 5G Cellular Paging...

Syed Rafiul Hussain (Purdue University), Mitziu Echeverria (University of Iowa), Omar Chowdhury (University of Iowa), Ninghui Li (Purdue University), Elisa Bertino (Purdue University)

Read More

Oligo-Snoop: A Non-Invasive Side Channel Attack Against DNA Synthesis...

Sina Faezi (University of California, Irvine), Sujit Rokka Chhetri (University of California, Irvine), Arnav Vaibhav Malawade (University of California, Irvine), John Charles Chaput (University of California, Irvine), William Grover (University of California, Riverside), Philip Brisk (University of California, Riverside), Mohammad Abdullah Al Faruque (University of California, Irvine)

Read More