Topic: New vulnerabilities in the advent of off-the-shelf ASIC mining (Read 4434 times)

Good to know that Gavin is willing to stand the ground. I am happy that Bitcoin has good leadership who's going to reject any compromise of the core principles of Bitcoin's design.


I would like to make a statement here as ppcoin's designer I fully understand the purpose of decentralization. We plan to phase out ppcoin's central checkpointing mechanism gradually as the network matures and gains strength against powerful attackers. Well I understand some folks would always doubt about our sincerity, but as of our v0.2 I am confident ppcoin can indeed remove dynamic checkpoints eventually. If you really thought about how an alter chain is started you would know that 51% attack is a serious threat to a young chain.

Ouch, you are right, the ASIC producers really could create timebomb chips.  Nice catch.  If we ever figure out who Satoshi is, we'll have to give him a little crap for missing that potential attack.  But honestly, who could have seen that one coming?

The good news is that there are several ASIC designs ongoing, and they will presumably all come out of different fabs, so in the long run, the diversity of the network should provide some safety.

Maybe we should put this on the hardfork wishlist.  Changing the hashing method entirely would be, well, bad.  But we could accept two different hashing methods, the old way and the new safer way that doesn't leak any information to the hashing device.  That way we aren't breaking the large investment into current ASICs, while allowing miners the option of safer hashing when they expand/replace their gear.

