Majority is not Enough: Bitcoin Mining is Vulnerable
arxiv.org
arxiv.org
In theory. There are many complex and subtle issues that must be thoroughly analyzed before passing judgment on this paper. For example, what if other miners, instead of joining the selfish pool, decide to create their own competing selfish pools? Also, as nullc points out elsewhere on this thread[1] and the Bitcoin Forum[2], peering between miners is already so extensive that temporarily keeping blocks secret could be much costlier than assumed by the authors of the paper.
The Bitcoin community must go through this paper in detail, but IF the authors' logic and math prove correct, this could be a real vulnerability.
--
[1] https://news.ycombinator.com/item?id=6669735
[2] https://bitcointalk.org/index.php?topic=324413.msg3476697#ms...
--
Edits: moved paragraphs around and added sentence about and footnotes pointing to nullc's thoughts.
An actor concerned with the viability of Bitcoin, in this scenario, would simply join the selfish pool and turn double-agent, broadcasting the selfish block chain. Assembling enough human Bitcoin operators to dominate the present-day Bitcoin network that way, and keeping such a rowdy band of idealists in line, sounds implausible.
I think the authors demonstrate why this would not be a preferable strategy:
"above a certain threshold size, the revenue of a selfish pool rises superlinearly with pool size above its revenue with the honest strategy."
So why create a new selfish pool when you could benefit more from joining the largest existing?
In short, the new thing here is the assumption that the attacker uses a network positional advantage to eliminate the loss associated with delaying blocks.
I am not fond of their proposed solution, since it creates a size advantage for large miners (of sizes which have already existed) in all cases, even without the network attack.
I'd rather initially focus on strengthening the network against the formation of the positional advantage in the short term. (There is already some belief that there is extensive peering between miners making the attack ineffective, but its impossible to know if its adequate, so there is no harm in in strengthening that some.)
For example, let's assume a "levels" topology, where mined blocks propagate in discrete turns from the miner to its peers, then to their peers, etc. If there are more honest peers on the first level, wouldn't the "honest" block (X in the paper) propagate faster than the pool block, P?
BTW, I found the paper absolutely fascinating regardless of this relatively minor issue. As you said, even with gamma=0, an attack is feasible.
Unfortunately there's very little we can do to defeat this attack, other than have miners use strategies that aren't strictly economically rational in the short term for them. In practice a sufficient amount of miners may be willing to do this, but if they aren't we're going to need better countermeasures than that.
Former algorithmic trader here. This solution does not appear to be incentive-compatible.
Suppose there are two branches, 0 and 0'. Miner receives 0 first. The probability of mining a block is proportional to the time spent mining. Miner thus (a) starts mining 0 immediately upon notification and (b) has a greater probability of finding a block on 0 than 0'. It is thus in Miner's interest for 0 to become the blockchain versus 0'. Since other miners are following a similar logic, it is in the miner's interest to propagate 0 over 0'.
Randomly selecting which branch to mine is rational only if (i) both branches arrive at the same time and (ii) there is no information about which branch other miners are showing preference towards.
The probability of finding a block does not change based on how long someone already has been mining.
Consider a fair coin - even if you get tails 20 times in a row, the probability of getting heads on the 21st try is still 50%.
In contrast, the probability of getting a heads at least once in 20 tries is 1-1/2^20.
By way of directly illustrating this, consider slot machines with identical payouts. Grandma has been inserting coins into slot machine A for twenty minutes, when suddenly slot machine A' is turned on. There's no difference between continuing to pump coins into slot machine A and switching slot machine A', the expected payoff is the same either way.
Analogies to slot machines and flipping coins obscures this fact.
Storing the minimum target nonce seen during mining has a key-space of size 256+96=352bits { midstate + { merkle_root, ntime, nbits } }.
So 1/2^352 chance of ever having a collision. Or 2.725094297605216460742E-107. 107 zeros between the decimal and the first interesting digit.
However you wouldn't have indexed this because ntime (the current time) is always going to be unique, and nbits (the current difficulty) might as well be too.
A single bit change in any part of the key completely changes the result, so there is no pattern you can infer by only storing a prefix.
Such a strategy is doomed.
EDIT: ntime is effectively unique as it is the Unix time and will roll over after many years, but the Bitcoin network requires mined blocks to have an ntime within threshold of the current actual time.
You can't, that's why your argument works here. It wouldn't work on a system where the objective was to find a secret number in 1 to N.
Your mistake is in the last point. The probability of finding a block in the next X time units is completely independent of what you did in the past (unless you managed to break the underlying cryptographic hash somehow ;-)). You can think of mining as repeated coin throws (with an extremely biased coin).
Tangentially, the best side effect of HFT seems to be that a lot of technical people have become more sophisticated in understanding incentive structures and contracts. I wonder how that affects funding decisions for startups of the ex-HFT crowd.
Now with enough tries it will happen that you find two blocks in a row - again happens all the time with pools. But what you do is that you wait until the other pools find theirs. Once they find the block (you already found it remember?), or they've wasted many cycles finding it, you publish yours that you've found already.
By doing this you kind of selectively publish the blocks you find, wasting other pools cycles and sort of giving you a heads start for the next block search. It's all actually about building a pool that selectively publishes blocks so that it can get you a heads start for the next mining cycle. Miners will likely join this selfish pool because they'll have a heads start and not feel as though their hashing power is going to waste since it's constantly being invalidated by the selfish pool (by publishing blocks at specific times).
The paper assumes there's only one selfish pool. I presume that if a selfish pool arises, there will also be a variety of other selfish pools arising at the same time. If all pools are acting this way, then there's really no incentive for miners to go to any specific pool (avoiding centralization). So it will just be like regular mining again.
Are you sure? It seems like it might be skewed towards the larger pools.
For instance, right now, a pool with 25% of the computation will get 25% of the mining revenue. If everyone is selfish, though, perhaps the 25% pool gets more share of the revenue, at the expense of the other selfish pools?
The rewards enjoyed by selfish miners are super-linear in the size (power) of the pool. So it makes sense for selfish miners to merge their pools.
It seems to me, though, that as soon as a cabal of defectors successfully captures the mining process, a next generation of defecting cabals would immediately form, using the advance information from the previous winning group, and the process would simply repeat in waves.
That is, what we currently have is a group of miners who all share their information with each other as soon as they find it. That's exactly what a sub-group exploiting the instability you identified would look like once it won.
They assume working as a malicious/selfish pool having less than 50% of hash rate, but still a significant portion of the total hash rate. All other miners that are not part of the selfish pool are called honest miners.
When selfish pool finds a block, they don't advertise it but continue mining their forked, private blockchain. They have an advantage of one block over the public blockchain now. Of course they have no chance of building longer blockchain in the long term, as they have less than 50% of hashing power and the public blockchain will always get longer after some number of blocks. But what they count on is this:
Scenario 1: honest miners discover a block and the public blockchain gets the same length as the selfish blockchain. They immediately publish their block as soon as they discover someone else discovered a block. They hope to create a race condition and a public blockchain fork - so that some hones miners will get the “honest” block, but some of honest miners will get their “selfish” block and start mining using it as a base. Having some of the honest miners on their side they have a chance that their fork will get longer and the “honest” fork will be declined by the network.
Scenario 2: selfish pool is lucky and discovers another block, giving their blockchain two blocks advantage over the public blockchain. They continue mining and they publish one block for every block discovered by the honest miners. This creates race condition with some of the honest miners on their side, but they still have some blocks found and not published. They publish all their remaining blocks as soon as their advantage decreases to one block. The network chooses their branch as it's longer and they get all the reward coins from their secretly mined chain.
Now, I know nothing about blocks discovery/notification mechanisms over the network and how fast it works, so an important question to someone knowledgeable is if this is a probable scenario that their block published only after some competing block has been found and published has still a chance to get to some significant number of honest miners first so that they start mining over their block - as this is required for their strategy to work.
If the above is viable, then this strategy of course requires some significant hash rate share, but I remember that even having 10% of total hash rate, the probability that you will mine couple of blocks in a row is quite high - and that's all you need to create situations when you have two-three blocks advantage over the public blockchain.
"When the public branch is longer than the private branch, the sel fish mining pool is behind the public branch. Because of the power di fferential between the selfi sh miners and the others, the chances of the sel fish miners mining on their own private branch and overtaking the main branch are small. Consequently, the selfi sh miner pool simply adopts the main branch whenever its private branch falls behind. As others find new blocks and publish them, the pool updates and mines at the current public head."
"When the sel fish miner pool finds a block, it is in an advantageous position with a single block lead on the public branch on which the honest miners operate. Instead of naively publishing this private block and notifying the rest of the miners of the newly discovered block, sel fish miners keep this block private to the pool. There are two outcomes possible at this point: either the honest miners discover a new block on the public branch, nullifying the pool's lead, or else the pool mines a second block and extends its lead on the honest miners."
"In the first scenario where the honest nodes succeed in finding a block on the public branch, nullifying the sel fish pool's lead, the pool immediately publishes its private branch (of length 1). This yields a toss-up where either branch may win. The selfi sh miners unanimously adopt and extend the previously private branch, while the honest miners will choose to mine on either branch, depending on the propagation of the noti fications. If the selfi sh pool manages to mine a subsequent block ahead of the honest miners that did not adopt the pool's recently revealed block, it publishes immediately to enjoy the revenue of both the first and the second blocks of its branch. If the honest miners mine a block after the pool's revealed block, the pool enjoys the revenue of its block, while the others get the revenue from their block. Finally, if the honest miners mine a block after their own block, they enjoy the revenue of their two blocks while the pool gets nothing."
"In the second scenario, where the sel fish pool succeeds in finding a second block, it develops a comfortable lead of two blocks that allow it with some cushion against discoveries by the honest miners. Once the pool reaches this point, it continues to mine at the head of its private branch. It publishes one block from its private branch for every block the others find. Since the sel fish pool is a minority, its lead will eventually reduce to a single block with high probability. At this point, the honest miners are too close, so the pool publishes its private branch. Since the private branch is longer than the public branch by one block, it is adopted by all miners as the main branch, and the pool enjoys the revenue of all its blocks. This brings the system back to a state where there is just a single branch until the pool bifurcates it again."
The attacking pool will need enough hashpower to discover blocks 0 and 121 before the network discovers block 121, even then, they will only get paid 25 btc + transaction fees for their trouble.
Also, 10 hrs is plenty of time for paranoid miners to figure out and mitigate such an attack.
Edit: grammar
They are playing odds, but they are behaving such that 'on average' they have an advantage over the honest peers. When they get lucky, they can use their temporary advantage to race ahead, until eventually settling back into the normal flow and thus generate the (legitimate) block chain for a short period. Because of this control, they get more bitcoins than average miners.
They aren't generating illicit coins, lying about transactions, double spending, or anything like that. They are happy to wait for the 120 block confirmation and spend the coins whenever.
It could easily be detected by nodes by checking the age of the transactions inside the block.
An honest node block would contain more recent transactions than a bad node block
It's obviously the wrong move, but just because you're a sociopath doesn't mean you're smart.
I hear people say to me all the time that it's "ok if I'm the only one doing it". If this papers strategy is effective, it is a realistic threat that lowers the bar necessary to destabilize the network. 33% to take over the network, but much less to start the ball rolling.
Does a "vested interest in high prices" stop anyone from gaming any economy, or is it a vested interest in current high prices that causes them to?
I would think miners have an interest in their profitability which happens to be exponentially squandered every day as hashing power joins the network, and every two weeks as difficulty is re-calculated.
The proposed selfish mining strategy in a nutshell is: when you find a block, keep it secret in the hope of finding a second one that will give you the leverage to start messing around. If someone else finds a block before you find your second, go ahead and publish.
Since by hypothesis you have a minority of the total computing power, usually someone else will find a block before you find your second.
But by the time you become aware of this, at least some other miners are also aware of it, whereas no others are yet aware of your block. With the 'first wins' tiebreaker, usually that means your block gets lost. So most of the time you lose out. So on average, selfish mining loses, at least as long as your computing power is small compared to the network total.
Is there something I'm missing?
Correct me if I'm wrong, but even if you've got future blocks precomputed for weeks in advance, all it takes is someone else finding the current block by chance to completely invalidate your private chain?
even if you've got future blocks precomputed for weeks in advance, all it takes is someone else finding the current block by chance to completely invalidate your private chain?
No, because peers use the longest valid chain (more or less) regardless of when it is revealed.
If I understand correctly, the only way to do this would be to get a private chain longer than the typical number of accepted confirmations, which is currently 6 for most merchants. In this method, you spend the coins, wait for 6 confirmations, the merchant ships the product, and then you reveal a longer chain where those coins were never spent. However, getting a chain advantage of that length is extremely unlikely without a massive fraction of the network power.
The attack described is for pools where they lack a majority of the processing power, but still have enough power to occasionally make chains at least a couple blocks longer than the rest of the miners.
For example, even if I'm a pool with 25% of mining power, I could still occasionally find 2 blocks in a row. But I won't maintain that lead because in general, over time, for every 1 block I find, 3 other blocks will be found.
It looks like this paper's technique is to take advantage of those temporary situations where one pool is lucky enough to get ahead.
I have a hard time seeing a majority of miners sabotage themselves like this, but preemptive solutions are definitely worth looking at.
I don't see how this will work in practice. If you're keep discovered blocks private, how are you taking part in bitcoin as a whole? You're just sitting on private info about transactions that may as well be made-up.
That's why miners are normally incentivized to release a block as soon as they find it. If they don't, and a different block is found and then a block is found that builds off that one, the "secret" block will probably never be part of the longest blockchain. And the longest blockchain is "the blockchain."
Sorry this comment can't be more helpful, I haven't read the paper yet.
By doing this, assuming they can, they don't suffer from orphaning due to their delays.
Let's make it simple. Take Y = I order 100k USD from some bank, pay with bitcoin. Y' = I pay 100k USD equivalent in bitcoin to myself. Suppose I discover a block significantly ahead of the public mining pool
Public: X + Y Mine: X + Y'
Now I reveal the X + Y' chain to part of the network, but not the part where the "target" of the Y transaction is located. And suppose I can get 50% hashrate working on my chain that way. Evolution
Public X + Y + Z1 + Z2 + Z3 (bank confirms transaction after 3 blocks, pays out my 100k USD) Mine X + Y' + Z1 + Z2 + Z2
At this point I put all my spare chips in. I suddenly "discover" 2 blocks. Result
Public X + Y + Z1 + Z2 + Z3 Mine X + Y' + Z1 + Z2 + Z3 + Z4 + Z5
And I re-unify the network at this point. All miners accept the "mine" blockchain, and I was able to confirm one transaction, get the payout, and undo the payment.
(obviously in reality, you'd use many tiny transactions, not one big one, and Z1 + Z2 + Z3 + Z4 + Z5 would only be able to contain transactions from the traitor network + whatever miners joined it after it was X + Y', and and and and and ... But I don't see a good reason it couldn't work)
Maybe you could make this work if you had an internet partition. (happens all the time, but you'd need a pretty big one)
Even simply acquiring the bids to verify transactions into the chain could make it worthwhile. When the "selfish" chain is published, it takes two blocks of transactions from anyone else, plus it has given the "selfish" miners the entire period from when they last discovered a secret to when they played their hand to mine for the block that will follow.
It may allow them to capture a greater portion of the main chain by denying information to other chain agents unless beaten or trumping.
Actually, that would be a good term for the method. "Trumping" the chain.
This means they still get some advantage, in a time lead over the general network, but they balance out some of the costs and risks of waiting. They will get their lucky block-ahead of the network less often, but perhaps it is a better strategy. Fascinating stuff.
(Note that essentially the same consideration applies to making and selling mining hardware vs. making it and keeping it to use to mine.)
There is a value in risk distribution that can cause mining hardware to be a good idea to rent out pieces of even if you're likely to make money on it, as long as the risk of losing money isn't trivially small.
In theory, what is the worst thing that could happen if a "selfish" version of Bitcoin was released?
(I see that bitcoin is another sacred cow.)