Topic: Majority is not Enough: Bitcoin Mining is Vulnerable - page 10. (Read 51045 times)

With multiple competing selfish miners the one with the lowest latency network wins. Or to be exact, some function of lowest latency per dollar spent. Not unlike the race in high-frequency trading to get ever lower latency network connections.

Sticking our collective heads in the sand and singing la-la-la doesn't lead to solutions, something we may need some time in the future as the profit margins in mining become lower. There's a lot of people who should know better who keep on saying that miners have proven to be altruistic and interested in the long-term success of Bitcoin, but Bitcoin is much stronger if we don't need that tenuous assumption.

I just printed out the paper and read it.

Since the algorithm for "Selfish Mining" is now public, all miners have an opportunity to employ it if they feel it gives them an advantage.  So the notion that there is only a single pool of colluding miners growing as other miners join it to reap its advantages is moot.

Initially the colluding pool is a small fraction of total hashrate, and therefore has a vanishingly small probability of being able to mine consecutive blocks on its private chain.  So the only thing it can do is force other people to waste time by delaying publication when it mines a block, and some fraction of the time, its block wins over the public block, and people who have attempted to append to that block lose their work.

This seems to me to be such a small epsilon in the hashing activity that no one is really going to care, and no one is going to bother to do Selfish Mining.  The work to reward ratio here is pretty large.

So basically, "Nothing to See Here," and no modification to the Bitcoin protocol is needed.

@OP:

That's why p2pool should be a solution. To prevent such things from happening in the future.

Makes it even easier when you have all these non-relaying nodes in the network and ppl falling behind several blocks.  Just add 70  more of those swiss nodes, gtg

I believe I have a simple and effective solution: http://www.mail-archive.com/[email protected]/msg03137.html

Nope, that idea doesn't work: http://www.mail-archive.com/[email protected]/msg03155.html

If I'm reading this correctly, an attacker is more likely to loose value performing this attack than to profit from it. Is that right?

They do in the GBT protocol supported by bitcoind, sadly the market chose to use the later stratum protocol over it primarily.   This, I think, is largely offtopic. There is no reason you wouldn't expect the hashers to be complicit in such a scheme: Even if delayed blocks can't be prevented with non-GBT mining protocols, they still can be trivially detected. (E.g. miners often issuing work with non-public prev, big orphan bursts)

Even of more concern is that IBM has been circling around these areas recently.

IBM has access to enormous computing power.  While they may not aggressively attack Bitcoin per se, they certainly could start brokering privileged positions in the network.  Computing power on that level is very much in the reach of IBM, and they are perhaps the biggest player in high technology for Financial applications.

I'd like to point out that a primitive version of this attack is 3 years old:

https://bitcointalksearch.org/topic/m.30064
https://bitcointalksearch.org/topic/m.30083

A miner in a traditional pool doesn't have the information needed to publish a block on his own. He has to submit the header w/ nonce to the pool, and then the pool broadcasts the block.

Excuse my naiveté, but I was under the impression that the software which coordinates the mining effort of a pool between the pool miners is NOT responsible for claiming the mining prize, but that each lowly pool miner - should he find the correct hash - claims the prize to an account belonging to the pool and immediately broadcasts his success. This way, immediate broadcasting of the new block is assured, and keeping stuff secret would never happen.

Your analysis is pretty incomplete. Their success at winning that "fast as possible" race, along with their total hashrate, is essential. Otherwise a delay is a pure loss.

This document in super short is about:

Keeping found blocks secret, to perform calculations on them so that others cannot, thereby giving a racing adventage. They "secretivers" will have a head start.

When "publicers" announce their block quickly publish the "secret" block to create a tieing situation.

Currently the first block that arrives is picked by miners so the "secretives" have incencitive to "delay public blocks", an incentive to listen in on other mining pools "detect early public block announcement to quick react to it" and to try and inject/publish their secretive block as fast as possible towards other miners that have not yet received a new block.

If the random picking solution is implemented, 50% of "publicers" will choose the "publicer" block, 50% will choose the "secretivers" blocks, while 100% of the "secrectives" pick the "secritive" block. 150% will therefore try and continue on "secretive" block and only 50% on "publicer" block, increasing the likelyhood of "secrective" block to win out, thereby injecting the secretive block into the blockchain, either the next block will be found be a publicer or by a secretiver, the more secretivers there are the more likely it will be found by them especially because of the headstart, leading to an incentive for others to join the "secretivers" also known as "(a)head-starters"  (actual percentages will depend on the size of the pools).

The conditions above describe the secretives being ahead 1 block.

The document continues with being 2 blocks ahead. (now it gets longer and fudgy for me at least):

I am not sure but I think in this case it will publish both secretive blocks if the publicers announce their block, immediatly invalidating their progress, this could also cause other self-ish miners to be in trouble, they could also publish their second block creating a new tie, or perhaps even a third.

