Pay miners to rewrite block(s)?

[FreeMoney]

Is there anything stopping this?

1. get 25000 coins stolen
2. after a few confirmations submit a tx with 1000BTC fee that comes from the now empty address
3. The fee could be claimed by rewriting the block that the first tx happened in.

Obviously this could be used for bad (double spends) too. Right now it can't be done with normal client, and miners aren't on the lookout anyway, but is it possible?

[1715144036]

1715144036

[1715144036]

1715144036

[1715144036]

1715144036

[1715144036]

1715144036

[1715144036]

1715144036

[makomk]

Cunning. It wouldn't work as you've proposed it, though - in order for the rewritten block to be accepted, you'd need to build a longer chain than the original one, and since all the mining pool that didn't find the first block would have no incentive to do so that's unlikely to happen. The obvious solution is that whoever builds the first block gives an incentive - in the form of a transaction fee - to find the next one, and so on. Even with this, it'd only work if mining pools making up significantly more than 50% of the total hashing power were in on the conspiracy.

The real barrier is that this would undermine trust in Bitcoin itself, which would probably make the conspirators' profits worthless.

[Sukrim]

Is there anything stopping this?

1. get 25000 coins stolen
2. after a few confirmations submit a tx with 1000BTC fee that comes from the now empty address
3. The fee could be claimed by rewriting the block that the first tx happened in.

Obviously this could be used for bad (double spends) too. Right now it can't be done with normal client, and miners aren't on the lookout anyway, but is it possible?

In the end you either want to have a negative balance in an address (I think this is NOT possible in Bitcoin at all) OR to have someone with a lot more hashing power than the current network performing an good old 51% - they won't do this for just 1000 BTC!

To invalidate a 6 blocks chain, you need 7 blocks faster than the rest of the network. I'm also not 100% sure how/if clients accept a block that is from a "netsplit" and originates a few blocks further behind.

In the end you want to give miners an incentive to 51% attack the network and cover your losses. If only a few catch on though, they won't have enough power and if all catch on, this would REALLY endanger their own systems (payouts etc.) as well...

I think in theory it might work, in practice I guess you won't find enough miners in less than an hour to mine for that Jackpot.

[FreeMoney]

Cunning. It wouldn't work as you've proposed it, though - in order for the rewritten block to be accepted, you'd need to build a longer chain than the original one, and since all the mining pool that didn't find the first block would have no incentive to do so that's unlikely to happen. The obvious solution is that whoever builds the first block gives an incentive - in the form of a transaction fee - to find the next one, and so on. Even with this, it'd only work if mining pools making up significantly more than 50% of the total hashing power were in on the conspiracy.

The real barrier is that this would undermine trust in Bitcoin itself, which would probably make the conspirators' profits worthless.

You only need to get the chain to be the longest for a second then everyone else starts working on it for you. If you are mining then you consider what your chances are of finding 2 blocks in a row and getting 50 + 50 + 1000 compared to the chance that you'll get only 1 block and it'll go to waste. It does not require mining pools at all, but they do make it more feasible for people to make the most profitable decisions without actually having to do it themselves. And why would you need "way more than 50%"? If you have more than 50% it's a lock, but with less you still have a chance.

I don't think it would undermine confidence in bitcoin at all. This can only happen if two or more entities that both have the private keys for an address are fighting over where to send the coins. It should reduce the profit in stealing someones wallet a little, that's all I see.

[FreeMoney]

I'm think of this as essentially a message saying "Hey network, something went really wrong and I'm willing to pay X for you to go back and fix it".

It's actually seeming to me like the equilibrium is for large amounts of stolen coins to get paid to miners. If person A with access gives a modest fee then B comes back with a high fee and A comes back with a 99% fee and maybe B does 100% to spite him. This assumes you can nearly instantly reissue a tx, but anyone who's on top of that is unlikely to be in this situation.

[ByteCoin]

1. get 25000 coins stolen
2. after a few confirmations submit a tx with 1000BTC fee that comes from the now empty address
3. The fee could be claimed by rewriting the block that the first tx happened in.

As people have pointed out, you'd have to rewrite the block and all subsequent blocks.

