Best Difficulty Algorithm, Timestamp Rules, Selfish Mining, Selecting N

[zawy12]

This is a summary of issues that keep coming up.

WTEMA is the only difficulty algorithm people should use

Every PoW needs to just use WTEMA. It's simple and every good algorithm gives almost identical results. Relative ASERT is really an EMA algorithm. "EMA" means
target = prior_target * e^(error/N)
where N = smoothing_constant aka filter, and for relative ASERT, error = t/T-1.
t = prior block solvetime
T = desired average block time.

WTEMA is an "infinite impulse response filters of 1st order". It's ideal in many situations. It very closely approximates relative ASERT by replacing e^x with 1+x which is very accurate for small x. Absolute ASERT is slightly better than relative ASERT because it prevents error caused by e^x function being imperfectly estimated and nBits imprecision. The error is linearly worse with larger N.

This means WTEMA is:
target = prior_target * ( 1 + t/T/N - 1/N )
This can be expanded out to allow integer math (no decimals) to be accurate because targets are so large, but make sure an overflow in target can't occur.

To code ASERT, you need to implement a b-spline approximation of e^x with integer math because compilers and hardware may have a small difference in the e^x calculation that can cause forks due to validators not seeing exactly the same thing. But this adds a lot of code so I prefer WTEMA because it's so much simpler with only a slightly larger error than absolute ASERT. Error is mostly consistent and predictable with modelling and can be reduced by changing the target block time such as using T=594 instead of 600 (bitcoin) if the error in modelling makes T 1% higher (e.g. if average solvetime = 606 in modelling).

Time and Timestamp rules

To summarize this section, to prevent all the attacks related to difficulty algorithms, time, and timestamps, Lamport's ancient distributed consensus requirements on time and timestamps should be applied to Nakamoto consensus. Nakamoto consensus is a distributed consensus mechanism and Lamport's derivations were independent of the algorithm. See "Timestamp Attacks" for a history of all the difficulty algorithm, time, and timestamp attacks on Nakamoto consensus due to Satoshi et al not following Lamport's requirements. These requirements are:

1. Peer time should not be used, only independent local time.
2. Monotonic timestamps should always be used, not the median of the past 11 timestamps (MTP).
3. Future Time Limit (FTL) should be reduced to a fraction of block time
4. Enforcement precision on timestamps must be slower than the propagation delay
5. Timespan limits and other methods of changing what a correct difficulty algorithm calculates should not be used.

Peer time should not be used. Independent local times being correct without asking anyone is the only correct way to validate Nakamoto consensus because the clocks in distributed consensus mechanisms must be more secure than the consensus mechanism. The proofs go back to and before the original Byzantine paper, when distributed consensus was called interactive consistency. Monotonic timestamps should always be used. MTP is an ugly and harmful fix to not following sequential timestamps in every block and should be replaced in all code with monotonicity. The monotonicity rule for miners should be

A newly-seen ("tip") block's timestamp is valid if 1) the timestamp is less than my local time plus the future time limit (FTL) and 2) it's at least 1 second after its parent block's timestamp. Otherwise reject the block permanently unless in 1) there is reason to believe local time had an error. When mining, the timestamp in the header is local time or 1 second plus parent block, whichever is greater, but do not release it unless and until that timestamp is less then my local time plus the FTL.

The FTL should be coded as a function of N blocks and T block time where N*T is the "difficulty averaging window" in seconds. FTL should be less than say 5% of N*T to have less than 5% artificial reduction in difficulty if a timestamp is set forward in time to the limit of the FTL. This FTL rule is actually way too lenient as described in the selfish mining section below. If there's a peer time due to devs not understanding the importance of local time in Nakamoto consensus, the allowed peer time error should be coded as FTL/2. BTC's "revert to local time if median of peer time is more than 70 minutes different from local time" approximately does this (its FTL is 120 minutes). BTC codes the 70 minutes as a constant instead of making it a function of FTL like FTL/2 which will allow a Sybil or eclipse attack if FTL is reduced below 70 minutes without removing peer time or reducing the time in the revert rule.

There should not be any timespan limits. When combined with non-monotonic timestamps, it allows an unlimited number of blocks to be mined in 2.8x the difficulty averaging window if the attacker has more than 50% of hashrate. Almost all coins have this exploit, and it works to a lesser extent even if there's monotonicity. I discovered this attack and within a few months of describing it, 5 coins had to fork to recover thousands of blocks. It's the oldest open issue on Litecoin.

Not following these rules has resulted in attacks on several coins where miners had alternate sources of mining income, which is itself a violation of Nakamoto security. BTC is the most secure in having the "non-repurpose-ability" security requirement and as a result it has had a lot of protection despite not correctly following distributed consensus requirements (in addition to having the worst difficulty algorithm). Most of the successful attacks on alts related to difficulty algorithms originate from BTC code and ideas in how it handles timestamps in ways that violate Lamport's 1978 clock's paper in the context of Nakamoto consensus.

