TSA RTT: Change Difficulty During the Block about difficulty-algorithms HOT 21 OPEN

Xchange successfully implemented a TSA version close to the BTC version above and it functions as well as expected. No solvetimes are more than 3.4x target.

from difficulty-algorithms.

Very interesting. I'm going to explore a way to integrate this with Verus Proof of Power. Thanks!

from difficulty-algorithms.

The average solvetime will probably not be correct if you use the clamp. The TSA formula without the clamp is the only one that will keep the correct solvetime when changing difficulty so drastically each block.

from difficulty-algorithms.

On the prelim BTC/zCash code.
This line seems off?
if ((previousTarget * 67) / 100 > nextTarget) { nextTarget = (previousTarget * 67); }
It seems like here the goal is to cap the decrease of nextTarget to 66% of the previousTarget.
However, the code is actually setting nextTarget to 67 * previousTarget. Is this really intentional, this seems to cause the target to get stuck at powLimit.

from difficulty-algorithms.

Thanks....I don't know how that error got in there. It's missing a divide by 100 at the end and reversing the first part makes it easier to understand. I wonder if a certain coin has this in their code.

if ( nextTarget < (previousTarget * 67) / 100 ) { nextTarget = (previousTarget * 67)/100; }

from difficulty-algorithms.

Glad to help.

I agree with the change you made around reversing, that's actually what I did first in my own code to fix this, it makes it much easier to understand. Another option (a long as these operations work for arith_unit256) is to use min/max so that this bug can't happen:

    // Clamp nextTarget between 66% and 150% of previousTarget
    const arith_uint256 prevTarget150pct = (previousTarget * 150) / 100;
    const arith_uint256 prevTarget66pct = (previousTarget * 67) / 100;
    nextTarget = std::max(std::min(nextTarget, prevTarget150pct), prevTarget66pct);

from difficulty-algorithms.

