Walk pindexBestHeader back to ChainActive().Tip() if it is invalid

TheBlueMatt commented at 10:18 pm on September 26, 2019: member

Instead of keeping pindexBestHeader set to the best header we’ve ever seen, reset it back to our validated tip if we find an ancestor of it turns out to be invalid. While the name is now a bit confusing, this matches much better with how it is used in practice, see below. Further, this opens up more use-cases for it in the future, namely aggressively searching for new peers in case we have discovered (possibly via some covert channel) headers which we do not know to be invalid, but which we cannot find block data for.

Places pindexBestHeader is used:

Various GUI displays of the best header and getblockchaininfo[“headers”], I don’t think changing this is bad, and if anything this is less confusing in the presence of an invalid block.
IsCurrentForFeeEstimation(): If anything I think ensuring pindexBestHeader isn’t some crazy invalid chain is better than the alternative, even in the case where you are rejecting the current chain due to hardware error (since hopefully in that case you won’t get any new blocks anyway).
ConnectBlock assumevalid checks: We use pindexBestHeader to check that the block we’re connecting leads to something with nMinimumChainWork (preventing a user-set assumevalid from having bogus work) and that the block we’re connecting leads to pindexBestHeader (I’m not too worried about this one - it’s nice to “disable” assumevalid if we have a long invalid headers chain, but I don’t see it as a critical protection).
BlockRequestAllowed() uses pindexBestHeader as its target to ensure the requested block is within a month of the “current chain”. I don’t think this is a meaningful difference, if we’re rejecting the current tip we’re trivially fingerprintable anyway, and if the chain really does have a bunch of invalid crap near the tip, using the best not-invalid header is likely a better criteria.
ProcessGetBlockData uses pindexBestHeader as the “current chain” definition of whether a block request is “historical” for the purpose of bandwidth limiting. Similarly, I don’t see why this is a meaningful change.
We use pindexBestHeader for requesting missing headers on receipt of a headers/compact block message or block inv as well as for initial getheaders. I think this is definitely wrong, using the best not-invalid header for such requests is much better.
We use pindexBestHeader to define the “current chain” for deciding when we’re close to done with initial headers sync. I don’t think this is a meaningful change.
We use pindexBestHeader to decide if initial headers sync has timed out. If we’re rejecting the chain due to hardware error this may result in additional cases where we ban a peer, but this is already true, so I think its fine.

DrahtBot added the label Validation on Sep 26, 2019

in src/validation.cpp:1417 in 64376bcba0 outdated

1425@@ -1422,6 +1426,8 @@ void static InvalidChainFound(CBlockIndex* pindexNew) EXCLUSIVE_LOCKS_REQUIRED(c
1426     CheckForkWarningConditions();
1427 }
1428 
1429+// Same as InvalidChainFound, above, except not called directly from InvalidateBlock,
1430+// which does its own setBlockIndexCandidates manageent.

practicalswift commented at 12:00 pm on September 27, 2019:

Nit: Should be “management” :)

DrahtBot commented at 8:49 pm on October 3, 2019: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

No conflicts as of last run.

DrahtBot added the label Needs rebase on Oct 30, 2019

Walk pindexBestHeader back to ChainActive().Tip() if it is invalid

Instead of keeping pindexBestHeader set to the best header we've
ever seen, reset it back to our validated tip if we find an ancestor
of it turns out to be invalid. While the name is now a bit confusing,
this matches much better with how it is used in practice, see below.
Further, this opens up more use-cases for it in the future, namely
aggressively searching for new peers in case we have discovered
(possibly via some covert channel) headers which we do not know to be
invalid, but which we cannot find block data for.

