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

TextBugger: Generating Adversarial Text Against Real-world Applications

Jinfeng Li (Zhejiang University), Shouling Ji (Zhejiang University), Tianyu Du (Zhejiang University), Bo Li (University of California, Berkeley), Ting Wang (Lehigh University)

Read More

The Crux of Voice (In)Security: A Brain Study of...

Ajaya Neupane (University of California Riverside), Nitesh Saxena (University of Alabama at Birmingham), Leanne Hirshfield (Syracuse University), Sarah Elaine Bratt (Syracuse University)

Read More

ExSpectre: Hiding Malware in Speculative Execution

Jack Wampler (University of Colorado Boulder), Ian Martiny (University of Colorado Boulder), Eric Wustrow (University of Colorado Boulder)

Read More

OBFUSCURO: A Commodity Obfuscation Engine on Intel SGX

Adil Ahmad (Purdue), Byunggill Joe (KAIST), Yuan Xiao (Ohio State University), Yinqian Zhang (Ohio State University), Insik Shin (KAIST), Byoungyoung Lee (Purdue/SNU)

Read More