[bug?] Time Warp exploits. Why is the attack chain accepted?

[Cryddit]

EDITED:

Okay, I get why someone can game a difficulty adjustment algorithm and lie about block timestamps in order to create an attack chain which

a) has more blocks,
b) ends on or before the same timestamp as the main chain,
c) took less than the same amount of hash power to produce.

And so far we've focused on the difficulty adjustment algorithms to try to fix it.  But I have a different question. 

Why aren't these attack chains recognized as containing less work?  Regardless of length, timestamps, or whatever, shouldn't they simply be recognized as containing less hashes and never given the chance to displace the main chain?

[Cryddit]

The Time Warp Exploit depends on the ability to get a block created by less hashing accepted as "longer" or having more work in it.  Ultimately, that determination is made by this routine.  The theory here is that this returns the number of hashes required, on average, to create this block. Thus the sum of it for each block from the root to the tip should equal the amount of hashing power required to create the chain.

It appears that this should do what it is intended to do.  And yet, Time Warp Exploits work.  Why?

Code:

    uint256 GetBlockWork() const
    {
        uint256 bnTarget;
        bool fNegative;
        bool fOverflow;
        bnTarget.SetCompact(nBits, &fNegative, &fOverflow);
        if (fNegative || fOverflow || bnTarget == 0)
            return 0;
        // We need to compute 2**256 / (bnTarget+1), but we can't represent 2**256
        // as it's too large for a uint256. However, as 2**256 is at least as large
        // as bnTarget+1, it is equal to ((2**256 - bnTarget - 1) / (bnTarget+1)) + 1,
        // or ~bnTarget / (nTarget+1) + 1.
        return (~bnTarget / (bnTarget + 1)) + 1;
    }

[Foxpup]

And yet, Time Warp Exploits work.

[citation needed]

[Cryddit]

Okay, I do see one way for timewarps to work as an attack, but only as a way to leverage the profitability of a 51% attack.

If an attacker screws around with timestamp lies and exploits the block reward adjustment algorithm, he can use 51% of hashing power to generate a blockchain with ten or fifteen times as many blocks - thus he gets ten or fifteen times as many block subsidies. 

The attack chain will be accepted because it has more hashes, not because he found a tricky way to get something created with less hash power accepted. 

So now I need to think about what is the correct fix for that.

[gmaxwell]

Okay, I get why someone can game a difficulty adjustment algorithm and lie about block timestamps in order to create an attack chain which
[...]
c) took less than the same amount of hash power to produce.

You cannot get nodes to accept such a chain, you're confused about what people are talking about with timewarps; or confused because this is really an altcoin question and some altcoins have further broken things. Bitcoin won't switch to a chain with less apparent work.

[Cryddit]

The attack has been used on several alts, so I'm looking for the bug that allows it in the bitcoin code they have in common. You can claim it's an "altcoin question" if you want, but the bug that allows this is in the code they inherit, whether or not they aggravate it with difficulty adjustment algorithms that respond more quickly to changes in network hashing power. 

[cr1776]

The attack has been used on several alts, so I'm looking for the bug that allows it in the bitcoin code they have in common. You can claim it's an "altcoin question" if you want, but the bug that allows this is in the code they inherit, whether or not they aggravate it with difficulty adjustment algorithms that respond more quickly to changes in network hashing power.  

I believe the common element is the so-called Kimoto Gravity Well which is not in bitcoin.  If you look at the TW exploits on AUR coin, for example, you'll see that the KGW appears to have opened this hole.  The point is that since KGW isn't in bitcoin, bitcoin shouldn't be impacted by this TW exploit.

So this is really an alt-coin question although it is interesting to see the side-effects of the KGW changes.  This is a positive to alt-coins in that they can be used for experiments like this.

[kjj]

The attack has been used on several alts, so I'm looking for the bug that allows it in the bitcoin code they have in common. You can claim it's an "altcoin question" if you want, but the bug that allows this is in the code they inherit, whether or not they aggravate it with difficulty adjustment algorithms that respond more quickly to changes in network hashing power. 

Not a bug.  There are several scamcoins that have deliberately chosen to disregard a safety measure built into bitcoin.

Search for artforz.  Several scamcoins ignored warnings that the attack was possible, so he demonstrated it live.

[DeathAndTaxes]

