Using EMA for BCH's new DA

[zawy12]

Begin update: This article is long and complicated because I wanted to cover every possibility, such as RTT which I'm sure no one is going to push. To make this long story short, this is all I think a dev needs to know to implement it.

1) See Mengerian or Mark L for the actual core code to do the EMA that uses bit shifting to prevent integer divisions. The math is

next_target = previous_target * (1 + st/600/N - 1/N ) 
st= previous solvetime

2) Use the code in wt-144 to prevent st < 0. Do not use if st < 0 then st=0 because it allows an easy & disastrous explopit. 3) Clip solvetimes to 7xT max, no min to prevent spam attacks [see addendum to this list] 4) Use previous solvetime and previous target. No median of 3. 5) Reduce FTL from 7200 to N*T/40 = 1000 seconds or less. FTL = 300 or less is working fine without any reported problem on 50 alt coins with my LWMA. FTL should be > 2x "typical" block propagation delay. In consensus theory that wants to know the "voting population" (hashes) in each block it is supposed to be << block target solvetime so that miners can't falsely affect next difficulty much. This also means consensus theory indicates it should be an RTT. 6) Reduce "revert to local time" from 70 minutes to FTL/2 or less to prevent Sybil attack on time. Best is to remove it. 7) Use N=72 to have the same random variation as SMA with N=144.

Clipping: An attacker with say 10% hashrate could set large forward times to lower difficulty to where he could get a lot of blocks and then submit them when that time arrives. He can't win a chain work race, but Mark L in a comment below was concerned this could enable spam if there is no clipping. Clipping could be done with max solvetime allowed like 7xT. This is the same as a max drop in difficulty. It should be a bit more than you normally expect to see if HR is constant. It can reduce the motivation for constant on-off attacks at a cost in slightly more delays depending on the size of HR changes but I was not been able to see a clear benefit from 6xT clipping after recommending it to a lot of alt coins. I recommended it because LWMA has a bigger problem of dropping too much when on-off mining leaves. There should not be any clipping on how much difficulty rises unless it is many multiples of the max drop. Otherwise a timespan limit attack is possible. To give an example of how clipping makes it harder to spam, a 10% HR miner could send a timestamp 333xT into the future and immediately drop an N=72 EMA to 1% of it's former difficulty. It would take 55 blocks if clipping is limited to 7xT and have a net cost of 12.4 blocks at the initial difficulty instead of just 1 block. So clipping in this example makes a spam attack 12x harder.

End update

A good difficulty algorithm can allow more time to consider a POW change. If BCH switches DAs, the best options seems to be the EMA (@dgenr8's improvement to @jacob-eliosoff's) such as the one @Mengerian is doing with bit-shifting is pretty much the same as @markblundeberg's re-invention of the perfect algorithm that Jacob once briefly considered (but not in the Real Time Target (RTT) form).

The following are all the things I know of that need to be considered in implementing an EMA.

