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

Automating Patching of Vulnerable Open-Source Software Versions in Application...

Ruian Duan (Georgia Institute of Technology), Ashish Bijlani (Georgia Institute of Technology), Yang Ji (Georgia Institute of Technology), Omar Alrawi (Georgia Institute of Technology), Yiyuan Xiong (Peking University), Moses Ike (Georgia Institute of Technology), Brendan Saltaformaggio (Georgia Institute of Technology), Wenke Lee (Georgia Institute of Technology)

Read More

TIMBER-V: Tag-Isolated Memory Bringing Fine-grained Enclaves to RISC-V

Samuel Weiser (Graz University of Technology), Mario Werner (Graz University of Technology), Ferdinand Brasser (Technische Universität Darmstadt), Maja Malenko (Graz University of Technology), Stefan Mangard (Graz University of Technology), Ahmad-Reza Sadeghi (Technische Universität Darmstadt)

Read More

Cracking the Wall of Confinement: Understanding and Analyzing Malicious...

Eihal Alowaisheq (Indiana University, King Saud University), Peng Wang (Indiana University), Sumayah Alrwais (King Saud University), Xiaojing Liao (Indiana University), XiaoFeng Wang (Indiana University), Tasneem Alowaisheq (Indiana University, King Saud University), Xianghang Mi (Indiana University), Siyuan Tang (Indiana University), Baojun Liu (Tsinghua University)

Read More

One Engine To Serve 'em All: Inferring Taint Rules...

Zheng Leong Chua (National University of Singapore), Yanhao Wang (TCA/SKLCS, Institute of Software, Chinese Academy of Sciences), Teodora Baluta (National University of Singapore), Prateek Saxena (National University of Singapore), Zhenkai Liang (National University of Singapore), Purui Su (TCA/SKLCS, Institute of Software, Chinese Academy of Sciences)

Read More