How would 51% double spending work in the long term ? Thought experiment

[ShadowOfHarbringer]

So i was thinking heavily and it produced questions which will help me (and hopefully some other people) to better understand how the Bitcoin protocol works.
If on any level i have made a mistake somebody correct me please.

Suppose that somebody (like Botnet, Russian Mafia, Government or FED) has amassed **significant** resources both in money and hashpower (HP > 51%), and following happens.

1. That somebody (let's call im adversary) pays a very large sum of BTC (let's say 1.000.000 BTC) to an exchange
2. Adversary waits for X blocks* (let's say 100 blocks), while secretly building his own alternate (double spending) chain on the side.
2a. Meanwhile, the exchange & people keep moving the Bitcoins , so the original sum of bitcoins gets divided like this:



3. After block 101 passes, adversary introduces his alternate, longer chain which double spends the original 1.000.000 transaction to an address different than the original address, and erases the original chain which divided the sum to multiple addresses from existence.
4. ?? ??
5. PROFIT ?

* - That is possible because he has >51% of HP, so he can always produce chain faster than the rest of the network. Also @see Meni Rosenfeld thread and whitepaper for details.

I have following questions:
a) What happens to all the transactions from the original chain that happened after the 1.000.000 BTC transaction ? Are they all erased from existence ?
b) What happens if the alternate chain completely drops many other (unrelated) transactions that were previously accepted into blocks and received from 1 to 100 confirmations ? Are these transactions completely lost (I) ? Or perhaps only confirmations are lost, and the transactions are unconfirmed (II) ?
b1) If only the transactions' confimations are erased (II), will the network re-relay all the 0-confirmation transactions that were done before ? Will the network keep information about unconfirmed transactions which do not exist anymore ?
c) Will the original chain be erased from every client's database instantly the moment when a longer valid chain is supplied, or is there some other mechanism at work here ?

[Meni Rosenfeld]

a) What happens to all the transactions from the original chain that happened after the 1.000.000 BTC transaction ? Are they all erased from existence ?

All these transactions will become invalid and will remain so forever (assuming everyone now builds on the attacker's branch and nobody replaces it with yet another one). It's actually worse than what you described because transactions can have multiple inputs. The attacker will get his 1M back, and also all coins which trace back to the original double-spent transaction (which can be much more than 1M, even all coins in existence) will be shuffled around.

However, AFAIK the transactions aren't literally erased. The current client version at least keeps blocks which are not part of the main chain, it just doesn't do anything with them.

b) What happens if the alternate chain completely drops many other (unrelated) transactions that were previously accepted into blocks and received from 1 to 100 confirmations ? Are these transactions completely lost (I) ? Or perhaps only confirmations are lost, and the transactions are unconfirmed (II) ?

I think that if a block is invalidated, all transactions in it which are not double-spent go back to the memory pool and can be included in the next block. Even if not, the client that originally sent the transaction still has it and can rebroadcast it, it is still just as valid.

c) Will the original chain be erased from every client's database instantly the moment when a longer valid chain is supplied, or is there some other mechanism at work here ?

See a, the client keeps forks, however this might change when pruning enters the picture.

[grau]

I have following questions:
a) What happens to all the transactions from the original chain that happened after the 1.000.000 BTC transaction ? Are they all erased from existence ?

Your question (all other follow from this) is not special to an attack.

The block chain is actually a tree. It is quite frequent (nearly every day in my experience) that alternate blocks compete to succeed the latest. It is less frequent but still a regular event that more than one blocks are orphaned (superseded) by an alternate branch.

Transactions that are in the orphaned blocks become invalid only if their input was also used in the now longest chain (say the trunk of the tree). Quite a few transactions will actually already be in the trunk (if it is not a real and nasty attack). Those transactions that remain valid but are not already in the trunk should enter the unconfirmed pool of the node.

I have not checked the Satoshi code if and how far it scans the orphaned branch to recollect unconfirmed transactions, but I assume it does reasonable effort to do so.

The bitsofproof supernode does this consequently entering every otherwise missed transaction in the orphaned branch into its unconfirmed pool that is used to build block templates for mining. It also re-broadcasts transactions that became unconfirmed in a freshly orphaned block.

