Pay miners to rewrite block(s)?

[JoelKatz]

So a corrupt miner would, if he is rational, cooperate with other corrupt miners.

Correct. Your analysis however assumes that the other miners will blithely accept his blocks if he wins the fee.

They should accept the longest chain. That's how BitCoin works. If he can make his chain longer than theirs, he should win.

The odds for a corrupt miner working by himself are even worse than you suggest because the other miners, seeing that they have not been "cut in" are not going to accept the lone miner's blocks. Even in 1% chance that the 10% miner gets two blocks, the other miners will not accept his blocks and will rapidly regain the longest chain.

Why wouldn't they accept his blocks? If his chain is longer than theirs, it's the "real chain" as far as they are concerned.

It seems plausible, given completely rational miners, that the rewrite would not be accepted unless >50% of the hashing power consents.

All the attacker has to do (not that this is easy, of course) is at some instant in time, possess a chain larger than the legitimate chain that does not include the transaction he wishes to revert.

You are quite correct, of course, that I understate how difficult it is to produce such a chain. But once you have such a chain, you win. All other miners should accept it immediately or else they're wasting their time.

[hannesnaude]

Case 2: I have 10% of the world's mining pool. Two blocks have to be rewritten. But I conspire with another 10%. The odds we'll rewrite the transaction are 20% of 20% or 4%. Since I'm half the conspiracy, if the blocks are rewritten, there's a 50% chance I get the money. 50% of 4% is 2%. So there's a 2% chance I'll claim the funds.

So a corrupt miner would, if he is rational, cooperate with other corrupt miners.

Whether this is true depends on you strategy when you successfully mine the 1st block. If you take the naive approach and just keep mining in order to get the 2nd block as well, one has to assume that your co-conspirators will dessert you, since there is no longer anything in it for them. So the odds that you get the money is still 10% of 10% = 1%. In other words you have to get both the first and the second block yourself, getting the 2nd after someone else got the 1st will net you nothing, and therefore getting the 1st while some helpful soul gets the 2nd for you is so unlikely as to be negligible. Unless you have some fixed agreement with you co-conspirators to remain loyal in these cases in which it makes more sense to see you as one block of 20% rather than 2 blocks of 10%.

Therefore the rational thing to do in order to pull others in is to immediately upon successful mining of a block issue a transaction that offers a further bribe for the next block by using your fraudulent gains as input and offering a substantial tx fee. So the question is, how much do you offer? Or, more to the point, how much do others typically offer? If, for example, other corrupt miners offer nothing and try to overtake the chain by themselves, then you would have been better off not relaying the initial bribe tx to them in the 1st place, since your chance of netting the bribe is unaffected (you still need to get the block yourself to claim the bribe).

I also realized recently that one should not assume that pool owners (or large scale miners of any sort) won't do this since it will hurt bitcoin and therefore themselves in the long term. The existence of derivative instruments like bitoption.org means that for all we know a power miner may be short on bitcoin in the long term, making him willing to partake in such attacks irrespective of the bribe offered. Right now there's nowhere near enough volume traded on bitoption to justify this, but I suspect that lots of people here are so bullish on bitcoin that if anyone were to offer a truly cheap call option, they would get snapped up like hotcakes.

[kjj]

It should be trivial to calculate how many blocks to wait before accepting a payment as valid, based on an estimate of the fraction of the world's hashing power under the control of the single largest corrupt mining organization.

[JoelKatz]

It should be trivial to calculate how many blocks to wait before accepting a payment as valid, based on an estimate of the fraction of the world's hashing power under the control of the single largest corrupt mining organization.

The problem is that the incentive to mine drops while the incentive to steal stays the same. So the time you may have to wait could go up significantly over time.

[kjj]

It should be trivial to calculate how many blocks to wait before accepting a payment as valid, based on an estimate of the fraction of the world's hashing power under the control of the single largest corrupt mining organization.

The problem is that the incentive to mine drops while the incentive to steal stays the same. So the time you may have to wait could go up significantly over time.

It is much harder to reverse a transaction that is buried in the chain than one in the most recent block.  If the recipient waits 5 blocks, even an attacker with half of the hashing power in the world has about a 1.5% chance of reversing it.  And that is assuming they start now and work until the end of time.  What fee would be large enough to make it worth a miner's time and effort, but small enough that the recipient won't wait for it to get buried?

