Why build on the longest chain?

[teukon]

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.

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

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.

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

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.

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.

[TierNolan]

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.

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

[Sergio_Demian_Lerner]

That said, we should try to deliver something that has the best security properties under the weakest possible assumptions.  

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

[monsterer]

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

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

[sickpig]

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

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/

[monsterer]

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.

[Sergio_Demian_Lerner]

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

[monsterer]

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

[Sergio_Demian_Lerner]

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?

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.

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.

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

[monsterer]

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?

[teukon]

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

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

[teukon]

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.

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.

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

[TierNolan]

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

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.

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

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.

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?

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.

[monsterer]

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+

[teukon]

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

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.

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

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

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.

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.

[Sergio_Demian_Lerner]

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

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.

[teukon]

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

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

[Sergio_Demian_Lerner]

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

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.

....
.

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. 

[teukon]

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?

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.

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.

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.

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

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