The unconfirmed pool is most likely in memory for all node implementations therefore there remains the chance that valid but unconfirmed transactions will cease at some (long) delay from the memory of the network.

It is the interest of the economy to minimize transaction drop through block orphaning, that is just a technical event and has no meaning to end user, and it is also the interest of miner to re-collect fees offered in unconfirmed transactions.

[ShadowOfHarbringer]

a) What happens to all the transactions from the original chain that happened after the 1.000.000 BTC transaction ? Are they all erased from existence ?

All these transactions will become invalid and will remain so forever (assuming everyone now builds on the attacker's branch and nobody replaces it with yet another one). It's actually worse than what you described because transactions can have multiple inputs. The attacker will get his 1M back, and also all coins which trace back to the original double-spent transaction (which can be much more than 1M, even all coins in existence) will be shuffled around.

Then i will expand my thought experiment. Let's say that Bitcoin network has grown, and people use it to trade 100.000.000$ worth of goods & currencies weekly.

1. A powerful adversary spends 50.000.000$ to buy 1.000.000 Bitcoins from MTGOX
2. He builds his alternate double - spending chain for a week, while in the meantime, people buy 100.000.000$ worth of goods & currencies using Bitcoin
3. After a week, adversary introduces his chain fork which double-spends his 1.000.000BTC to his address
4. At least 100.000.000$ worth of currencies & goods that were bought through the week are lost
5. This causes major havoc in the Bitcoin world, people's trust in the currency is seriously undermined.
6. ?? ??
7. PROFIT !

So how do we avoid this ?
If even I have produced this scenario, it is reasonable to think that powerful adversaries may already be working on it.

Also, another logical conclusion of mine is that all alt-currencies like Litecoin are useless, because attack like above can be arranged with ease using little hashing power.

I think that if a block is invalidated, all transactions in it which are not double-spent go back to the memory pool and can be included in the next block. Even if not, the client that originally sent the transaction still has it and can rebroadcast it, it is still just as valid.

Yes, but will the client rebroadcast it ? Was such scenario already tested ?

c) Will the original chain be erased from every client's database instantly the moment when a longer valid chain is supplied, or is there some other mechanism at work here ?

See a, the client keeps forks, however this might change when pruning enters the picture.

Ok, so my logical conclusion is that pruning cannot be implemented, until we solve this problem once and for all.

The unconfirmed pool is most likely in memory for all node implementations therefore there remains the chance that valid but unconfirmed transactions will cease at some (long) delay from the memory of the network.

But when they do, there will be no way to fix the mess.

[Meni Rosenfeld]

a) What happens to all the transactions from the original chain that happened after the 1.000.000 BTC transaction ? Are they all erased from existence ?

All these transactions will become invalid and will remain so forever (assuming everyone now builds on the attacker's branch and nobody replaces it with yet another one). It's actually worse than what you described because transactions can have multiple inputs. The attacker will get his 1M back, and also all coins which trace back to the original double-spent transaction (which can be much more than 1M, even all coins in existence) will be shuffled around.

Then i will expand my thought experiment. Let's say that Bitcoin network has grown, and people use it to trade 100.000.000$ worth of goods & currencies weekly.

1. A powerful adversary spends 50.000.000$ to buy 1.000.000 Bitcoins from MTGOX
2. He builds his alternate double - spending chain for a week, while in the meantime, people buy 100.000.000$ worth of goods & currencies using Bitcoin
3. After a week, adversary introduces his chain fork which double-spends his 1.000.000BTC to his address
4. At least 100.000.000$ worth of currencies & goods that were bought through the week are lost
5. This causes major havoc in the Bitcoin world, people's trust in the currency is seriously undermined.
6. ?? ??
7. PROFIT !

So how do we avoid this ?
If even I have produced this scenario, it is reasonable to think that powerful adversaries may already be working on it.

It is well known that if someone has sustained majority hashrate and wishes to use it to damage Bitcoin, it is bad.

So the options are:
1. Hope no entity wishing to destroy Bitcoin will obtain majority hashrate.
2. Adopt a more comprehensive branch selection solution which is harder to attack.

#2 would probably take the form of a hierarchy of various levels of synchronization signals, each of which can be cemented but overridden by the next, slower level. I imagine one of the top levels will be broadcasting a "block hash of the week" all over the internet and via TV, radio, newspaper, billboards etc. This way, if someone gets stuck on the wrong version, he will notice.

To protect against excluding all transactions, a DAG structure may have to be adopted.

Also, another logical conclusion of mine is that all alt-currencies like Litecoin are useless, because attack like above can be arranged with ease using little hashing power.

The incentive to attack them is correspondingly small, however. This of course does not apply to MM alts; also, even with Litecoin it did not have a serious attack yet (that I know of), and hypothetically it could one day surpass Bitcoin in total compute power.

c) Will the original chain be erased from every client's database instantly the moment when a longer valid chain is supplied, or is there some other mechanism at work here ?