However, the basic idea is sound. It's true that very large fees would induce rational miners to abandon work on continuing the current block chain and start a new branch which would allow the collection of the fee.

In order to encourage miners to work on the new block chain, the miner that got the huge fee would have to pay the other miners for their blocks on the "old" branch which will never mature, as well as cut them in on the remaining profit from the massive fee. As long as >50% of the hashing power feels adequately compensated then the attack should succeed.

So the new block which collects the fee would also contain transactions which compensate the miners and cut them in. No special communication or negotiation with other miners is required if they are "fee aware"!

The miners in the above scenario act as an ad-hoc cartel for a period of time.

ByteCoin

[gmaxwell]

In order to encourage miners to work on the new block chain, the miner that got the huge fee would have to pay the other miners for their blocks on the "old" branch which will never mature, as well as cut them in on the remaining profit from the massive fee. As long as >50% of the hashing power feels adequately compensated then the attack should succeed.

Nope.

TXN 1 pays 200 BTC fee plus 1000 to TXN 2 and the rest back to owner, TXN 2 pays 200 BTC fee 700 to TXN 3...
and so on, enough to pay for the race and then some.

The TXN use nLocktime to spread them out and pay for the complete fork all on their own.

[kjj]

Why wouldn't the next guy just pay 1500 BTC to reverse the 1000 BTC "earned" by the first miner?

[FreeMoney]

Why wouldn't the next guy just pay 1500 BTC to reverse the 1000 BTC "earned" by the first miner?

Yep, there won't be much profit left in stealing wallets. If multiple warring entities both have keys the coins go to miners.

[da2ce7]

@FreeMoney, I really like this idea... the bad guy must both steal the coins AND put in a massive transaction fee.

Whomever owns the wallet will put the transaction fee up to 100% before letting the adversary keep the coins.  It would be reasonable (and rational) that the owner of the coins could put the fee at 120% or more.

You could even have code that automatically detects an unauthorized spend and creates a transaction of a higher fee automatically to a new address.  The adversity will automatically rise the fee also... so the fee will quickly get to 100% / 100%

This will kill much the incentive for stealing somebodies btc.

Problem... make a new transaction after paying somebody... That has a fee higher fee.  Means that double spends are easy.

[just_someguy]

Very interesting double spend attack.

To get more miners involved you could keep building very profitable transactions off of the last block.
First you would spend 25,000.
Then double spend but only 1k at a time: 1k in fees and 24k back to you.
If a miner takes the bait turn right around and do it again off of the new block: 1k in fees and 23k back to you.
Like dangling a carrot in front of a donkey you could slowly build that other side of the chain getting more and more miners involved each time.

This would require more active management on part of the miners but its very interesting.

[FreeMoney]

Problem... make a new transaction after paying somebody... That has a fee higher fee.  Means that double spends are easy.

Keep in mind that this is only feasible for large amounts and that it gets more expensive the more confirms you want to wait before double spending.

If this became common we would know how much miners require to go back a certain number of blocks and wait until it would be more than the whole amount of the tx to deliver goods.

[hannesnaude]

Problem... make a new transaction after paying somebody... That has a fee higher fee.  Means that double spends are easy.

Keep in mind that this is only feasible for large amounts and that it gets more expensive the more confirms you want to wait before double spending.

If this became common we would know how much miners require to go back a certain number of blocks and wait until it would be more than the whole amount of the tx to deliver goods.

But this does make one doubt the oft-repeated statement that a retailer does not need to wait for confirmations when selling goods of small value. I could buy a cup of coffee and broadcast a new version of the transaction into the network offering half of the price as tx fee. If 10% of miners are maximising transaction fees then there's a 10% chance I get a 50% discount on my coffee. If everyone does this the retailer sees a 10% loss. Suddenly makes Mastercard and VISA look good.

As far as confirmed transactions are concerned, one can easily calculate for a miner with a give percentage of total network hash power that coldly maximises profit, how large the tx fee would have to be to attempt to overturn something X blocks back in the chain (assuming that none of the other miners are bribeable and he needs to do it alone). The figures look good for solo mining, but for pooled mining and especially 0% fee pooled mining, the situation quickly changes since the pool owner (who will make the decision) will keep all of the bribe if he attempts the heist and is successful, but keep 0% (or a very small %) of the coinbase reward if he chooses to keep to the straight and narrow.

