More details about the bug are posted here: https://bitcointalk.org/index.php?topic=1065504.0

Also reported in #5712. FYI I don't think this is possible to hit on testnet even if it were to be reset, because the starting difficulty is high enough to prevent overflow. Would be nice to fix this for regtest though...

Correct. It can only be hit on regtest.

You're right, testnet3 shares the same pow limit as mainnet. I'll edit my commit message to match.

Fixed the protected members by declaring all other base_uint classes to be friends of any base_uint<BITS>.

@jrick: wouldn't it make sense to provide a RPC test (maybe qa/rpc-tests/reorg-overflow.py or so) where you could prove your implementation? The test should fail on current master and succeed with master+this PR on top.

@jonasschnelli agree that exercising this with a test would be good to have. I can try my hand at the RPC test at it if no one else picks it up, but I am not familiar with python.

Don't want to sidetrack the discussion, but writing tests in a different language that contributors might not know seems like a strange decision. Testing everything over RPC instead of calling the functions directly also complicates the RPC API by requiring exposing many internals that otherwise an RPC client should not need.

@jrick: no need to expose internals over RPC. If you PR solves a real world problems (which this PR does IMO) you should be able to automate the steps-to-produce-the-error-you-solve by creating a RPC test. You don't need to know python. Just copy'n'paste from other tests and adapt your scenario. :)

Added RPC tests.

Tested (regtest only!). ACK.
Changes look sane to me but i'm not sure if the changes in src/pow.cpp should go over chainparams (or something similar) so that this PR only affects regtest.

Changes look sane to me but i'm not sure if the changes in src/pow.cpp should go over chainparams (or something similar) so that this PR only affects regtest.

I'm also wary of this, if this is a problem that affects only testing code (regtest), it's unnecessary risk to change mainnet consensus code for it.

Remind me: Why does it retarget difficulty on regtest at all? From what I've always understood, the difficulty was supposed to be fixed at the bare minimum to allow instant block generation.

I can't speak for regtest, but @davecgh and I hit this issue while I was patching in support for btcd's simnet so I could do some testing against one of our private test networks. The difficulty retarget is needed in this case, or block generation timings on our network would not be as realistic as we need.

In the past, whenever we've talked about simnet in #bitcoin-dev, we've been told "that sounds just like regtest, why not use that instead?", so there are some people who do expect regtest to also work for simulation testing and long-lived private networks. A network that always has the lowest possible difficulty would indeed be useful for some situations, but useless for others.

Assumming the regtest retarget is kept, how would you incorporate the logic to use the 512-bit math only on regtest? I'm all for avoiding touching working mainnet code, but tests become less and less useful the more special cases are made for the test environment. In this case, I would think that sharing the difficulty retarget code on all networks is safest.

I would also suggest that having a test for the retarget code which does not rely on special casing or branches specific to the network makes the most sense and is the least risky approach.

This code path is currently uncovered by the test code. The block tester tool does not generate enough blocks to hit the retarget interval, and I haven't seen any test cases anywhere which otherwise cover it. Empirically, it works properly on mainnet and testnet, and naturally mainnet can be externally tested via an ASIC by disabling checkpoints, which are all good things. However, I personally don't think it's a good idea to solely rely on human testing for consensus-related code.

It's probably better for the rpc tests to calculate the exact expected retarget difficulty, instead of simply checking that the change was within the expected bounds.

Regtest does retarget just like mainnet, the only difference is that it starts off at a much lower difficulty.

Given that part of the purpose of that regtest is covering code to be used by mainnet, I think it's important that they do use the same code. I'm not very keen on changing the code for mainnet, though - even if it shouldn't make any difference, so I don't really know what the best solution is...

NACK, I would prefer regtest not to ever retarget as @laanwj suggests.

Leaning towards closing. Seems unlikely to be merged anytime soon given current comments.

[Weak] NACK.

If it isn't an issue, IMHO, don't bother adding the code to calculate it, however, it would be nice to document and assert that assumption.

As previously mentioned, it is in fact an issue on regtest. Retargets are not possible on regtest currently (and they used to be before commit df9eb5e). Unfortunately, there is currently no test coverage which exercise the retarget code and is why this was able to go through.

Repeating what I said above, I would also suggest that having a test for the retarget code which does not rely on special casing or branches specific to the network makes the most sense and is the least risky approach. That is the approach this pull request takes. It would appear @sipa agrees as he commented that it "ideally means using the same code for both."

This isn't a theoretical issue. We hit it because we were doing some testing with btcd and Bitcoin Core on regtest which involved retargets and noticed that btcd handles it correctly while Bitcoin Core does not even though they used to both handle it correctly in the past. This creates a situation where 3rd-party software can't properly be tested across retarget intervals on the regression test network with Bitcoin Core.

As retargetting never worked on regtest I'd prefer it to be disabled completely, as from what I've gathered, people don't really expect the difficulty on regtest to ramp up.

@sipa I agree, that would be a much clearer solution. I know the versionbits integration tests are going to need the ability to generate more than 2016 blocks on regtestnet (afaik). refs #6816

@sipa @btcdrak Regarding your fNoRetargetting, indeed! I had to force CheckProofOfWork to return true to actually run tests on #6816

@CodeShark maybe you should just fix it in your PR, or should there be a separate PR?

@laanwj: It is not true that retargetting never worked on regtest. It worked prior to commit df9eb5e.

For the record, I was in favor of this pull, but not strongly enough to continue advocating for it.

I also ACKed this PR. If only the mainnet effects would be reduced by moving/encapsulating the changes from the PR in CalculateNextWorkRequired() somehow towards chainparams.cpp ...

This code path is currently uncovered by the test code.

Actually there's currently some unittest for CalculateNextWorkRequired(), see https://github.com/bitcoin/bitcoin/blob/master/src/test/pow_tests.cpp.
In fact, testing was the reason why CalculateNextWorkRequired() was separated from GetNextWorkRequired() in the first place (see 34e5015 ).