See a, the client keeps forks, however this might change when pruning enters the picture.

Ok, so my logical conclusion is that pruning cannot be implemented, until we solve this problem once and for all.

Depends on the kind of pruning. Also, even with pruning implemented there are still expected to be archive nodes.

[kjj]

Then i will expand my thought experiment. Let's say that Bitcoin network has grown, and people use it to trade 100.000.000$ worth of goods & currencies weekly.

1. A powerful adversary spends 50.000.000$ to buy 1.000.000 Bitcoins from MTGOX
2. He builds his alternate double - spending chain for a week, while in the meantime, people buy 100.000.000$ worth of goods & currencies using Bitcoin
3. After a week, adversary introduces his chain fork which double-spends his 1.000.000BTC to his address
4. At least 100.000.000$ worth of currencies & goods that were bought through the week are lost
5. This causes major havoc in the Bitcoin world, people's trust in the currency is seriously undermined.
6. ?? ??
7. PROFIT !

So how do we avoid this ?
If even I have produced this scenario, it is reasonable to think that powerful adversaries may already be working on it.

Also, another logical conclusion of mine is that all alt-currencies like Litecoin are useless, because attack like above can be arranged with ease using little hashing power.

There is no step 7.  This attack is non-economic, meaning that the attacker has to be willing to burn a lot of wealth to do the attack.  This alone severely limits the categories of potential attackers, but it is not unreasonable to think that such an attacker might show up some day, so it deserves some attention.

To counter this, I proposed an exponential difficulty ramp for reorganizations.  Reorgs of up to X blocks (6 might be a good value for X) happen normally, with the longer chain winning.  Reorgs beyond X blocks require Y^(B-X) more difficulty in the new chain than the old chain, where B is the number of blocks to be thrown out.  Y could be pretty small and still give good safety, maybe 1.1 or 1.05.  For example, for X=6 and Y=1.05, reversing 100 blocks would need ~50 times the total network power, not half.  And replacing 144 blocks (1 day) would require ~400 times the network power.  Recipients of large transactions would be able to decide on their own how long they needed to wait to meet their own safety requirements.  Selling a billion dollar widget?  Wait a week, and then the attacker would need 1*10²¹ times the total network hashing power to unbury it.

I think that if a block is invalidated, all transactions in it which are not double-spent go back to the memory pool and can be included in the next block. Even if not, the client that originally sent the transaction still has it and can rebroadcast it, it is still just as valid.

Yes, but will the client rebroadcast it ? Was such scenario already tested ?

Yes, reorgs happen naturally every few days.  All transactions from the discarded blocks go back into the memory pool, and if they are still valid in the new context, they will be retransmitted and eventually end up in new blocks.

c) Will the original chain be erased from every client's database instantly the moment when a longer valid chain is supplied, or is there some other mechanism at work here ?

See a, the client keeps forks, however this might change when pruning enters the picture.

Ok, so my logical conclusion is that pruning cannot be implemented, until we solve this problem once and for all.

ultraprune stores rollback information for exactly this reason, even though it doesn't actually do any pruning yet.

Transactions that are in the orphaned blocks become invalid only if their input was also used in the now longest chain (say the trunk of the tree). Quite a few transactions will actually already be in the trunk (if it is not a real and nasty attack). Those transactions that remain valid but are not already in the trunk should enter the unconfirmed pool of the node.

