Make Ethereum massively scalable today with delayed computations

Suppose you're writing a contract which involves a huge amount of participants. As an example, think of an online, blockchain-based Trading-Card Game with tournaments. How would you program a playCard function? You might be thinking of something like this:

function playCard(uint player, uint card){
    ...
    else if (card == PROFESSOR_OAK){
        // shuffles the player's hand on his deck
        shuffleHand(player)

        // draws 7 cards
        for (int i=0; i<7; ++i)
            drawCard(player);
    }
    ...
}

Which is cute but also terribly wrong, and the very reason Ethereum is believed to have scaling issues. Shuffling a 60-card deck is a very expensive operation, and drawing 7 cards requires many SSTOREs. Making every node perform that computation is a waste, and if you're expecting your users to pay half a dollar in order to make a single move in your game, then you're doomed to fail. This is how you do it:

// every end-user action of the DApp must be submitted through this call
// it just writes the action to a log, at a very small, fixed gas cost
function submitAction(string action){
    actions.push(Action(msg.sender, action));
}

The only thing this function does is register that the action occurred. It doesn't actually change the state of the contract in any way other than that. The point is that this is the only function the average user ever calls. If you're doing it right, it could cost as few as 5000 gas - much less than a cent; and you could compact many calls into once, making the cost/action even lower. And that's all you need! Now, you might ask:

If the contract isn't actually computing anything, how do users/players know the state of the app/game as they play?

For that, we need a computeState() function:

// iterates through the list of actions,
// setting the DApp's state
function computeState()

The DApp users simply have to call that funtion offline, using web3. That way, the computation is only executed locally, at no gas cost!

But if everyone is running `computeState()` offline, then it is, essentially, the same as running it on the EVM.

No! The major difference here is that the EVM is global. Here, only the interested parties need to run the computation! Imagine that the Ethereum network has 1 million users, but this tournament has only 256 players. Only they need to call computeState as the tournament proceeds.

OK, but the state is invisible to the contract. When the game is over, how does it know who won, to send the reward?

So, yes, at this point, the computation must be executed "globally". For that, we require a withdrawal function which checks if the state is up to date.

// only this function can withdrawal Ether from the contract
// the state must have been computed for it to work
function withdrawal()

It needs the state to be up-to-date because sending money is a "global consensus point", because Ether is a global currency. So, in order to withdrawal, the winner (whoever wants to withdrawal money) is forced to call computeState(), paying the gas cost and making the state visible to the contract.

You just moved the gas costs to the winner!

Correct and wrong! Yes, the winner (i.e., whoever benefits from the computation) pays the gas cost. That is game-theoretically sound, because he is the one interested on the computation result. But it doesn't just move the cost; it also makes it enormously smaller. The reason is that each SSTORE operation costs about 20000 gas, while a MSTORE operation costs only 3 gas! SSTORE is by far the most expensive OPCODE. By delaying the entire computation to a single moment, you can perform it all in memory, making it about 6000x less expensive! Much better, isn't it?

Okay, but everyone on the network still need to run it eventually, which is still a waste, doesn't scale, etc. Can you fix that too?

Actually, yes. Now that we delayed the computation to the right moment, we can get rid of it entirely. The solution is simple: use a compute oracle. I'm not talking about a separate contract such as Golem (which is a great project, but isn't ready for that yet). It can be done, today, by just adding two new functions to your contract:

// sets the state without making the whole network compute it
// requires the sender to temporarily lock enough money to pay
// the gas cost of running computeState()
function submitState(...);

// calls computeState(); if someone previously submitted a
// state that doesn't match, that person pays the gas cost
// with his locked money
function reportLiar(...);

It works that way: instead of calling computeState() and paying a ton of gas, the winner instead computes the state on his own computer and calls submitState, which sets the state of app. He must temporarily lock enough Ether to compute the whole state with gas. The contract then waits for some period on which anyone can call reportLiar() to dispute the submitted state. reportLiar() runs computeState() on-chain and, if the submitter lied, uses his locked money to compensate the reporter's gas costs. If nobody disputes it, then the network can safely assume the state is correct. It is, thus, solidified, and the winner gets his locked money plus the prize. Game-theoretically speaking, in practice, reportLiar() will never be called. Moreover, the DApp can be completed with only the interested parties actually needing to run the DApp's code.

And, that's it! Massive scaling without sharding achieved!

Summary: the delayed-computation DApp pattern

To summarize, this is the pattern that I suggest you to write all your DApps:

// every end-user action of the DApp must be submitted through this call
// it just writes the action to a log, proving it occurred at given time,
// at a very small, fixed gas cost
function submitAction(...);

// iterates through the list of actions
// and returns the game/DApp state
function computeState(...);

// only this function can withdrawal Ether from the contract
// the state must have been computed for it to work
function withdrawal(...);

// sets the state without making the whole network compute it
// requires the sender to temporarily lock enough money to pay
// the gas cost of running computeState()
function submitState(...);

// calls computeState(); if someone previously submitted a
// state that doesn't match, that person pays the gas cost
// with his locked money
function reportLiar(...);

Note most of the techniques presented here are known, but not widely adopted. I'm posting this to bring attention to this simple pattern, which can make Ethereum DApps massively scalable, today, without having to wait for further protocol developments such as sharding, or compute markets such as Golem to mature. I could be wrong, but, for the time being, I'm so convinced this pattern is the right way to develop DApps that I'd even add it directly to Solidity, if I could.

Bunjin/ethereum_delayed_computations.md