Why build on the longest chain?

[teukon]

Hypothetical:
Two transactions are broadcast to the network, each with a whopping 5 BTC fee!  After a few minutes, AntPool finds a block and includes both the transactions.  Slush thinks that AntPool was greedy and begins to work on a parallel block.  Slush finds a block before anyone extends AntPool's chain and he includes just one of the two transactions, leaving the other in the mempool.  Discus Fish, BitFury, and KnCMiner all All other miners notice that AntPool's chain and Slush's chain have the same length and that they can get 5 BTC more by extending Slush's chain.  Soon enough, BitFury extends Slush's chain and AntPool's block is orphaned.

                     --->  AntPool (35 BTC)  ---| (Orphan)
                   /
   (Main chain) ---
                   \
                     --->   Slush (30 BTC)   --->  BitFury (30 BTC)  ---> (Main chain)


Is this an attack?  If so, who are the attackers?  Was AntPool greedy?  Was Slush clever or just lucky?  Should a miner always prefer the longest chain?

See also:

• Related question on StackExchange.
  
• Inspiration from a comment by goatpig.
  
• DECOR (DEterministic COnflict Resolution).
  
• DECOR+.
  
• DECOR++.
  
• GHOST (Greedy Heaviest-Observed Sub-Tree).
  

Edit:

• Added information about the behaviours of other miners.

[GermanGiant]

A picture is worth a thousand words. Slush executed the correct course of action to win the Luck advantage.

[hhanh00]

Sorry but why is Slush smarter? Its profit is 30 BTC with lower odds than if it had simply extended Antpool. Did it want to punish Antpool, if so - why even bother? I would understand if it took the 5 BTC fee and left behind a bit more than Antpool.

[teukon]

Sorry but why is Slush smarter? Its profit is 30 BTC with lower odds than if it had simply extended Antpool. Did it want to punish Antpool, if so - why even bother? I would understand if it took the 5 BTC fee and left behind a bit more than Antpool.

(emphasis mine)

Could you explain exactly why Slush's odds were lower?  Were the odds lowered enough to make it unwise to try for an extra 5 BTC?

To clarify: Slush was only interested in profit in this story, not in punishing AntPool.

[hhanh00]

Because you said that Slush thought Antpool was greedy. That means they started working after Antpool published their block. So Slush has one block to catch up... Unless you are saying that Slush predicted Antpool greed.

[teukon]

Because you said that Slush thought Antpool was greedy. That means they started working after Antpool published their block. So Slush has one block to catch up... Unless you are saying that Slush predicted Antpool greed.

No, I'm not assuming any special predictive powers.  What I'm looking for is some analysis of the supposed "lower odds" Slush must endure for competing with an existing block.  What exactly is the risk of this one-block catch-up?

Allow me to offer a simple analysis.  Perhaps you can refine it:
    AntPool will try to extend its own block.  Meanwhile, let's say all other miners work on Slush's block (because it's the more profitable chain for them).  Slush's 30 BTC will be reasonably secure if and only if AntPool does not find the next block.  This is in contrast to the default strategy where Slush builds on AntPool's block for 25 BTC, a sum that will be reasonably secure regardless of which miner finds the next block.  If AntPool's share of the network's total hashrate is less than 5/30 (currently true: 13.7% < 16.7%) then the lower odds will have been more than compensated for by the extra reward.

[DannyHamilton]

In your example, Slush was taking a significant risk.  He didn't know that anyone else would mine on top of his block.  In general most miners operate on a "first seen" block when they have two forks of the same length.  This means that Slush was risking 25 BTC (the BTC he would have gotten if he just extended AntPool's chain) in the hope that the pool that successfully mined the next block would notice and choose to mine on top of his.  His payoff for this risk was an extra 5 BTC.

Let say that Slush knew that 50% of the gobal hash power had all switched to software that would notice the advantage of mining on top of his block and would take advantage of it.  This means that 50% of the time that he takes this risk he would lose 25 BTC, and 50% of the time he would gain the extra 5 BTC.

Example:
Slush wins 200 blocks in a period of time.
200 X 25 = 5000 BTC

Using your method:
100 X 0 = 0 BTC
100 X 30 = 3000 BTC