The unconfirmed pool is most likely in memory for all node implementations therefore there remains the chance that valid but unconfirmed transactions will cease at some (long) delay from the memory of the network.

But when they do, there will be no way to fix the mess.

Well, even if the rest of the network forgets, each node scans their own wallet from time to time, and any transactions they see in their local wallet database but not in blocks and not in memory get retransmitted.  So, as long as your wallet is still live, the transactions still have a way to get back on the network.  Hilariously, this causes problems today because if you realize that a transaction isn't going to make it into a block within a reasonable amount of time, there isn't a simple way to prevent your wallet from keeping it alive.  You have to hack your wallet database to delete that transaction so that the network can forget about it, so that you can double spend it with a fee or whatever.

Also, there are ways to fix it, but they aren't particularly pleasant.  One ad hoc way to get things right would be to trace the fork back to the initial divergence, and then hardcode that first block's hash into a blacklist.  This would only help people that upgrade to the new blacklist-enabled version, but basically everyone would want to make that upgrade.  The blacklist could just be a text file in the datadir, managed by each node's user individually; they would have a powerful incentive to not put anything other than obvious attack blocks in it.

What I think really saves us from this scenario is that hashing capacity of sufficient power for the attack does not currently exist in the world, in a readily available form.  There just aren't enough physical Radeon's in the world, in purchasable form, for someone to gather them easily or quickly, even with a huge budget.  The attacker's best bet would be to spend about a year developing an ASIC, but that attack window is not going to stay open much longer.

[Meni Rosenfeld]

Then i will expand my thought experiment. Let's say that Bitcoin network has grown, and people use it to trade 100.000.000$ worth of goods & currencies weekly.

1. A powerful adversary spends 50.000.000$ to buy 1.000.000 Bitcoins from MTGOX
2. He builds his alternate double - spending chain for a week, while in the meantime, people buy 100.000.000$ worth of goods & currencies using Bitcoin
3. After a week, adversary introduces his chain fork which double-spends his 1.000.000BTC to his address
4. At least 100.000.000$ worth of currencies & goods that were bought through the week are lost
5. This causes major havoc in the Bitcoin world, people's trust in the currency is seriously undermined.
6. ?? ??
7. PROFIT !

So how do we avoid this ?
If even I have produced this scenario, it is reasonable to think that powerful adversaries may already be working on it.

Also, another logical conclusion of mine is that all alt-currencies like Litecoin are useless, because attack like above can be arranged with ease using little hashing power.

There is no step 7.  This attack is non-economic, meaning that the attacker has to be willing to burn a lot of wealth to do the attack.  This alone severely limits the categories of potential attackers, but it is not unreasonable to think that such an attacker might show up some day, so it deserves some attention.

The incentives to carry out the attack are well documented.
1. Someone could take a large short position on Bitcoin, carry out the attack, and profit from the panic selling.
2. Banks and similar organizations can do it to maintain their monopoly.
3. Governments could do it for fear of illegitimate uses of Bitcoin.

To counter this, I proposed an exponential difficulty ramp for reorganizations.  Reorgs of up to X blocks (6 might be a good value for X) happen normally, with the longer chain winning.  Reorgs beyond X blocks require Y^(B-X) more difficulty in the new chain than the old chain, where B is the number of blocks to be thrown out.  Y could be pretty small and still give good safety, maybe 1.1 or 1.05.  For example, for X=6 and Y=1.05, reversing 100 blocks would need ~50 times the total network power, not half.  And replacing 144 blocks (1 day) would require ~400 times the network power.  Recipients of large transactions would be able to decide on their own how long they needed to wait to meet their own safety requirements.  Selling a billion dollar widget?  Wait a week, and then the attacker would need 1*10²¹ times the total network hashing power to unbury it.

This is just a form of cementing. The obvious hurdle is that different nodes see things at different times and thus this is not a signal that will converge to universal agreement (unlike vanilla longest-branch). More concretely, a node could be stuck on the wrong version. This can be used only if there is a higher-level signal that can override the cementing. (Currently it's hardcoded checkpoints, but they're too infrequent to be practical).

Also, in itself it is useless against attacking by rejecting all other blocks and excluding all transactions.

