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

BadBluetooth: Breaking Android Security Mechanisms via Malicious Bluetooth Peripherals

Fenghao Xu (The Chinese University of Hong Kong), Wenrui Diao (Jinan University), Zhou Li (University of California, Irvine), Jiongyi Chen (The Chinese University of Hong Kong), Kehuan Zhang (The Chinese University of Hong Kong)

Read More

Please Forget Where I Was Last Summer: The Privacy...

Kostas Drakonakis (FORTH, Greece), Panagiotis Ilia (FORTH, Greece), Sotiris Ioannidis (FORTH, Greece), Jason Polakis (University of Illinois at Chicago, USA)

Read More

Fine-Grained and Controlled Rewriting in Blockchains: Chameleon-Hashing Gone Attribute-Based

David Derler (DFINITY), Kai Samelin (TÜV Rheinland i-sec GmbH), Daniel Slamanig (AIT Austrian Institute of Technology), Christoph Striecks (AIT Austrian Institute of Technology)

Read More