Oh, yes, also. The coins I checked do have this bug :( I checked a few to see if maybe this was just a bug in the post.

from difficulty-algorithms.

Both of those lines were deleted because they caused other problems that they did not cause in LWMA

from difficulty-algorithms.

No limits should be used with TSA. If it varies too much according to your desires, then the thing to do is increase the R value

from difficulty-algorithms.

Got it, so those lines should be used in LWMA when not using TSA.
However, if you are using TSA it will handle effectively clamping the difficulty adjust (or at least swinging too far on a difficult adjust does not cause as much trouble with TSA).

from difficulty-algorithms.

Those lines are only needed in certain LWMAs and I'm removing them from the current one. I'm only aware of 1 coin that has this error. Luckily it is never triggered, otherwise the difficulty will probably go very very low and maybe stay there, so it has never been triggered if they have not noticed it So they might be able to fix the affected coin by a hot-fix since the fix would be backwards compatible.

from difficulty-algorithms.

Yeah, it seems like it would very difficult for this condition to occur. I only hit it during development on a brand new chain, and yes if the condition has never occurred in the past a hot fix is viable.

from difficulty-algorithms.

Monitoring.

from difficulty-algorithms.

I'm confused @zawy12. If solve times are under a modal distribution, they are LESS like a Poisson process. Significantly less like one.

A goodness-of-fit for your data to show that the result is more like a Poisson process is simple: test whether the expected solvetime equals the variance of the solvetime. If you have an extremely tight, unimodal distribution with mode at 100 seconds (or whatever) your variance will be very small compared to the expectation.

What you have is not a Poisson process. It's variance is too large, and your process is not memoryless. Memorylessness is essential to proof of work, and moreover, there is only one continuous distribution that is memoryless: the exponential distribution. If your difficulty adjustment algorithm is actively shaping the inter-block arrival time/solve time distribution to be anything other than exponential, then you are creating a non-memoryless block arrival time.

This allows miners to abandon a block the moment that it's taking longer to solve than median/mode/expectation, which will drive overall block arrival time down... which will drive your difficulty up... despite that hashrate has not changed.

So, maybe I'm confused, or maybe I need an explanation of the goal of your difficulty adjustment method.

from difficulty-algorithms.

It's variance is too large

Maybe you have this mis-perception because the charts show a wide variance in difficulty that drives solvetime variance low. I call it "tightening" the Poisson because the solvetime variance is less than the expected value. The solvetime variances for M=2 and M=4 are 0.43 and 0.63 for "dedicated miner" ("constant HR") assumption, and 0.29 and 0.38 under a simple "max-profit" model where the miner can decide to start or stop mining in easily in the current block (and supposedly has other coins to mine during his off time).

This allows miners to abandon a block the moment that it's taking longer to solve

Difficulty gets lower and lower as the solvetime gets longer. They will want to stay.

is not memoryless

I do not know why POW requires memorylessness, but 'll give two observational arguments that it is not a problem, and a 3rd argument that it really is memoryless.

1. The aggregate miner motivation changes all the time in small coins. This changes lambda in the Poisson, sometimes throwing solvetimes off, making them too fast or slow. The DA sees this and eventually corrects. TSA reverses the process. It changes lambda to affect miner motivation.

2. I've done a lot of modelling with various miner motivation assumptions and can accurately predict results of DAs on live coins. The results above should be close to live coin results. I don't know how miners will respond to this nearly as well as other DAs, but it reacts correctly under all the things I've given it, so that there should not be any problem no matter what miners do.

3. Lambda is the only time-dependent variable in the Poisson. TSA converts it to a distinct function of time. In other words, it warps time. Living in the real-world, we think it is not a Poisson. But in the time-warped world it still is. It warps miner-motivation, which warps lambda.

from difficulty-algorithms.

Why must POW be memoryless? Because it must be progress-free. Why must it be progress-free? Satoshi made this point at least once here but didn't elaborate.

Imagine if proof of work had progress (like a progress bar when you are installing a video game) or more specifically had a memory. If POW is using a progress-based approach, then the fastest machine always gets the next block with very high probability. This changes the threat model from a 50+% attack to whoever has the single fastest machine. Not decentralized.

Inefficient miners can't even probabilistically get lucky. The "more reliable" the memory of a system, the closer you are to a progress bar, and the less that small miners can get probabilistically lucky, i.e. less decentralized. The closer the system is to memoryless, the more likely that a small miner or pool can at least get a few blocks at least occasionally by happenstance.

So the next question is: how do your simulations take all the above into account, or how can they be modified so that they do?

from difficulty-algorithms.

The blockchain is a time-invariant system. There is no time from Block A to Block B; only there is the state transition from one block to the next. The implication of "progress" and "memory" is not meaningful in the present context. That a block sequence number is higher, and that the reported solve time is higher than the preceding block sequence number is also a yes/no state with no additional reliable information available. We rely on the emergent behavior of a consensus network to determine whether the solve time is "sane" or "insane", as nodes accept or reject blocks according to what they believe the current time is. The only valid sanity tests related to "time" for each node are: a) Is the block reported solve time After the preceding block's reported solve time? b) Is the block reported solved time Before the current time as I understand it? There's no good reason to accept a block that has a timestamp that is in the future.

from difficulty-algorithms.

The relative probability of finding a block remains the same. If you're 1% of network HR, then you have 1% chance of finding the block for any given timestamp. The difficulty changes with time, but it's not because of how many hashes have been done.

I have no concerns about it other than the things I mention in the issue. I consider it finished, except I need to find a better baseline DA for the BTC/Zcash version (target method has more solvetime error than difficulty method).

from difficulty-algorithms.

Congratulations! FYI, Zcash is a 17 block average, so the comparison may be different... (??)

from difficulty-algorithms.

The Extra addition that was made to Xchange.

if ( (previousTimestamp - badblockcheck->GetBlockTime()) <= T/R && ST<(T-(T/5)) ) { TSATarget = nextTarget*(1/5); } else if ( ST <= T/5 ) { TSATarget = nextTarget*(1/5); }

To clarify why I did this,

else if ( ST <= T/5 ) { TSATarget = nextTarget*(1/5); } Hash attack programs attack the difficulty 0-1 secs, so when it solves the difficulty before it reaches a T/5, the

if ( (previousTimestamp - badblockcheck->GetBlockTime()) <= T/R && ST<(T-(T/5)) ) { TSATarget = nextTarget*(1/5); }

checks the previous block preventing it from breaking the chain and allowing a high hash attack. So the next target is decreased 1/5 X and if that is solved it re-checks and decreases it again. This breaks the loop of the attack. Ultimately breaking the attack.
This is why it is anti-51%. The on and off is handled by the TSA.

I did this studying attacks by using the program used in high hash attack. I placed a bounty on proof on 51% attack for XCG, yet no-one has been successful.

from difficulty-algorithms.

This is the TSA we used on Xchange