These situations could be easy to detect, the second block would be announced immediatly ? perhaps the algorithm can be refined somewehat by introducing a believable delay of a few minutes, though risky if another selfish pool announces it sooner, though keeping the second block secret could also be an option and try and rely on tieing only. Though for many this would not be statisfactory and would probably try the third block strategy and so forth and thus keep immediatly publishing any found blocks immediatly to try and win over the main network.

This last line of thought is described in the last else statement.

If more than 2 blocks ahead, publish all of them to solidify the gains. If this is truely the longest chain then they'll win and be garantueed of the rewards, if this is not truely the longest chain then they will be superseeded/defeatede by another selfish mining pool... so I am in doubt that this last else statement is smart in case of multiple selfish mining pools.

Eventually they would be defeated by another selfish mining pool that may delay their +1 block to try and defeat the other selfish mining pool into wasting their processing time on their private blocks which they hope would be the new public chain... eventually the longer selfish mining pool may win out by delaying their publication of their found blocks.

So I do think the algorithm can be refined somewhat by building in delays to try and defeat other selfish mining pools. Thus if this does get implemented we'll be seeing some kind of time wars... publish to late and one may be superseeded, publish too soon and one may be superseeded, however in this case one would always be superseeded so it makes no sense, and thus always publishing beyond two makes sense... either you truely have most processing power or not, however this does not include luck and by chance...

Perhaps the document describes these lines of thoughts and explains how to handle it or maybe not... maybe it was too difficult to analyze how the algorithm would perform against itself.

For now I shall give it a rest until further notice

Some points to sum up:

+ Find a block and keep it secret.
+ Find the next block for the secret block.
+ Publish the secret block if a public block is published.
+ Try to get the secret block published sooner.
+ Some honest nodes may work on the published secret block and if they find the next block the secret block wins.
+ Secret block has more chance of winning if random selection is implemented (this could be the true motive for the document, implementors of bitcoin beware ! ).
+ Currently fastest announced block seems to win.
+ Incentive to keep public blocks delayed.
+ Incentive to spy on other pools to detect early block announcement.
+ Incentive to detect traitors by selective announcing private blocks found by pool maintainer.
+ Spying on selfish pools is a potential counter-strategy if done in secret somehow.

I have no time to read carefully the paper but..

Some time ago I posted in http://bitslog.wordpress.com/2013/06/26/the-bitcoin-eternal-choice-for-the-dark-side-attack-ecdsa/ a solution to another attack that may also work to protect from this attack:


This protocol protects from the appearance of simultaneously competing blocks but also from other attacks that may based on hidden branches. So I'll refer the method as "hidden-branch-protection".

Does it help?

I think it is a little worse than that. An effective Sybil attack is necessary to make the attack viable for a small pool, but the larger the pool is,  the less effective the Sybil attack needs to be. For a pool larger than 33% of the network, no Sybil attack is required.

On the other hand, one mitigating factor that is not mentioned in the paper is that the attack buys you more revenue long term, but in the short term you will see a loss of revenue. You are not finding more blocks than before (in fact you are losing some of your blocks) so your income within a difficulty adjustment period will actually drop (but so will everyone else's). The increase in revenue comes later due to the fact that you caused others to lose blocks which makes the difficulty drop (or just rise less than it would have) which then nets you more blocks in the long run.

However, since
 a) The attack can easily be detected (sudden increase in orphaned blocks)
 b) The attack will negatively affect the bitcoin price.
the revenue impact of performing the attack is probably negative even in the long run.

Interesting document.

What seems to be missing is when multiple selfish-mining pools exist... what will happen then ?

Maybe one would be a bit faster than the other... though humans tend to want to oppose each other so I am thinking there will always be groups of people trying to defeat the others.

Maybe they would also do it to try and keep the system in balance or so. Then again maybe not.

The change seems simple enough to implement.