[JoelKatz]

It is much harder to reverse a transaction that is buried in the chain than one in the most recent block.  If the recipient waits 5 blocks, even an attacker with half of the hashing power in the world has about a 1.5% chance of reversing it.  And that is assuming they start now and work until the end of time.  What fee would be large enough to make it worth a miner's time and effort, but small enough that the recipient won't wait for it to get buried?

I agree. This is a theoretical risk that would be practical only under circumstances that are extremely unlikely.

More importantly, it is an intentional property of the design. For any cryptographic system, the designer should be able to say, "Someone can break this system if they do X, and X is hard enough to do that we don't have to worry about it." The system gets weaker either if X gets more practical or someone finds an attack that is easier than X.

An attacker producing a longer chain is the intentional, by design weakest link in BitCoin. This is BitCoin's X.

Rational people will always be able to reliably estimate how long to wait and add a sufficient safety factor. For small transactions, this will almost always be no time at all. For very large transactions, it might hit two hours or so under unlikely but possible future circumstances.

[kjj]

It is much harder to reverse a transaction that is buried in the chain than one in the most recent block.  If the recipient waits 5 blocks, even an attacker with half of the hashing power in the world has about a 1.5% chance of reversing it.  And that is assuming they start now and work until the end of time.  What fee would be large enough to make it worth a miner's time and effort, but small enough that the recipient won't wait for it to get buried?

I agree. This is a theoretical risk that would be practical only under circumstances that are extremely unlikely.

More importantly, it is an intentional property of the design. For any cryptographic system, the designer should be able to say, "Someone can break this system if they do X, and X is hard enough to do that we don't have to worry about it." The system gets weaker either if X gets more practical or someone finds an attack that is easier than X.

An attacker producing a longer chain is the intentional, by design weakest link in BitCoin. This is BitCoin's X.

Rational people will always be able to reliably estimate how long to wait and add a sufficient safety factor. For small transactions, this will almost always be no time at all. For very large transactions, it might hit two hours or so under unlikely but possible future circumstances.

If chain reversal required an exponential increase in demonstrated difficulty, rather than merely an improvement over equality, a transaction could be made absolutely safe after some number of blocks have passed, instead of merely statistically safe.  The effort would be minimal, and my estimate of the side effects are likewise minimal, but there is no desire to do even that, because block chain attacks are horribly impractical, even today, and they get less practical by 40 or 50% every couple of weeks.

[JoelKatz]

If chain reversal required an exponential increase in demonstrated difficulty, rather than merely an improvement over equality, a transaction could be made absolutely safe after some number of blocks have passed, instead of merely statistically safe.  The effort would be minimal, and my estimate of the side effects are likewise minimal, but there is no desire to do even that, because block chain attacks are horribly impractical, even today, and they get less practical by 40 or 50% every couple of weeks.

Do you explain a mechanism for doing that anywhere? Or could you sketch it out here?

I think they may get slightly more practical in the future. I think the gap between purpose-built fully custom mining hardware (that would only be profitable if you could attack the chain) and commodity hardware (that would be used by miners) will increase over time. And I think it's at least possible that the interest in mining may drop over time and thus the resources an attacker might need relative to those he could muster might decrease.

Consider a person who designs and builds a beast with 1,000 fully-custom chips. Current cost would be around $10,000,000. You can't make that back by mining.

[kjj]

If chain reversal required an exponential increase in demonstrated difficulty, rather than merely an improvement over equality, a transaction could be made absolutely safe after some number of blocks have passed, instead of merely statistically safe.  The effort would be minimal, and my estimate of the side effects are likewise minimal, but there is no desire to do even that, because block chain attacks are horribly impractical, even today, and they get less practical by 40 or 50% every couple of weeks.

Do you explain a mechanism for doing that anywhere? Or could you sketch it out here?

I think they may get slightly more practical in the future. I think the gap between purpose-built fully custom mining hardware (that would only be profitable if you could attack the chain) and commodity hardware (that would be used by miners) will increase over time. And I think it's at least possible that the interest in mining may drop over time and thus the resources an attacker might need relative to those he could muster might decrease.