#

.

Selfish Mining Prevention

TL;DR: To stop selfish mining, softly-require timestamps to be accurate. This works because an attacker has to assign timestamps before he knows when he'll need to release it. From a consensus theory point of view, it works because it increases node synchronization which is one of 3 requirement that are necessary to get consensus with only 51%.

Selfish mining (and all attacks on mathematically-correct difficulty algorithms) can be prevented by enforcing Leslie Lamport's 1978 rules for timestamps. The rules were proven to be required for all concepts of time-based interactive consensus ("distributed consensus" was not a term invented at the time and falls under this more general category). Nakamoto consensus is a concept, implemented by an algorithm, that seeks distributed consensus so it must follow the proven rules. By not strictly following the rules, selfish mining is possible.

To get 51% security the known minimum requirements for all distributed consensus mechanisms are:

1. Digital signatures on messages (which are provided to the blocks in the form of the costliness of winning hashes), independent clocks (peer time should be removed)
2. monotonic timestamps
3. timestamps that are much more accurate than the length of a consensus round (block time)
4. Timestamp enforcement precision must be slower than the "typically maximum, normal and anticipated" propagation delay

The timestamp rules are to keep nodes in sync and come from 1978 proofs. The degree to which nodes aren't synced is the degree to which security with 51% be achieved. Bitcoin isn't enforcing decent synchronization because the MTP of the past 11 blocks and 7200 seconds for the future time limit (FTL) are way too lenient compared to what it could safely enforce.

The blockquote below is a specific rule to softly-enforce better synchronization. Honest miners can immediately agree to implement this rule without a code update, and abandon it if it doesn't work. The honest hashrate enforcing this needs to be at least as large as the attackers' hashrate. Non-enforcers aren't harmed if they have accurate clocks and use accurate timestamps. By "softly-enforce" I mean PoW overrides the rule within 1 block time. PoW must be the final determination because nodes can't necessarily tell the difference between an attack and a genuine disruption to the mining network's connectivity (an "honest" partition).

Rule: Do not accept a new block, including a tip with such a block, for ln(2) = 0.693 * blocktime if its timestamp is more than +10 seconds from local time into the future, or more than -15 seconds into the past at the moment the node first sees the blocks. Continue to reject a block after the timeout period if it's timestamp is still >10 s in the future. Honest nodes' clocks must have less than +/- 5 seconds of error to not be rejected or work on the wrong chain. A mining node who's been disconnected and rejoining the network doesn't enforce the past time limit on new blocks until he's synced back up with the longest chain he can find.

If rejoining and ignoring the rule causes a node to join the attacker's chain, it's not a problem because this rule means he'll switch to the honest as soon as the honest chain has more work because all new blocks in the honest chain after he joined will have good timestamps.

The constants are chosen from estimates and theory, not arbitrarily by me. They assume nodes can keep time only to within 5 seconds and that typical, maximum propagations delays are up to 5 seconds. These constants can be relaxed by a specific node if it can't achieve them. It only stops working if the attacker plus 1/2 of the nodes ignoring the new requirements (aka "agnostics") exceeds 50%, and at that point it's disadvantageous to a node to follow it. Notice that no data on the block chain is affected. The ln(2) * blocktime is the median time to solve a block. It's the minimum amount needed to remove the luck of a <50% attack.

The extra 5 s for "in the past" verses "in the future" is to allow for typically-maximum propagation delays. A miner who is sometimes more than 5 seconds away from the network can relax the rule for himself to not reject valid blocks, and add a few seconds to his clock so that his blocks aren't rejected. A node doesn't follow the rule if he thinks his clock has excessive error.

This scheme increases the chances of a chain split if there are network delays, but the timeout rule allows PoW to eventually determine the correct tip. It should delay normal reparation only for the length of the timeout period. If nodes believe there is an honest network partition and not an attacker, they can communicate with each other to agree to suspend the "past time limit" and only reject blocks with "future" timestamps. They need to all agree at the same time to not orphan each other.

The only way I know of for this protocol to "break" is if clocks can't keep <5 s accuracy or if propagation delays are persistently above 5 s. In other words, these are the 2 assumptions that need to be correct. Bitcoin could still stop most selfish mining profits if the clock error allowed is +/- 30 seconds instead of +/- 10.

An attacker can use the rule to split the network in half (as he currently can on all chains with a future time limit) by releasing a block exactly on the +10 or -15 s limits, and if he does it perfectly, he needs only >25% hashrate to have good luck in getting the next block on one of the 2 partitions, but he's still competing with the other partition, so there's no net benefit. But this is the reason timeout period needs to be kept short.

As always, ideally the monotonicity rule described should also be enforced.

Value of N, removing parameters from code

