Bitcoin Forum

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:

https://i.imgur.com/ryrkW.png

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 (https://bitcointalk.org/index.php?topic=130222.0) and whitepaper (https://bitcoil.co.il/Doublespend.pdf) 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 ?

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.

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.

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

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.

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.



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


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


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

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.

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.

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

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.


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.


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


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.

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.

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.

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.

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)

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.

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?


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.

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 ?

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

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.

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.

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.

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.

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.

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

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?

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?

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

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

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.

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

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.

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.

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

Not sure if serious.

Yes, but in no way will this be easy to do.

It would require simultaneously VERY significant resources in multiple countries around the world AND >51% Hashing power, AND few million $ to buy Bitcoins to perform an attack.
Which makes it infeasible for almost every possible adversary on the planet.

Attack like this would be almost impossible to do, even for government of a very rich country (we all know what country I am talking about).


So the only time a block reorg longer than 10 blocks will ever happen is because an advanced double spending attack.
Logically, implementing cementing after Y blocks (where Y = relatively big number, like 15, 20 or 50) should be an absolutely viable solution to our problems.

Unless there are other drawbacks, not mentioned in this discussion.

I surely could use @Gavin's opinion here.

Doesn't this already occur on an ad-hoc basis when new versions of the client are released through the process of creating a "checkpoint"?

Exactly. This already happens, but only once every few months.
So why not make it more often if there are no known drawbacks ?

Simple solutions are not always bad.

Or when there is an exploit, community detects it, patches are produced, executables distributed and all the legitimate transactions are redone.

https://en.bitcoin.it/wiki/Incidents#CVE-2010-5139

Yes, but checkpoints are much more infrequent, and require upgrading the client.

If the IP vote overrides the longer chain, it is not clear you still need majority hashrate. You can use your IPs to vote on your minority branch. How this works exactly will depend on the specific implementation and attack.

Also, the cost is additive. You'll need the cost of multiple IPs + cost of hashpower + cost of bitcoins. Tripling the resource cost isn't so impressive if the attacker might have a thousand-to-one resource advantage.

Suppose you're a new node joining the network. Of course you are not cemented on anything. You see some nodes broadcasting a short chain and some an incompatible, longer chain. Who do you believe? If you default to the longer chain, you could fall right into the majority attacker's net. If you use something else you make it easier to carry out an attack without majority hashrate.

In this way the attacker can prevent new nodes from joining reliably. Not "some poor victim somewhere will be attacked". Nobody can join the network. Unless, of course, we spend some time thinking about a framework for higher-level overriding.

And I will repeat myself and say there are two primary attacks with majority hashrate - double-spending and rejection. Cementing helps with one. What about the other?

I agree, when we do start seriously thinking about this, we will need more knowledgeable people to take part.

I more-or-less agree with with the rest of your post, this is the part i have doubts about:


How is this different when using cementing ?
I mean clients already take longest chain when offered multiple chains or different length.

No change here.

(Unless you were talking about the majority rule, not cementing itself)

Without cementing, new nodes use the longest branch, as do all other nodes. In case there's a majority attacker, he can make attacks but at least the nodes are consistent with each other.