Hmmm, looks like a bad decision.  He's going to end up earning 2000 BTC less!

In order to make it worthwhile to take the risk for the extra 5 BTC, he's going to need to be very certain that at least 84% of the global hash power is all running software that will notice what he's done and will take advantage of it.

Keep in mind that if there is enough hash power that is taking advantage of the opportunity, then a significant amount of the hash power will NOT be building on top of Slush's block.  Instead they'll be attempting to create another competing block of their own, and which keeps less than the 5 BTC that Sluch chose to keep. This will reduce the amount of mining power working on extending Slush's chain to the point where Slush will probably have to extend his own block before AntMiner extends his own.  This process of everyone extending their own blocks will continue until a single chain is far enough ahead of all the others that the majority of hash power gives up and returns to "normal" operation.

[hhanh00]

The reason I said Slush has lower odds is because while they work to find their 30 btc block, other miners would be working on Antpool 35 btc block . If Slush finds it before Antpool chain extends, we are in the situation you describe. My concern is regarding the odds of getting there.

[DannyHamilton]

The reason I said Slush has lower odds is because while they work to find their 30 btc block, other miners would be working on Antpool 35 btc block.
- snip -

I don't think you read all the way through the OP example. Or at least you didn't understand what you read.

- snip -
Discus Fish, BitFury, and KnCMiner all notice that AntPool's chain and Slush's chain have the same length and that they can get 5 BTC more by extending Slush's chain . . . BitFury extends Slush's chain and AntPool's block is orphaned.
- snip -

[TierNolan]

This is a concern as the minting fee reduces.

At the moment, a majority of the mining power mines on the earliest block seen.  There is no reason why miners couldn't switch over to mining on the one that gives them the most profit.

If enough miners do that, then the optimal strategy shifts to leaving enough fees available so that other miners build on your block.

Analysis is hard, since you have to assume what all the other miners are going to use as strategy.

I could see miners using a strategy of "take the average fee per block in fees, and pass the rest of OP_TRUE and break ties in favor of blocks which follow this rule".

[teukon]

In general most miners operate on a "first seen" block when they have two forks of the same length.

In order to make it worthwhile to take the risk for the extra 5 BTC, he's going to need to be pretty sure that at least 84% of the global hash power is all running software that will notice what he's done and will take advantage of it.

Interesting.  So it seems that Slush's idea in the story is thwarted not by the financial incentives of other miners but by their attachment to an unprofitable default.  Can we expect miners to continue to respect this "first seen" default in the long term?  Is it important that they do so?

[teukon]

This is a concern as the minting fee reduces.

At the moment, a majority of the mining power mines on the earliest block seen.  There is no reason why miners couldn't switch over to mining on the one that gives them the most profit.

If enough miners do that, then the optimal strategy shifts to leaving enough fees available so that other miners build on your block.

Ok, but this leaves me with some concerns.  In particular, bigger mining entities are better able to defend their blocks and so may be able to take a larger chunk of the mempool with each of their blocks.  Smaller pools may have to claim much less or risk being orphaned.  This would give larger miners a quadratic advantage over smaller ones.

Analysis is hard, since you have to assume what all the other miners are going to use as strategy.

I could see miners using a strategy of "take the average fee per block in fees, and pass the rest of OP_TRUE and break ties in favor of blocks which follow this rule".

(emphasis mine)

Could you expand on this point for me please?

[DannyHamilton]

- snip -
Interesting.  So it seems that Slush's idea in the story is thwarted not by the financial incentives of other miners but by their attachment to an unprofitable default.  Can we expect miner's to continue to respect this "first seen" default in the long term?  Is it important that they do so?

Keep in mind that if there is enough hash power that is taking advantage of the opportunity, then a significant amount of the hash power will NOT be building on top of Slush's block.  Instead they'll be attempting to create another competing block of their own, and which keeps less than the 5 BTC that Sluch chose to keep. This will reduce the amount of mining power working on extending Slush's chain to the point where Slush will probably have to extend his own block before AntMiner extends his own.  This process of everyone extending their own blocks will continue until a single chain is far enough ahead of all the others that the majority of hash power gives up and returns to "normal" operation.

