Skip to content

Using EMA for BCH's new DA #49

@zawy12

Description

@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
  1. 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.
  2. Clip solvetimes to 7xT max, no min to prevent spam attacks [see addendum to this list]
  3. Use previous solvetime and previous target. No median of 3.
  4. 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.
  5. Reduce "revert to local time" from 70 minutes to FTL/2 or less to prevent Sybil attack on time. Best is to remove it.
  6. 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%
image

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%
image

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%
image

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%
image

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%
image

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%
image

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.

image

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions