Topic: Regarding Auroracoin TW exploit (Fix included) - page 2. (Read 27339 times)

So, lets have a gander at Auroracoin Block Explorer to prove a point I made in my post right above this, about how default KGW sucks and is a coin fountain.

Lets look at the two most recent groups, of 100 blocks.  With a 5 minute block target, we should average 12 blocks per hour, taking about 8 hours & 20 minutes to generate 100 blocks.

14532   2014-04-29 08:34:53   10   diff 122.244
to
14631   2014-04-29 19:26:02   4   diff 109.553

Just shy of 11 hours to generate the above 100 blocks.  Over a 100 block period, I'd really hope that I'd be reasonably close to being on target time wise.  2.5 hours off is significant.  But lets look at the last 100.

14632   2014-04-29 19:36:12   7   diff 109.722
to
14731   2014-04-29 23:38:07   7   diff 134.433

100 blocks in 4 hours.  That is a huge swing, and what I like to call "clumping".  Which what default KGW is prone to, because its looking at a huge window, and not reacting fast enough to whats going on "right now". But look at the block 14731, right before the diff hit 134.433.

14730   2014-04-29 23:29:39   2   diff 118.773

So, 99 blocks to go from a difficulty of 109 to 118, then bam.  Finally it decides enough is enough.  But wait...  I just notice this...

14590   2014-04-29 15:34:26   22   diff 117.466
14591   2014-04-29 15:40:09   5   diff 114.095
14592   2014-04-29 18:18:58   33   diff 114.132
14593   2014-04-29 18:19:41   1   diff 71.654

With difficulty dropping, 14592 was a 2 hour and 40 minute block.  14593, difficulty dropped to 71!  Here is where the coin fountain kicked in. In a matter of 5 hours and 20 minutes, 139 blocks were generated.  Remarkably close to the 144 block minimum window standard KGW looks at. 

14592   2014-04-29 18:18:58   33   diff 114.132
14617   2014-04-29 18:23:37   1   diff 107.076

The first 25 block of this fast period were stripped off in 5 minutes!!!  25 blocks in the period that only 1 was supposed to be generated.  Crazy stuff...  KGW sucks...  Was this an attack, or just bad luck that prompted this crazy swing?  I think you can just chock it up to KGW sucking badly in stock form with that 144 block minimum window.  Yes, if you add up all the blocks over time since KGW has kicked in, you might be near your block generation target.  But no matter how bad of luck you run into, 25 blocks in 5 minutes is unacceptable.   Bad luck is bad luck, no one should be rewarded like that for it.  Those blocks should just be lost is it was that bad.  This scares me more than time warp, because it will happen under just normal operating conditions.

Those running KGW might want to take a look and my commit for BOB's Wormhole, and possibly adapt it to their own coin, if they still plan to keep it KGW.  That is if no one finds its flaws are worse than stock.
BOB's Wormh0le - Kimoto Gravity Well Customization

My first post doesn't count?  Default KGW is a coin fountain.  You don't even need to exploit it.  Just throw hash at the coin, and it starts spitting blocks out.  Grab about 40 - 50 blocks in a couple minutes, then take your hash elsewhere.  Simple as that.  BOB's Wormhole addresses that issue.  Does it create more problems than it addresses?  That's why I posted here for review.  Did I choose KGW for Dobbscoin?  No.  Another member of the Dobbscoin crew approached Shakezula on the subject of difficulty retarget algorithms, and he put together this commit, which with settings like "PastSecondsMin = TimeDaySeconds * 2.5;" was sure to turn Dobbscoin into a coin fountain.  Not to mention that he failed to address the fact that Dobbscoin has a working testnet.  BOB's Wormhole is KGW tuned to a 10 minute block target, with a much smaller event horizon window.  Settings like no one else is running.  Put forth in this thread to be scrutinized.  I personally think KGW sucks.  The Wormhole IMO being the best implementation out.  I'll take clamping over coin fountain, any day.  Especially with a 10 minute block target, on a coin that isn't meant for speculators.  Maybe look at my commit history for Dobbscoin, and learn how to make a Coingen coin better than most of whats out right now.