// Xbuffer Xchange (c) 2018 Kalcan
// TSA Copyright (c) 2018 Zawy, Kalcan (XCG)
// LWMA Copyright (c) 2017-2018 The Bitcoin Gold developers
// ############# Begin LWMA
const int64_t T = consensusParams.nPowTargetSpacing;
const int64_t N = consensusParams.nZawyLwmaAveragingWindow;
const int64_t k = N * (N + 1) * T / 2;
const int64_t height = pindexPrev->nHeight;
const arith_uint256 powLimit = UintToArith256(consensusParams.powLimit);
// For startup:
int64_t hashrateGuess = 1000; // hashes per second expected at startup
arith_uint256 targetGuess = 115E75/(hashrateGuess*T); // 115E75 =~ pow(2,256)

if ( targetGuess > powLimit ) { targetGuess=powLimit; }
if ( height <= N+1 ) { return targetGuess.GetCompact(); }

arith_uint256 sumTarget, previousTarget, nextTarget;
int64_t thisTimestamp, previousTimestamp;
int64_t t = 0, j = 0, SumWAvgtime=0, SS=0;   // Remove SS if following only LWMA and TSA

const CBlockIndex* blockPreviousTimestamp = pindexPrev->GetAncestor(height - N);
previousTimestamp = blockPreviousTimestamp->GetBlockTime();

// Loop through N most recent blocks. // LWMA previous target-> bits and Timestamps are the focys
for (int64_t i = height - N + 1; i <= height; i++) {
  const CBlockIndex* block = pindexPrev->GetAncestor(i);
  thisTimestamp = (block->GetBlockTime() > previousTimestamp) ? block->GetBlockTime() : previousTimestamp + 1;
  int64_t solvetime = std::min(6 * T, thisTimestamp - previousTimestamp);
  previousTimestamp = thisTimestamp;
  SS+=solvetime;
  j++;
  t += solvetime * j; // Weighted solvetime sum.
  arith_uint256 target;
  target.SetCompact(block->nBits);
  sumTarget += target / (k * N);
}
nextTarget = t * sumTarget;

// The above completes the BTG/MicroBitcoin/Zawy code except last 3 lines were removed

// ##############    Begin TSA Declarations
// R is the "softness" of the per-block TSA adjustment to the DA. R<6 is aggressive.
int64_t R = 2;  assert(R > 1);
// "m" is a factor to help get e^x from integer math. 1E5 was not as precise
int64_t m = 1E6;
arith_uint256  TSATarget;
int64_t exm = m;  // This will become m*e^x. Initial value is m*e^(mod(<1)) = m.
int64_t SC, ST, i, f; //remove SC for TSA & LWMA
int64_t templateTimestamp = pblock->nTime;
previousTimestamp = pindexPrev->GetBlockTime();
const CBlockIndex* badblockcheck = pindexPrev->GetAncestor(height-1); //Only for Xbuffer

ST = std::min(templateTimestamp - previousTimestamp, 6*T);

// #########  Begin Unwanted Modification to TSA logic
//----------Xbuffer------------------------------
SC=ST; 
if ( SS/N + 1 <= T/R ) { SS = ( SS/(N + 1)/T )*SS; }
ST = ( ST*( ( SS/(N + 1)*1000 )/T ) ) / 1000;
if ( SC > T/R && ST == 0 ) { ST = SC; }
if ( ST < 0 ) { ST = 0; }
if ( (previousTimestamp - badblockcheck->GetBlockTime()) <= T/R && ST<(T-(T/5)) ) { TSATarget = nextTarget*(1/5); }
else if ( ST <= T/5 ) { TSATarget = nextTarget*(1/5);}

// ########### Begin Actual TSA   ##########
else {
  // It would be good to turn the for statement into a look-up table;
  for ( i = 1; i <= ST/T/R ; i++ ) { exm = (exm*static_cast<int64_t>(2.71828*m))/m; }
  f = ST % (T*R);
  exm = (exm*(m+(f*(m+(f*(m+(f*(m+(f*m)/(4*T*R)))/(3*T*R)))/(2*T*R)))/(T*R)))/m;
  // 1000 below is to prevent overflow on testnet
  TSATarget = (nextTarget*((1000*(m*T + (ST - T)*exm))/(m*ST)))/1000;
}
if (TSATarget > powLimit) { TSATarget = powLimit; }
return TSATarget.GetCompact();
}

from difficulty-algorithms.