Track best-possible-headers

TheBlueMatt commented at 10:48 pm on January 10, 2018: member

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.

Require setBlockIndexCandidates be !BLOCK_FAILED_MASK

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.

b1afd3e7a2

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

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.

7b8055ff53

Default to running -checkblockindex in test_framework

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).

350395d1b5

Do not unlock cs_main in ABC unless we've actually made progress.

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).

a9db3dada0

Stop using pindexBestHeader outside of validation.cpp

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.

8525f50c36

Replace ProcessNewBlock's fRequested with candidate header check

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.

ed5b2770b0

TheBlueMatt force-pushed on Jan 10, 2018

jonasschnelli commented at 10:55 pm on January 10, 2018: contributor

Great work! Concept ACK. Will review…

jonasschnelli added the label P2P on Jan 10, 2018

TheBlueMatt renamed this:
~~Track best-possible-headers~~
[WIP] Track best-possible-headers
on Jan 10, 2018

TheBlueMatt renamed this:
~~[WIP] Track best-possible-headers~~
Track best-possible-headers
on Jan 10, 2018

TheBlueMatt commented at 10:58 pm on January 10, 2018: member

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.

in src/validation.cpp:1335 in 7b8055ff53 outdated

1330+                // chains, not anything in them. At this point we should be
1331+                // consistent by adding pindex, there should be more more work
1332+                // to do here.
1333+                setBlockIndexHeaderCandidates.erase(it);
1334+                break;
1335+                parent_present = true;

bpay commented at 1:09 am on January 16, 2018:

Dead code?

TheBlueMatt commented at 9:11 pm on January 17, 2018:

Oops, indeed, fixed.

in src/validation.cpp:2778 in ed5b2770b0

2793-            pindexNewTip = chainActive.Tip();
2794-            pindexFork = chainActive.FindFork(pindexOldTip);
2795-            fInitialDownload = IsInitialBlockDownload();
2796+                if (fInvalidFound) {
2797+                    // Wipe cache, we may need another branch now.
2798+                    pindexMostWork = nullptr;

skeees commented at 1:19 am on April 16, 2018:

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

in src/validation.cpp:2756 in ed5b2770b0

2757-                pindexMostWork = FindMostWorkChain();
2758-            }
2759+            arith_uint256 starting_work = chainActive.Tip() ? chainActive.Tip()->nChainWork : arith_uint256(0);
2760+            bool blocks_connected = false;
2761+            do {
2762+                // We absolutely may not unlock cs_main until we've made forward progress

skeees commented at 1:19 am on April 16, 2018:

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

skeees commented at 1:23 am on April 16, 2018: contributor

just a review of: https://github.com/bitcoin/bitcoin/pull/12138/commits/a9db3dada0119c183d16627805e90c4dbca05c6a

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

MarcoFalke added the label Needs rebase on Jun 6, 2018

TheBlueMatt closed this on Jun 14, 2018

Sjors commented at 10:30 am on June 15, 2018: member

@TheBlueMatt did you move this work somewhere else?

Update:

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

MarcoFalke referenced this in commit a08533c1a0 on Aug 11, 2018

MarcoFalke referenced this in commit e2dfeb0146 on Dec 22, 2018

laanwj removed the label Needs rebase on Oct 24, 2019

PastaPastaPasta referenced this in commit 81bf95e464 on Jun 27, 2021

PastaPastaPasta referenced this in commit 021fb4905d on Jun 27, 2021

PastaPastaPasta referenced this in commit 23417499e0 on Jun 28, 2021

PastaPastaPasta referenced this in commit bb34e9d287 on Jun 28, 2021

PastaPastaPasta referenced this in commit 5edf4694d4 on Jun 29, 2021

PastaPastaPasta referenced this in commit a47278fbdd on Jun 29, 2021

PastaPastaPasta referenced this in commit d42488ea69 on Jun 29, 2021

PastaPastaPasta referenced this in commit fa5755785b on Jun 29, 2021

PastaPastaPasta referenced this in commit f33c2c8101 on Jun 29, 2021

PastaPastaPasta referenced this in commit b04090df10 on Jun 29, 2021

PastaPastaPasta referenced this in commit 42776d0db8 on Jul 1, 2021

PastaPastaPasta referenced this in commit 045e9c87ce on Jul 1, 2021

PastaPastaPasta referenced this in commit 28ff288386 on Jul 1, 2021

UdjinM6 referenced this in commit 7c634146e0 on Jul 5, 2021

PastaPastaPasta referenced this in commit 9e6c0d0524 on Jul 8, 2021

MarcoFalke locked this on Dec 16, 2021

Track best-possible-headers #12138