Yes, and ghostlander has a number of quality contribution to the thread.

How about you doing the same?

Actually, those are the MinGW Versions of standard GNU C & C++ runtime libraries.  32-bit, 64 bit, I don't know...  Your wallet ran on a neither my Windows XP or 64-bit Windows 7 VM's.  Fail!  Rather than adapting the project file to conform to your non-compliant build system(breaking the build for others in the process), you should be editing your command lines used to invoke qmake & make, to accomplish the task of statically compiling binaries.  Valid criticism is not a cheap insult.  It would seem you started the insults, so maybe you should piss off.


You need to come back to the real world, where people like options.  Stop making excuses for why you can't build to Bitcoin standards.


Failed comeback.  Vague response.  You sound like a little child.  Game over.  This was actually a quite informative, leading edge thread on the subject of difficulty retargeting algorithms until you popped in and sullied it with your stench.  If you want to continue taking it on the head, we hash this out over on CCT.  No more cluttering this thread with your BS.   

libstdc++ and libgcc_s_dw2 are regular 32-bit MinGW runtimes, no real need to compile them in. In fact, this executable has even these two compiled in after a project file update. All other non-system dependencies are also built in. A cheap insult, piss off.


Blah-blah-blah. If no one in the community needs Mac or Linux or Plan 9 or whatever binaries, why am I supposed to deliver these? Come back to the real world where over 90% are Windows users and most Linux users can build Qt clients & daemons themselves. Feel proud of being a Mac user? Most of the others don't give a shit.


Really? Feel free to tell me more about coin generation, make my day.

LOL, this from the guy who can't even compile a release quality wallet.  DLL's included in the Zip for your pleasure, right?  LOL

Over at Dobbscoin, we release a full compliment of Wallets with each update.  Built to Bitcoin standards.  Not this frankenstein build system built, windows wallet only garbage that you and Shakezula seem to have pioneered.  You and your cult of crapcoin are the ones who will be dying off soon.

After a quick look at your Orbitcoin block explorer, it would appear your coin generation is all over the place.  Nowhere in the realm of where they should be for what you claim the targets are.  For PoS or PoW.

P.S. To BCX and other "testers"...  Orbitcoin is most definitely worthy of annihilation...  Feel free to hit Dobbscoin just as hard...

Been looking for a decent replacement to the PPC every block retarget algorithm. KGW, DGW, DigiShield, whatever else does no good. Have got the job done myself finally.

https://github.com/ghostlander/Orbitcoin/blob/1e417b40a65dc316037855b1d3db3b32165c80db/src/main.cpp#L1157

Re-targets every block with separate fixed targets for PoW and PoS. Two averaging windows (short of 5 blocks and long of 20 blocks), both are limited against time warping. Interwindow averaging and 0.25 damping with the final +1% / -2% difficulty limiting. Runs fine so far.



OMFG, this Bobcoin spam is now here at Bitcointalk. This annoying Coingen nonsense will get killed some day. The sooner is the better.

I invite you all to smack around Dobbscoin a.k.a. BOB, some.  It also uses KGW, has the fix in the OP applied, but it's running some settings we like to call BOB's Wormh0le, with a much smaller event horizon window.  Not intended to be the be all end all answer...  It's still KGW.  But putting something a little different out there, that we might be able to learn from.  Yeah, there is practically no hash on the coin, so it won't take much to hammer it, so try not to hit it too hard and just shatter it.  Though, at the end of the day, we're not trippin.  Checkpoint, increment versions, rebuild, release...  It'd be nicer if you didn't try to completely ruin the fun for everyone.  I'm thinking we're most susceptible to a difficulty walkup.  Haven't really tested it.  Figure some of you all might be better equipped to accomplish the task of exposing flaws with excellence.  BTCBob will probably get mad at me for posting this.  But hey...  Anyone down to hammer the h0le?  Heh heh...  Them other Bobbies will probably freak out if they see some huge diff spikes... LOL

Dobbscoin Homepage

