Friday, September 9, 2016

Ideal difficulty algorithms for cryptocurrencies

a post to github related to monero and zcash:

I've come to the conclusion that the best difficulty will be a simple rolling average:

next Diff = avg past N Diff * TargetInterval / Avg past N solve times.

The shorter the window average, the more protection against attacks, but there is more variation in solve times. This is unavoidable. There is a law written in stone: if difficulty is allowed to go down, you can have good protection or good solve times with a low standard deviation, but you can't have both. You have to choose how many blocks you want to "give away" by choosing the max time for say 10% of the block solves. Low block window averaging is higher protecting but wider swings in solve times. You could use N=5 for great protection if it is OK to have time to solve > 5x your target for 5% of the blocks. Once manipulators come in, you need to be prepared for 5x target 10% of the time. But such a short averaging window requires an accurate timestamp on blocks instead of miner generated times. Without that I would copy what Zcash is doing (N=17 window average with a median instead of mean for the solve times), except be sure not to use the 8% up and 16% down limits they are using, which I hope and suspect they drop before release. There is something weird with their method of getting the median that works better than the way I get the median, so us eit, which I guess comes from Digishield v3. But if you get an accurate timestamp, use the mean.

And low N averages have accidental spikes in difficulty and solve times. Miners can choose to come in immediately after those which makes the next difficulty and solve time spike even higher. so they can put it into oscillation for profit. But this might be a problem for all windows of even larger N.

The biggest protection against attacks might be to discover the methods and encourage and enable everyone to use them. That tends to block the profits of cheaters by actually leveling out the swings, helpig the constant-on miners. For example, in time warp attack is less and less useful if you initiate it and 10 people come in to take it away, splitting the profit. So maybe you shoulld give the code to enable everyone to do it. It might then become useless to everyone. Of you try to pick a bottom, but then someone comes in earlier so your bottom does not occur, and so on, until there is no bottom.

The only way I have found to get perfect protection against attackers (and fairness) and to have a perfect release schedule is to never let the difficulty drop but follow a slow steady rise, use a valid timestamp on solved blocks, and pay miners inversely proportional (Tim Olson's idea) to their solve time relative to the average time that is expected for the current difficulty setting. If a miner solves fast, he gets paid proportionally less. If he solves slow, he gets paid more. The coin release schedule stays as perfect as your clock, and there's zero profit from manipulations. The problem with a clock is that it is a third party. But it is not a problem if you're already using a subtle 3rd party going under the name of "trusted peers" who will set to a universal time clock. (The trusted timestamp also prevents timewarp attacks. ETH uses one.)

This has very important stable, real value implications. For example, miners are paid PER BLOCK for the amount of electricity needed, getting closer to the ideal of value=joules, not merely based on the average electricity expense per block expected. This requires abandoning the idea that blocks must be solved within a certain time frame. If the coin can survive post-mining on fees, then it should survive solve delays in the exact same manner to prove it can survive on fees ahead of time. But it may not result in substantial delays as everything is done so well.

This probably changes too much in bitcoin's core, and there are likely good reasons Satoshi did not do it. But it's best by starting with a known ideal and work backwards. In this case it means every time you let difficulty fall, you are harming constant-on miners relative to other types of miners.

No comments:

Post a Comment