(Verification would be trivial, wouldn't even need a new block version.  If the normal hash attempt doesn't work, try it again with the header's nonce field set to zero and the external nonce value set to whatever was in the block.)

Amusingly, on IRC we were talking about chips that could accept the entire header as their input rather than the midstate.  This way, ASIC designers could build their chips to refuse to participate in certain kinds of attacks, which would reduce the amount of trust that miners need to have in the pools they use.  I'm curious how the mining world would balance these two concerns with contradictory solutions.

Sorry, I thought that I had been quite clear about it.

The rule that I suggested was "not more than X hours newer than the deep block with the same height", where X is >=3.  Keep in mind that this is only for deep replacement, that is important.

As in, I'm currently on block # 197,710.  I get a new block claiming to be # 193,001.  The timestamp on the new block is from yesterday, which is ~2.5 million seconds later than the block # 193,001 that I already have, thus I conclude that the new block is bogus and drop it.

However, if there was a natural network gap of more than X hours, and an attacker presented a chain during that time, that chain wouldn't really be an attack, it would be the chain.

An answer to a bit old post...


gmaxwell has pointer out that to me that there are some fields that are passed to the bitforce hardware. They are:

- timestamp    
- difficulty target

Any one of them can be used code a "time bomb".

I would have been better if Hash(Hash(Header-without-nonce) || nonce) would be chosen for PoW instead of Hash(header) for Bitcoin.

Perhaps you need to speak more concretely then. What rule?
Any rule you can imagine could be met by a natural block gap. E.g. you set it to two hours. Then a natural two hour gap happens, and an attacker can create a chain killer fork that covers that gap.

No. They wouldn't. Nodes only propagate what they believe to be the best chain.

But that is less than 10 minutes, well inside the range to be "not a jump".  A timestamp discontinuity isn't "more than the last few blocks", it is "more than the rules say".


The nodes that do not use your algorithm would still be flooding the network (or at least each other) with BS blocks.  The only way to prevent that is to force nodes to switch to your algorithm, which would be a protocol change.  Currently, they are allowed to do it however they want, as long as the end result is the same.  The difference is subtle today, but I think it will be less so as the network outgrows the current homogeneous period.


+1

No. Absolutely not.

He would cut back one week, and create a fork with a bunch of consecutive timestamps.  e.g. 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 ....

Then a new bootstrapping node would startup and see "1 1 1 1 1 1 2 2 2 2 2 2 3 3 3". Then it would hear the valid chain, and see "1 600 1200..." and think that it jumped.

Of course there would be, otherwise it would be a config option and not an RPC.

We do not have any 'dynamic risk' "last resort" mechanisms anymore: no safemode alerts. Checkpoints only get changed by updating the software.
Your reject-txn sounds like sipa's fork-mode patch.
0_o I don't consider that a midpoint at all. We'd first have to rename Gavin "Bitcoin Bernanke", but fortunately I know he's smart enough to not accept that job.  I don't quite see how making it possible for anyone who kidnaps Gavin to shut down bitcoin is an improvement over your million dollar scale attack, as I expect it would cost much less than a million dollars to do so...

First, I just want to thank kjj for linking the code that shows how BF work, gmaxwell for his proposal and all for this excellent discussion.

Maybe we could implement the idea of dynamic checkpoints (Gavin) but only if they come signed by the Alert signing key ...

Or even we could create a special Alert message that comes with a new checkpoint embedded.

This would be a mid point between Gavin and gmaxwell positions.

I vote for signed checkpoints, with a confirmation dialog shown to the user. +1

as it is possible that a user checkpoints a chain which becomes orphan i think we need a mechanismen to override user checkpoints by checkpoints from new bitcoin versions

FWIW I like the idea of being able to add checkpoints via RPC. Yes, there's potential for abuse but Bitcoin has always had "last resort" safety mechanisms in it, like the ability for alerts to shutdown the RPC interface, checkpoints themselves, etc.

If anything "addcheckpoint" is not really the right solution. What we really need is a "markinvalid" RPC that marks the given transaction as rejected, triggering a hard-fork point. Otherwise you can only checkpoint blocks that were already mined. If something goes wrong and miners are all working on a chain that is broken somehow, you really want the ability to temporarily switch to an alternative chain. If it's the block itself that you want to kill off then just mark the coinbase as invalid.

If there's no central distribution list for these and it's up to miners/merchants to invoke the RPC by hand, IMHO it feels safe enough. In a worst case scenario of a sustained attack a set of scripts that downloads a list of bad transactions from a central place and auto-blacklists them could be thrown together in a hurry, but I doubt it'd survive to become some kind of central authority in the absence of tremendous external pressure (like governments forcing miners to use their blacklists).

How would an attacker re-write the timestamps in the blocks that everyone already has?  The original chain has a sequence of blocks with (more or less) evenly spaced timestamps, and there is no possible way for an attacker to make that look like it has a jump in it.  The best the attacker could do would be to pile up the timestamps, one after another, in his attack chain.  He can't go backwards to make a jump.

Essentially, if we are looking at a possible fork from, say, a month ago, the first block in the newly presented fork really should have a timestamp from a month ago too.


Good point on the constant work amount.  Whatever he gains by messing with the old timestamps, he'll lose when his fork is putting out blocks more often than usual and he'll end up in the same place.


Yup, that idea would have some issues.  I occasionally suggest using an exponential difficulty difference for triggering deep reorgs (or rather for avoiding them), and people make similar objections to that proposal too.

Also, it doesn't help that we are wandering around two different issues, a 51% attack and a BS blockspam annoyance.  Your algorithm would kill the blockspam problem, but only if every client uses your algorithm, which would be a de facto protocol change.

@gmaxwell
Is there an open issue about your proposal on bitcoin git?

You're imagining a honest shorter chain, and a dishonest longer fork that has a big timestamp gap. Lets reverse that:

Imagine the network is following your rules. There is an honest longest chain. Now I construct a dishonest fork timestamped such that the true longest chain looks like it jumped forward in time relative to to my fork. Either the whole network now rejects the honest chain on seeing my fork (bad),  or they only apply your rule only one way on reorg decision (e.g. only demand it when switching from a 'better timestamped' shorter fork to a longer fork) which would mean that a newly bootstraped node's chain decision depends on which chain he heard first (because the dishonest fork may have been the longest from his perspective until he heard the longer one) and as a result network can't reliably converge (bad).

I'm skeptical about the extra work comment... The amount of work needed to overtake the longest chain from a given cut point is _constant_: its the amount of work in the longest chain after that cut. Difficulty doesn't come into play.  Ignoring the timewarp issue, there isn't much advantage that can be gained by lying about the timestamps, and most you could get 4x per 8 weeks you cut. Go too far back and you need a really significant super majority to get ahead in a reasonable time... and the advantage is just the inflation you could create for as a factor of log4(your rate/network rate) from undercorrection with your correct timestamps during the point where your chain is 'catching up'.


When I initially read your message I misread it as asserting that sufficiently old stamped blocks should not be considered. I realize now I misread it, but since someone else might have:

I'm not sure that my suggestion actually allows for permanent forks, at least not honest ones.  In an honest fork, the timestamps in both branches will follow the rules, allowing an isolated network to rejoin.

Heh, I did read it.  It seems like a good system for usability/performance.  I wouldn't classify that as a "minor" change in client behavior exactly, but it does have the advantage of not changing the timestamp rules.  Something about it bothers me, but I'm not sure what.  I think it might be that it only protects clients that use that algorithm for fetching blocks, leaving the rest of the network open to the attack.  The same could probably be said about changes to the timestamp rules, at least right now while the network is fairly homogeneous.  I will ponder on it some more.

Unrelated to your algorithm, say that the attacker did have 51% of the network power, which I think is silly, but try it anyway.  The current rules allow him to rewrite history, and blatantly tell everyone that he is doing it (by using correct timestamps).  Why not force him to make fake timestamps back to his chosen fork point, and then accept the difficulty adjustment consequences of doing so?  The amount of extra work for the attacker would in some cases be non-trivial.

And my philosophical objection still stands.  Why should the network accept a block today, with a timestamp of today, as a candidate to start a fork days or weeks or months in the past?  Inertia doesn't seem to be a good answer to that question.

Please do me the respect of reading my message above where (in the last paragraph) I explain how to solve this, in a way which isn't a fork or a rule change at all... just a minor difference in the order of operations when fetching and checking a chain. While I didn't include an actual implementation, I provided pseudocode of the algorithm detailed enough to propose attacks against.  It isn't a new idea: this whole set of issues has been discussed many times before and so far no one has yet pointed out why what I suggest wouldn't make it mostly a non-issue.

I was trying to draw attention to the fact that all the suggested fixes here involve allowing permanent forks. But yeah I misread some tenses.

The problem is that when you look at a block by itself, you don't know if that block is eventually going to be part of a chain with more difficulty than what you already have or not.  The timewarp won't give the attacker a longer (more difficult) chain, but it can allow him to create a ton of blocks that look valid enough by themselves that we have to keep them around anyway.  This is a potential DOS vector, not necessarily a Finney.

I know that a ton of work is currently underway on the block storing and indexing parts of the client, so presumably a node will be able to purge BS blocks like this sooner or later, but why even assist the attacker by letting the network relay them?

Right. Because of the timewarp attack an attacker who cuts >2 weeks back (more is better, of course) can make a chain with interleaved past timestamps which reduces in difficulty no matter how much hashpower he's throwing at it (if anyone is interested in this attack, I performed it on testnet3). Of course, if he doesn't have a majority of the hashpower his chain won't be the longest; so it's moot except as a flooding DOS against nodes with the full block sync behavior.

It's possible to do a little more aggressive timestamp sanity checking to largely close that behavior... but it's hardly an attack if nodes first check header difficulty before pulling a chain.