The attack has been used on several alts, so I'm looking for the bug that allows it in the bitcoin code they have in common. You can claim it's an "altcoin question" if you want, but the bug that allows this is in the code they inherit, whether or not they aggravate it with difficulty adjustment algorithms that respond more quickly to changes in network hashing power.  

This.  Yet people claim altcoins are innovating.  While that may be true in some very limited cases the majority of the altcoins to date have been created by people who may understand WHAT bitcoins does but they don't understand WHY it does it.  It is like trying to do surgery in the dark.

[Cryddit]

When I went looking for the bug that allows time warp exploits, I found something related.  Not what I had been told the time warp exploit does, but something related to it.

If you can use timestamp lies in some way to trick or manipulate a difficulty adjustment algorithm,  an attack chain can arrive at the same timestamp as the main chain with many times more actual blocks, having used the same amount of hashing to get there. 

The result is that a 51% attack can use an attack chain with a STOOPID number of coins, rather than an attack chain that simply gets all the coins that the main chain issued to other miners while  the attack chain was built.

Bitcoin had an irregularity (really too slight to be called a bug) in its implementation of difficulty adjustment that allowed a certain type of fiddling, in that it adjusted difficulty every 2016 blocks, based on the 2015 intervals between those blocks; but once per difficulty adjustment, one interval between the end of one block and the beginning of the next was skipped by diff adjustment.  Thus, Bitcoin's difficulty adjustment algorithm could be manipulated by an attacker, but only by about a quarter of one percent per difficulty adjustment period, which is why it's an irregularity rather than a bug.  An attacker would do this by selecting that skipped interval to make a backward jump in time which difficulty adjustment wouldn't take into account.  This would be a 51% attack, in that he'd have to use hashing power equivalent to the hashing power of the entire legitimate network to form his attack chain.  In Bitcoin's case, the attacker would have to generate a chain that stretched through dozens of difficulty adjustment periods to have a really significant impact on Bitcoin's difficulty adjustment, and even if he had the multi-petahash infrastructure that would take, there'd be a checkpoint locking out his attack chain by the time he got the difficulty in his attack chain down significantly.

This irregularity became an outright bug in altcoins which shortened the adjustment interval to the point where this kind of manipulation could give an attacker nearly-arbitrary control over difficulty adjustments and block rates - in some cases even allowing the attacker to walk timestamps backward WHILE lowering difficulty, by making intervals shorter than 6 intervals (the 'median-of-last-11-blocks' rule guarantees nondecreasing timestamps only for adjustment periods longer than 6 intervals).  KGW and several other difficulty adjustment algorithms introduced new and different bugs that allowed the same kind of manipulation.  So this attack, applied to those alts, could instamine their entire remaining supply of coins in a 51% attack, and the very short difficulty adjustment periods made it feasible to form attack chains that invoked difficulty adjustment hundreds of times.

But none of these difficulty adjustment bugs would EVER have allowed an attack chain formed with less than 50% of hashing power to displace the main chain, assuming the routine I quoted above remained in place.  So the Time Warp attack as described to me is either not this attack, or the person who described it was simply wrong. 

Is that what the time warp has been all along?  Just a particular type of 51% attack?

[Evil-Knievel]

This message was too old and has been purged

[Cryddit]

It is like trying to do surgery in the dark.

I think the metaphor I'd have selected is that it's like trying to do surgery on an individual of an unknown species.  You can see what's in front of you, but you must understand what it does and why it's important (and therefore what aspects of its behavior must be preserved and what else must be adjusted if you change it) before you mess with it.

I'm an old crypto geek, but there is a LOT more to this code than crypto.  In fact, the crypto aspects of it are among the very smallest parts.  

It's good code, but frequently nonobvious, and commented even less than most opensource projects.  The 'nonobvious and uncommented' combination makes it hard to get full understanding.  'nonobvious and commented wrong' would be even worse, of course, and that's the most frequent alternative.

Finally I'm stunned to see how much it's using SSL and Boost, because SSL is a crawling horror, and Boost is too large and complex to be genuinely believed secure.  

some reading.... http://clearcrypt.org/tls/

[Cryddit]

Well what counts is the cumulative work done.

So let us say the current difficulty is 10,000,000,000
and someone accidently finds a block with a much higher difficulty like 1000,000,000,000 (which may happen by chance).
When he withholds the block, he will be able to reverse all transaction until the next 100 blocks have been found, right?

