KIP: 4
Layer: Consensus (hard fork), DAA
Title: Sparse Difficulty Windows
Author: Shai Wyborski <[email protected]>
Michael Sutton <[email protected]>
Georges Künzli <[email protected]>
Status: implemented in testnet ([PR](https://github.com/kaspanet/rusty-kaspa/pull/186))
The difficulty adjustment algorithm requires maintaining, for each block, a list of the N blocks in its past with the highest accumulated weight. When validating a block this list needs to be traversed to compute the various quantities required for computing the difficulty target. Since the length of the difficulty window corresponds to real-time considerations, the size of desired difficulty window is measured in seconds, not blocks. This means that if we increase the block rate by a factor of R, we increase the complexity of the difficulty adjustment by R^2 (the first factor is due to the fact that validating each block requires R times more steps, and the second factor is since blocks emerge R times faster).
This is partially mitigated by the incremental nature of the difficulty window. Like the blue set, each block inherits its selected parent's difficulty window and then fixes it according to the blocks in its merge set. This converts some of the CPU overhead to RAM overhead, which would also increase by a factor of R.
To reduce the overhead, the current Golang implementation uses window sizes that are not optimal (263 blocks for timestamp flexibility, 2641 blocks for DAA window). As a result, miners whose clock drifts into the future more than two minutes than the majority of the network have their block delayed decreasing the probability they will be blue. Hence, a secondary motivation for this proposal is to increase the timestamp flexibility (which requires increasing the DAA window accordingly) efficiently.
For the sake of discussion, we will call a window long/short to indicate the length of time it represents, and large/small to indicate the number of blocks it contains. In the current state, the size of a window is its length times the BPS. Thus, increasing the BPS by a factor of R while retaining window lengths implies increasing the sizes of all windows by a factor of R.
Currently, a window of a block B of length L is the set of L*BPS blocks in the past of B with the highest blue work.
Difficulty windows are windows used for determining how to readjust the difficulty target. The difficulty adjustment algorithm actually uses two windows:
- the timestamp flexibility window, used to bound the allowed deviation from the expected timestamp.
- the difficulty window, used to approximate the deviation of block creation time from the expected time.
Timestamp flexibility length corresponds to natural deviations and drifts across different clocks of the network. Short timestamp flexibility window means the network is less tolerable towards clock drifts and more punishing towards poorly connected miners. However, long timestamp flexibility allows an adversarial miner more leeway for timestamp manipulations (e.g. for the purpose of difficulty attacks). This is countered by making the difficulty window much longer.
In the current implementations, efficiency considerations already force us to choose a shorter-than-desired timestamp flexibility length, namely 263 seconds. The corresponding difficulty window length is 2641 seconds. These lengths are already not optimal in two ways: the tolerated drift is too short, and the maximum possible difficulty attack via timestamp manipulation is higher than desired. However, efficiency concerns prohibit meaningfully extending the windows. (It should be noted that an optimal timestamp manipulation attack would require a lot of resources and luck to apply consistently, while only affecting the network mildly.)
Increasing the block rates while retaining window lengths will force us to increase window sizes accordingly, which is prohibitive in terms of complexity. Making the windows shorter is prohibitive in terms of security. Hence, finding a better way to represent a window is required.
The idea of sparse window is simple: instead of using all blocks in the past, choose an appropriate subset of the past. If the subset is small enough, yet well distributed across the non-sparse window, it could be used as a replacement. The subset should be:
- Deterministic: it could be calculated from the DAG and would turn out the same for all nodes
- Uniformly distributed: it should be well spread across the non-sparse window
- Incremental: it should not depend on the point of view of a particular block, so it could be inherited by future blocks
- Secure: a miner should not be able to cheaply affect the probability of their block to be sampled, the cost should be comparable to discarding a valid block
In the previous proposal, we used the hash of the window block as a method to sample blocks. However, this approach turned out to be gameable. In the current proposal we consider a much simpler approach, defined by the following parameters:
length: the length of the window in secondssize: the size of the window in blocks
The length and size measurements are natural in the sense that they describe the real-time period represented by the window, and the number of samples we desire, regardless of BPS. E.g. we could specify that "for computing difficulty we should sample 1000 blocks from the last 500 minutes".
Since security only relies on the lenghts of the flexibility and difficulty windows, this allows us to modify the sizes without compromising security. In particular, it is reasonable to use a lower sample rate for the difficulty compared to the flexibility, as it is measured over a much larger period of time.
From these we can define a new quantity sparsity = length*BPS/size. Intuitively, we use "one out of every sparsity blocks". Note that sparsity is the only quantity affected by the BPS, and in particular setting sparsity=1 recovers the current, non-sparse windows.
We also assume that for any block B there is some determined order to traverse the merge set of B, we will shortly propose an explicit ordering we find suitable. Once such an ordering is available, we intuitively define the window by starting with the window of B.selected_parent and then traversing B.merge_set, each time adding one block and the skipping sparsity-1 blocks, while also removing the blocks with lowest blue_work from the window to conserve its size.
The resulting subset is equally dense in all contiguous stretches of the non-sparse window (relative to blue_work ordering) whose size is larger than a typical anticone, making it suitable for our purposes.
We define for any block B a field called B.window(size,sparsity) which contains a bounded min_heap prioritized by blue_work and bounded by size. This means that if there are size elements in B.window then whenever an element is pushed into B.window(size,sparsity), B.window(size,sparsity).extract_min() is performed automatically, consevring the heap size.
Note that the field B.window(size,sparsity) is transient: it is not stored with the block, but it is cached. In case the selected parent of B is not cached, this field would be computed on the fly.
Remark: Currently, if the selected parent of B is not cached, the entire window is computed. A possible optimization would be to check whether a shallow selected ancestor is cached and proceed the computation from there. However, in practice the selected parent is almost always cached, so this optimization is probably not worth the effort.
The procedure for computing B.window(size,sparsity) is as follows:
function complete_window(m,B):
let i = 0
for C in B.merge_set:
if C.blue_score < B.blue_score - length*BPS:
mark C as non-DAA
continue
i++
if i + B.selected_parent.DAA_score % sparsity == 0:
m.push(C)
if B.selected_parent is cached:
B.window(size,sparsity) = complete_window(B,B.selected_parent.window(size,sparsity).copy())
else:
B.window(size,sparsity) = new bounded_min_heap(bound = size)
C = B
while B.window(size,sparsity).size() < size OR C.blue_work >= B.window(size,sparsity).min():
B.window(size,sparsity) = complete_window(C,B.window(size,sparsity))
C = C.selected_parent
Remarks:
- The window of the cached selected parent is copied and not modified in place, as it might be needed for computing the windows of several blocks
- The computation process in the non-cached case goes back in the chain, but it produces the same result as incrementally updating a cached window due to the strong monotonicity of DAA_score.
It remains to specify the ordering in which B.merge_set is traversed, we propose using blue_work in descending order. That is, starting with the highest blue_work. This way the ordering of the merge set depends on the future, making it harder to game.
A block B would not reward any block C in its merge set which is marked as non-DAA. Consequentially, the sets of blocks that are rewarded is the set of all blocks that are not marked non-DAA by any chain block. This exclusion of blocks that were created "too late" to be rewarded without messing the schedule is very similar to the current non-rewarding policy, though there are edge cases of blocks that will be rewarded according to the proposed policy albeit not rewarded according to the current policy. Such blocks can only be produced in scenarios that occur very rarely naturally, and producing such scenarios deliberately requires a large fraction of the global hashrate. Even if an adversary put the work to produce such a scenario artifically, thus creating excess emission, they can not guarantee that this excesss emission would be paid to them. Such an attack is highly impractical, and requires resources that could be used much more productively to disrupt the network. Hence, we disregard this nuance for the sake of simplicity.
We propose the following:
- Timesatmp flexibility:
length=1210(~20 minutes),size=121. - Difficulty:
length=30000(500 minutes),size=1000.
Breaks consensus rules, requires hardfork