1. Prevent out-of-sequence timestamps. Allowing timestamps as far back as the MTP enables a malicious 50% private mining attack to make the most-work chain return a negative difficulty by retarding the MTP N*T seconds. This can be stopped by preventing out-of-sequence stamps in the protocol, requiring +1 s each block (preferred) or use @kyuupichan's method for making sure the DA handles out-of-sequence safely. This will also prevent the timespan limit attack which allows a >50% miner to get unlimited blocks in 3.5 days on BCH.
2. Do not limit target adjustment. I do not think there there is a reason to limit what the Da calculates. This may enable an attack like the timespan limit attack.
3. Use most recent solvetime. EMA should read the previous block's true solvetime, not an earlier one. (BTW it must use previous target. See plot at very bottom of this page if current delay in targets is used) Pools not updating timestamps in headers during hashing will reduce the benefits of the EMA by causing a 1-block delay in the correct solvetime. This causes a measurable reduction in performance. Using median of 3 (which causes a 1-block delay) on top of a pool delay will make the EMA substantially worse (see 2nd chart below). The median of 3 method is interesting, but there is not anything in terms of difficulty manipulation that it helps. [Edit: some of these problems may be eliminated by using an average of a few of the past solvetimes and/or targets, but it needs testing. For example, cryptonote coins use previous block solvetime as current timestamp. Using avg of past two solvetimes and targets may help. ]
4. RTT. Item 4 is an argument for using EMA as a mild RTT with N=80 which makes the difficulty only 1% lower at t=0 and 1% above avg at t=2xT. N=80 has the same stability as SMA N=144 if hashrate is constant. If the pools continue to not adjust their timestamps they will lose "only" 1% and not do any damage other than not taking advantage of RTT benefits. By using a Future Time Limit (FTL) that is less than the block's target time instead of BTC's default 2 hours, a cheating timestamp on this RTT can only make difficulty < 1% lower. Despite changing only 2% between 0 and 2xT, this mild RTT EMA is a lot better than the normal EMA (see delay and stolen metrics below).
5. Future Timestamp Limit (FTL) needs greatly reduced. If RTT is used or not, the FTL needs to be greatly reduced to prevent the 8% excess profit that it currently allows >50% miners or impromptu collusion to get. They needs to be >50% because it only lowers the next difficulty (in non-RTT DAs) instead of their so they need a good probability of getting the subsequent block before an honest timestamp receives the benefit and erases its effects. This is something a Bitmex article failed to mention). The median of 3 does little to reduce it because there's pre-requisite of >50% for the benefit which can bypass the median of 3. Hashrate is already jumping 600% on 10% changes, so this 8% manipulation should be very attractive to a >50% collusion. There's a related manipulation I won't describe here. No one seems to know (including Mike Hearn and kjj) why Satoshi-Hal chose such wide "-1 hour" MTP and + 2 hour limits on timestamps. No one I've spoken to can find a reason not to make them as low as +1 s to say 20 seconds, which seems to prevent any possible problem in mild to moderate RTTs. Vitalik supported Zcash going to +1 second and on the upside Daira supported lowering Zcash's to 1000 s.
6. EMA N=80 RTT. Snice a forward timestamp can help a miner in an RTT algo to lower his own difficulty, the FTL needs to be tight. FTL = 60 seconds will only allow a miner to get <0.1% lower difficulty in the T=600 and EMA N=80 situation. A miner can begin mining with a timestamp further into the future than the FTL, but he has to wait on that time to arrive before submitting the block to the network, risking another block being submitted before his. The incentives on what timestamp to set are complex. If many big miner's are trying to do this, they will cancel each most of each other's profits. Less sophisticated miners would lose very little. The competing miners would help keep solvetime close to T, so they are providing benefit, as long as they are not making it too precise and thereby causing more orphans. This will not be the case in any mild RTT.
7. EMA N=80 + EMA RTT N=11 The last chart below is my recommended algorithm described inTSA update # 3. It's a baseline normal EMA with N=80 and an EMA RTT N=11 riding on top. The negative "stolen" value indicates it's costly to attempt and on-off mining attack.
8. In EMA and Mark's, if there is a consistent offset error in the target, such rounding down if using a 1 byte precision (0.004 avg error) target instead of 3 byte, the error is amplified by multiplying by N. This can be a large error and difficult to identify. 1.004*144 = 1.76

The following are testing results on the various options. The attack models BCH's current situation which is a fairly rigorous test compared to other possible settings. Other settings result in similar relative results. The target solvetimes were tweaked to give the same avg solvetime so to prevent an unfair advantage. All the algos except the RTT have an N setting that gives the same Std Dev in difficulty as SMA N=144 under constant hashrate.

The best way to a judge a good algorithm from these charts is to see if the blue lines (avg of 11 solvetimes) are not going up and down too much, and also for thin green bars which is how many blocks (not time) the attacker is getting before difficulty has risen above his "stop mining" point. The stolen metric is the time-weighted target the attacker faced verses the average. If it's 3% then his target was 3% higher than a dedicated miner (his difficulty was 3% lower). The delay metric is the sum of solvetimes in terms of target solvetimes that took 6xT, minus 2xT, expressed as a percentage of the total number of blocks.

SMA_ Target ST/avgST= 599/600.357 N= 144 attack_size: 600 start/start: 130/135, StdDev STs: 1.283 delays: 9.6% stolen: 5.4%

