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

Selfish Miner can also pre-broadcast his Merkle tree.

The interesting points of this solution are to minimize the advantage of the low latency connection of the selfish miner.

Yes, a crucial step in this SM attack is to release two blocks one after one immediately . This kind of behavior is not normal and meaningless. If we can stop this kind of behavior, we can prevent the SM attack.

I originally thought of it as a way of more efficiently scaling to very large block sizes, but it might have the added effect of making this attack more difficult too.

Here, I compiled v2 of the paper from its TeX source.  There's some error producing the citations but you can still read the text.

https://dl.dropboxusercontent.com/u/3133557/Bitcoin/btcProc.pdf

I thought difficulty related to the number of LEADING zeros, not trailing zeros...

I feel that this post might be the solution to this 33% attack.

As a valid block must be pre-broadcasted in the step 2), earlier than a certain time period, and there is a single time system globally, the Selfish Miner's private block should not be seen as valid if it has no pre-broadcasted Merkle tree.

This precautions essentially makes everyone can announce a block no faster than a certain speed, so that we can constrain the centralization of Bitcoin mining power.

It's indeed a bit more complex than the article (who's link is now broken, apperently the pdf converter crashed... update: v1 seems to still be available, v1 is from 1 november, v2 seems to have crashed, v2 is from 4 november) seems to make out, at least from the algorithm, but later it examines the revenues at page 9, which is basically what my posting below is about, however their algorithm does not include my refinement below, I don't think their algorithm includes spreading/delaying techniques, sometimes sabotaging the enemy or sometimes helping the enemy when it's beneficial, ofcourse this needs to be formulated in code/extra lines but it shouldn't be too hard, my posting examines the friction between calculation speed versus spread speed and could help to make more clear decisions of what to do in certain cases:

Let's denote the attackers as the secretives: S
Let's denote the public as the publics: P

Working on blocks now has a few possibilities:

PSS
PSP
PPS
PPP

Both start working on the previous public block indicated by the first P.

PS   (Group S works on next block S based on block P)
PP   (Group P works on next block P based on block P)

Both find their block at the same time.

S wants to keep it secret to continue work on the next S.
P wants to publish their P.

Here it's clear that S wants to delay P as long as possible, so here a delay of the enemy/P is beneficial towards S, you agree with this so far ?

Now suppose P was late.

(the first P of the three letters is now ignored so:
SS
SP
PS
PP
are the possibilities)

S can now comfortable work on their next S.
P catches up and publishes their first P.

S now has to publish their first S and does so and hopes to win from P. Again here S has a incentive/benefit to delaying P.

However let's assume S is not too successfull at delaying the spread of block P.

And now both blocks arrive at miners, both blocks are now candidates to be included into the block chain.

Now a situation occurs where S has a benefit to help P spread their next block P as fast as possible but only if next block P was based/calculated on block S.

Otherwise again S has a benefit at delaying next block P. If next block P was not based on block S then block S loses their block and instead block P becomes the main chain followed by next block P.

Therefore for this selfish mining algorithm to work well blocks have to be analyzed.

Sometimes it's beneficial for S to sabotage/delay P and sometimes it's beneficial for S to help/speed up spread of P.

However this assumes that S cannot quickly enough calculate next block S, if they instead could then it would still not be wise to help P.

However it's more likely that next block P will spread before they can calculate next block S based on previous block S so it's seems clear to take the money and run... be statisfied with what you got so far.

However it's clear that there is some friction here.

Calculation speed of next block S based on block S versus spread of next block P based on block S.

S now has a choice:

1. Delay spread of next block P based on block S and thereby undermining it's own block S in the hopes of calculating next block S based on block S itself and thus getting a double reward.

versus

2. Acceptance of spread of next block P based on block S and thereby at least embedding block S into the main blockchain and throwing away calculations on next block S and starting over based on next block P and thus getting a single reward.

As long as calculation speed of next block S based on block S is slower than spread of next block P based on block S it seems to make sense to choose option 2.

In other words, the algorithm will need to be adaptive and determine if the spreading block of the opponent was based on a previous block from S or a previous block from P and take a decision on that and do what it thinks is best based on speeds, calculation speed versus spreading speed. Spreading speed seems to be in a few seconds, while calculation speed can be 10 minutes.

However other factors may influence this, denial of service attacks, network attacks, crashes etc.

(Also this posting only looks at S versus P, it does not include S versus S versus P )

One problem with this logic of yours is that it does not include the possibility of an entire existing mining pool to switch software over to the new selfish-mining algorithm.

This will quickly change the bitcoin game

However perhaps this is mosterd after the meal, perhaps it already happened a few years ago. What ever happened to deepbit mining pool ? Did it merge or did it disappear ? or rename ? Or was it eclisped by other mining pools, perhaps people left that pool and flocked to others