Consider a person who designs and builds a beast with 1,000 fully-custom chips. Current cost would be around $10,000,000. You can't make that back by mining.

I think that they will become less practical.  Currently there are a small number of miners that are mostly in it for the reward.  In the future, I think there will be a large number of miners that are mostly in it for the security.  Dedicated hardware will make it even more so.

Exponential difficulty increase summary:

Consider the longest honest blockchain fork that is likely to happen innocently, now pick a smallish number, still somewhat greater than that, call it X.  6 is probably a suitable number for X.

A node gets a new block in, that extends a side chain instead of the main chain.  For the new chain to replace the main chain, the node must replace a number of blocks, call this Y.  I don't think that Y has been greater than 2 yet.  By my estimation, it should happen every 27 million blocks or so.  But my estimate is based on a tiny data set, there could have been a 3 or 4 block reversal in the early days that I don't know about.

Now if Y is less than X, the chain with the highest difficulty wins (this pretty much always means the longer chain).

However, if Y is equal to or greater than X, it calculates: current_difficulty*2^(Y-X).  If the difference in difficulty between the current chain and the proposed chain is greater than this amount, the proposed chain is accepted.  If it is less than that amount, the proposed chain is still ignored, but kept on hand in case it continues to grow.  Notice that 2^(Y-X) grows rapidly, quickly exceeding even unimaginable hashing power.

The side effect is that it can cause a fork in the chain to become permanent, at least until humans intervene.  But this side effect is unlikely, and the more nodes that would need to be fixed by hand, the less likely it is.  If the earth was literally chopped in half, and all radio communication was prevented between the halves, we would have a hell of a mess to sort out.  You know, after we defeat the aliens that cut the planet in half, and glue the two halves back together.

[JoelKatz]

Unless I'm misunderstanding, this means that two clients that both see precisely the same blocks right now may choose different chains because of what order they saw the blocks even if the two chains have different difficulties.

[kjj]

Unless I'm misunderstanding, this means that two clients that both see precisely the same blocks right now may choose different chains because of what order they saw the blocks even if the two chains have different difficulties.

Yes, exactly.  This prevents a miner with a lot of power from building their own chain and keeping it private until it is longer than the real chain.  And X is chosen to make it unlikely to happen during normal operation.

Oh, but keep in mind that these two nodes have to be isolated from each other, but still in contact with enough mining power to produce blocks in reasonable times.  That means totally isolating part of the internet, and keeping it isolated for a minimum of about 2 hours (assuming the mining power on each half of the divide is equal).  The less equal the division, the longer the isolation needs to last before the fork becomes permanent, and also the less difficult the manual cleanup after will be.

[JoelKatz]

Unless I'm misunderstanding, this means that two clients that both see precisely the same blocks right now may choose different chains because of what order they saw the blocks even if the two chains have different difficulties.

Yes, exactly.  This prevents a miner with a lot of power from building their own chain and keeping it private until it is longer than the real chain.  And X is chosen to make it unlikely to happen during normal operation.

Oh, okay. You're trying to prevent a different attack from the one I'm imagining. I'm much more worried about an attacker who only changes four or five blocks. (So if you're willing to wait an hour, you're good IMO.)

Oh, but keep in mind that these two nodes have to be isolated from each other, but still in contact with enough mining power to produce blocks in reasonable times.  That means totally isolating part of the internet, and keeping it isolated for a minimum of about 2 hours (assuming the mining power on each half of the divide is equal).  The less equal the division, the longer the isolation needs to last before the fork becomes permanent, and also the less difficult the manual cleanup after will be.

I don't see why. The two nodes can be talking to each other directly and each 100% agree on which blocks are available and still pick different chains. Your algorithm only makes any difference if some client at some point knowingly chooses a chain that is not the longest one on the basis of how it got to that point. Any other client that starts up during this condition, lacking that same history, will pick the longer chain.

[kjj]

Unless I'm misunderstanding, this means that two clients that both see precisely the same blocks right now may choose different chains because of what order they saw the blocks even if the two chains have different difficulties.

Yes, exactly.  This prevents a miner with a lot of power from building their own chain and keeping it private until it is longer than the real chain.  And X is chosen to make it unlikely to happen during normal operation.