Latest Dobbscoin Release

Dobbscoin Source

Dobbscoin Block Explorer (might be interesting to compare to Auroracoin block explorer)

Dobbscoin Home Pool

Dobbscoin SMF

#dobbscoin on FreeNode

P.S.  Though BOB has Coingen roots, Testnet does work.  So that's always an option.  Though the seed node can be wonky at times.

You should start with some control theory when adjusting difficulty.

I suggest looking at a Kalman filter first.  It is provably the optimum when the noise is random.  It is just a few multiplications and is easy to implement in a few lines of C.

But at a high level, don't try to write this in a small C function.  You have trillions of clock cycles between blocks, fork out some $$$ and write a decent high level implementation.

Why not add something like liboctave or R to the source code?  Then you could use ready-made implementations of these things.

In order to create a kalman filter, you need to create a model of how the dynamics of the system should behave.  If the goal of the control system is to keep the block output at a fixed rate, then the distance from that rate is the error you want to correct.

In addition to this error, you have a noise generator which represents your inability to control correctly.  The kalman filter will over time adjust and learn the standard deviation for the noise and thus apply the optimum error correction (adjustment to difficulty).

What you generally need to estimate is the correlation matrix between the variables in your model.

You want your underlying model to be as simple as possible, but also as correct as possible.  Some variables in a model could for example be:  the % increase in issued coins by a block, the difficulty, the difficulty error (difference from ideal inter-block time), the estimated hashing power of the network (which requires a separate model to estimate), the relative exchange value wrt bitcoin, etc.

You also need to estimate the correlation matrix between these variables, but this is mostly to make the filter more efficient.  You can set the correlations to 0 if you want.


A last point I want to make is that hard forks are not bad.  It has been shown again and again that bitcoin does not solve distributed consensus.  Both because the amount of computing power is unknown, and more politically because hashing power is already too concentrated.  Changing the algorithm on a deployed coin is something the users/developers of the coins control, not the miners, unlike what people tend to believe.  It doesn't matter how much hashing power an attacker has if he refuses to run the same algorithm as the users of a coin requires.

You can adjust difficulty every block, but you should take more than one block of history into account when you do.  Here's a simple algorithm for rapid emergency adjustment; you could use this in addition to a periodic fine-tuning adjustment, if you want. 

For a rapid emergency adjustment, look at the five, nine, and seventeen block average times.  If they are *all* too short (say, 3/4 of your desired interval or less) then adjust difficulty 20% upward.  If they are *all* too long (say, 4/3 of your desired interval or more) then adjust difficulty 20% downward.   You can make an adjustment every block, and the miners can lie about block completion times as much as they do now, but it won't be possible for them to drive the difficulty down while getting blocks faster than the interval time. 

Five, Nine, and Seventeen - because none of them divides any other, guaranteeing that no short repeating pattern of timestamp lies exposes a harmonic that will repeatedly allow them all to be mistaken in the same direction at the same time. You could use a different set, or more than three intervals, but whatever.  I'd advise against using something smaller than 5 as your smallest interval, if you're keeping the median-of-last-11-blocks rule.  Also, because although the shortest interval is your reaction time in *stopping* adjustments once the right difficulty level is reached, shortening it also increases the frequency with which natural time variation will stop a needed adjustment from being applied and how often someone lying about blocktimes can deliberately *prevent* a needed adjustment from being applied. 

20% adjustments up  or down because the 6:5 or 4:5 ratios of speed are closer to 1 than the 4:3 or 3:4 ratios that trigger the adjustment - so adjustment is guaranteed to 'damp' automatically rather than entering hysteresis (alternately overshooting in both directions).

When burst miners jump on with massive hashing power, there's a slight delay before the reaction starts as enough too-short intervals build up to 'tip the scales' of the averages.   But then block adjustments start happening *OFTEN,* and there is no pattern of timestamp lies that can do more than slow it down a little bit.  When difficulty reaches the "right" level, the adjustments quickly stop when the shortest interval saturates with appropriate-length blocks, and there is no pattern of timestamp lies that can keep it on average more than one adjustment off of where it's supposed to be.