What I think really saves us from this scenario is that hashing capacity of sufficient power for the attack does not currently exist in the world, in a readily available form.  There just aren't enough physical Radeon's in the world, in purchasable form, for someone to gather them easily or quickly, even with a huge budget.  The attacker's best bet would be to spend about a year developing an ASIC, but that attack window is not going to stay open much longer.

Since we're talking about governments and such, they can surely fund the development of ASICs more efficient than those available on the market, followed by mass production, in a quantity that takes into account from the start how the market will look like 1-2 years in the future.

[wachtwoord]

It is likely this will never be economically viable. If the value of Bitcoin increases to a point where it becomes economically viable given the current network strength the network strength will have grown with it to be able to withstand the attack. This is the general economic idea behind the entire currency and I 'believe' this to be true.

We'll see in practice whether I am right in doing so (Because the financial incentive continues to increase)

[ShadowOfHarbringer]

It is likely this will never be economically viable.

I am not exactly taking economic viability into equation. I am saying that some entity may execute such attack even if it is totally not economically viable.

[kjj]

To counter this, I proposed an exponential difficulty ramp for reorganizations.  Reorgs of up to X blocks (6 might be a good value for X) happen normally, with the longer chain winning.  Reorgs beyond X blocks require Y^(B-X) more difficulty in the new chain than the old chain, where B is the number of blocks to be thrown out.  Y could be pretty small and still give good safety, maybe 1.1 or 1.05.  For example, for X=6 and Y=1.05, reversing 100 blocks would need ~50 times the total network power, not half.  And replacing 144 blocks (1 day) would require ~400 times the network power.  Recipients of large transactions would be able to decide on their own how long they needed to wait to meet their own safety requirements.  Selling a billion dollar widget?  Wait a week, and then the attacker would need 1*10²¹ times the total network hashing power to unbury it.

This is just a form of cementing. The obvious hurdle is that different nodes see things at different times and thus this is not a signal that will converge to universal agreement (unlike vanilla longest-branch). More concretely, a node could be stuck on the wrong version. This can be used only if there is a higher-level signal that can override the cementing. (Currently it's hardcoded checkpoints, but they're too infrequent to be practical).

Also, in itself it is useless against attacking by rejecting all other blocks and excluding all transactions.

Meh.  It will converge to near-universal agreement, and the nodes that don't converge to that agreement will know that they need to fix their shit manually.  In your terms, the "higher-level signal" would be a human, and I don't see that as a downside.  If you assume that an attacker can isolate some subset of the network and feed it garbage, then those nodes will need manual help one way or the other.  Why not take the safe and simple measure to protect the rest of the network?

What I think really saves us from this scenario is that hashing capacity of sufficient power for the attack does not currently exist in the world, in a readily available form.  There just aren't enough physical Radeon's in the world, in purchasable form, for someone to gather them easily or quickly, even with a huge budget.  The attacker's best bet would be to spend about a year developing an ASIC, but that attack window is not going to stay open much longer.

Since we're talking about governments and such, they can surely fund the development of ASICs more efficient than those available on the market, followed by mass production, in a quantity that takes into account from the start how the market will look like 1-2 years in the future.

Right now, they would have a 30x power advantage with their ASICs vs. the rest of the network currently running GPUs and FPGAs.  Once we've all switched to ASICs, all they will have is numeric superiority at more-or-less parity per unit.  That's a huge difference.

[ShadowOfHarbringer]

This is just a form of cementing. The obvious hurdle is that different nodes see things at different times and thus this is not a signal that will converge to universal agreement (unlike vanilla longest-branch). More concretely, a node could be stuck on the wrong version. This can be used only if there is a higher-level signal that can override the cementing. (Currently it's hardcoded checkpoints, but they're too infrequent to be practical).

What if overriding cementing would require some kind of majority vote ?

So every time a client receives a new/alternate chain, which overrides something already cemented, it also checks if majority of the network agrees with this ? This could be done by connecting to let's say... 128 randomly selected peers but limited to single node per 65536 IP block (X.X.*.*).

Do I make any sense, or is this a stupid idea ?

[ShadowOfHarbringer]

