Improve BlockWindow performance
Closed this issue · 3 comments
BlockWindow plays a role in calculating pastMedianTime and DAA.
The current algorithm is the most computationally intensive part of adding a block to the DAG beside transaction signature validation.
To resolve this issue, please design and implement a solution that will either improve BlockWindow or remove the dependency on it altogether.
The current Kaspa DAA is
T = targetTimePerBlock
N = windowSize
target = avgTarget * ((MaxTimestamp - MinTimestamp) / (T * N))
The options to make it faster in computation are to use WTEMA or a variation of Digishield.
WTEMA is "relative" ASERT's very close cousin, which only requires the parents and grandparents. It is very close to "relative" ASERT by using the e^x =~ 1+x approximation for small x. "Relative" means using the grandparent instead of a reference block in the "absolute" ASERT at the bottom of this comment. Here's WTEMA for a normal POW chain.
ST = solvetime between parent and grandparent
next_target = prior_target * (1+ ST/T/N - 1/N)
To see how it works, if ST = T there is no adjustment and then notice the outcomes if ST>T or < T. ETH uses a variation of this. You can expand the above equation out to use integer math. A high N =1320 will accumulate error if nBits is not higher precision than in BTC. BTC's nBits lowest precision range is 2^(-15) and the error is then N/2 * 2*(-15) = 2% in the solvetime for N=1320.
N=1320 for ASERT and WTEMA have the same stability as N=2640 in Kaspa's current SMA and they are faster to respond to hashrate changes.
If the ST in WTEMA is too small to have good accuracy, then WTEMA can be modified in a way that makes it like Digishield. This also happens to be a way to modify the current algo that requires a lot less computation and greatly reduces possibility of oscillations. If you have to go N blocks in the past for WTEMA to get a large enough ST or want to make the current SMA 10x more efficient by going from N=2640 to N=2640/10 = 264, then the equation would be (leaving out PPD and PD adjustments):
N = 264
T = blocktime
timespan = Max - Min timestamps which are N+1 blocks apart.
M = 10 = "filter", "buffer", "tempering", or "dilution" factor. Notice M=1 makes it an SMA.
target = sumNAncestorTargets/N * (1 + timespan/N/T/M - 1/M)
Again, multiply it out to use integer math. This has same stability as Kaspa's current SMA. But M=10 is a big change from the well-tested Digishield which uses M=4. To be safe, I would not go above M=6 without testing.
WTEMA and Kaspa above are not targeting solvetimes after a miner 1st sees a block, but the propagation delay plus the solve time. But that's not correct either because propagation delay has a non-linear effect on DAG width which depends on how close it is to the miner's solvetime, and DAG width has a linear effect on the difficulty algorithm in the opposite direction as the propagation delay. Propagation delay alone decreases difficulty because of the longer apparent solvetime, but as it gets closer to the solvetime (a DAG is needed precisely because propagations delays are "close" to solvetimes), the extra DAG width makes the averaging window in Kaspa go back less in time (smaller Max-Min timespan) which increases difficulty (decreases target) which pulls propagation delays back away from from the total solvetime, decreasing DAG width. It's a negative feedback that seems to work out OK towards a balance, except you're controlling a combination of DAG width (propagation delay) and the apparent solvetime (aka generation time) instead of having good control of either. Does it risk oscillations?
There are other ways to do a DAA for a DAG but they require measuring DAG width. You could target solve time after a block's arrival, the ratio of propagation time to solvetime, or target a DAG width.
If you want to target solve time after a miner sees a block, the average parents per block (PPB) in the window might be a good-enough estimate of siblings per generation which you can use it to adjust the equation. Another way to get PPB might be to count generations by counting the number of median blue parent to median blue parents in the window so that PPB = N/count. Here's what I have to adjust for this and propagation delays (PD). PD can be estimated from PPB (see equation in GhostDAG paper) by using a lookup table. Notice that PPB (& therefore PD) can be artificially lowered by a selfish miner (but not raised without a commensurate higher hashrate) which only makes the difficulty harder. The only potential drawback to this is that a block-withholding attacker can make the public difficulty go high to discourage public hashrate before working on his private chain.
// an attempt to target N/PPB generations, each with solvetime T.
target = avgTarget * ((Max - Min - PD * N/PPB) / (T * N/PPB))
If the DAG width is being controlled and set to a constant, then you can use "median" timestamp, target, and height of the block's parents as the input to BCH's new ASERT. It's the best DAA. It only requires looking at the parents. It looks like it could cause serious problems if the DAG width is not set to a constant. In ASERT's case, there is a reference block at some point in the past that the DAA uses as "initialization" of target and height. It knows how to set the difficulty by counting blocks after that reference height and knowing (for a given DAG width) how many blocks there should have been since then.
"Absolute" ASERT in normal POW is
T = block time
ts = timespan between parent and reference block
dH = difference between parent and reference blocks' heights
=
next_target = reference_target * e^( ts/dH/T/N-1/N)
How about using the timestamp of the earliest chain block in the window? That is,
T = targetTimePerBlock
N = windowSize
B = minimal chain block in the window
target = avgTarget * ((current.Timestamp - B.Timestamp) / (T * N))
(I'm not sure what `avgTarget' stands for here, I'm following the description by @zawy12 above)
This seems close enough to the current design (security wise), and can significantly simplify the implementation and remove the overhead on performance, since you only need to keep track of each block's DAA predecessor (can be done similarly to / inside the code that tracks a block's finality point)
Fixed by #1948