Likewise when they jump back off again, there's a delay as enough too-long intervals build up to tip the scales of the running averages, but then difficulty adjustments start happening *OFTEN*, and once again there's no pattern of timestamp lies that can do more than slow it down slightly.  Again, when difficulty reaches the "right" level, the adjustments quickly stop because the shortest interval quickly saturates, and there's no pattern of timestamp lies that can hold it more than one adjustment off of where it's supposed to be.

If with any set of timestamp lies you can generate more blocks than the rest of the network with this adjustment algorithm in less time, you're within a few percent of being able to mount a "real" 51% attack anyway. 

:-D Frankly, do you see this as a new desperate attempt to fix something which is not fixable or do you see this as a new algorihtm maybe avoiding some of the flaws previous ones have?

This is basicly dogecoin's digishield with 2 main differences;
1) in dogecoin the reference point is difference between 2 latest block's time. In this algorithm the reference point is difference from the targeted time.
2) this does not limit the maximum adjustment (I think doge limits too much) that much.

Let's assume 10 minute target time and a block generated 1 min after previous, Fundamentally, Digishield (and all other retargets) considers it has been calculated with 10x hashing power and it should basicly increase the difference to 10 times higher (10/1). This algorithm considers it is 9 minutes too early and adjusts the difficulty just the same amount compared to a block which is 9 minutes too late. The adjustment would only be 1+(9/10) = 1.9. 

I must admit that for adjusting the hashing power, digishield is actually more accurate. But is it substantially better? Is this better against random time variance and intentional time manipulation? Does this open some new attack vectors? Maybe?

Downwards the adjustemtn would be the same, 10 times longer calculation times means 1/10 of the difficulty.

One problem with difficulty readjustment is that is is designed to adjust the difficulty based on real block calculation times. It's symmetry causes difficulty to rise exponentially if time difference between blocks approach to zero.

Maybe this kind of symmetry gives better protection against time manipulation? Or is it even worse? (this area is full of mines..).

Anything where someone has 51% or more of the hashing power will go down to a 51% attack, of course.

But with timewarp, specifically, doesn't the attacker depend on being able to fool the code that estimates the hashing power in a chain?

If that code were producing an accurate estimate, then it shouldn't matter where you can get the difficulty via timewarp or anything else.

It seems so. Cheers for the discussion.

I've seen Orbitcoin time warped today with their difficulty falling to near zero in minutes literally. The coin is a fork of NVC with some bells and whistles using 1 hour PPC style retarget window and very fast blocks. Such a small window combined with their low network hash rate and no limits in the code made it possible. Their previous retarget fix sibstituted negative time span with 0, but it didn't help much. 1 wouldn't help either. The attacker instamined a couple thousand blocks in a few hours and got away.

The conclusion is, the more weird/complicated algorithm you employ, the more likely you to run into a trouble with it some day.

The issue is a bug in branch difficulty evaluation, IMO.

BCX, can you check the logic here?  Isn't the real vulnerability to time warp due to it being possible to create a branch using less than 51% hashing power that the current code believes has more hashing work in it, than a branch created using more than 51% hashing power?  And doesn't that depend on the existence of a bug in the code that estimates how much hashing has gone into a branch?

Time warp exploits really oughtn't be possible if you can accurately pick the highest-work branch. 

If you pick a 'threshold' difficulty just high enough to ensure that any block meeting that threshold could appear in either branch regardless of when it was mined, and then you count the blocks meeting *that* difficulty, you get a very good comparison of the real hashing power used.  The one with the most such blocks is the one with the most hashing work.  Award no partial credit for blocks mined at lower difficulty as the current code (IMO erroneously) does, and I think you wind up with no time warp vulnerability. 

Right. Agree on both counts. I was specifically referring to the fix. The fix treats blocks from that past as very, very fast blocks which shoots up the diff [which is not what you want].


Didn't know about that. Interesting!

So what do you suggest? Other retargeting algos that seem promising, but haven't taken a look at is digishield and dark gravity wave2. How do they perform?