If many (or even most) blocks mined by this pool have corresponding orphan blocks, then we have enough reason to put it in the alert list.

It only becomes a problem if this pool owner (eg. some governments) wants to destroy the bitcoin. Otherwise, they will voluntarily reduce the hash rate (just as BTCGuild already did) to avoid being close to 51%. They have to do this, because their business is based on the validity of BTC and once their hash rate is close to 51%, the market will crash and so does their business.

a slightly different question:

how would we detect if such an attack is taking place?

As far as I understand, the attacking miner would have a slightly higher
ratio of blocks broadcast in pairs. That is, normally if his block rate  is alpha
then  rate for pairs should be alpha^2,  but if he is running the attack this value would
be slightly but significantly higher, and depends on gamma (how successful he is with
his sybil attack). It'd take a long time to detect though

This is economically irrelevant to the total bitcoin and that's why markets didn't seem to care.  No extra bitcoins are created here.  It's more of an issue of one group trying to "steal" mining revenue.  But they already do that.  That's what the competition in solving and publishing blocks is all about.  If a pool holds back a solved block isn't it true that individual miners can see that they found a solution but it hasn't been published?  Couldn't they then hop to another pool and claim the reward there as well or perhaps try to publish directly themselves solo?  Basically I find out this "evil" pool exists and game it.  I mine in pps format and if I find a block I know this pool will hold it back and not publish so then I simply grab that solution and try to publish elsewhere and if I succeed then don't I get paid twice?

Ok, what about that problem:

Some guy with deep pocket (government?) establish a very stable mining pool with the best
protection agaisnt ddos and with the lowest network latency possible and welcomes everybody to mine with 0% (or even negative) fee.

So, eventually he will get 51% of hashing power, will not he?
And he even do not need to exploit the problem discussed in this thread, he can just be the honest mining pool.

The problem with this paper, I think, is that it uses a much stronger assumption than Satoshi's, that it's a strictly one malicious miner vs a bunch of honest/profit maximize miners scenario, implying the malicious miner miraculously knows every other miner to be honest, profit-maximizing, yet they know hardly anything about him, while in Satoshi's assumption, you basically mine against a number of peers which are unknown to you.

This makes a big difference from the game theory perspective: how can the malicious miner be sure that no one else is going to copy his strategy, forming a even bigger mining coalition, and force him to become his own strategy's victim and lose everything? He will have to think hard to devise a way to guarantee his success, so that nobody can defeat him in his own game, and work out the amount of hashing power he needs to acquire for such guarantee, after several days of work, he is finally done! And congratulations, he has just rediscovered the old and true "51% attack".

The issue here is the definition of work. Work is based on the target, and not based on the block hash itself. It is a statistical fallacy to claim that a block with a lower hash required more work than another block mined with the same target.

When two blocks have the same target, the earliest-received is preferred.

How often does it happen that two miners simultaneously find a block with exactly equal work values?

Sorry for confusing you there. Obviously any node prefers the highest total work— the protocol isn't convergent otherwise. This is about blocks which have equal work. Nodes prefer the first heard among those with otherwise equal work. The obvious alternative policies create issues like... incentives for large miners to delay their announcements.

Rogue governments and banks have deep pockets.  They could simply pay a small premium to their pool members, and get people to join their pool that way.  They hardly need to use the complicated strategy disclosed in the paper to improve their payout.

This probably won't happen.  If it did, it wouldn't happen overnight, and the developers would have ample time to make some new rules about maximum pool size and forking and push them out to everyone, before the evil pool reached any sort of critical mass.

So 99.9% chance the paper is forgotten in a week, and no one cares enough to implement it.  0.1% chance someone decides to run with it, it is instantly noticed, sticks out like a sore thumb, and in the unlikely event large numbers of people start climbing on, we probably have months to make a tweek before it becomes any sort of problem.

The blockchain fork between different versions of the client was a 100 times worse malfunction than this thing ever could be, and that was dealt with successfully in short order.

That's right, which is included in the paper.  The problem of course is that to get 2 blocks ahead you have to first withhold your first block, and if you are a minority miner then you're going to get orphaned far more often than you would find 2 blocks in a row.  So the result is you end up losing a huge majority of your revenue trying to hit these streaks, and since you rarely hit these streaks, it has minimal impact on the rest of the miners.

The selfish strategy just simply does not work unless you can win these orphan contests nearly every time.  Even if the selfish miner becomes amazingly connected and has super low latency to many nodes in the network, what's to stop another miner doing the same?  So its a big stretch to just assume that a selfish miner can always win these races.  It needs to be demonstrated in practice for this to be a serious threat.

A better solution is to allow both types of blocks for the next year, then force the new type of block. No ASIC is going to last a year.