Track best-possible-headers (TheBlueMatt)

Sjors commented at 2:02 pm on August 10, 2018: member

Rebase of #12138:

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.

Not included:

#13912 (test framework change)
#13930 (source code comment which is useful on its own)
a9db3dada0119c183d16627805e90c4dbca05c6a “Do not unlock cs_main in ABC unless we’ve actually made progress”: already merged as part of #13023

Noteble rebase changes:

pindex_was_in_chain is still needed due to #12431, in order to notify the gui about a new block tip, only if the active chain was modified
qt/clientmodel.cpp changed significantly, because things were moved to interfaces/node.cpp
updated ProcessNewBlock bench

I added an additional commit, because the new !fHasMoreOrSameWork && !parent_of_header_candidate check in AcceptBlock can cause submitblock (modified in #13439) to mistakingly believe the block is a duplicate.

Added debug log statements to rpc_preciousblock.py that helped me figure out the above issue.

Sjors commented at 2:04 pm on August 10, 2018: member

cc @TheBlueMatt, @MarcoFalke, @jamesob as this touches your work

cc @jonasschnelli since you reviewed the original PR (@skeees did too, but only the commit that I dropped)

Sjors force-pushed on Aug 10, 2018

DrahtBot commented at 4:24 pm on August 10, 2018: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#14624 (Some simple improvements to the RNG code by sipa)
#12151 (rpc: Remove cs_main lock from blockToJSON and blockheaderToJSON by promag)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

in src/validation.cpp:1422 in 7b2a938fa5 outdated

1421+            }
1422+            std::set<CBlockIndex*, CBlockIndexWorkComparator>::iterator forward_it = it.base(); // Is one past it
1423+            forward_it--; // Now points to it
1424+            forward_it = set_candidates.erase(forward_it);
1425+            it = std::set<CBlockIndex*, CBlockIndexWorkComparator>::reverse_iterator(forward_it);
1426+            // forward_it == it.base() now points to one-past previous it, making it point to one-before previous it.

Sjors commented at 4:29 pm on August 10, 2018:

Note: I find the above reverse-to-forward iterator dance remarkably confusing.

laanwj added the label Validation on Aug 10, 2018

in src/validation.cpp:1391 in 7b2a938fa5 outdated