Once miners know that other miners may be corruptible the figures change dramatically and a vicious cycle may be born. Also, a large bribe on large tx is not necessarily required, many small bribes on many small txs can add up to the same effect. All in all, I'm a little worried. Please tell me why this won't happen.

[FreeMoney]

Problem... make a new transaction after paying somebody... That has a fee higher fee.  Means that double spends are easy.

Keep in mind that this is only feasible for large amounts and that it gets more expensive the more confirms you want to wait before double spending.

If this became common we would know how much miners require to go back a certain number of blocks and wait until it would be more than the whole amount of the tx to deliver goods.

But this does make one doubt the oft-repeated statement that a retailer does not need to wait for confirmations when selling goods of small value. I could buy a cup of coffee and broadcast a new version of the transaction into the network offering half of the price as tx fee. If 10% of miners are maximising transaction fees then there's a 10% chance I get a 50% discount on my coffee. If everyone does this the retailer sees a 10% loss. Suddenly makes Mastercard and VISA look good.

As far as confirmed transactions are concerned, one can easily calculate for a miner with a give percentage of total network hash power that coldly maximises profit, how large the tx fee would have to be to attempt to overturn something X blocks back in the chain (assuming that none of the other miners are bribeable and he needs to do it alone). The figures look good for solo mining, but for pooled mining and especially 0% fee pooled mining, the situation quickly changes since the pool owner (who will make the decision) will keep all of the bribe if he attempts the heist and is successful, but keep 0% (or a very small %) of the coinbase reward if he chooses to keep to the straight and narrow.

Once miners know that other miners may be corruptible the figures change dramatically and a vicious cycle may be born. Also, a large bribe on large tx is not necessarily required, many small bribes on many small txs can add up to the same effect. All in all, I'm a little worried. Please tell me why this won't happen.

Even if this was implemented I wouldn't hassle people at my shop to wait around for small value tx to confirm. People just don't steal very often when they looked you in the eyes. How many people walk out on restaurant bills? So few that everyone gets served all they want and pays afterwards.

For bigger, but not huge, stuff maybe you wait 1 confirm. Paying the network to go back even one block is going to cost a lot more than a tv. For selling cars and larger, you know how you are dealing with anyway.

For goods bought online it doesn't matter at all, they won't ship for 100 confirms anyway.

[hannesnaude]

Even if this was implemented I wouldn't hassle people at my shop to wait around for small value tx to confirm. People just don't steal very often when they looked you in the eyes. How many people walk out on restaurant bills? So few that everyone gets served all they want and pays afterwards.

This is a very powerful argument. The problem is that many people may not even realise they are stealing. A single corrupt individual releases a new android app that attempts a double spend 2 minutes after every transaction. This spend targets 50% of the value at miners 25% to the author and 25% back to the originator. This gets pitched as a "loyalty program" where you would occasionally win 25% cashback on transactions. Initially people don't even know they are stealing, so this gets real popular real quick.. Then retailers make a noise and most people know, but suddenly it looks more like a morally gray area.

Also most people won't steal from a mom & pop shop after looking the shopkeeper in the eye. But many have far less of a problem ripping off Wallmart or pretty much any giant faceless corporation. How many people point it out when they are given too much change at a till?
 

For bigger, but not huge, stuff maybe you wait 1 confirm. Paying the network to go back even one block is going to cost a lot more than a tv. For selling cars and larger, you know how you are dealing with anyway.

Problem is, if many people are doing it, the total bribe quickly adds up. If it works, more people start doing it, more miners become corruptible and the vicious cycle fuels itself. Even a 0.01 BTC bribe may be enough if the block was going to get invalidated anyway due to other unrelated bribes.

For goods bought online it doesn't matter at all, they won't ship for 100 confirms anyway.

Agreed.

[FreeMoney]

Even if this was implemented I wouldn't hassle people at my shop to wait around for small value tx to confirm. People just don't steal very often when they looked you in the eyes. How many people walk out on restaurant bills? So few that everyone gets served all they want and pays afterwards.