Myself and others have spent a lot of time trying to decide on the value of N, the number of blocks to use in "difficulty averaging". It's not really crucial except you want a larger value than I have used in the past but not so large that it's not responding to price changes in the coin, and definitely not so small that the difficulty changes a lot due to the random nature of the solvetimes. The StdDev of difficulty for ASERT & WTEMA (when hashrate is constant) is about 1/SQRT(2*N) so that if N=50 blocks, you'll have 10% StdDev in difficulty. My current thinking is to set it equal to 1 or 2 day's worth of blocks. This sounds flippant but it's serious and the result of modelling and experience. This makes N a function of T. In everything related to blockchains that seek to be decentralized and objective, it's really good to prevent developers from needing to choose any constants. The science and math of consensus security should choose everything. Even T could be a function of something but may still require some ultimate constant. For example, you may want to change T in a DAG blockchain if you want the DAG to maintain a specific width (the subsequent constant) or have a consistent confirmation time as propagation delays change.

Real Time Targeting

One of the complaints of real-time targeting (RTT) has been that it allows the miner who is assigning the timestamp to reduce his own difficulty. Notice that the selfish mining fix also greatly reduces this effect, so the barrier to entry to RTT should be lower.

[A60AB5450353F40E]

Re. above Selfish Mining Prevention

I wonder if it would go well with a deterministic tie-breaker: https://gitlab.com/0353F40E/selfish-mining-fix

When a miner receives two valid blocks, A and B, at the same height, they:

1. Order the blocks canonically (e.g., lexicographically by hash: min(A,B) || max(A,B)).
2. Compute H = SHA256(min(A,B) || max(A,B)).
3. If H < (2^256-1)/2, select A; otherwise, select B.
   Miners then mine on the selected block and propagate both, as in [1].
   If only one block is seen (e.g., A), they mine on it until a competitor arrives, switching if the tiebreaker dictates.
   For longer equal-work chains (e.g., N+A+B vs. N+C+D), compute H(B || D) (latest tips); if chainwork differs, then simply pick the higher chainwork tip.
   For three or more equal-work blocks at one height (e.g., A, B, C), extend to H(A || B || C) and split the 2^256 range evenly (e.g., thirds).

[zawy12]

That's an interesting fix to the problem of a "lowest hash = winner" rule motivating a miner to begin the attack if he accidentally gets a low hash. The tie breaker alone isn't good for selfish mining because it violates the idea that the largest partition of the network should win. If two blocks are seen before the next block then one will be randomly chosen. That subverts the PoW measurement. The largest partition in a split network has the largest hashrate and will accumulate the largest PoW. My method is enforcing better synchronization to block cheaters without harming the PoW determination. However, since my time-limits are fairly loose, it can be used if two blocks come within an allowable time period. My method says a block's timestamp can be 2+6 seconds before local time when it arrives or 6 seconds in the future (which I just notice I got FTL & PTL backwards in my article above). If a node sees a 2nd block within 4 seconds, he would apply the tie-breaker. 4 seconds because the 2nd block miner's node could have been 2-seconds of propagation delay away from the 1st block miner and therefore he was not mining on it for up to 2 seconds, and it may have taken his block 2 more seconds to arrive to me. In other words, the tie breaker can be incorporated to assist in the old orphan problem, with only a slight violation of the PoW metric.

[A60AB5450353F40E]

That subverts the PoW measurement.

Sure, but with just 1 sample it's such a fuzzy measurement anyway, and I thought about the problem of someone finding B 9 minutes after A and kicking A out just because of H(A||B). Why would B mine for 9 minutes, though? B would take on a huge risk there because his block N is sure to lose to a N+1 chain which A could find at any moment during B's search for alternative N. Also, B's expected revenue is only 50% because he can't know whether his block will win, he'd have to put in 2x work to be sure to flip A. So, I think incentives here work against any intentional delay.

Anyway, I came to the same conclusion as you: we could just limit the time while at it, so consider the combination where there's only a 4 seconds replacement window during which the tie-breaker would do the tie-breaking.

In other words, the tie breaker can be incorporated to assist in the old orphan problem, with only a slight violation of the PoW metric.

Yes! This way orphan losses due to few seconds of lag would be socialized rather than laggy miner always taking a bigger hit, so impact of orphans would hit everyone equally (on average) and then it wouldn't be a centralization factor.
Effect of orphans would then be just as if price dropped for the % (a revenue drop affecting everyone equally) and the network would get less hashes because difficulty would drop to a slightly lower equilibrium.

[zawy12]

Assume the network is partitioned into A and B. If a block comes faster from A, it is more likely to have higher hashrate, so the PoW mechanism works even down to the sub-blocktime level if everyone keeps an accurate local time and enforces my FTL & PTL. Below that level PoW can't work, so the tie breaker can be used. Counting blocks (adding up difficulty) is PoW, but that's a PoW per "time since genesis" or "time since prior block". So PoW is actually proof of highest hashrate since genesis or prior block. 1 block in 10 seconds is more "PoW" than 1 block in 20 seconds.