Bitcoin Forum

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 (http://bitcoin.stackexchange.com/questions/7637/why-should-a-miner-chose-the-longest-blockchain-if-an-other-chain-has-a-higher-e).
  
• Inspiration from a comment by goatpig (http://bitcointalk.org/index.php?topic=1163102.msg12336393#msg12336393).
  
• DECOR (http://bitslog.wordpress.com/2014/05/02/decor/) (DEterministic COnflict Resolution).
  
• DECOR+ (http://bitslog.wordpress.com/2014/05/07/decor-2/).
  
• DECOR++ (http://bitslog.wordpress.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-design/).
  
• GHOST (http://eprint.iacr.org/2013/881.pdf) (Greedy Heaviest-Observed Sub-Tree).
  

Edit:

• Added information about the behaviours of other miners.

http://40.media.tumblr.com/ba49679c6f953dd93fb6bcc5852f7d30/tumblr_mi0mk8Zpkb1rn3g71o1_500.jpg

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

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.

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.

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.

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.

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

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

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?

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.

(emphasis mine)

Could you expand on this point for me please?

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?

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

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.

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.

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.

D'oh!  Of course.

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

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.

I'm with you so far.  No arguments here.


I'm curious.  What does "isotropic" mean in this context?


Interesting.  Do you have a link to more on this?  I've searched the forum and the web but all I've found so far is the "Increasing Anonymity in Bitcoin" paper.

I think it is likely that there would be something like an exponential decay function.  Breaking a tie is pretty much zero risk.  The miner can just pick either block in the tie. 

For a one block reversal to be worth it would require a larger payoff and for a two block reversal to be worth risking, the payoff would need to be even higher and so on.

I think that miners would likely either build on the longest chain or maybe 1 block back.  Large reversals would require much higher payouts.

You could model the rest of the miners as x% on the longest chain and (1-x)% on one block back and then find x so that it is stable.  When the fees are stable, then x will be pretty much 100%.

Fee delegation with or without human intervention has many problems. It has the huge drawback that nobody has come up with proven strategy for miners that is optimal and stable (or a Schelling point).

The solution is to share the block reward using the DECOR+ protocol.

In a nutshell DECOR+ stipulates that all competing blocks receive a share of the reward. For instance, if A finds a block with a 10 BTC fee, and B finds a competing block, then A gets 5, and B gets 5 (- some small amount that is burnt and some small amount that is paid to the miner that includes the uncle header).

In practice, we can soft-fork so that the coinbase transactions pays to OP_TRUE, and specify an additional payload of a bitcoin address. Also the coinbase field can include a reference to an uncle header: UNCLE:<version,parent-height,time,merkle-root,nonce> (48 bytes). Or this can be embedded in an OP_RETURN <data>. 100 bocks later (when the coinbase matures), the miner must split the reward between all competing miners by spending the 100-block old coinbase that was paid to OP_TRUE. If he does not, then the block becomes invalid.

The outcome when a high fee is paid is that is that the network slows down until the revenue from the high fee is split between many miners, and the share value goes below the average fees (in the backlog).

The huge benefit is that during the time a huge fee is being split, the blockchain does not fork, there are no competing views of the block-chain, it's stable. There is no hidden strategy. The network is incentive compatible. All participants know that fee sharing is taking place. They can send their transactions as normal and they will be queue in the backlog. Transactions won't be confirmed and than rolled back. Just queued.

The drawback is that the block-chain does not move forward during the sharing time (*), as all miners are mining at the same block height. However, once all miners see the B competing blocks, and HighFeeReward/B < AverageBlockReward, they all start moving forward again as usual. (this requires also that competing blocks are forwarded).

I hate to repeat myself over and over about DECOR+, but it's the solution to most of the problems/vulnerabilities I'm hearing about Bitcoin these days. I will present a paper about DECOR+ in the Scalability workshop in China. Because... it also solves some scalability problems too :)

(*) This is not entirely true, as miners who already mined a competing block will stop competing with themselves earlier than the others.
The miner who has already mined K competing blocks will move forward if (K+1)*HighFeeReward/(B+1) - K*HighFeeReward/B < AverageBlockReward

Do you have a link? A google revealed a lot of blogs about decorating.

https://bitslog.wordpress.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-design/

Many thanks.

This is very similar to the ghost protocol?

I was never really sure that incentivising block production on orphaned chains was a good idea. I do like the idea of including orphans in the chain selection rule, though as that helps reduce the amount of wasted hashes, leading to better efficiency.

This is the original post: https://bitslog.wordpress.com/2014/05/02/decor/
And this is a follow up: https://bitslog.wordpress.com/2014/05/07/decor-2/
This is an additional follow up: https://bitslog.wordpress.com/2015/08/16/how-decor-can-eradicate-selfish-mining-incentive-by-design/

This last post about DECOR++ is misleading and actually criticizes DECOR+ without enough good reasons.

DECOR+ eliminates selfish mining by aligning the monetary incentives of miners so that competition is open and not hidden. But it does not eliminate competition.

DECOR++ eliminates selfish mining by design: eliminating competition altogether.  DECOR++ has many other problems, such as not coping well when difficulty changes downward (e.g. back mining may be more profitable than going forward in the short term)

I really prefer DECOR+.

Personally I wouldn't chose to worsen 1 block orphan rates in favour of lower length reorgs overall.

No. Only in the data structures it uses. GHOST uses uncles to choose the "longest" chain.
DECOR+ uses uncles to split rewards.

These are two complementary concepts.


With DECOR+ you're not "incentivizing" block production on orphaned chains. DECOR+ does not incentivize an orphaned chain to have children. It pays miners that created orphans because of delays in propagation. Incentivize miners to create orphans (uncles) to split a very high (uncommon) block reward. And incentivize miners to prefer one of N competing blocks (all will choose the same parent) in case of a competition (they choose the parent with higher reward).

But by paying for single block orphans, you pay for work that does not contribute to the longest chain... and since you don't include orphan blocks in the chain selection rule, how does this reduce the overall orphan rate?

What exactly does "fees are stable" mean in this context?

I'm also not sure about a strategy of taking "the average fee per block in fees" given variable block discovery times.  I was thinking of a strategy of taking some fraction y of the total fees in the mempool (maybe y = h% / (1 + h%) where h% is the hashrate of the largest miner).

I've now read through some of the GHOST and DECOR work, thanks for the links.  Unfortunately, this is going to take some time for me to fully absorb.


By chopping up, passing around, and burning parts of the coinbase, will we not be promoting out-of-band fees?

I meant that the rate of tx fees being generated by users is constant and you are not dealing with a surge of transactions (or one transaction with massive fees).  

It would also occur when there is a backlog that is large enough so that any one block worth of transactions doesn't affect the total fees available for the next block by much.


As the backlog increases, consuming a single block worth of transactions makes less difference to the next set of transactions.  If there is two to three blocks worth of transactions that pays x per kB, then there is no point in risking orphaning a block.  You can create a new block that pays the same as what you could get by attempting a fork and with much less risk.  This is still worth it if the new block pays slightly less than x per kB, since there is much lower risk.


It can.  Under the rule, POW from uncles can count towards determining the longest chain when comparing forks.  I am not sure if that is formally part of the specification though.

The reason this works is that uncles are directly referenced by child blocks.  You have to include the uncle block's headers as part of the header chain.

This is part of GHOST, but (apparently) not part of DECOR+

Thanks for clarifying.  This is what I imagined but didn't want to guess.


Certainly, when there is a healthy backlog, the difference between taking an absolute fee based on an average of past blocks will seem very similar to taking a ratio of the existing mempool.  However, I think the average-based strategy will empty the mempool infinitely often and this is where natural incentives most clearly lead to intentional forks.  With a ratio, the mempool will never be emptied and the value in undermining a block will stay tied to the value of extending it.

I think the use of a ratio (possibly based on an average of past observations) would go a long way to generalising your example strategy beyond the need for the "fees are stable" assumptions.

Out-of-band fees require coordination between the sender and the miner. It's a private agreement. There is no way to prevent that. Competing miners cannot share out-of-band fees, but out-of-band (private) fees cannot generate contention, so there will be no competition in case a large out-of-band fee appears in a transaction.

There could be the case that the sender sends double-spend transactions to each different miner, using out-of-band fees tailored for each one. This requires that the sender knows a bitcoin address of each miner, and miners are prepared to treat those out-of-band payments as fees, and that miners accept transactions over a communication channel other than the Bitcoin network (which will never forward more than 1 double-spend). So the whole thing looks like an attack more than a real possibility arising from normal usage. In this rare case DECOR+ will fall back to a normal orphaning war. However the subsidy is still shared, and while the subsidy is higher than the rare huge out-of-band fee, no orphaning war will occur.

What if a sender, instead of including a fee in the standard way, includes an extra standard output, sending the fee to an address for which a corresponding private key is publicly known?  Miners could easily claim these fees while the protocol itself would be left in the dark.

If there is a significant advantage to senders, I could imagine wallets and clients with "stealth-fee support" arising quite naturally and gaining some popularity.  I guess that the Bitcoin-harming stigma attached to such a "feature" would make it much less popular than something like Adblock Plus, but I don't think it's a stretch to imagine 5-10% of all fees being paid in this way.

Do you consider this a real possibility?  If so (and assuming a low subsidy), can the constants of DECOR+ be set so as to endure a bit of this abuse? (so that the essential relationships are maintained).

It's true that sending to OP_TRUE may be used also as an out-of-band fee channel.
But what would that "significant advantage" be?
It makes a transaction a bit larger, so users must pay more out-of-band fees than the normal case. Also the transaction would not propagate through the network, as it does not have "official" fees.
Also there is no benefit for the client wallet, because those transactions would be understood by a minority of the miners, slowing down confirmation.

So it must be an attack. And only miners having an interface to accept non-standard transactions directly would benefit from the bait. If there is a single miner having such service, then the attack does not work, and only wastes the attacker's money. And it still requires a modified miner software (a miner must prepare his software to enter an orphaning war in case a high OP_TRUE output is found). And the attack can only cause a temporary disruption, until miners do fee delegation (via more OP_TRUEs outputs) or the miner having the majority of the hash rate outperforms the others by a large number of blocks.

I don't see all these conditions for the attack to succeed and be profitable happening anytime soon. 

That's the question I'm interested in.  I don't have the best grasp of DECOR+ but for any proposal that moves chunks of block rewards around my first question is always "do out-of-bound fees upset the incentives".

Regarding the situation described in your DECOR+ blog entry, what if Bob creates his block first and Alice intentionally sets about attacking it?  She would need to make her coinbase larger than Bob's to have everyone (except Bob) switch to her block.  Beyond that, she would prefer not to share her transaction fees out or have them burnt.  Alice would have to share her coinbase but could keep her out-of-band fees for herself.


All valid points in my eyes.  A client wallet could in many cases create two, mutually incompatible transactions, one paying the fee in the normal way and the other paying a slightly lower overall fee using an OP_TRUE (including standard minrelaytxfee).  If there's just one miner that wants to capitalise on the OP_TRUE output then this is still a gain for the user.


I grant all of these drawbacks, but I can imagine a large enough profit incentive overcoming them.  Hopefully there is no strong incentive of this type in DECOR+.