This sounds dangerous.

That's not the way it works.  The routine above estimates the amount of hashing required to solve the current difficulty, not the amount of hashing required to get the particular hash. 

IOW, if he gets a hash (any hash, no matter how low) for a block whose difficulty is 10B,  the chain including that block only gets credit for 10B hashes. 

[Evil-Knievel]

This message was too old and has been purged

[DeathAndTaxes]

Is that what the time warp has been all along?  Just a particular type of 51% attack?

Yes the original time warp bug requires the attacker to have more computing power than the rest of the "legit" network.  It is a potential attack for an attacker with a majority of the computing power.  Double spending, timewarp exploit and transaction halting are all exploits which become possible when the attacker has a majority of the computing power.

As explained by ArtForz (whatever happened to him?) here:

Obviously this ignores the "problem" of the attackers chain having way lower sum-of-difficulty
but that's easy to fix - just keep driving diff up at maximum speed until you have the same total work as the real chain.

Here's where I get confused. I haven't looked at the calculation in detail but surely you can't get the same total work as the real chain without doing approximately the same amount of hashing as the real chain, no matter how many blocks is in your chain or how you've manipulated the difficulty? Please explain further...

No, obviously you need to do the same or more total hashes as the real chain (it is a 51% attack...)
The "bad" part is that you can make your chain have more blocks while having the same start and end nTime.
And yes, it *should* be using 3-7, 7-11, ... but it doesn't. (probably to avoid the issue of the first interval after genesis, as you'd need to know when hashing of genesis started = the timestamp of the block before genesis).
The code I'm currently playing with gets around this by special-casing that first retarget to have a nInterval-1 span instead of nInterval.

Now with so many developers of unknown skill combined with minimal peer review and often very rushed schedules (pump and dump) it is possible some altcoins may be attackable with less than a majority of the hashpower but the original attack was always limited to a 51% exploit.  The sad thing is ArtForz outlined a fix back in 2011 yet many of the "innovative" altcoins not only didn't use the fix, they amplified the attack by not understanding the implications of changing the the adjustment period, the symmetrical max adjustments, and the block interval.

But none of these difficulty adjustment bugs would EVER have allowed an attack chain formed with less than 50% of hashing power to displace the main chain, assuming the routine I quoted above remained in place.  So the Time Warp attack as described to me is either not this attack, or the person who described it was simply wrong.

a) has more blocks,
b) ends on or before the same timestamp as the main chain,
c) took less than the same amount of hash power to produce.

Baring evidence to the contrary, whoever informed you is wrong about c.  In the case of Bitcoin it is definitively wrong.  It may be true for some altcoins but as much as altcoins have messed up the Bitcoin security model in some cases I don't know of any which are so messed up that they make c true.

[Cryddit]

Okay, I feel better now. 

It turns out that that description of time warp's effect was just plain wrong in the first place, and time warp is nothing but a subspecies of 51% attack.

So the boneheaded bug I was looking for does not in fact exist.  Nor have I (and many others) been just stupid for not being able to see it. 

Time warp amplifies the destructive power of a 51% attack drastically, but a 51% attack means you're kinda screwed anyway, doesn't it, so this is a more minor deal than I'd thought.

 

 

[gmaxwell]

Time warp amplifies the destructive power of a 51% attack drastically, but a 51% attack means you're kinda screwed anyway, doesn't it, so this is a more minor deal than I'd thought.

Yup. Some altcoins have made it worse with crazy rule changes but in bitcoin it's kinda boring. We could also close it with a soft forking change e.g. detect the median dodging and add a further time clamp, but its such an unimportant thing no one has given any real though to the safe and sufficient rule for it.  I went as far as adding an attack to testnet so there would be something to test against.

[thaReal]

Hey, glad I finally found this thread - I had caught the tail end of a previous discussion on this and that thread was closed shortly after. Anyway, I've been spending time looking into trying to figure out an improved version to KGW and some of the variants on it. Cryddit had replied to one of my questions on the last thread with a very good piece of code that re-ignited my interest in this. So I had been doing my  best to follow the results of the Time-Warp attack and while I understand the principals mathematically, (I'm only a 'hobby-coder', so to speak) I wasn't completely sure one way or another whether specific pieces of code that I was not completely familiar with could allow the alternate chain to be accepted. So thankfully, I think this is a pretty conclusive answer by some knowledgeable people and especially thanks to kjj and DeathAndTaxes for the super informative history lesson about ArtForz - I looked into his posts on the discovery of the problem and his subsequent simple fix using a known past reference block to invalidate a forged chain.