Oh, okay. You're trying to prevent a different attack from the one I'm imagining. I'm much more worried about an attacker who only changes four or five blocks. (So if you're willing to wait an hour, you're good IMO.)

Yup.  And if a transaction is worth paying to have reversed, it is probably also worth waiting for.

Oh, but keep in mind that these two nodes have to be isolated from each other, but still in contact with enough mining power to produce blocks in reasonable times.  That means totally isolating part of the internet, and keeping it isolated for a minimum of about 2 hours (assuming the mining power on each half of the divide is equal).  The less equal the division, the longer the isolation needs to last before the fork becomes permanent, and also the less difficult the manual cleanup after will be.

I don't see why. The two nodes can be talking to each other directly and each 100% agree on which blocks are available and still pick different chains. Your algorithm only makes any difference if some client at some point knowingly chooses a chain that is not the longest one on the basis of how it got to that point. Any other client that starts up during this condition, lacking that same history, will pick the longer chain.

I'm not sure from this part if I'm misunderstanding your meaning, or if you are fuzzy on how the current chain dispute resolution protocol works on the network.

As soon as a block is found, the miner announces it to every attached node, and they broadcast it to their attached nodes, etc, until it spreads across the entire network.  The spreading across the network takes some time, but not much.  Another node might also find a block at roughly the same time, and announce it too.  Now there are two "next" blocks on the network, both legitimate.  The nodes handle it by trusting the one they get first, since the difficulty will always been the same (otherwise one or the other would be invalid).  When the second block arrives at a node, it is stored as an alternate.  On the network as it is now, this happens roughly once per 200 to 400 blocks by my estimation, that is, every couple of days.

So, now all the miners are working on the next next block, but the next next block they are working on corresponds to whichever next block made it first to the node running the miners.  The next next block that is found will determine which of the two previous next blocks wins the race.  As it spreads across the network, it will cause a single block reversion on those nodes that had initially seen the other next block first.

Unless, of course, a second next next block is found and announced before the first next next block has had enough time to reach every node.  In this case, every node now believes one of the two chains, and keeps the other around as a potential alternate.  I'm ignoring the chances of the fork forking here, but that just restarts this phase of the race.  I estimate by multiplication that this happens about once every 40,00 to 160,000 blocks.

It can go on from here, of course, but the odds are already stacked against it.  Of the first pair, one of them was probably slightly sooner than the other, and the network is probably not very evenly distributed, so most likely one block will be on more nodes than the other, which means that more miners will be working on one of them and the next will probably be found sooner for it.  The second pair has all of the same imbalances, plus it started off on a lopsided network.  The more blocks are involved in the fork, the more the coincidences have to pile up just to keep the fork from resolving.  If my 1 in 300 estimate is even close to right, I won't live long enough to see a fork get to 4 (and probably not even 3).

[JoelKatz]

My issue is that you are introducing path dependence in the chain. For example, if the attacker aggressively connects to new clients and pushes them onto his chain, he can stick them on his chain and they won't switch back to the main chain, even if its difficulty is greater. This could cause someone using that client to believe they had received some BitCoins, believe they're confirmed for a few blocks, and then still ultimately have them rejected.

You are trying to make the client 'sticky' so it gets stuck on the main chain to prevent it from getting diverted to a short-term side chain that will eventually collapse. But in exchange, you run the risk that a newly-started client that is catching up before the fork can be duped by a malicious client onto a side chain and it will stay on it longer even as the main chain exceeds its difficulty. The attacker can continue to build the side chain and the main chain has to get further and further ahead of it to win.

Yes, you make it very hard to push the client over to a side chain. But you also make it very hard to get a stuck client off a side chain that is being slowly grown by a malicious attacker.

[kjj]

My issue is that you are introducing path dependence in the chain. For example, if the attacker aggressively connects to new clients and pushes them onto his chain, he can stick them on his chain and they won't switch back to the main chain, even if its difficulty is greater. This could cause someone using that client to believe they had received some BitCoins, believe they're confirmed for a few blocks, and then still ultimately have them rejected.

