Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Make Ethereum massively scalable today with delayed computations

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.

@raineorshine

This comment has been minimized.

Copy link

raineorshine commented Feb 7, 2017

Okay, I've read through this and I see the game theoretic strength of this approach. Let me ask a few questions to test it out and see if it's robust. That halting problem is the biggest concern I have.

  1. How does the contract ensure the actions are legal without computing the state as it goes? If a malicious user adds a massive amount of spurious actions, how does the contract determine the correct sequence of actions? Is it possible to stall out the contract in this way so that reportLiar would never complete?

  2. Similarly, how do you know how much gas to "temporarily" lock for submitAction if you don't know if the program halts?

@MaiaVictor

This comment has been minimized.

Copy link
Owner Author

MaiaVictor commented Feb 22, 2017

Hey, sorry, I didn't see your question.

  1. It doesn't. I think, yes, it is possible to considerably stall the contract, but what would be the incentive to do so? An attacker would, basically, be burning his money in order to force the "winner" to burn his own money. For example, in an exchange, if submitAction costs 10x less than the actual computation of including a tx on the book, then an attacker could spend $50k to cause a $500k damage to the market. Is that what you mean? I definitely see how this would be a problem, even more so if the memory-performed gas cost of a tx is much higher than 20k. I'm not sure if game-theoretically people would actually do that. Edit: actually since submitState requires as much Ether as required to pay the computation gas, then, again, an attacker spamming malicious txs would just burn money to no effect (since, when the system works, nobody actually pays any gas)... if, though, someone sent a wrong state, that person would need to pay all the gas anyway, so just 2 malicious actors burning themselves out... not sure how to reserve enough gas to guarantee the computation, but it could simply be, "if someone disputes and all the submitter gas isn't sufficient to pay the computation, then the submitter's answer is invalidated". So, if you submit a wrong answer and not enough Ether to pay for its computation, you just lose all your Ether for no effect.

  2. Not sure what you mean? submitAction doesn't lock gas, it costs 5000-20000 gas depending...

@NIC619

This comment has been minimized.

Copy link

NIC619 commented Feb 28, 2017

Hi, I have one question here. In submitAction, what do you mean by

writes the action to a log

and

It doesn't actually change the state of the contract

?
I supposed you meant event log? But if you are using event log, how can you compute states based on event log since you can't access them in a smart contract?
Thanks.

@raineorshine

This comment has been minimized.

Copy link

raineorshine commented Mar 1, 2017

@NIC619 I don't think he means event log, but rather an on-chain "log" or list of actions.

@etscrivner

This comment has been minimized.

Copy link

etscrivner commented Mar 2, 2017

I enjoyed the thoughtful article, but suspect there might be an attack vector here.

At first blush, this seems vulnerable to a very simple denial-of-service attack at minimal cost to an attacker.

To perform this attack, simply spam submitAction until there are a huge number of queued actions (hundreds of millions). At some point withdrawal or any other action that calls computeState becomes prohibitively expensive.

I may be missing something, as this is just an initial thought. But we've seen, especially with recent spam attacks, that attackers are often willing to lose money to degrade service on the Ethereum network. So it stands to reason they might also be willing to lose money to deny service to a contract. This definitely poses some interesting design challenges for these sorts of things.

@MaiaVictor

This comment has been minimized.

Copy link
Owner Author

MaiaVictor commented Apr 29, 2017

@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:

  1. 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.

  2. 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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.