This is a very powerful argument. The problem is that many people may not even realise they are stealing. A single corrupt individual releases a new android app that attempts a double spend 2 minutes after every transaction. This spend targets 50% of the value at miners 25% to the author and 25% back to the originator. This gets pitched as a "loyalty program" where you would occasionally win 25% cashback on transactions. Initially people don't even know they are stealing, so this gets real popular real quick.. Then retailers make a noise and most people know, but suddenly it looks more like a morally gray area.

Also most people won't steal from a mom & pop shop after looking the shopkeeper in the eye. But many have far less of a problem ripping off Wallmart or pretty much any giant faceless corporation. How many people point it out when they are given too much change at a till?
 

For bigger, but not huge, stuff maybe you wait 1 confirm. Paying the network to go back even one block is going to cost a lot more than a tv. For selling cars and larger, you know how you are dealing with anyway.

Problem is, if many people are doing it, the total bribe quickly adds up. If it works, more people start doing it, more miners become corruptible and the vicious cycle fuels itself. Even a 0.01 BTC bribe may be enough if the block was going to get invalidated anyway due to other unrelated bribes.
 

Those are some good points. I hadn't thought about the rewrite fees adding up, but of course they do.

All of this is only a problem as long as people are sending coins directly, but there will surely be mybitcoin esque sites that handle payments for people so that you can get instant clearing and not have to worry about securing a wallet file and such. Those companies won't cheat for fear of losing all of their connections and reputation.

Being able to use the chain directly is really nice though and the whole point is not to need large trusted parties, I need to think some more about these issues.

[kjj]

Most nodes won't even bother relaying a transaction that involves an input that has already been redeemed, so it will be difficult to get your second spend out to enough miners.  Also, having some fraction of honest miners that are unwilling to rewrite transactions for money will make the attack much less likely to work, since the mercenary miners are also facing the risk that their work will be wasted if someone else wins.

[hannesnaude]

Most nodes won't even bother relaying a transaction that involves an input that has already been redeemed, so it will be difficult to get your second spend out to enough miners.  Also, having some fraction of honest miners that are unwilling to rewrite transactions for money will make the attack much less likely to work, since the mercenary miners are also facing the risk that their work will be wasted if someone else wins.

That's a good point. However, this attack would almost certainly need a corrupt pool owner to get started in the 1st place, so anyone attempting it would send it directly to each of the pools. I suspect determining their IPs will be trivial. Haven't studied the relaying mechanism in detail so I might be way off base here.

If all corrupt miners follow the same rule, then as soon as one of the pools turn rogue, all of the corrupt miners will be connected to one another with the corrupt pool serving as a hub. However, it is not clear that even a corrupted miner will relay such a message as, in doing so, he increases the probability that the heist will be successful, but reduces the probability that he will get a cut of the gains. I need to think this through some more.   

[JoelKatz]

If all corrupt miners follow the same rule, then as soon as one of the pools turn rogue, all of the corrupt miners will be connected to one another with the corrupt pool serving as a hub. However, it is not clear that even a corrupted miner will relay such a message as, in doing so, he increases the probability that the heist will be successful, but reduces the probability that he will get a cut of the gains. I need to think this through some more.  

This is not true, he increases the probability that he will get a cut of the gains. I think you mean he decreases the contingent probability that he will get a cut of the gains if the block is rewritten. But there is no rational reason for him to care about this contingent probability unless he has some grudge against other miners.

The numbers look like this (oversimplified and with small errors, but the concept is correct):

Case 1: I have 10% of the world's mining pool. Two blocks have to be rewritten. I work alone. The odds that I'll solve two blocks in a row is 10% of 10% or 1%. So there is a 1% chance the blocks will be rewritten. If they are, there's a 100% chance I get the money. 100% of 1% is 1%. So there's a 1% chance I'll claim the funds.

If two 10%'ers each work alone, the chance the attack will succeed is 2%, and they each have a 1% chance to claim the funds.

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.

[ByteCoin]

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.

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.

The only way in which the rewriting can succeed is if enough of the miners gain "enough" of the profits. Exactly what their negotiating strategies should be is hard to determine though....

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

ByteCoin

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