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.

@etscrivner that doesn't make sense since you'd have to pay for hundreds of millions of SSTORES. Let's assume 1 SSTORE per action and a hundred million transactions. That's 20k * 100m gas, or 44k Ether, or 3 million USD to perform such attack. So, yes, there is clearly a room for DDOS, but it is not viable at the "hundred million" scale. Let's quantify this vector more precisely.

Each submitAction takes about 20k gas. Remember, submitAction just writes down "Bob did something", without actually computing the effects of "doing something". Eventually, that action will be executed by the compute() function (when someone needs the result of the computation, that is, the final state of the "game"). This will cost K gas. Let's call K the real cost of the action. Now, suppose the final state has a value of 100k USD (i.e., it is the prize for the winner of the "game"). If K == 20k (i.e., the real cost of the action is equal to the cost of submitting it), then each dollar the attacker burns (by making spam transactions) is a dollar less that the winner will get. So, if he burns 10k USD with fake transactions, the winner will gain 90k USD (because he paid 10k USD to execute the computation). If K == 40k (i.e., the real cost of the action is double of the cost of submitting it) then each dollar the attacker burns will cause the winner to get two dollars less. And so on. So, that's the attack.

In general, the bigger the realActionCost / submitActionCost, the more efficient an attacker gets into "burning" money from this DApp's users. As long as you keep that ratio low, though, I believe it shouldn't be a problem. All an attacker can do is burn his own money to burn the DApp user's money, but he can already do that in many ways; "shorting" the DApp at a loss, hiring people to "defame" the DApp, by building his own competition for this DApp and marketing it, and so on. It is a natural feature of capitalism that you can burn your money to burn someone else's money, so, nothing new here; this just provides an "automated" way to do that. Moreover, if you really burn 1m to "defame" a 1m-worth DApp, for example, it is likely that the market will perceive the DApp as 1m more valuable, so its token will gain market value, and your attack will be futile. It is a similar situation to trying to artificially shorting an asset to destroy it - just doesn't work.

In any case, that only applies to the naive implementation of the principle. It does not take in account two very important factors:

SSTORE / MSTORE imbalance: a MSTORE costs 3 gas, a SSTORE costs 5k-20k gas. The difference is ridiculous, which means you can be much (really, hundreds of times) more gas-efficient doing everything in a single call, so keeping the realActionCost / submitActionCost low should be really easy.
Finally, mainly: all of the above is absolutely irrelevant when you have a TrueBit-like computation outsourcing solution. The idea is simple, it works, and it allows the DApp to accept a submission of the final state at almost no gas cost. So even if an attacker burns 100 billion trillion dollars to flood the DApp with fake actions, someone will just compute it once on his computer, submit to the blockchain, prove it is correct (cheaply), and the attacker can go cry on his new lair below an abandoned bridge.

To put things in perspective: calling "submitAction" costs 0.3 cents of USD (today). That's enough to pay a digital ocean machine for about 40 minutes, which is sufficient to render a HD movie. So, under the TrueBit model, in order for an attacker to reach the 1-to-1 burn ratio, your DApp would need to be rendering a whole HD movie for each user action. At this point I suspect you might consider hiring better programmers.

VictorTaelin/ethereum_delayed_computations.md