  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. M I RACLE 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.