(During my first scan/read of the document my system frooze up completely, then I installed a new update of acrobat reader, and no more problems... I did clean my system two days ago or so and it been running all night so could be an issue with that... kinda weird though.. so then I read it in full it's a very interesting document and a very easy attack).

I am glad somebody with more mathematical background and statistical reasoning figured this out... I've wondered for a long time now what kind of benefit keeping the found block secret/private would have and how to exploit it... this document does a fine job of explaining all possibilities, and under all possibilities it's a good/beneficial attack with high likelyhood of working/accepted under the current bitcoin system.

The most funny thing is the parallel nature/exponential nature of it... the more people/miners join it, the better it starts to work... which reminds me of the king and the grain on the checkerboard/chessboard... it starts out small but ends up big How big I never knew but this document examines it more.

For this too work people would have to be convinced that they pay out on a selfish-mining-pool is greater than "honest" pools...

Also such data may fluctuate over time probably leading to multiple selfish mining pools... what happens then is unclear probably one will win out over the other... or perhaps it's too close too call and both continue to grow bigger, honest nodes/miners would then loose out... I don't really see it as honest vs non-honest... it's just a different way to handle the blockchain and new blocks.

Also I would totally not be surprised if some mining pools already implemented this in one form or another... I would surely have tried to do something like this... so the likelyhood of this already existing in the wild is super high.

Sounds more like this is a document written by somebody that got sick of the cheaters and wants to ratt out on them... to try and prevent system take-over/collapse on the long run protecting it's wealth thereby =D
(I read the document up to page 7, then skipped some of the state machine analysis and maths also read some page 12 about pool formation and page 13 fixing bitcoin).

Most fun document about bitcoin I have seen so far and it came out this week... lucky me... I just happened to come and see how bitcoin is doing or so I guess I had a hunch something was going on I dont know or I just got lucky wiee

Will be interesting to see how this plays out... even with the fix... it's going to remain problematic somewhat... apperently now 25% is enough for a selfish pool... but what if multiple selfish-pools exist ? hmmm

Maybe if multiple exists it won't be much of a problem. So that will be my next lookout... a document examining such a scenerio

One question that also remains unanswered in my brain is the following:

How far back (how many blocks) is a client allowed to switch branches ? Only 1 block ? or multiple ? or a fixed number ? Maybe 2048 ? Me rusty on bitcoin...

Isn't the economic benefit to joining the selfish pool easy to extinguish?

The further ahead the selfish pool is, the greater the cost to them if they lose that race.   The only economic benefit to the selfish miner comes from the block reward subsidy + fees from future blocks on that chain.  But if it becomes known that a selfish pool is operating then an incentive for defecting from the selfish pool/cartel can be offered (in a way so that it is not available to the selfish pool as well).   If those incentives cause mining on the selfish pool to be less rewarding then the selfish pool strategy can be defeated.

Wouldn't it be easy to tell if a block seems to be coming from a selfish pool (as each new block will appear to be laggng since it has no recently arrived transactions)?  So if this lag can be detected then cannot an incentive to honest pools be offered?

A way to offer this incentive so that it is only available to the honest miners is to periodically send a type of marker transaction.  There is a promise to pay an incentive/reward for including the marker transaction within N seconds after it is broadcast.  So the selfish pool's previously mined block would not be able to include this marker transaction promptly, but honest miners are including recent transactions and thus would be able to include it.  And then when that "included within N seconds" condition is true, those offering the incentive then send the incentive payment to the Bitcoin address for the coinbase transaction for that block.

[Edited]

I believe that the flaw with this system is that the success rate of your sybil attack has to be the inverse of your share of network hash rate.  For example, if you have 10% of network hash rate, you need your sybil attack to be successful >= 90% of the time in order to profit, otherwise you lose.

Consider:

's' = selfish pools share of network power (eg 0.1)
'o' = honest share of network power (eg. 0.9)
'a' = success rate for a sybil attack ('sybil attack' meaning you intercept an honest block, surpress its propogation, and propogate your own equal-length pre-mined chain which is seen by the mining majority).

The selfish pool will mine on the honest chain until it finds a block, at which point it withholds the block and begins mining on its own private chain.  The honest nodes will find the next block with probility 'o', which triggers a contest.  Eg. where the selfish pool has 10% hash rate, the selfish strategy will require them to execute their sybil attack on 90% of the blocks they mine.

Percentage of selfish pool blocks that will require sybil propogation = o.
Percentage of selfish pool work wasted from ineffective sybil attacks = o(1-a).
(Eg. with 10% hashrate and 50% sybil success rate, the selfish pool will waste 45% of their work.)

Percentage of honest workers blocks that suffer sybil attack = s.
Percentage of honest work wasted due to sybil attack = s*a.
(Eg. with 90% hashrate at 50% sybil success rate, the honest nodes will only waste 5% of their work.)

The reason why I compare the percentage of work wasted, is because that is the way to measure the relative return on hash rate invested.  If the selfish strategy wastes more % of work than the honest strategy, then it doesn't pay off to mine in the selfish pool.

Based on this formula, the selfish pool will only be at an advantage if 'a' (sybil success rate) is greater than 'o' (honest share of hashing power).  In other words, the sybil attack must be successful at a rate inverse to your mining power.

So, basically the main threat here is the sybil attack.

Can anyone spot any flaws in this analysis?

Vitalik Buterin's writeup on this on BitcoinMagazine.com

Selfish Mining: A 25% Attack Against the Bitcoin Network
 - http://bitcoinmagazine.com/7953/selfish-mining-a-25-attack-against-the-bitcoin-network

Beat me to it!

No; miners have a natural incentive to want to be closely connected to as many other miners as possible (to reduce orphan costs).

RE: Evaluating sybil resistance: I would still like to see blocks and transactions being broadcast over another completely different networking protocol, either peer-to-peer or not. More diversity so we're not relying on the one p2p network would be great, and, depending on how it was implemented, might automatically bring sybil resistance.