And do you agree with the trade-off? Implementing the fix pushes in erroneous diff adjustments that could be detrimental to the coin. Or make it so that a 51%-er can mint more blocks with the same work? Currently, I think it's not ideal to implement the current tw fix that everyone is implementing, since if someone is maliciously doing a 51% attack, you are screwed anyway...

Thoughts?

Altcoins check underneath their bed at night for BCX

1 second isn't much better than 0. There should be either a higher value as a fraction of block target or these blocks may be skipped from difficulty calculation or their time stamps recalculated as average of neighborous blocks. Another way is to limit every difficulty adjustment like many non-KGW algorithms do.


Not every. Those operating with large traditional averaging windows are fine, though their time warp vulnerability level is higher than usual. PPC even allows negative actual time span, so many faster forks got burned by this "feature". It samples only 2 time stamps per retarget (the last block and the previous one), applies extreme damping and gets the job done. Very slow as the damping suggests, though very easy to allow difficulty manipulations through time warps. Those PPC forks brave enough to run without the ACP enabled can be torn apart by 51% attacks quite easily.

So here's my understanding of the TW exploit & the fix.

The problem with the well is that any blocks in the past (or blocks with the same timestamp), get regarded as "PastRateActualSeconds = 0"

      if (PastRateActualSeconds < 0) { PastRateActualSeconds = 0; }

What happens now, is that IF PastRateActualSeconds are 0, it does not adjust the diff.

     if (PastRateActualSeconds != 0 && PastRateTargetSeconds != 0)

So, the attacker does the following: they work on their own chain. They put the timestamp as far as possible into the future to get max downward adjustment, and continues until the diff is lowest possible diff for the chain. At that point, the attacker generates blocks with the same timestamp, until it hits the "block-time too early" (getmedianpast) check in AcceptBlock. Basically, the attacker is pumping loads of low-diff blocks "at the same time" until they can't anymore. Putting blocks in the past don't help as they get regarded as "0" anyway in terms of diff adjustment. But putting blocks in the past, allows the attacker to get back in line with the main chain.

So, now they do it again. Until getmedianpast check doesn't fail, and do it again. It's a trade-off between being too far ahead and having enough work. But if the chains match based on the time, it's entirely possible that the attacker has the same work, with more blocks and the chains re-organise.

So if I understand it correctly (correct me if I'm wrong), the attacker still needs 51%. But now that they HAVE that 51% they can do the same amount of work, but generate more blocks.

While the fix protects against this attack, by making it unfeasible, it actually causes other problems [sky high diff adjustments as was seen with Aiden & Coin-o].

What's SUPPOSED to happen is that the attacker is not supposed to generate blocks with the same timestamp & keep the same diff. In most scenarios, this would mean there is A LOT of hashing power and the diff should adjust accordingly.

That's what this fix does here:

if (PastRateActualSeconds < 1) { PastRateActualSeconds = 1; }

If it's a block in the past, or the same timestamp, it's regarded as having taken 1 second. The problem with this is, is that if there are legitimate blocks in the past [due to network lag, or other reasons] it is regarded as an extremely fast block, rather than a legitimate block [within range]. This shoots up the difficulty (as we've seen with some coins). This happens more easily with coins with low block-times.

These diff adjustments didn't happen with the original KGW because they weren't taken into account for the diff adjustment.

With diff adjustments happening per block, it's a difficult problem to solve. Any 1-block algo is vulnerable, as blocks in the past [which is a legitimate anomaly] is an "odd" happenstance in 1-block diff algos.

So the trade-off is:

1) When an attacker gains 51%, they have the capability to generate more blocks with the same work. While this is not ideal, the reason why this is bad, is that incentives 51% attacks (as it is more monetary profitable).
2) Remove the incentives with this fix, but screw up legitimate blocks from the past [which causes absurd diff adjustments].

Personally, I think there needs to be a small "free" period where blocks from the past is okay, which of course makes the KGW not a 1 block algo...

This is of course, all assuming I'm correct... BCX? Nite69? Others? Care to comment?

Thoughts?