Meh.  It will converge to near-universal agreement, and the nodes that don't converge to that agreement will know that they need to fix their shit manually.  In your terms, the "higher-level signal" would be a human, and I don't see that as a downside.  If you assume that an attacker can isolate some subset of the network and feed it garbage, then those nodes will need manual help one way or the other.  Why not take the safe and simple measure to protect the rest of the network?

I think you are correct and the main logical reason is that cementing protects 100% of the clients (entire network) at the cost of very small fraction of clients gone bad.

So the question we must ask ourselves is: what is more important - (1) protecting the entire network against powerful adversaries, or (2) protecting single (<1%) stranded clients gone wild because of either an attack, or local network malfunction ?

For me, the answer will be always (1).

[paraipan]

It is likely this will never be economically viable.

I am not exactly taking economic viability into equation. I am saying that some entity may execute such attack even if it is totally not economically viable.

I thought about this issue many times already, and yes it could wreak havoc in the whole network, but don't think people will look and do nothing about it. Probably the first time it will get us by surprise, and leave something worthy to remember and tell to our grandchildren, but the next times people will already have measures in place to make such an attack useless. We're making history here, have no doubt about it.

Edit: I would love to have an option in the Satoshi client that gives me the choice to accept or deny any re-org bigger than 6 confirmations. Having the feature and educating people about it would render an attack like that pretty useless.

[wachtwoord]

It is likely this will never be economically viable.

I am not exactly taking economic viability into equation. I am saying that some entity may execute such attack even if it is totally not economically viable.

Why?

[ShadowOfHarbringer]

It is likely this will never be economically viable.

I am not exactly taking economic viability into equation. I am saying that some entity may execute such attack even if it is totally not economically viable.

Why?

Because (being only reasonably paranoid) there are and/or there will be organizations which would love nothing more than to kill "our small project".

Now we are going slow, but wait till bitcoin capitalization reaches 1.000.000.000$ or 10.000.000.000$ - that is when we will see what Bitcoin really can do. And shit will hit the fan. Hopefully it will be too late for them to try anything.

[Meni Rosenfeld]

This is just a form of cementing. The obvious hurdle is that different nodes see things at different times and thus this is not a signal that will converge to universal agreement (unlike vanilla longest-branch). More concretely, a node could be stuck on the wrong version. This can be used only if there is a higher-level signal that can override the cementing. (Currently it's hardcoded checkpoints, but they're too infrequent to be practical).

What if overriding cementing would require some kind of majority vote ?

So every time a client receives a new/alternate chain, which overrides something already cemented, it also checks if majority of the network agrees with this ? This could be done by connecting to let's say... 128 randomly selected peers but limited to single node per 65536 IP block (X.X.*.*).

Do I make any sense, or is this a stupid idea ?

It's not very robust. Even with the IP range restriction it should be easy for an attacker to game this.

Proof of Stake is exactly an attempt to do a majority vote based on the harder-to-fake ownership of coins. It may or may not have a place in the hierarchy.

So the question we must ask ourselves is: what is more important - (1) protecting the entire network against powerful adversaries, or (2) protecting single (<1%) stranded clients gone wild because of either an attack, or local network malfunction ?

For me, the answer will be always (1).

I can see the marketing copy - "With Bitcoin, you are in full control of your money, and payments cannot be reversed! Unless you're one of the 1% whom we don't care about, and then payments to you could be completely bogus."

Seriously though, I don't disagree but moving away from pure PoW is a fundamental design change and we need to consider it carefully to keep disruption and unwanted side-effects at an absolute minimum. If nodes aren't safe when participating in the network then the network is meaningless.

And as mentioned, if we consider majority attack to be plausible we need to protect against rejection attacks, not just double-spending.

It is likely this will never be economically viable.

I am not exactly taking economic viability into equation. I am saying that some entity may execute such attack even if it is totally not economically viable.

Why?

See my post above for various motivations. They are all "economic" with sufficiently broad usage of the term, but not in the most direct sense.

Edit: I would love to have an option in the Satoshi client that gives me the choice to accept or deny any re-org bigger than 6 confirmations. Having the feature and educating people about it would render an attack like that pretty useless.

This isn't a client-level choice, it's a network fork.

[ShadowOfHarbringer]

