Track best-possible-headers #12138

TheBlueMatt · 2018-01-10T22:48:02Z

This adds a setBlockIndexHeaderCandidates which mimics setBlockIndexCandidates and is
The set of all leaf CBlockIndex entries with BLOCK_VALID_TREE (for itself and all ancestors) and
as good as our current tip or better. Entries here are potential future candidates for insertion
into setBlockIndexCandidates, once we get all the required block data. Thus, entries here
represent chains on which we should be actively downloading block data.

Note that we define "as good as our current tip or better" slightly differently here than in
setBlockIndexCandidates - we include things which will have a higher nSequence (but have the
same chain work) here, but do not include such entries in setBlockIndexCandidates. This is
because we prefer to also download towards chains which have the same total work as our current
chain (as an optimization since a reorg is very possible in such cases).

Note that, unlike setBlockIndexCandidates, we only store "leaf" entries here, as we are not as
aggressively prune-able (setBlockIndexCandidates are things which we can, and usually do, try to
connect immediately, and thus entries dont stick around for long). Thus, it may be the case that
chainActive.Tip() is NOT in setBlockIndexHeaderCandidates.

Additionally, unlike setBlockIndexCandidates, we are happy to store entries which are not
connectable due to pruning here.

This is useful as it (finally) disconnects net_processing logic from the "store on disk" logic in validation.cpp. More importantly, it represents what you'd need from the consensus logic to implement a spv-first sync mode, as this provides a best-header which will follow invalidity - always pointing to the best-possible header even after block(s) are found to be invalid.

When we find an invalid block, instead of adding BLOCK_FAILED_CHILD to its descendants in FindMostWorkChain, iterate setBlockIndexCandidates to find candidate descendants and mark them as BLOCK_FAILED_CHILD immediately, removing them from setBlockIndexCandidates as we go. This keeps BLOCK_FAILED_MASK entries out of setBlockIndexCandidates. This also adds a few checks to CheckBlockIndex, including one which checks that blocks with BLOCK_FAILED_CHILD are not, themselves, marked invalid, but have an invalid parent. This should be fine for most block indexes, however InvalidateBlock previously violated this. Luckily most users shouldn't be running with -checkblockindex Note that this introduces a bug where a block who's header was received but data was not when a ancestor was found to be invalid will not be marked BLOCK_FAILED_CHILD. Thus, when that block is received, it will be added to setBlockIndexCandidates, violating the new invariant. This is fixed in the next commit.

This mirrors setBlockIndexCandidates but for BLOCK_VALID_TREE instead of BLOCK_VALID_TRANSACTIONS && nTx. There are a few differences between the two to keep the new set practical, see code comments for more.

Block index inconsistencies are one of the most critical types of bugs we could see. Making sure we get good coverage of CheckBlockIndex() is pretty important (and there is minimal, if any performance difference in a default run).

Technically, some internal datastructures may be in an inconsistent state if we do this, though there are no known bugs there. Still, for future safety, its much better to only unlock cs_main if we've made progress (not just tried a reorg which may make progress).

pindexBestHeader never considers the invalidity of a chain, only the validity of the header chain. Using it for sync estimation and GETHEADERS etc requests in net makes no sense. Instead, use the new setBlockIndexHeaderCandidates to find the best candidate tip.

Instead of allowing net_processing to inform AcceptBlock as to whether a block is interesting enough to commit to disk, use the new setBlockIndexHeadersCandidates to determine if they lead towards a chain with at least the same (or more) work as our current tip. This further decouples the maze in net_processing from our consensus anti-DoS logic.

jonasschnelli · 2018-01-10T22:55:21Z

Great work!
Concept ACK. Will review...

TheBlueMatt · 2018-01-10T22:58:48Z

Note that FindNextBlocksToDownload may want to grow a corresponding nMinimumChainWork check before downloading towards any headers which do not (yet) meet that requirement. Otherwise we'll have a (bandwidth-wasting, but otherwise harmless) infinite download loop on regtest nodes that manually-specify minimum chain work on the command line.

bpay · 2018-01-16T01:09:54Z

src/validation.cpp

+                // to do here.
+                setBlockIndexHeaderCandidates.erase(it);
+                break;
+                parent_present = true;


Oops, indeed, fixed.

skeees

just a review of: a9db3da

note that this appears to change the semantics of how often the UpdatedBlockTip() signal will be invoked. That seems like the desired intention but just wanted to mention

skeees · 2018-04-16T01:19:21Z

src/validation.cpp

