New difficulty algorithm

[zawy12]

Here's my new difficulty algorithm that 6 Monero clones are using. It is much better than karbowanec's (which is what I recommended back in November 2016). Masari has put in a pull request to Monero for it which they are considering.

The following is about how to handle bad timestamps that miners can use to lower the difficulty. Because of the following, method 3 in the algorithm is the best way to handle bad timestamps.

I've spent a lot of time finding the best way to handle bad timestamps. The best method I've found so far is to allow negative solvetimes (out of sequence timestamps) and to make
CRYPTONOTE_BLOCK_FUTURE_TIME_LIMIT = 7*T
where T=target solvetime. The default for this variable is 7200 which is bitcoin's default which is way too large when T=120 instead of T=600. Such a large future limit allows an exploit in all difficulty algorithms that can lower difficulty to (N-7200/T)/N of the initial difficulty by a large > 50% miner. For N<61, he can drive difficulty to zero. He simply assigns a large forward timestamp. But the number of blocks he can get at low difficulty is limited by how low he drives difficulty. To maximize the number of blocks he can get without difficulty rising, he can come in and assign
timestamp = (HR+P)/P*T + previous_timestamp
where P is his hashrate multiple of the network's hashrate HR before he came online. For example, if he has 2x network hashrate, he can assign 1.333xT plus previous timestamp for all his timestamps. This prevents difficulty from rising, keeping it the same value, maximizing the number of blocks he can get. With CRYPTONOTE_BLOCK_FUTURE_TIME_LIMIT=7200 and T=120 seconds, this would allow him to get 7200/120 = 60 blocks without the difficulty rising. He can't continue because he will have reached the future time limit that the nodes enforce. He then leaves and difficulty starts rising if negative solvetimes are allowed in the difficulty calculation. If negative solvetimes are not allowed (method 1 timestamp handling in my LWMA), he gets 60 blocks all the same over the course of 90 blocks that he and the rest of the network obtained. The average real solvetime for the 90 would be 1/3 of T (if he has 2x the network hashrate) without the difficulty rising. And when he leaves, difficulty will stay the same. So the algorithm will have issued blocks too quickly without penalizing other miners (except for coin inflation which also penalizes hodlers).

[aivve]

Thank you, this one is on our radar as we have updating current algo on roadmap. I was curious about Simplest difficulty algorithm too.

[zawy12]

There's no problem with the Simple DA. The LWMA is only marginally better. It's a little slow if T=600, but should work good with your T=120. Just now I lowered the N=35 to N=30.

You should remove the timestamp limits if you set
CRYPTONOTE_BLOCK_FUTURE_TIME_LIMIT = 7*T

[aivve]

We have T = 240. I will try Simple DA again, so far I got it lowering difficulty to zero. Must be some error in my implementation - I was trying Digishield version though.

[zawy12]

I often make mistakes in converting my spreadsheet algorithms to the pseudocode, but I can't see an error in this case.

[aivve]

No, as I said, I suspect it is I made mistake :)

[zawy12]

With T=240, use N=7 and adjust=0.983 for that one. This will make it a little faster. In terms of an SMA, this is like N=50 but better. LWMA is only a little bit better.

[aivve]

We need to investigate how the network will behave with CRYPTONOTE_BLOCK_FUTURE_TIME_LIMIT = 7*T on advancing to daylight saving time. It depends mainly on correct time settings of pools servers so probably it's will be OK because pool servers will most likely have correct clock settings.

[zawy12]

I'm having a discussion with Monero on this future timestamp limit change.

[aivve]

I don't think Monero gonna change this, it is not affecting them.
I think I know what mistake I made in Simple DA - I was using target instead of / as difficulty 😅

[zawy12]