With cementing, if a certain attack is executed, new nodes will be detached from the rest of the network (e.g., the veteran network is cemented on a shorter branch, but the new node will join the attacker's longer branch). At the very least it shows that cementing doesn't make the network (where "the network" includes the ability of nodes to join it) immune to such attacks.

Wow, I didn't think about that. Thanks for clearing this up, @Meni.

This is a very good discussion we are having, i wish I did that more often.

Erm, don't take this the wrong way, but this seems like a strawman to me.  If an attacker has you isolated, they can already feed you bogus blocks, and there isn't a damn thing you can do about it.  In a parity proof-of-work system, when the isolation is broken, your node will resync with the rest of the world.  But the damage (to you) has already been done, it was done when you accepted blocks that you thought were current, but really weren't.  Throwing them out and loading the correct blocks doesn't fix anything, and might actually make it harder for you to realize what happened.

This is the trade in reality.
You get:  your node can fix itself when reconnected to the global network.
You pay:  The entire global network is vulnerable to hidden chains, whatever damage you suffered while disconnected is unchanged, you don't necessarily know that you were attacked.

Seems like a terrible trade to me.


The best part of my proposal is that it doesn't change the network rules at all.  It is still pure proof of work.  The only change is that the burden of proof for a reorganization is higher than it is now, and it scales with the amount of danger than such a reorganization represents.

I sent ShadowOfHarbringer's some of my thoughts on this in this private message:

I don't worry much right now about economically irrational, "I'm going to spend millions of dollars to disrupt the bitcoin network" attacks because I don't think anybody is going to spend millions of dollars to disrupt our tiny payment network.

I have no idea what bitcoin payments will look like in 5-10 years; I expect all sorts of trust mechanisms and relationships to develop that are independent of the bitcoin network, and I suspect some of those will make 51% attacks irrelevant.

And I have no idea what the mining landscape will look like in 5-10 years; if thousands of companies around the world are installing bitcoin mining hardware for free in every house built in cold climates (generate bitcoins and get a discount on your heating bill) then it may be completely inconceivable for even a government to amass enough hashing power to mount a 51% attack.

So while I encourage y'all to keep thinking about it as an interesting theoretical problem, it is only slightly higher on my personal priority list than worrying about quantum computers breaking ECDSA.

This is not how things work. Let me tell you how you should do it, it you ever want something done (as with my fork I have already learned the hard way how things work in the world).

Nobody will do anything for you (for free). If you ever want to get stuff done, you must work hard, do it and code it yourself, test it thoroughly and only then - when you are 100% sure that it works correctly, you can try to convince people to merge it to the client.

Maybe. I think the ability to recover is important, both practically and for the theoretical "correctness" of the system.

I used "Pure PoW" in the narrower sense of sticking to the longest branch (which depends only on the current observed data and not the history of receiving it).

Thank you for this. I would however like to emphasize that table 2 is probably the least reliable item in the paper, it assumes a specific model for an attack which is likely to diverge significantly from reality. (And doesn't even follow the math of that model to the end because of the complexity of the calculations.)

I see what you're saying. When you say it's only slightly higher than breaking ECDSA, you mean that THIS PROBLEM IS SO EXTREME AND URGENT THAT WE NEED TO FREAK OUT ABOUT IT RIGHT NOW!  No? Ok.

Nice to know that Gavin, thank you. Will be interesting to see how solutions are developed with enough time.

You don't lose the ability to recover.  You only lose the silent, automatic recovery that obfuscates the damage.  You, the human, is going to have a mess that you are personally going to have to deal with.  The difference is that in one scenario, you have no idea what happened or why, and in the other scenario, you have to clear out some invalid blocks and restart your node, but you know exactly why.


Also, I should point out that section 6 of the paper doesn't really apply here, because section 6 is written with the assumption that q < p, while the assumption in this thread is that q > p.  In this case, it means that we are assuming that the attacker will eventually overtake the honest network.  Your only protection in that case is to have done all transactions and converted all of your bitcoins to wealth prior to the block when the attacker publishes their chain that destroys the entire system.

this

Another case is when a country or an island gets isolated from the rest of the world.
I guess that's why Satoshi did not put an automatic cementing feature. But such a case can be detected due to a sudden really slower network speed ? At least, the user may know it :p

In such a case the "cementing feature" would be more than useful, to lock in clients on the "island blockchain".

Just imagine how would you react after trading for a whole year with your neighbors, and then a new neighbor comes in with a satellite link to the Internet and the whole island blockchain is dumped the moment first wallet updates (assuming the main chain is longer). I know I would be pissed, and at least would like to have the option to keep doing business on the "island blockchain". The moment you have a group of bitcoin users that work and trade over a blockchain fork for a period larger than a week, you can confidently say they are trading in their own digital currency, and there isn't an easy way to deal with it at the blockchain level.

This is similar to bitcoin tech ported onto other planets, which in absence of some low latency telecommunication channel, that would naturally create their own local currency.

I may be wrong, but i think that the best solution would be to implement @kjj's idea with difficulty automatically increasing exponentially if block chain fork is longer than Y blocks.

This is still pure Proof Of Work, not really cementing. It would simply require much more than 51% to fork blockchain after Y number of blocks.

It's soft cementing (wet cement?). It probably has some advantages over hard cementing, but essentially it has the same tradeoffs.

::sigh:: I'm pretty sure I've gone through this before, but perhaps I now know how to explain this in a way that will get through.

Self-consistency and global convergence are mutually incompatible objectives.  Large scale of convergence is the worst possible failure mode for Bitcoin, worse than any amount of transaction reversal.

If participants prefer their past state it means that two participants with different pasts can fail to agree on the current state even when presented with identical information. Small amounts of self-consistency can be tolerated but it is at the direct expense of convergence (which is why bitcoin is often not converged at all after just a single block, though it becomes converged with infinitesimal chance of convergence failure after enough blocks relative to the communication delays).

The problem of non-convergence is made worse for a distributed systems in a universes with a speed of light, as an attacker can pick which nodes have which past by selecting their 'locations' that they use to announce messages and so they can choose the shape of the non-convergence to be most damaging.

To specifically address your particular suggestion:  A byzantine attacker obtains a large amount of hashpower for long enough to mine a couple blocks— say twelve total for your figures— faster than the network, and he maps out the locations of large mining power concentrations with some accuracy.   Then he mines two forks off the current head, starting with blocks A and A'.  He feeds these forks all in parallel to all nodes, giving A to half the estimated hash power and A' to the other half. Congrats: Bitcoin is over, from one currency you have two. (well, at least until people manually intervene, turn off your 'tweak' or force nodes onto the state they're rejecting, and the system causes a reversal of all transactions on one side or another, belonging and trusted by roughly half the participants).

The idea of 'solving' high hashpower attackers by imposing some kind of self-consistency constraint appears to be one of the perennial (bad-)proposals around here. They all damage consistency— which is a more important objective—, they all fail to prevent reversals with certainty (e.g. huge amounts would be reversed in my above attack example when consistency is finally recovered, ones with many many more confirms than the 6 the attacker produced), and to the extent that they might do anything at all they all present a new practical attack surface where none existed before. It's possible to propose forms which are which are so weak— e.g. only bar >=210000 block reorgs— that they do nothing at all and thus also don't create a practical problem, but if you propose one that would stop an actual attack then that same attack effort could instead be put into creating an optimized convergence failure by careful propagation to produce a maximum entropy partitioning.