-            fInitialDownload = IsInitialBlockDownload();
+                if (fInvalidFound) {
+                    // Wipe cache, we may need another branch now.
+                    pindexMostWork = nullptr;


FindMostWorkChain() isn't particularly expensive to call redundantly when you know you are on the tip (it amounts to two hashtable lookups)
If you don't mind calling it unnecessarily on your last pass through the loop you can substantially tighten the 3 if statements you have to implement this logic

skeees · 2018-04-16T01:19:26Z

src/validation.cpp

+            arith_uint256 starting_work = chainActive.Tip() ? chainActive.Tip()->nChainWork : arith_uint256(0);
+            bool blocks_connected = false;
+            do {
+                // We absolutely may not unlock cs_main until we've made forward progress


Is there always guaranteed to be progress? From reading this loop it seems like it could interrogate a potential alternate chain - find some invalidity and then roll back to the original tip

Sjors · 2018-06-15T10:30:04Z

@TheBlueMatt did you move this work somewhere else?

Update:

I guess this should be tagged "up for grabs, including possibly by the original author"?

…_args fa31ca0 qa: Remove redundant checkmempool/checkblockindex extra_args (MarcoFalke) Pull request description: They are already enabled by default for regtest: https://github.com/bitcoin/bitcoin/blob/df9f71274645a917e2578c52a1c59745bce8112d/src/init.cpp#L1002-L1007 Closes #13912. CC #12138 Tree-SHA512: b11a3e8cc4715569f917ab89132f8c8dcae64aebcd7a34182675f86cf7f6e207e3187b7ea01a56c92c8c3af76122b6b995e84f533e134676863f8953dc1f0574

…ks in AcceptBlockHeader 66e15e8 Explain GetAncestor check for m_failed_blocks in AcceptBlockHeader (Sjors Provoost) Pull request description: Salvaged (but slightly modified) from #12138, the comment there was really helpful to wrap my head around that part of the code. In addition, a naive reader like yours truly will first think `IsValid(BLOCK_VALID_SCRIPTS)` means the previous block was invalid. But IIUC that's not what it means. Instead, it means the block hasn't been checked for validity at the `BLOCK_VALID_SCRIPTS` level yet. So in that case the existing text "previous block index isn't valid" is wrong. Tree-SHA512: 442a319a83290d94697fdf51376463b70454e0f3909d4a45594ddc2e7c26cd19dc703808385a25e26d6d2dddab0aa35ca41722f2e65ee6fe57bbaf62652d3ec8

…x extra_args fa31ca0 qa: Remove redundant checkmempool/checkblockindex extra_args (MarcoFalke) Pull request description: They are already enabled by default for regtest: https://github.com/bitcoin/bitcoin/blob/df9f71274645a917e2578c52a1c59745bce8112d/src/init.cpp#L1002-L1007 Closes bitcoin#13912. CC bitcoin#12138 Tree-SHA512: b11a3e8cc4715569f917ab89132f8c8dcae64aebcd7a34182675f86cf7f6e207e3187b7ea01a56c92c8c3af76122b6b995e84f533e134676863f8953dc1f0574

…ed_blocks in AcceptBlockHeader 66e15e8 Explain GetAncestor check for m_failed_blocks in AcceptBlockHeader (Sjors Provoost) Pull request description: Salvaged (but slightly modified) from bitcoin#12138, the comment there was really helpful to wrap my head around that part of the code. In addition, a naive reader like yours truly will first think `IsValid(BLOCK_VALID_SCRIPTS)` means the previous block was invalid. But IIUC that's not what it means. Instead, it means the block hasn't been checked for validity at the `BLOCK_VALID_SCRIPTS` level yet. So in that case the existing text "previous block index isn't valid" is wrong. Tree-SHA512: 442a319a83290d94697fdf51376463b70454e0f3909d4a45594ddc2e7c26cd19dc703808385a25e26d6d2dddab0aa35ca41722f2e65ee6fe57bbaf62652d3ec8

…x extra_args fa31ca0 qa: Remove redundant checkmempool/checkblockindex extra_args (MarcoFalke) Pull request description: They are already enabled by default for regtest: https://github.com/bitcoin/bitcoin/blob/df9f71274645a917e2578c52a1c59745bce8112d/src/init.cpp#L1002-L1007 Closes bitcoin#13912. CC bitcoin#12138 Tree-SHA512: b11a3e8cc4715569f917ab89132f8c8dcae64aebcd7a34182675f86cf7f6e207e3187b7ea01a56c92c8c3af76122b6b995e84f533e134676863f8953dc1f0574

…ed_blocks in AcceptBlockHeader 66e15e8 Explain GetAncestor check for m_failed_blocks in AcceptBlockHeader (Sjors Provoost) Pull request description: Salvaged (but slightly modified) from bitcoin#12138, the comment there was really helpful to wrap my head around that part of the code. In addition, a naive reader like yours truly will first think `IsValid(BLOCK_VALID_SCRIPTS)` means the previous block was invalid. But IIUC that's not what it means. Instead, it means the block hasn't been checked for validity at the `BLOCK_VALID_SCRIPTS` level yet. So in that case the existing text "previous block index isn't valid" is wrong. Tree-SHA512: 442a319a83290d94697fdf51376463b70454e0f3909d4a45594ddc2e7c26cd19dc703808385a25e26d6d2dddab0aa35ca41722f2e65ee6fe57bbaf62652d3ec8

…x extra_args fa31ca0 qa: Remove redundant checkmempool/checkblockindex extra_args (MarcoFalke) Pull request description: They are already enabled by default for regtest: https://github.com/bitcoin/bitcoin/blob/df9f71274645a917e2578c52a1c59745bce8112d/src/init.cpp#L1002-L1007 Closes bitcoin#13912. CC bitcoin#12138 Tree-SHA512: b11a3e8cc4715569f917ab89132f8c8dcae64aebcd7a34182675f86cf7f6e207e3187b7ea01a56c92c8c3af76122b6b995e84f533e134676863f8953dc1f0574

…ed_blocks in AcceptBlockHeader 66e15e8 Explain GetAncestor check for m_failed_blocks in AcceptBlockHeader (Sjors Provoost) Pull request description: Salvaged (but slightly modified) from bitcoin#12138, the comment there was really helpful to wrap my head around that part of the code. In addition, a naive reader like yours truly will first think `IsValid(BLOCK_VALID_SCRIPTS)` means the previous block was invalid. But IIUC that's not what it means. Instead, it means the block hasn't been checked for validity at the `BLOCK_VALID_SCRIPTS` level yet. So in that case the existing text "previous block index isn't valid" is wrong. Tree-SHA512: 442a319a83290d94697fdf51376463b70454e0f3909d4a45594ddc2e7c26cd19dc703808385a25e26d6d2dddab0aa35ca41722f2e65ee6fe57bbaf62652d3ec8

…x extra_args fa31ca0 qa: Remove redundant checkmempool/checkblockindex extra_args (MarcoFalke) Pull request description: They are already enabled by default for regtest: https://github.com/bitcoin/bitcoin/blob/df9f71274645a917e2578c52a1c59745bce8112d/src/init.cpp#L1002-L1007 Closes bitcoin#13912. CC bitcoin#12138 Tree-SHA512: b11a3e8cc4715569f917ab89132f8c8dcae64aebcd7a34182675f86cf7f6e207e3187b7ea01a56c92c8c3af76122b6b995e84f533e134676863f8953dc1f0574

…ed_blocks in AcceptBlockHeader 66e15e8 Explain GetAncestor check for m_failed_blocks in AcceptBlockHeader (Sjors Provoost) Pull request description: Salvaged (but slightly modified) from bitcoin#12138, the comment there was really helpful to wrap my head around that part of the code. In addition, a naive reader like yours truly will first think `IsValid(BLOCK_VALID_SCRIPTS)` means the previous block was invalid. But IIUC that's not what it means. Instead, it means the block hasn't been checked for validity at the `BLOCK_VALID_SCRIPTS` level yet. So in that case the existing text "previous block index isn't valid" is wrong. Tree-SHA512: 442a319a83290d94697fdf51376463b70454e0f3909d4a45594ddc2e7c26cd19dc703808385a25e26d6d2dddab0aa35ca41722f2e65ee6fe57bbaf62652d3ec8

TheBlueMatt added 6 commits January 10, 2018 16:59

Add a set to track potential future chain tips based only on SPV.

7b8055f

This mirrors setBlockIndexCandidates but for BLOCK_VALID_TREE instead of BLOCK_VALID_TRANSACTIONS && nTx. There are a few differences between the two to keep the new set practical, see code comments for more.

Default to running -checkblockindex in test_framework

350395d

Block index inconsistencies are one of the most critical types of bugs we could see. Making sure we get good coverage of CheckBlockIndex() is pretty important (and there is minimal, if any performance difference in a default run).

TheBlueMatt force-pushed the 2017-10-best-header-tracking branch from e7aa9ce to ed5b277 Compare January 10, 2018 22:53

jonasschnelli added the P2P label Jan 10, 2018

TheBlueMatt changed the title ~~Track best-possible-headers~~ [WIP] Track best-possible-headers Jan 10, 2018

TheBlueMatt changed the title ~~[WIP] Track best-possible-headers~~ Track best-possible-headers Jan 10, 2018

bpay reviewed Jan 16, 2018

View reviewed changes

ajtowns mentioned this pull request Jan 16, 2018

[tests] Rename functional tests #11774

Merged

ryanofsky mentioned this pull request Mar 23, 2018

Complete hybrid full block SPV mode #9483

Closed

skeees reviewed Apr 16, 2018

View reviewed changes

maflcko added the Needs rebase label Jun 6, 2018

TheBlueMatt closed this Jun 14, 2018

Sjors mentioned this pull request Aug 8, 2018

test: Default to running -checkblockindex in test_framework (TheBlueMatt) #13912

Closed

maflcko mentioned this pull request Aug 8, 2018

qa: Remove redundant checkmempool/checkblockindex extra_args #13913

Merged

This was referenced Aug 9, 2018

doc: Better explain GetAncestor check for m_failed_blocks in AcceptBlockHeader #13930

Merged

Track best-possible-headers (TheBlueMatt) #13937

Closed

laanwj removed the Needs rebase label Oct 24, 2019

TheBlueMatt mentioned this pull request Nov 12, 2019

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

Merged

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Track best-possible-headers #12138

Track best-possible-headers #12138

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Track best-possible-headers #12138

Track best-possible-headers #12138

Uh oh!

Conversation

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!