5 Monero clones are having really good success with the new algorithm. Your difficulty will be a lot more stable with fewer delays than the old one. But if you use EMA instead of LWMA, it will be nearly as good (I'll probably be the only one who notices a difference) and it will be good to have data for EMA. EMA is more mathematically pure.

[aivve]

I made implementation of LWMA in the meanwhile and EMA (Simple DA).

It looks like both can not work from scratch (for a new coin), i. e. it needs to be kickstarted by default cryptonote algo then switched to. If difficulty somehow is dropped to 1 it can not climb up and will fall into loop of difficulty 1. 😕

[zawy12]

Thanks for pointing this out. I'll make a note in the algo. To make the code simple, I would give LWMA an arbitrarily low difficulty constant if the height is less than N. Just "give" the first N blocks away. Similarly for EMA, it just needs an initial value. They correct fast. A lot faster than Digishield that takes 500 blocks.

[aivve]

I am not sure I made EMA correcly because the formula is for target and I changed it for difficulty

[zawy12]

If you invert prev_target and next_target to be difficulties, it should work. But check to make sure there is not a problem when ST = or < 0.

[zawy12]

It looks correct to me.

[aivve]

Looks like previous double_t for k part of the formula is better

[zawy12]

Oh, yeah, k needs to be floating, not integer. There should be a way to make everything integers if yuo wanted. All my spreadsheet testing is with the difficulty form, so you have what I tested the most.

[aivve]

Looks like double_t k = N + ST / T / adjust - 1; instead of int64_t k = static_cast<int64_t>(N + ST / T / adjust - 1); is more precise

[zawy12]

See LWMA for a recent change. I've re-written the pseudocode to be more easy to understand, and made the difficulty a harmonic mean instead of arithmetic mean to get more accurate avg solvetime.

[aivve]

I made version with your recent changes, still testing it

[zawy12]

Thanks. I'm glad to see someone using my new terminology. I'm going to highlight your code as the "reference implementation".

[zawy12]

No, actually, that 7200 second limit on the future time will still allow an attack. I would go ahead with LWMA

[aivve]

Yes, that's possible. LWMA is ready, just need to make sure it's safe to cast from double_t to uint64_t. The difficulty in float should not get that hight to overflow.

[zawy12]

The attacker had 1/3 of the network hash power and simply assigned the max forward time which is 2 hours into the future. The first bad timestamp was block 213936 and the last was 214563. From 8:07 am to 8:42. 627 blocks released in 35 minutes.

[helder-garcia]

We suffered the same attack yesterday. After each 2 blocks mined one block 2 hours on the future.

[aivve]

This is my final version. I will be thankful for your thoughts.

[aivve]

This branch is going to protect from this exploit. Along with this future time limit. I missed the chance to test it on summer time transition.

[helder-garcia]

Thanks for sharing. I have my changes (based on yours) ready to go. I'm just testing the upgrade voting in testnet first.

[zawy12]

Excellent. Everything exactly like I wanted. Two minor points:

if (timestamps.size() > N + 1) {
would be OK without the +1.

And
if (n <= 1)
Seems to need to be
if (n <= 2)

[helder-garcia]

In if (timestamps.size() > N) { should we change the resize to N?

[zawy12]

No, no, the resize is correct because the first pass of the loop needs to look at timestamp[0] and the last pass will use timestamp[N]. The loop runs N times, but needs N+1 data points.

To be clear, timestamp[N] is the most recently solved block?

[helder-garcia]

Yes, I understand. But wouldn't be pointless to call resize to N+1 when timestamps.size() is equal to N+1?
I mean, the first case of (timestamps.size() > N) is when timestamps.size() is N+1. In this specific case we don't need to call resize. So, it would make more sense to keep the test as (timestamps.size() > N + 1)

[zawy12]

The timestamp size may be >> N and we need the last element to be indexed by N and we need first index to be 0.
Is the difference between these two correct?

const size_t N = CryptoNote::parameters::DIFFICULTY_WINDOW_V3 - 1;
...
assert(n <= CryptoNote::parameters::DIFFICULTY_WINDOW_V3);

[zawy12]

Doesn't assert throw an error if true? This looks like it will throw an error at the beginning of a coin instead of returning 1 for the difficulty.
assert(n <= CryptoNote::parameters::DIFFICULTY_WINDOW_V3);

I assume all the following is to just return 1 if it's at the beginning of a coin.

		size_t n = timestamps.size();
		assert(n == cumulativeDifficulties.size());
		assert(n <= CryptoNote::parameters::DIFFICULTY_WINDOW_V3);
		if (n <= 1)
			return 1;

[aivve]

I need N to correspond to the number of timespans and difficulties, i.e. N should be 60 and we should get 60 elements in the loop.

DIFFICULTY_WINDOW_V3 = 60 + 1 so it should be correct, it's double check inherited from prev. versions.

I would prefer all integer math for the algo if it's possible, by the way.

[zawy12]

But if timestamp size < 60 at beginning of coin, then n < 60, so error is thrown instead of "1"

[aivve]

No, it works at the beginning, this is a check that n i.e. vectors of timestamps and cumul. difficulties are less or equal than 61

[zawy12]

Doh. I had it backwards. I think if (n <= 1) should be if (n < N+1) Can't run a loop on N+1 elements if there are < N+1 elements.

[helder-garcia]

Yes, you're right. n should not be less than N + 1 to go to the loop. But shouldn't it return 100000 as minimum difficulty instead of 1? At least from block 3? If we keep 1, for new coins the first N+1 blocks will have diff 1 and will be mined pretty fast.

[aivve]

It doesn't matter how you call it in a loop. In a loop we have to get N elements in vectors of solvetimes and difficulties the same as the whole formula is designed for.

100000 minimum limit is my arbitrary for karbo only, maybe it stopped from larger disaster yesterday. This formula won't kick up on new coin from scratch, I think some minimum difficulty to get it some solvetime is necessary.

[helder-garcia]

I'm going with

	const int64_t T = static_cast<int64_t>(m_difficultyTarget);
	const size_t N = CryptoNote::parameters::DIFFICULTY_WINDOW_V4 - 1;
	if (timestamps.size() > N + 1) {
		timestamps.resize(N + 1);
		cumulativeDifficulties.resize(N + 1);
	}
	size_t n = timestamps.size();
	assert(n == cumulativeDifficulties.size());
	assert(n <= CryptoNote::parameters::DIFFICULTY_WINDOW_V4);
	if (n <= 2) return 1;
	if (n < (N + 1)) return 100000;

[zawy12]

In case a new coin copies the code, it must be the following

size_t n = timestamps.size(); 		
assert(n == cumulativeDifficulties.size()); 	
	if (n <= N+1) 			return 1;

[aivve]

Lets hope this will protect us from future attacks. Future timestamp limit can be activated right off the hand. It's just required for all major pools and services to update.

[helder-garcia]

Are you going to roll back the chain to the height before the attack? We're NOT going this path, because we think the damage would be worse, rolling back legitimate transactions.
And, on this way, the only change of the future timestamp variable will cause fail to a node sync from scratch. we need to use a height alignment for this limit change.
https://github.com/niobio-cash/niobio-node-daemon/commit/1a7fabf6d3e755a713b8e8437f54e0ec55984181

[aivve]

Wallets on all exchanges are suspended.

Daemon and wallet should sync ok from scratch to the checkpoints. Placing checkpoints where needed should suffice.