You are trying to make the client 'sticky' so it gets stuck on the main chain to prevent it from getting diverted to a short-term side chain that will eventually collapse. But in exchange, you run the risk that a newly-started client that is catching up before the fork can be duped by a malicious client onto a side chain and it will stay on it longer even as the main chain exceeds its difficulty. The attacker can continue to build the side chain and the main chain has to get further and further ahead of it to win.

Yes, you make it very hard to push the client over to a side chain. But you also make it very hard to get a stuck client off a side chain that is being slowly grown by a malicious attacker.

I actually don't care about one node, or even a small percentage of all nodes.  Nodes are expendable.  Their operators will figure it out eventually.  I want to protect the network from accepting a bogus chain grown in the dark to overturn transactions long thought safe.

Oh, and I only see your scenario working as a very targeted attack.  There is no way an attacker could place themselves in a position to take on all 8 connections from even a tiny fraction of random new nodes.

[da2ce7]

In the long run... this is a mutually assured destruction.  As the owner of the first transaction will just make a new competing transaction with higher fees than the doubble spend...  If this is an automated process, very quickly the frees reach 100% of the transaction.  This is a good tool to make as an disincentive of stealing coins (where you want to stop the thief to have any coins).

Not such a good attack to a shop, as the shop will implement a system  that automatically increases the fee until 100%.  (and bans the customer).  The person trying to get the coins back will loose 100% also.

[hannesnaude]

Oh, and I only see your scenario working as a very targeted attack.  There is no way an attacker could place themselves in a position to take on all 8 connections from even a tiny fraction of random new nodes.

But this is the difference between the way bitcoin works today and what you are proposing. Today, one would have to take on all 8 connections in order to keep the longer blockchain from a new node. With your scheme, one only needs to take on 1 and make sure that the new node sees your shorter branch first. The node eventually learns about the longer branch from its other peers, but doesn't switch. What's worse is that it is now effectively a poisoned node that will forward blocks to other new nodes in the same incorrect order that it received them. And so the rot spreads.

[ByteCoin]

Exponential difficulty increase summary:

My understanding is that the bulk of the discussion occurring under this subject heading revolves around a proposal by kjj linked to above which is not the behaviour of the current system.

May I suggest that you request help from a moderator to move your posts discussing this special system to a new thread (which it clearly deserves) as someone casually following the new posts to Dev & Tech (like me) gets confused because you appear at first sight to be discussing the behaviour of the current system but incorrectly.

If the proposed system for discouraging block chain re-organizations was in it its own thread (and explained properly) then I believe it would attract wider interest and be more easily found in future when such proposals are discussed again.

ByteCoin

Edit: I gather from kjj that it already has had a thread. In this case it might be useful to mention in your posts that you are discussing the merits of a proposed change and link to a post outlining the change.

[kjj]

Exponential difficulty increase summary:

My understanding is that the bulk of the discussion occurring under this subject heading revolves around a proposal by kjj linked to above which is not the behaviour of the current system.

May I suggest that you request help from a moderator to move your posts discussing this special system to a new thread (which it clearly deserves) as someone casually following the new posts to Dev & Tech (like me) gets confused because you appear at first sight to be discussing the behaviour of the current system but incorrectly.

If the proposed system for discouraging block chain re-organizations was in it its own thread (and explained properly) then I believe it would attract wider interest and be more easily found in future when such proposals are discussed again.

ByteCoin

Correct.  The thread for it is buried deep, page 8.  That's a lot of new topics for 3 weeks.

At any rate, yes, posts 29 to 37 inclusive are about my proposal, and are sorta off topic for this thread.  I like to point out that these attacks can be changed from improbable to impossible, and it occasionally leads to the tangent seen above.

But this is the difference between the way bitcoin works today and what you are proposing. Today, one would have to take on all 8 connections in order to keep the longer blockchain from a new node. With your scheme, one only needs to take on 1 and make sure that the new node sees your shorter branch first. The node eventually learns about the longer branch from its other peers, but doesn't switch. What's worse is that it is now effectively a poisoned node that will forward blocks to other new nodes in the same incorrect order that it received them. And so the rot spreads.

It would be pretty easy to code a startup mode where the client gets multiple copies of all blocks until it catches up.  And even if it does become a poisoned node, it still prevents a poisoned network.