So at this point, I think a new "difficulty re-target" solution is something that is long overdue. Now I'm not going to claim that I can come in and magically write some amazing formula that's going to solve everything, but I'm fairly confident that we can certainly do better than the current status quo.

One of the most mind boggling things to me is how KGW was never truly "introduced" or "explained", unless there's an actual whitepaper somewhere that I haven't managed to find. Rather, it seems like it was more or less described in a forum post for megacoin by a user who hadn't even created it himself and even at one point writes that he does not understand the mathematics behind it. Then this post was turned into a mix of a semi-scientific explanation, an advertisement for megacoin, and several jokes and all bundled into a 'flyer' of sorts which became the official KGW reference. That in itself isn't anything special... But I guess as a result of the massive growth of multipools almost every single coin adopted it basically as-is without having any real idea of how it was working (or more specifically, how the actual parameters would effect their coin individually) and it seems like no one has questioned how absolutely absurd  the entire situation is behind its creation because it would then require them to propose a better solution.

Anyway, I do want acknowledge that at least their have been attempts as of late with DGW and DigiShield, and I have to imagine that they are indeed improvements, but I think there's a better way to approach the problem in general.  So rather than try to jump straight to an algorithm, I think if I could restructure the layout of the problem we're looking at, we might be able to find a model that could essentially be 'tuned' to work with any coin. So I guess before I attempt to do this - is anyone aware of some type of real analysis of this or something that explains how the original kimoto formula was derived? I'm going to assume no, but maybe there's something out there that I missed along the way.

Thanks again all.


 

[gmaxwell]

"KGW" is just an EWMA with not especially well justified parameters and a technobable name that obfuscates what it actually does. Other coins used similar things (some to their own demise) before it was ever described. All of the faster update rules make things more stable in the face of hopping (as opposed to, say, merged mining which makes hopping not happen) but do so at the expense of reducing security against isolation, I don't think they're a good win— and when they're not fixing the self inflicted wound of being a redundant coin without merged mining they're usually just the kind of superficial change altcoins typically make that don't require even knowing how to code. They're also far outside the realm of bitcoin today as we've never had a problem due to the update rule, and not really related to the timewarp attack (as it can be closed completely with basically two characters changed in the code— correct the off-by-one to make the retarget windows share a block.

[Cryddit]

I looked at KGW and didn't much like it. 

The code I posted in the other thread adjusts when several moving averages are in agreement as to the adjustment needed, and doesn't make the kind of nonlinear twitchy adjustment KGW can do.  It can make adjustments every block, but does not make its decision about adjustment based on the timing of just the last individual block.  The very shortest moving average prevents most adjustments once they're in the neighborhood of being right, and the longer moving average doesn't permit adjustments unless they're justified by the more statistically significant larger sample size.  So you get a significant adjustment every block when a pool or a burst miner jumps on or off and you're way out of balance, but you don't get twitchy stupid adjustments when a couple of blocks come in within seconds of each other.

Merged mining is a very good thing, but if you're trying to implement it for an altcoin be very careful.  It's done correctly in namecoin, but incorrectly in several other places.  It can be a vulnerability for an altcoin unless done safely.  Several alts have been attacked after implementing merged mining wrong.  Also, think very clearly about why you want to implement an altcoin.  What are you doing that Bitcoin (and instruments based on it) does not and cannot do, and is there a significant niche where that is actually needed?  If there's no answer, your altcoin doesn't have a mission -- nor a chance in hell of success.

Having satisfied myself that Bitcoin is not particularly vulnerable to time warp at this time, I would say that one thing you could do to protect an altcoin from a timewarp would be to include a recent bitcoin block hash in its block, to authenticate the timestamp.  A block 2 hours old is fairly immune to Bitcoin chain reorgs and would flatly prevent anyone from being able to form altcoin blocks more than 2 hours in advance of their claimed timestamp. That means a time warp, even if successful, could not claim very many 'extra' coins.