unsigned integer underflow
psychocrypt opened this issue · 11 comments
I think both problems should be solved by clamping L value. Rearranging the equation, I think 2415 is a good value. This represents more around three-fold increase in difficulty, more that enough control authority IMO.
Similarly clamp at 36234 will put a five-fold cap on the drop in difficulty.
Negative values of L are supposed to be prevented by the- 3xT limit on solvetimes. What timestamps did you send that resulted in a negative?
I will do divide by zero since that's more obvious. Assume somebody set all the timestamps in the window to the same value.
ST = std::max(-FTL, std::min( (int64_t)(timestamps[i]) - (int64_t)(timestamps[i-1]), 6*T));
ST = std::max(-FTL, std::min(0, 6*T));
ST = 0
L += 0 * i ;
next_D = ((cumulative_difficulties[N] - cumulative_difficulties[0])*T*(N+1)*99)/(100*2* 0 );
Negative L can be achieved in the same way (by making timestamps decrease). This will set the difficulty to an unattainable value (around 2^63 or 9,223,372,036,854,775,808).
I don't know if the jagerman MTP patch does it this way, but the best way to employ the MTP limit is do like BTC and Zcash and set any timestamp < or = to the MTP plus 1 second. 11 is the setting I tell everyone and what's used in BTC and Zcash use. That means the oldest timestamp you can assign is basically what the 6th block in the past had. So an attacker can send up to 6 small negative solvetimes in a row, then his blocks after that are "supposed" to be reset to +1 after the previous one he was trying to send.
I guess he could send -100 seconds 6 times in a row, then if he were able to get the next ~50 blocks in a row, it would go negative, even if the +1 is used employed. I believe any honest timestamp in the sequence would erase the effect. So a 56x attacker has a 50% chance of success. I'll add the old limit back in. Thanks for letting me know.
MTP is unfortunately unapplicabble here, as the attacker is unlikely to run unmodified code. The only limits are "timestamp > median" and "timestamp < time() + ftl".
Consider attack sequence:
- Attacker disables the FTL limit on his node, then offlines by cutting all p2p connections.
- Attacker builds up his own fork staring with T + x hours timestamp, and 50%+ hashrate
- Attacker decrements each timestamp
- Once L is negative and (x hours - ftl) passed (both conditions must be met), he onlines the node
- Network is disabled permanently
OK, good catch. Here's the limit I added back in:
if ( L < (T*N*N)/40 ) { L = (T*N*N)/40; }
What about cumulative difficulties? Does chain validation ensure old blocks always increase?
Yes, that one is infinitely better behaved as it isn't user-controlled input. It is essentially a sum of our previous outputs.
I opted to clamp it in a slightly different way, that is defined in terms of a cap on total control authority of the algo by simple rearrangement of your equation.
int64_t clamp_increase = (T*(N+1)*99)/int64_t(100.0*2.0 * 2.5);
int64_t clamp_decrease = (T*(N+1)*99)/int64_t(100.0*2.0 * 0.2);
I had a "20" and "40" where they both need to be 40.
Your clamp looks like it's trying to limit next_D to 60% decrease and 500% increase. If that's a per-block limit, you should make the 2.5 and 0.2 equal to the max LWMA with N=60 can do: 1.5 and 0.87. But I need to find an equation that relates the max LWMA changes to N. You could say "1.5 and 0.87 for N=60 only". The 0.87 would be smaller if the +6xT were not limiting it.
I can't get your scenario to work out. Remember, he can't send more than 6 negative solvetimes due to the MTP. If he starts with +2 hour, then any large negative solvetime will be limited by the -FTL in the code. But if the +1 was not used in your MTP patch, then a zero is still possible.
[edited]
Your clamp looks like it's trying to limit next_D to 60% decrease and 500% increase.
It is actually clamping at between 0.2next_D and 2.5next_D That's five-fold (500%) decrease and two-and-a-half fold (250%) increase respectively. There is no way to get zero since, looking at the equation (T*(N+1)*99)/int64_t(100.0*2.0 * 2.5) for the result to be 0, T or N would have to be zero.
Perhaps actual code will illustrate it better:
assert(timestamps.size() == N+1);
assert(cumulative_difficulties.size() == N+1);
for(int64_t i = 1; i <= N; i++)
{
ST = clamp(-FTL, int64_t(timestamps[i]) - int64_t(timestamps[i - 1]), 6 * T);
L += ST * i;
if(i > N - 3)
sum_3_ST += ST;
}
L = clamp(clamp_increase, L, clamp_decrease);
next_D = ((cumulative_difficulties[N] - cumulative_difficulties[0]) * T * (N + 1) * 99) / (100 * 2 * L);