crypto-perry
commented
4 years ago Hello,
Happy to see you reviewed the paper so promptly.
Your comments are all valid points. Let me respond to them in order:
Section 3.2 We were not trying to say that BCH is really bad just that the situation can get much worse, maybe we were not very explicit. You are absolutely right saying that the situation used to be better and this can be seen from the plot measuring number of blocks per hour, but as you rightly point out this only used to happen when coin-hopping was not happening and mining was subsidised. I think in the future coin-hopping will happen more and more as mining pools introduce auto-switching functionalities, so deserts and spikes will indeed get out of hand.
I think the problem with a sliding window is actually an important factor for sustained cyclicality. It's just not right that a solve time influences the hash rate estimation twice: when it enters the window with negative feedback (i.e. if the solve time is long, it increases the window length and causes the difficulty to go down) and also when it falls off the window with positive feedback (i.e. when a long solve time falls off the window, its length decreases and the difficulty goes up). The reason I don't believe the entire average is balancing out is that this is not just a random process where long block times occur randomly because miners will respond to these oscillations by mining according to profitability. Positive feedback should not exist in any DA because it creates incentives that should not be there. This positive feedback is essentially sustained by coin-hoppers and that's how the cycle of long block times followed by short solve times forms. The fact that the SMA also has a delay, is a major factor as well as you describe very well in some of your posts, because it allows coin-hoppers to operate without the DA noticing their activity immediately. I think we basically have the same views, just that we believe that
miners causing the oscillation
is actually the DA's fault for creating the incentive in the first place. I mean why expect miners to not be economically rational and profit seeking?
Section 4.2.1
D/st is not an estimate of H for small samples due to increased frequency of small st values making avg(1/st) > 1/avg(st) = 1/T.
This is indeed absolutely true. We explain this issue when we argue for the introduction of the correction from 1 + T/S to e^(T/S). The reason this is not just an approximation (like it usually is for small values of T/S) but actually a correction is exactly what you describe. We are not quite sure how to include the effects of more probable shorter st without getting some very convoluted probabilistic formulas so instead we gave that indirect argument relying on a scenario under which the algorithm must work correctly.
Section 4.6
A 2-hour or 10 second rule are not honored because >50% of miners decide to. It's honored because each honest node will immediately reject a chain that is ahead of time due to world time being an objective and obvious fact that the protocol and network do not, should not, and can't provide.
We were trying to make 2 points here and I think we are mostly in agreement over them. First of all this rule is not a consensus rule as miners catching up with the network cannot impose it at all. Secondly, it is not at all obvious what constitutes a block that lies about its timestamp by placing it in the future. If miners would not globally agree on a certain cutoff time that is approximately the same for all of them (be it 2hrs or 10 mins in the future) then they would not know which blocks to consider as adopted by others as well and start mining on them or ignore them as the block is too much in the future (and maybe other miners think so as well). If there would not be majority consensus over the exact time a block is allowed to be in the future (I don't understand why 2 hours... it seems way too much to me) then miners would essentially not know what blocks their peers consider as valid at this time and might keep mining on the previous chain hoping others do so similarly. Essentially this would lead to many different competing forks that miners switch between as they grow and as blocks with various future timestamps are appended. The reason we make the devil's advocate regarding breaking this 2-hour rule is to argue that using RTT is actually a viable alternative because the rule is not just "some rule" that miners happen to respect, but in fact everything would descend into chaos without it as miners would not be able to agree what amounts to lying and what not. So a majority of nodes do indeed need to agree on how much can a new block's timestamp differ from the current time. Also it is not clear to me immediately that miners have no incentive to break this rule so that's why we make that argument. If you already believe that they will follow real time no matter what then great! :)))
Section 5.5 Indeed, NEFDA-MTP-72 is really quite bad. We did not want to create the impression it's good at all. We were just trying to make the point that if the smoothing factor is not large in comparison to the MTP window size then this leads to similar oscillations problems. We were giving this configuration as a bad example, and for showing how to mitigate its problems by increasing the smoothing factor. We really like your simulations with stolen blocks but the space limitations of an academic paper kind of limited the depth of analysis we could go into. In my opinion simulating miner's behaviour is a whole paper on its own. In fact the model section of our paper could probably be more rigorously extended by proving the properties it has in a short paper as well.
Overall it seems like we are on the same page, which is very much expected as we studied your work a lot and found it really detailed, rigorous and insightful. Finally, I guess... Well Done! to both of us and especially to Jacob Eliosoff and Mark Lundeberg who saw the value in this algorithm long ago. The only question that remains is why is this not already used in many blockchains?
PS. The only "regret" I have about the paper is not placing enough emphasis on the importance of simulating various scenarios when configuring this EMA / ASERT / NEFDA. I think this should be THE algorithm of choice for most blockchains, provided they configure it accordingly after simulating scenarios that are relevant to their use case.
zawy12
where Wolfram Alpha uses log() = ln().
jacob-eliosoff
tromp
This article is about the ASERT difficulty algorithm that was independently discovered by Jacob Eliosoff, Mark Lundeberg, and a group at Imperial College. Jonathan Toomin did a lot of work (here and here) to show it's the best we have, to decide how long the crucial averaging window should be, and to implement it for BCH.
There is a relative ASERT and an absolute ASERT. They are mathematically the same, but relative is expressed more like other difficulty algorithms and has a potentially large error if the "averaging window" is large due to nBit's having up to 2^(-15) imprecision and in approximating e^x in the necessary integer math. Absolute ASERT reduces those errors to effectively zero. EMA aka WTEMA is a very close approximation to relative ASERT.
Relative ASERT:
target[i+1] = target[i] * e^(st/T/N - 1/N)st = solvetime target[i] = target at block height i, 2^256/difficulty T = desired block time N = mean_lifetime = half_life/ln(2) The amount of error in difficulty and therefore solvetime is up to N * 2^(-15) as a fraction of the correct value.Absolute ASERT:
target[i+1] = target[M] * e^((t[i] - t[M])/T/N - (i-M)/N)t = timestamp M = a fixed block height in the past. The above is how Mark Lundeberg's ASERT paper expresses it, but to be perfectly correct, it needs to change target[M] to target[M+1]. The BCH ASERT code expresses this correction as:target[i+1] = target[M] * e^((t[i] - t[M-1])/T/N - (i-M+1)/N)It's really interesting that the absolute form does not even need to depend on past targets or timestamps if you use the genesis time and just set difficulty to 1. This makes the absolute form:
target = e^((t/T-h)/N) where h = current block height t = current time since genesis (miners can just use their own local and with large N and reasonable tight validator limits, lying about current time will not lower difficulty unless miner wants other miners to orphan his block for cheating)
To make the weirdness more clear, if we use an "averaging window" of N=286 (BCH's is 288) and invert the absolute form to get it in terms of difficulty, ASERT is: difficulty = 1.0035^E where E = number of blocks the chain has emitted ahead of time. So if genesis starts at D=1, it increases 0.35% for each block it gets behind.
WTEMA algorithm: Relative ASERT is virtually identical to WTEMA by using the approximation that e^x = 1+x for small x. By expanding the parenthesis in the following integer math can be used, taking care to prevent target overflow or underflow (if negative solvetimes are allowed. ASERT can handle the negatives well).
target[i+1] = target[i] * ( 1+ st/T/N - 1/N)Problems
The first problem is that it gets behind or ahead in the number of blocks it emits over the long term as the hashrate increases or decreases by excess_blocks_emitted = mean_lifetime_in_blocks * ln(current_difficulty/start_difficulty) All algos have this problem. The easiest and safest solution to reduce the error is to have a lower mean_lifetime less than say 144 blocks. This may come at a cost allowing switch mining to gain up up to 0.5% more blocks and makes it easier to conduct the "38% attack" described below. If it's 400, there can be over 1% in excess block rate emission in normal conditions (and up to 38% in attack or attack-like conditions). To make sure too many or two few blocks are emitted, the average solvetime can be checked over a longer averaging window and then adjust the target solve time from the official value by a percent that is in the opposite direction of the long-term error. This turns out to be a PI controller as described in a comment below. The comments describes how to do it safely but the results will be worse if there is a long term oscillation that matches the secondary averaging window. If you choose a window that is too slow it has no effect.
Another problem is that if you use N=1, the median solvetime is ~ln(2)/2 instead of the expected ln(2) of the target time. This indicates it makes the difficulty too easy too often, despite being the only DA that has the perfectly correct average target solve time for N=1. If it's possible to have both, it might be evidence of having the perfect algorithm.
Another problem is that it can emit up to 38% more blocks in a long-term private mining attack than simply getting 100% of the blocks. This is done by setting the first timestamp in the private mine to 2x the mean lifetime window and then all the subsequent timestamps to 0 or 1 second. In SMA the attack gets 50% more blocks. In LWMA I could not find any benefit to timestamp manipulation. If the average of say the past 6 solvetimes is used as the input for the "past solvetime" the attack can get 50% instead of 38%. If the max solvetime allowed is 6x block time, EMA can be reduced from 33% to 28%. It's not 38% because the exploit pushes the boundaries of its e^x approximation.
Another problem is complexity of implementation. EMA is a lot simpler and almost the exact same so I prefer it it LWMA is not used. N can't be small because large N allows the e^x=1+x approximation by making x small, but it can't be large because it has the average solvetime error like relative ASERT. I would use N=100 to 200. Also, it needs code I've mentioned elsewhere to handle out of sequence timestamps correctly.
Another issue (an easily solved "problem") is that the paper below recommends the absolute form of ASERT. This exacerbates the 1st problem if a coin forks to ASERT and uses an initial target that is in the distant past: it immediately releases too many coins at the fork. It will also be a problem if a coin changes the POW and needs to make a large sudden change to the difficulty. Both of these are easily solved by changing the baseline difficulty to the difficulty at the fork, but it's something to be aware of.
Another issue is that relative ASERT and WTEMA accumulate error due to nBits which has 2^-23 to 2^-15 truncation error. From bitcoin wiki on difficulty: "0x008000 is the smallest legal value for the lower 24 bits since targets are always stored with the lowest possible exponent. " This is only 2^(-15) = 0.003% error but it decreases average solvetime in proportion to N. The max decrease (error) in solvetime is approximately 2^(-15) * N = 1.8% for N=600.
The error in the e^x approximation in the code accumulates in the same way in relative ASERT (and WTEMA), requiring higher precision in the integer-based e^x estimator if N is large. The error might be made to offset the average nBits error.
A trivial fix for the last two problems is to change the target solvetime by the same amount to offset them, but an attacker doing a private mine (or miners as a group) could select timestamps that minimize difficulty by about 1/2 the error for which you correct. These last two problems are why absolute ASERT is usually recommended. But N=100 is a good setting for relative ASERT and has only 0.3% error in the nBits portion.
My "Derivations" of ASERT
For Relative ASERT, there seems to be direct & solid argument in claiming it's simply using the exponential distribution: (I've inverted the equation to use difficulty instead of target). D = prev_D exp_dist_observed / exp_dist_expected D = prev_D [ 1/T e^(-st/T) ] / [ 1/T e^(-T/T) ] D = prev_D * e^(-st/T) / e^(-1)
This can vary a lot with st values jumping around, so a smoothing factor is needed. Since a sequence of adjustments to D are multiplying the ratio over and over, an Nth root of this equation can be used. In physics equations the N in e^(-x/N) is called an attenuation depth or mean free path. The best name in this context is "mean lifetime" where time is measured in blocks. An SMA has the same Std Dev of difficulties if its averaging window is 2N.
Including a mean lifetime low-pass filter to what I have above gives relative ASERT:
D = prev_D * e^( (1-st/T) / N).
Absolute ASERT is mathematically the same as relative, but its form allows a different explanation. Apparently, we can claim it's a solution to the differential equation that says we should increase the difficulty per error E (the number of blocks behind schedule) in proportion to the current difficulty. dD(E)/dE = k*D(E) The solution to this is D(E) = D0 e^(k\E) which is absolute ASERT with k=1/N.
More complicated derivation
Only previous block data is needed To estimate current hashrate H we use past difficulties (D's) and solvetimes (st's). If our previous estimate was the best possible given all past D's and st's, then just the previous D and st should be sufficient to modify our previous H estimate. Even if we did not use all past D's and st's and our estimate is far from perfect, a perfect correction should be in the right direction and trend towards being perfect, so over the long term it will actually be perfect, so we only need the "single-block" adjustment to be perfect. Given an H we expected in the prior block, we want to adjust D like this:
D = prev_D * H_actual / H_expected
We can't use solvetime to directly estimate H_actual because a solvetime that is 10% high or low does not indicate H is 10% low or high. This is because solvetimes have a probability distribution around T that will persistently overestimate H because solvetimes are much more frequently < T than > T. We need to map the relationship between st and H to some linear function that properly estimates H with only a single st. The relationship between H and st is given by how we model solvetimes:
CDF = 1 - e^(-st H / D) 1 - CDF = e^(-st H / D) CDF & 1-CDF are random variables from 0 to 1. All equal-sized ranges within 0 to 1 have equal probability. I use the 2nd equation to model solvetimes with 1-CDF = x = rand(0,1). x = e^(-st * H / D)
If avg(st) over many blocks = T, the D was selected correctly for the given H, i.e. H / D = 1/T so that on average we will see: x = e^(- avg(st) /T) = e^(-1). If H is 10% higher than expected, i.e. H_actual = 1.1 * H_expected, then avg(st) will be T/1.1 too low for the D. But we have to use the x equation to estimate avg(st) from a single st.
I'll claim the random variable "x" is the desired linear mapping of the solvetimes that takes the probabilities into account. I can't explain/prove it, but it seemed apparent when I first saw ASERT / NEFDA that this is what it's doing:
D = prev_D x_actual / x_expected D = prev_D e^(-st/T) / e^(-1)
Comments on the Imperial College Paper
Below is a review of a new difficulty algorithm paper, "Unstable Throughput: When the Difficulty Algorithm Breaks" . ( Their tn in this will be the timestamp of prev_D, not current time. )
IMO the paper is good, except for these notes / complaints. I appreciate the author's citing my DA articles and speaking well of this repository of work I've put into it. As with Tom Harding's and Mark Lundeburg's papers, it's good to see better mathematicians carry things through.
For the sake of history in trying to understand why it's taking so long to find the best DA, Jacob Eliosoff is the first one I know of who considered this algorithm, knowing it may have been the best, but opted for the approximation (EMA) due to wanting to avoid the exponential.
Section 3.2 I believe BCH very closely followed the Poisson distribution for a year post-EDA when on-off mining was not a problem due to a higher price & subsidized mining. The depictions of how far away from the ideal Poisson seem a little unfair in the sense that problem happens only when on-off mining is a big problem. It's infinitely better than BTC's. Further, a coin has a much bigger security issue than the DA if on-off mining is a problem because it shows > 50% of miners do not depend exclusively on the coin for income which is the sole basis of BTC's security.
SMA's do not directly cause oscillations as a result of high or low solvetimes falling out the back of the window because new solvetimes coming in the front and the entire averaging should balance out. The SMA is a fair estimate of the current hashrate as it was in the past at 1/2 the size of the averaging window. Accidentally going low with accidental slow solvetimes out the back or long solvetimes in the front can motivate extra miners to come online. So in that sense it can be a "cause", but it doesn't oscillate if H is constant. Once miner motivation causes a significant change for several blocks, the SMA does not dampen the oscillation. It invites a continuance. A close analogy: a steel bar does not ring with oscillations unless you strike it while it's in the air (no dampening from holding it). The strike causes the ringing, not the bar.
Oscillations made worse by delays The median of 3 blocks BCH uses may directly cause a very slight oscillation due to the delay. Delays like using the MTP as the most recent st as the authors suggest (and as is done in Digishield) may directly cause some oscillation. Zcash has always had a mild oscillation from using MTP. Monero's algorithm caused huge problems in alt coins that copied it because of the various ways it causes a delay (does not use the most recent solvetimes). All alts I'm aware of that used it "blew up" and got stuck until they switched algorithms.
Section 4.2.1 D/st is not an estimate of H for small samples due to increased frequency of small st values making avg(1/st) > 1/avg(st) = 1/T. The best H estimator I have is sum(D)/sum(st) (N-1)/N. I do not know how to get hashrate or the expected number of hashes from 1 solvetime unless we also have an a priori expected value of the solvetime (i.e. H), in which case it appears the "observed" H for 1 block is D/T e^(-st/T) where D/T is the expected H. I wonder if there is an e^x function that can do away with the (N-1)/N and always correctly estimate HR. BTW If solvetimes are prevented from being < 1, the estimate of H for 1 block that gives the right average is: avg(1/st) = D/st/7. The avg H estimate for 1 block is not an integral that converges if st can be 0.
Section 4.6 I've never seen any argument against having a future time limit of say 10 seconds. Based on distributive consensus theory, it only needs to be > 2x propagation delays and should be << block solve time. Block solve time is purposefully chosen to be >> propagation delay. There is no BFT without a pre-consensus on time and its limits. A 2-hour or 10 second rule are not honored because >50% of miners decide to. It's honored because each honest node will immediately reject a chain that is ahead of time due to world time being an objective and obvious fact that the protocol and network do not, should not, and can't provide. Peer time is not the basis because it's rejected if it is 70 minutes off from local time. It should not have been used.
Section 5.5 NEFDA-MTP-72 (which is has the same smoothness as BCH under constant H) is as bad as BCH's DA in terms of delays & "stolen" blocks when modeling on-off mining problems. It invites bad oscillations. The oscillations are faster but more frequent. My method of testing it is a step function that goes on or off if D goes too low or too high, respectively. Since a 10% change in D can cause a 10,000% change in HR, it's pretty accurate. I've used this a lot to simulate live attacks very accurately.