As TierNolan pointed out, predicting what all the rest of the hash power will do if there isn't an "attachment to an unprofitable default", is difficult.  How many other miners are likely to ignore both Slush's and AntPool's blocks and try to create their own competing block?  How many are going to remain with the "attachment to an unprofitable default", since they don't feel like they have enough hashpower to ever compete with the rest of the network?  How many are trying to extend Slush's (they feel there's an advantage in mining on top of Slush's, but somehow don't see the advantage in competing with Slush's)?  How many are concerned that if they mine on top of Slush's, that someone will repeat the process by mining a competing block to BitFury's?

[teukon]

Keep in mind that if there is enough hash power that is taking advantage of the opportunity, then a significant amount of the hash power will NOT be building on top of Slush's block.  Instead they'll be attempting to create another competing block of their own, and which keeps less than the 5 BTC that Sluch chose to keep. This will reduce the amount of mining power working on extending Slush's chain to the point where Slush will probably have to extend his own block before AntMiner extends his own.  This process of everyone extending their own blocks will continue until a single chain is far enough ahead of all the others that the majority of hash power gives up and returns to "normal" operation.

Good point.  While I don't think this works in this precise scenario because the miners cannot divide either of the 5 BTC sums, this could take place in a subsidy-less environment with many transactions (which is what I'm really studying here anyway).

[teukon]

As TierNolan pointed out, predicting what all the rest of the hash power will do if there isn't an "attachment to an unprofitable default", is difficult.  How many other miners are likely to ignore both Slush's and AntPool's blocks and try to create their own competing block?  How many are going to remain with the "attachment to an unprofitable default", since they don't feel like they have enough hashpower to ever compete with the rest of the network?  How many are trying to extend Slush's (they feel there's an advantage in mining on top of Slush's, but somehow don't see the advantage in competing with Slush's)?  How many are concerned that if they mine on top of Slush's, that someone will repeat the process by mining a competing block to BitFury's?

Yes, it does seem to get complicated pretty quickly.  I guess I'm interested in looking for equilibria, particularly equilibria where miners are co-operating in a fair¹ and efficient² manner.

[1] A miner's reward is approximately proportional to its hashing power.
[2] Most hashing power is employed to extend the longest chain.

[DannyHamilton]

Good point.  While I don't think this works in this precise scenario because the miners cannot divide either of the 5 BTC sums,
- snip -

Sure they can.

Just include both transactions in their block, take the fees, and create a transaction that will allow the next block to claim whatever portion of that 10 BTC they want to provide as incentive.

[TierNolan]

Could you expand on this point for me please?

I meant pass the rest to OP_TRUE.  This is an output that anyone is allowed to spend.  It is effectively a gift to the miner of the next block, since why would the miners include someone else's transaction spending it, when they can spend it themselves.

If the average fee per block was around 1BTC, but you include a transaction with 10BTC fee, then your coinbase gets 11BTC in fees.

If you assign the entire 11BTC to yourself, then other miners might reject your block and create an alternative block.  

Another miner might create a block with 11BTC in fees, but pay 3 BTC to himself and 8 BTC to OP_TRUE.

This means that anyone can spend the 8 BTC.

The other miners have a choice, they can build on your block and just get the average of 1BTC or they can build on the other block and get part of the 8 BTC paid to OP_TRUE.

If they decide to build on the 8 BTC OP_TRUE block they have to decide how much to take.  They might decide to take only 1BTC, so they get 1BTC in fees plus 8 BTC from the OP_TRUE output and then pay 7 BTC to OP_TRUE.

Some could also create a third block since they think that 2BTC out of the 10BTC was to much.  Knowing how other miners will react is key to figuring out how much you should take of the payment to OP_TRUE.

[teukon]

Good point.  While I don't think this works in this precise scenario because the miners cannot divide either of the 5 BTC sums,
- snip -

Sure they can.

Just include both transactions in their block, take the fees, and create a transaction that will allow the next block to claim whatever portion of that 10 BTC they want to provide as incentive.

D'oh!  Of course.

[teukon]

Could you expand on this point for me please?

I meant pass the rest to OP_TRUE.  This is an output that anyone is allowed to spend.  It is effectively a gift to the miner of the next block, since why would the miners include someone else's transaction spending it, when they can spend it themselves.

If the average fee per block was around 1BTC, but you include a transaction with 10BTC fee, then your coinbase gets 11BTC in fees.

If you assign the entire 11BTC to yourself, then other miners might reject your block and create an alternative block.  

Another miner might create a block with 11BTC in fees, but pay 3 BTC to himself and 8 BTC to OP_TRUE.

This means that anyone can spend the 8 BTC.

The other miners have a choice, they can build on your block and just get the average of 1BTC or they can build on the other block and get part of the 8 BTC paid to OP_TRUE.

If they decide to build on the 8 BTC OP_TRUE block they have to decide how much to take.  They might decide to take only 1BTC, so they get 1BTC in fees plus 8 BTC from the OP_TRUE output and then pay 7 BTC to OP_TRUE.

Some could also create a third block since they think that 2BTC out of the 10BTC was to much.  Knowing how other miners will react is key to figuring out how much you should take of the payment to OP_TRUE.

Thanks for the details.  My blind spot was in not realising that a miner could process a transaction but then pass its fee onto the next miner.  I assumed that a miner would only leave value in the mempool by abstaining from processing some transactions.  Danny also caught me on this.

I appreciate that the problem is difficult but would appreciate any links you might have to attempts to take this further.

If your example strategy:

"take the average fee per block in fees, and pass the rest of OP_TRUE and break ties in favor of blocks which follow this rule"

works then it looks like a miner could choose, at no cost, whether to process some transactions and channel the fee to an OP_TRUE output or simply leave these same transactions in the mempool.  In fact, they might realise a gain in the long term by intentionally leaving low-fee transactions on the table, signalling to users that 1-satoshi-fee transactions will occasionally be delayed.  The classic tragedy-of-the-commons argument of a future with trivial fees would fall apart.  A more careful analysis of this could be valuable in the block size limit debate as the popular BIP100 proposal appears to be partly motivated by the need for an artificial block size limit to create a fee market in the long term.

I'm not convinced this strategy would be stable because it seems to rely on a widespread tie-breaker of "favor blocks which follow this rule" just as we currently rely on the widespread tie-breaker "favour blocks first seen".  If the more profitable tie-breaker of "favour blocks which leave more on the table" becomes widespread then miners would have occasion to profit by undermining blocks built by small miners (basically no risk) while respecting similar blocks built by large miners.  I'm sure we'd settle into some equilibrium but perhaps that equilibrium will only have one miner.

[gmaxwell]

Bitcoin has a stronger security story if you assume that there are many alturistic miners (or lazy parties and a total absense of economically rational developers to sell them better software).

This kind of pattern has been discussed many times in the past with varrious variations, includling things like pay to bury a double spend (with a chain of locked transactions paying high fees).  Most of them right now only apply to fairly contrived cases involving mistaken fees, though as the subsidy goes down all fees end up high enough to trigger them.

Is it right to just assume the network is altruistic (or usefully lazy)? No -- if for no other reason than we've directly seen instances of miners intentionally act in ways to screw over users in order to make more profit. But I think it's also wrong to assume that it isn't alturistic at all.  And at that point we start leaving the realm of what we can reason about formally and enter the realm of things that can only be judged by expirence and which are more vulnerable to chance. This doesn't frighten me-- even in the much stronger systems the real world always undermine your most critical assumptions.

That said, we should try to deliver something that has the best security properties under the weakest possible assumptions.  The particular problem you've suggested here pretty much go away if transaction fees are mostly isotropic (which they would presumably be if transaction fees were efficiently allocated) and there is a standing backlog of transactions.

The harder case is the pay-for-reorg, and so far the best tool I've found to potentially improve that is the use of one-way-aggregatable signatures to make it computationally to extract a transaction that you only learned about from a block announcement and include it in your own block... but I think thats a fairly weak protection.

DannyHamilton suggests that there is coordination risk, but income maximizing behavior is a an awful good shelling point. Especially in a world where single miners have macroscopic shares of the hashpower, I'm not sure this risk of defection from rational behavior is a terribly strong protection-- but it is some protection.