EMA with 2-block delay on timestamps Target ST/avgST= 594/599.769 N= 80 attack_size: 600 start/start: 130/135, StdDev STs: 1.270 delays: 6.3% stolen: 4.4%

EMA (normal) Target ST/avgST= 594/599.721 N= 80 attack_size: 600 start/start: 130/135, StdDev STs: 1.265 delays: 5.5% stolen: 3.3%

Marks RTT "EMA" This is identical in results to a normal EMA using current block's solvetime instead of previous block's. Target ST/avgST= 602/600.094 N= 80 attack_size: 600 start/start: 130/135, StdDev STs: 1.130 delays: 1.4% stolen: 0.7%

LWMA (looks same as normal EMA) Target ST/avgST= 598/600.321 N= 144 attack_size: 600 start/start: 130/135, StdDev STs: 1.270 delays: 5.7% stolen: 3.4%

TSA (A slow normal EMA N=80 with a fast EMA N=11 RTT riding on top) The negative stolen metric indicates it's costly to try to pick a low difficulty to being mining with a high hashrate. The blue + symbols are the target the miner actually had to solve. The purple solid line is the difficulty that goes on the chain. If you look closely, almost no + marks in the green areas (attacks) are below the average difficulty. This is because the big hashrate is doing a fast solve which causes difficulty to be higher. Notice the delays and blue line swings are not any better, but in practice they will a lot better because big miners will be much less likely to participate if a 2% loss like this is the outcome as opposed to the current 5.4% gain in SMA. I discuss this more in my TSA article. Target ST/avgST= 595/599.93 N= 80 and M=11 attack_size: 600 start/start: 130/135 StdDev STs: 1.13 delays: 2.13% stolen: -1.23%

This shows the difference between an EMA with a 2-block solvetime delay (like the chart above) WITH a 1 block delay in targets. It's a disaster.

[markblundeberg]

Hmm, regarding the last graph, negative stolen seems fundamentally wrong to me ... by definition, a switch miner should only direct their hashrate at this chain when it is profitable, i.e., when the target they have to hit is strictly higher than some threshold. Since for TSA there is the distinction between actual target and the fake blockheader target, I wonder if your calculation might not be using the correct target?

[zawy12]

I mentioned that indirectly in the 2nd to last sentence. Attacking for a loss does not make sense, so they will do something else like not attack. To clarify TSA, the attack trigger is if the N=80 baseline difficulty is below their threshold not the actual difficulty. Doing it this way implies they can't switch on and off quickly, losing less than about 10 seconds of mining time between two coin choices. If they can, then I'm missing is an important case that could harm the results enough to be more like the others. If large hashrate sources can switch so easily, they can wait until after T to get the lower-than avg difficulty, which will occur in < 1/e = 36% of the blocks. This will make post T solves very fast and drive up pre-T difficulty for everyone else. In studying optimal attacks for normal DAs, I noticed a very large miner could always get up to 1/3 of the blocks at zero cost without regard to the DA so 1/e =~ 1.3 of the blocks coming in at > T could indicate the rule still applies. The rule comes from the very large miner mining 2/3 of the blocks getting (effectively) 1/3 of the block at an average D cost, the other 1/3 at zero cost, and the remaining 1/3 that he's not mining would equal to 2x the average D.

You asked for data on the time-weighted avg difficulties for the above. 1374 SMA 1367 EMA 2-block delay 1355 EMA 1331 Mark RTT 1358 LWMA 1207 TSA

Constant HR: if there are no 6x attackers, avg D is 1000 in this simulation (at dedicated miners hashrate). The avg time-weighted D's for the regular DAs was 1000. The RTTs had 1.5% lower for Mark1 and 8% lower for TSA.

[zawy12]

I've updated the beginning of this article to facilitate discussion.

[markblundeberg]

There are a few practical things I wonder:

• Are the tighter timestamp rules going to affect miners adversely? I know timestamp rolling can theoretically be used for ASICboost, though it seems to be not used much in practice.
• The 144 / 72 numbers still sound arbitrary, like satoshi's 2016. There needs to be analysis of realistic price action with realistic switch/steady mining ratios to see what kind of numbers make sense. My gut feeling is that analysis would recommend a slower DAA (even a slow DAA can actually respond fairly quickly due to switch mining).
• I totally get the hesitance about putting clipping, however I am nervous that a DAA which permits huge difficulty drops would allow cheaply making low difficulty header chains to spam nodes (and cause out-of-memory): basically just one blocks' worth of PoW to drop difficulty to 1, then create a long string of difficulty-1 headers. I don't know if there is any non-rule-based (just optional) mitigation that can block these without also creating a sneaky chain split risk.

Finally, there are four rule changes proposed: 1) DAA, 2) Timestamp monotonicity, 3) FTL, 4) Clock. Even if they are simple changes and the final state is robust, the transition needs to be handled carefully and consider the interaction between all these changes happening around the same time.

[zawy12]

I have not heard of any theory or observation that timestamps limits even as low as a few seconds have caused a problem.

Only 1 rule change needed. Keep current timestamp limits? 3 of the 4 rule changes can be avoided: Monotonicity can be done within the DA code (see bottom). FTL and clock can also be left alone. The potential damage from leaving FTL=7200 is a forwarded timestamp at that limit that would lower the next block's difficulty.
1/( 1+t/T/N-1/N) => 1/(1 + 7200/600/N - 1/N) = 13% easier difficulty.
The full 13% drop can be achieved only once per 2 hours, or spread out over it, benefiting the next block (not necessarily the "cheaters" difficulty) and penalizing others. The forced monotonicity (either by protocol of the DA) will make the next 10 or so honest solvetimes 1 second, increasing difficulty 1/(1-1/N) = 1.4% per block, bringing difficulty and avg solvetime back to the correct values. So the risk is mild. BTW if you clip the difficulty to not drop too much, say 5%, then the avg solvetime will be lower. I believe it means block emission will be 600 * (0.13-0.05) = 48 seconds behind, costing all of today's miners that much coin (8% of one reward).

N > 72 is probably a good idea The 72 gives about the same std dev in difficulty under constant hashrate condition as the current SMA N=144 which is about 9%. See charts below. Given that miners are reacting to 5% changes with strong sensitivity I believe you are right that a longer window would be better. A problem is that the reduction in random variation is a function of SQRT(N) while the slowness to respond to HR changes is a function of N, so with higher N we get slower faster than we get stable.

Clipping drops in difficulty with limit on solvetime Concerning the need for limited drops in difficulty, the method I've used in many coins is to limit the solvetime as used in the difficulty to 6xT which is very infrequent from random variation. This would allow a max drop in difficulty in a block of (6-1)/N = 7% for N=72. A longer window will reduce this. 5xT is possible, but not lower. This type of clipping can lead to larger-than-expected solvetimes if on-off mining triggers it a lot.

Currently, single block difficulty can rise or fall 10% due to long solvetimes coming into and out of the averaging window. With EMA, rises are limited to 1/N, so it gives miners more time to decide to leave, which reduces the chances that they all leave at once, preventing the long solve time if the DA reacts fast enough to drop as they leave. 1/72 = 1.4% and since they are sensitive to 5% changes, a larger N is again reasonable.

Code to prevent negative solvetimes

// We do not want to use MTP because of the 6-block delay, so we do this
// My source of the idea is T Harding who cites kyuupichan
// Catastrophic exploits result from attempting  if (st<1) { st=1;} 
// Attacker simply assigns old timestamp. Next honest stamp lower difficulty.
// Repeating this with 20% attacking HR if MTP(11)=6 quickly leads to a difficulty of 1.

previous_timestamp = timestamps[0];
for ( uint64_t i = 1; i <= 11; i++) {  // 11 is most recent block
      if (timestamps[i] > previous_timestamp  ) {   
            this_timestamp = timestamps[i];
      } else {  this_timestamp = previous_timestamp+1 ;   } // +1 sort of a safety measure
      solvetimes[i] = this_timestamp - previous_timestamp;
      previous_timestamp = this_timestamp;
}
// clip, if desired:
solvetime[11] = min[6*T, solvetime[11]);  
// EMA would use solvetime[11]