Places pindexBestHeader is used:

 * Various GUI displays of the best header and getblockchaininfo["headers"],
   I don't think changing this is bad, and if anything this is less confusing
   in the presence of an invalid block.
 * IsCurrentForFeeEstimation(): If anything I think ensuring pindexBestHeader
   isn't some crazy invalid chain is better than the alternative, even in the
   case where you are rejecting the current chain due to hardware error (since
   hopefully in that case you won't get any new blocks anyway).
 * ConnectBlock assumevalid checks: We use pindexBestHeader to check that the
   block we're connecting leads to something with nMinimumChainWork (preventing
   a user-set assumevalid from having bogus work) and that the block we're
   connecting leads to pindexBestHeader (I'm not too worried about this one -
   it's nice to "disable" assumevalid if we have a long invalid headers chain,
   but I don't see it as a critical protection).
 * BlockRequestAllowed() uses pindexBestHeader as its target to ensure the
   requested block is within a month of the "current chain". I don't think this
   is a meaningful difference, if we're rejecting the current tip we're
   trivially fingerprintable anyway, and if the chain really does have a bunch
   of invalid crap near the tip, using the best not-invalid header is likely a
   better criteria.
 * ProcessGetBlockData uses pindexBestHeader as the "current chain" definition
   of whether a block request is "historical" for the purpose of bandwidth
   limiting. Similarly, I don't see why this is a meaningful change.
 * We use pindexBestHeader for requesting missing headers on receipt of a
   headers/compact block message or block inv as well as for initial getheaders.
   I think this is definitely wrong, using the best not-invalid header for such
   requests is much better.
 * We use pindexBestHeader to define the "current chain" for deciding when
   we're close to done with initial headers sync. I don't think this is a
   meaningful change.
 * We use pindexBestHeader to decide if initial headers sync has timed out. If
   we're rejecting the chain due to hardware error this may result in
   additional cases where we ban a peer, but this is already true, so I think
   its fine.

0a50019fde

TheBlueMatt force-pushed on Oct 30, 2019

sdaftuar commented at 5:59 pm on October 30, 2019: member

utACK, apart from verifying how the GUI will handle the situation of pindexBestHeader going backward. I can try to take a look at that later. (One observation that suggests that this ought to be a safe change is that in LoadBlockIndex(), we already set pindexBestHeader to be the most-work valid header.)

DrahtBot removed the label Needs rebase on Oct 30, 2019

laanwj added this to the "Blockers" column in a project

ariard commented at 11:10 pm on November 8, 2019: member

utACK 0a50019

Let’s say you have headers topology :

      B - C
   /
 A 
   \ 
     D - E

If pindexBestHeader points to E, if D or E are invalid blocks, block validation sequence is going to reset pointer to A until next header connection, after then it would point to C. Right now, pointer stays dirty on E until next header connection driven by AcceptBlockHeader logic, after then it would point also to C. So contrary of what I thought at first, this change it’s not an event anticipation on what header connection logic would have done but a real (slight) behavior modif.

Does this change have meaningful consequences ?

GUI: getHeaderTip is used to display best known header, so yes that’s a change but in anycase it’s better to display a non-invalid one
IsCurrentForFeeEstimation: right now we wouldn’t consider for fee estimation txn even if we may not be effectively behind due to our best header being in fact invalid (and assuming that’s only header branch we have). With this change, we are going to consider txn for estimation while we may be behind due to other non-invalid header branch being hidden by proven invalidity of our previous best header. That’s a change in the set of wrong-considered transactions but this one is more liberal (and seems better to include near-to-tip txn than dropping them due to invalid chain header)
assumevalid : if block failed before hashAssumeValid, pointer is going to be back to current valid tip, which is going to be part of the assumevalid chain but starting from then a new validation is going to start on another non-assumevalid branch on selection of which pindexBestHeader doesn’t interfer even if still dirty. So no change here.
NotifyHeaderTip: called after AcceptBlockHeader in ProcessNewBlockHeader and before ActivateBestChain in ProcessNewBlock. Shouldn’t see the difference
BlockRequestAllowed : if someone send you an invalid block, pointer is going to be reset to current tip and effectively offer a short grace delay compare to what it’s now but this edge is flattened at next header announcement (and variance of their announcement is not meaningful compare to scale of STALE_RELAY_AGE_LIMIT)
ProcessGetBlockData : same analysis than previously, a bit more meaningful because HISTORICAL_BLOCK_AGE is shorter but it’s not a sound attack to produce expensive block to gain potentially bandwidth beyond rate-limiting cap for a super slight delay from other peers
ProcessHeaderMessage: seems better to ask for headers from a valid starting point than a proven-invalid one
inv.type == MSG_BLOCK : same analysis than previously
strCommand == NetMsgType::CMPCTBLOCK : same analysis than previously
on block sync : going to lock us a bit more in initial sync but right now we would exit based on proven-invalid block so better
nHeadersSyncTimeout : invalid blocks is going to push backward GetBlockTime so may increase slightly timeout but is this going an edge compare to what an attacker could do with nHeadersSyncTimeout ? Don’t think so

TheBlueMatt commented at 6:11 pm on November 9, 2019: member

A more important scenario than the one you described is:

0    B -> C
1  /
2A
3  \
4    D -> E -> F

In the current model, if D is found to be invalid, even after we’ve connected to C, pindexBestHeader will still point to F, which is nonsense.

sipa commented at 7:59 pm on November 9, 2019: member

I see no problem with changing the definition of pindexBestHeader from “best block header” to “best not-known-to-be-invalid block header”.

It feels a bit strange to only implement this as a reset when an invalid block is found, as that does not actually maintain the “best not-known-to-be-invalid” invariant at all times. Given the relative unimportance of pindexBestHeader maybe this is fine, but in that case maybe it should be documented as “A block header that is at least as good as the active tip, and not known to be invalid. We optimistically try to keep it at the best block header under those constraints, but this is not guaranteed.” or so.

An alternative (open for consideration, I’m not convinced this is necessary) is to build something similar to setBlockIndexCandidates for headers without the have-had-full-transactions requirements, and use its tip instead of pindexBestHeader.

TheBlueMatt commented at 2:10 am on November 12, 2019: member

Right, if we ever have a need for definitely-best-header, we can revive #12138 (which I think worked as-is, its just a nontrivial amount of code).

promag commented at 10:05 pm on November 24, 2019: member

Another alternative is to add the best header for each setBlockIndexCandidates entry? @TheBlueMatt how hard is to add a test that would fail without this change?

TheBlueMatt commented at 4:56 pm on November 25, 2019: member

@promag I don’t think that helps - setBlockIndexCandidates is only for things for which we have the data, ie not-just-headers.

fanquake deleted a comment on Nov 25, 2019

fjahr commented at 7:58 pm on December 20, 2019: member

ACK 0a50019fde7781263e0c8f041d1d9dcb0dee77e8

Thanks for the detailed comments and evaluation on the usages, I also grepped myself to make sure no important usages where missed.

Here is a super simple test for the behavior change in getblockchaininfo: https://github.com/fjahr/bitcoin/commit/2e599d86b13e15a2aa25e90690ee72d16e642f5e Feel free to use.

kallewoof commented at 7:15 am on January 10, 2020: member

ACK 0a50019fde7781263e0c8f041d1d9dcb0dee77e8

laanwj removed this from the "Blockers" column in a project

laanwj added this to the "Blockers" column in a project

laanwj referenced this in commit 651e343888 on Feb 3, 2020

laanwj merged this on Feb 3, 2020

laanwj closed this on Feb 3, 2020

laanwj removed this from the "Blockers" column in a project

sidhujag referenced this in commit 124ac6a348 on Feb 3, 2020

sidhujag referenced this in commit 0c879c941c on Nov 10, 2020

Fabcien referenced this in commit bc14a0e2b8 on Dec 22, 2020

DrahtBot locked this on Feb 15, 2022

Walk pindexBestHeader back to ChainActive().Tip() if it is invalid #16974

Conflicts