1390+
1391+const CBlockIndex* CChainState::GetBestHeader() {
1392+    LOCK(cs_main);
1393+    auto it = setBlockIndexHeaderCandidates.rbegin();
1394+    if (it == setBlockIndexHeaderCandidates.rend())
1395+        return nullptr;

donaloconnor commented at 2:28 pm on August 11, 2018:

Numerous places call this function but no nullptr check is performed and dereferences are executed on the ptr. Can this return null in any case where this function is called?

Sjors commented at 12:49 pm on August 26, 2018:

That seems problematic indeed. There’s an assert for this in https://github.com/bitcoin/bitcoin/blame/7b1ab22384d944f638c514f838e25b391204ef67/src/net_processing.cpp#L3308, but not in the calls from validation.cpp:

in NotifyHeaderTip(): here it’s compared with pindexHeaderOld which is a nullptr initially, but would non-null the next time. It’s not dereferenced in that function, but it is passed on to uiInterface.NotifyHeaderTip. I could add an assert insideif (fNotify)
in IsCurrentForFeeEstimation(): I could add an assert directly above the if statement that deferences it

The comment in InvalidBlockFound suggests that sometimes setBlockIndexHeaderCandidates can be empty, so the above wouldn’t be enough. Rather than assert I could explicitly check for nullptr in both functions and deal with them, as well as put a warning where this set is defined.

in src/interfaces/node.cpp:157 in 7b2a938fa5 outdated

151@@ -152,10 +152,10 @@ class NodeImpl : public Node
152     size_t getMempoolDynamicUsage() override { return ::mempool.DynamicMemoryUsage(); }
153     bool getHeaderTip(int& height, int64_t& block_time) override
154     {
155-        LOCK(::cs_main);
156-        if (::pindexBestHeader) {
157-            height = ::pindexBestHeader->nHeight;
158-            block_time = ::pindexBestHeader->GetBlockTime();
159+        const CBlockIndex* best_header = ::GetBestHeader();
160+        if (best_header) {

donaloconnor commented at 2:41 pm on August 11, 2018:

Possible race condition here since we don’t lock cs_main? Can the best_head data be deleted between time we call GetBestHeader() and when we use the ptr?

I’m not familiar with the code enough to know the answer to this so just putting it here in case.

Sjors commented at 11:21 am on August 26, 2018:

~It sounds like it would be safer to also make a PR for https://github.com/bitcoin/bitcoin/commit/a9db3dada0119c183d16627805e90c4dbca05c6a that I left out?~ (nvm that was already merged in #13023)

I’ll see if I can understand the potential race condition you mention.

DrahtBot added the label Needs rebase on Aug 25, 2018

Sjors force-pushed on Aug 26, 2018

DrahtBot removed the label Needs rebase on Aug 26, 2018

Sjors commented at 2:12 pm on August 26, 2018: member

Rebased.

I added commits to explicitly handle cases where GetBestHeader() returns nullptr in validation.cpp. Both cases are UI related and don’t seem very important, so they’re handled in a fairly lazy way.

I added a commit to make header count fall back to block height in getblockchaininfo (rpc/blockchain.cpp).

That leaves net_processing.cpp, where I’m not sure what to do:

one existing assert in: https://github.com/bitcoin/bitcoin/blob/9ce44d8156576c58390a10007b60f507d107d042/src/net_processing.cpp#L3308
one deference ->GetBlockTime() in BlockRequestAllowed
one dereference in ->GetBlockTime()`` in ProcessGetBlockData`
one passing the pointer on to connman in ProcessHeadersMessage
passing into chainActive.GetLocator in ProcessMessage

Original commit where pindexBestHeader was replaced by GetBestHeader() for reference: https://github.com/bitcoin/bitcoin/pull/12138/commits/8525f50c369e737098f785c6867d89f392b77f95

I’m not sure if those are safe.

Perhaps there should be a guarantee that GetBestHeader() returns the last known valid block (worst case genesis), by inserting that whenever the last entry is deleted?

DrahtBot added the label Needs rebase on Aug 31, 2018

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.

481b45c5ea

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.

e0bb934113

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.

4116040337

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.

6096c63802

[test] precious_block: additional debug log statements 5fcddb0126

[validation] explictly handle GetBestHeader() == nullptr 6638093b60

[rpc] explictly handle GetBestHeader() == nullptr bdaf9f9693

Sjors force-pushed on Oct 30, 2018

Sjors commented at 8:50 am on October 30, 2018: member

Rebased. I’ll hold back on addressing specific feedback until there’s some high level agreement on whether this is useful at all.

DrahtBot removed the label Needs rebase on Oct 30, 2018

in src/validation.cpp:1364 in bdaf9f9693

1359+                // chains, not anything in them. At this point we should be
1360+                // consistent by adding pindex, there should be more more work
1361+                // to do here.
1362+                setBlockIndexHeaderCandidates.erase(it);
1363+                break;
1364+                parent_present = true;

practicalswift commented at 8:46 pm on October 30, 2018:

This is dead code. The parent_present = true; is not meant to be after break; in this scope? :-)

in src/validation.cpp:1378 in bdaf9f9693

1373+        // skip the whole scan.
1374+        for (auto it = setBlockIndexHeaderCandidates.rbegin(); it != setBlockIndexHeaderCandidates.rend() && (*it)->nChainWork > pindex->nChainWork; it++) {
1375+            if ((*it)->GetAncestor(pindex->nHeight) == pindex) {
1376+                // pindex is useless - even if there are other tips based on it
1377+                // which we want in setBlockIndexHeaderCandidates, we're not
1378+                // gonna find them here.

practicalswift commented at 8:47 pm on October 30, 2018:

“going to find them here.” :-)

in src/validation.cpp:1329 in bdaf9f9693

1324+ * headers above the tip leading down different chains, for which we really
1325+ * only want to keep the tip of each chain.
1326+ *
1327+ * Works even if chainActive is empty!
1328+ *
1329+ * If chain_ordered_inertion, we assume that if pindex->pprev was previously a

practicalswift commented at 8:47 pm on October 30, 2018:

Should be insertion?

in src/validation.cpp:128 in bdaf9f9693

125+     * because we prefer to also download towards chains which have the same total work as our current
126+     * chain (as an optimization since a reorg is very possible in such cases).
127+     *
128+     * Note that, unlike setBlockIndexCandidates, we only store "leaf" entries here, as we are not as
129+     * aggressively prune-able (setBlockIndexCandidates are things which we can, and usually do, try to
130+     * connect immediately, and thus entries dont stick around for long). Thus, it may be the case that

practicalswift commented at 8:49 pm on October 30, 2018:

“Don’t” :-)

in src/validation.cpp:3700 in bdaf9f9693

3710+                parent_of_min_chainwork_header_candidate = true;
3711+                break;
3712+            }
3713+        }
3714+    }
3715+    if (!fHasMoreOrSameWork && !parent_of_header_candidate) return true; // We dont think this block leads somewhere interesting

practicalswift commented at 8:49 pm on October 30, 2018:

“Don’t” :-)

Sjors commented at 10:58 am on November 30, 2018: member

Abandoning for now. Consider it up for grabs, but I suggest getting concept ACKs before trying to rebase.

Sjors closed this on Nov 30, 2018

fanquake added the label Up for grabs on Nov 30, 2018

ryanofsky commented at 4:30 pm on December 3, 2018: member

Since this is marked up for grabs, it might be useful to say what motivations for this change are.

It looks like it was brought up in IRC on 12/1 in the context of “SPV sync” but the relationship seems unclear. (I believe “SPV sync” refers to downloading blocks out of order during initial sync so wallet can show unvalidated transactions and be usable before the sync finishes.)

Sjors commented at 9:55 am on December 4, 2018: member

@ryanofsky it started out here: #9483 (comment), so just one step to make it easier to sync headers and fresh blocks first, and then catch up on historical blocks later.

MarcoFalke locked this on Sep 8, 2021

Track best-possible-headers (TheBlueMatt) #13937

Conflicts