This is just a form of cementing. The obvious hurdle is that different nodes see things at different times and thus this is not a signal that will converge to universal agreement (unlike vanilla longest-branch). More concretely, a node could be stuck on the wrong version. This can be used only if there is a higher-level signal that can override the cementing. (Currently it's hardcoded checkpoints, but they're too infrequent to be practical).

What if overriding cementing would require some kind of majority vote ?

So every time a client receives a new/alternate chain, which overrides something already cemented, it also checks if majority of the network agrees with this ? This could be done by connecting to let's say... 128 randomly selected peers but limited to single node per 65536 IP block (X.X.*.*).

Do I make any sense, or is this a stupid idea ?

It's not very robust. Even with the IP range restriction it should be easy for an attacker to game this.

How exactly ?

Also, if we implement cementing after Y confirmations as a quick fix and set Y to something relatively high (like 20), shouldn't everybody be safe this way ?

I mean, were there ever blocks reorgs longer than 10 blocks ? Do they even occur naturally?

[paraipan]

...

Edit: I would love to have an option in the Satoshi client that gives me the choice to accept or deny any re-org bigger than 6 confirmations. Having the feature and educating people about it would render an attack like that pretty useless.

This isn't a client-level choice, it's a network fork.

You sure 

You didn't give a second thought... What is a network fork Meni? What if 75% of the clients make a choice? Could be a network fork?

I think at it like this: every individual client/member can go in automatic only if less than 6 block re-orgs happen, and ask for user intervention if something bigger happens? It could present some evidence about it's "confusion" to help the user decide (re-org size, double spends, transaction quantity, blocks from known pools, etc). What does you mathematics tell you about this?

[2112]

To protect against excluding all transactions, a DAG structure may have to be adopted.

I feel that Ripple may come to the rescue here. If not Ripple (the company) exactly then at least Ripple-like mechanical way of finding largest spanning sub-graphs.

Out of all Bitcoin users some meaningfull fraction will not have problem with forgetting anonymity and openly disclosing their credit limits with their counterparties.

If you make an assumption that a "51% attacker" is a highly concentrated entity with relatively little history of previous transactions with the rest of the network then it should be a relatively simple graph search operation to isolate him/her. The "remaining" network will be just 49%, but intensely interconnected and with longer history.

On the other hand, if you cannot make the above assumption that the "51% attacker" is highly concentrated then you've may have discovered a genuine grass-roots movement. I would understand such situation as a revolt against the obstructionism from the core development team.

To quote Erik Voorhees: "Democracy is the original 51% attack."

[Meni Rosenfeld]

How exactly ?

By running multiple nodes spanned over various IP addresses, of course.

Also, if we implement cementing after Y confirmations as a quick fix and set Y to something relatively high (like 20), shouldn't everybody be safe this way ?

Maybe. Let's put it this way - cementing is simple and obvious, if it was that great Satoshi would have implemented it from the start. So we shouldn't do any "quick fix" without a solid understanding of the reasons for the decision and a thorough analysis of the dynamics of the new system.

I mean, were there ever blocks reorgs longer than 10 blocks ? Do they even occur naturally?

AFAIK no, and depends on the definition of "naturally" but essentially no.

What is a network fork Meni?

A network fork is when one client thinks some block is valid and another client thinks it is invalid. Short-term forks are normal but longer-term ones are effectively splitting the original network into two (or more) separate networks.

What if 75% of the clients make a choice? Could be a network fork?

Yes, then 75% of the clients will be on one network and the other 25% will be in a separate, incompatible network (assuming there was in fact a reorg that required making a choice). In fact those that chose cementing may be further divided between them based on what they observed during various reorgs.

However, if the 75% is by hashrate, then those clients will eventually build a longer chain, which the non-cementers will switch to, with a massive disruptive reorg. Which will happen again every time there is such a fork.

I think at it like this: every individual client/member can go in automatic only if less than 6 block re-orgs happen, and ask for user intervention if something bigger happens? It could present some evidence about it's "confusion" to help the user decide (re-org size, double spends, transaction quantity, blocks from known pools, etc).

If the user makes a choice then the clients will fork based on what their users choose (unless, of course, for some reason all users' choices lead to the same results).

What does you mathematics tell you about this?

Not sure if serious.