Prepare block connection logic for headers-first

sipa commented at 7:36 pm on December 8, 2013: member

This is a preparation for headers-first, which is on itself useful, but doesn’t change the downloading or verification semantics yet.

It does change how the block connection logic works: it always makes sure the oldest valid chain with most work is connected. Instead of doing a “connect the received block now” atomically during process of that block, there is just a generic loop that disconnects and connects block to aim for the assumed best chain - reverting if necessary.

Let’s see if pulltester likes this…

laanwj commented at 6:18 am on December 11, 2013: member

I’ve synced both the testnet and mainnet chain with this patch applied (from the network), I’ve had no problems, and no apparent difference in speed.

sipa commented at 10:49 am on December 11, 2013: member

@laanwj It’s not being able to sync I’m worried about. It must however also deal well with invalid blocks and orphans. I’ll do a local pulltester run next weekend to see what goes wrong.

sipa commented at 2:38 pm on December 14, 2013: member

Rebased, and fixed two bugs that PullTester found (thanks, @TheBlueMatt!):

Blocks with potential corruption weren’t removed from mapAlreadyAskedFor, so they weren’t downloaded again.
When checking for a new most-work chain, only blocks that weren’t in the previous most-work chain were checked for errors, instead of all blocks that weren’t already active.

sipa commented at 9:39 pm on December 20, 2013: member

Can I have some reviews? @gavinandresen @laanwj @gmaxwell @jgarzik

in src/main.cpp: in 366987a1a9 outdated

4025@@ -4004,16 +4026,21 @@ bool SendMessages(CNode* pto, bool fSendTrickle)
4026         if (!lockMain)
4027             return true;
4028 
4029-        if (State(pto->GetId())->fShouldBan) {
4030+        CNodeState &state = *State(pto->GetId());

laanwj commented at 9:45 am on December 21, 2013:

You’re dereferencing a pointer and putting it into a reference, making it impossible to check for NULL, which can be returned from State(). Could this ever be an issue?

sipa commented at 4:46 pm on December 22, 2013:

The main-specific node state is created when a CNode is created, and destroyed when it is deleted (called from constructor and destructor). This means that for an existing CNode (pto in this case), state will always exist. When using a stored NodeId, the chance exists that it has been deleted in the mean time.

sipa commented at 4:48 pm on December 22, 2013: member

Update: mapBlockSource now also stores source information for orphan blocks. That means that we can potentially assign them a DoS score if their block is found to be invalid later on. It also means we can potentially send them a “reject” message for it.

sipa commented at 10:43 pm on December 23, 2013: member

Reverted to an older version… let’s see if pulltester likes it again :(

TheBlueMatt commented at 11:09 pm on December 23, 2013: member

Are you sure it’s not pull testers fault?

sipa commented at 11:14 pm on December 23, 2013: member

I think it is indeterminism. I’ve seen report 1, 6 and 8 blocks which differ. Maybe I was just lucky the first time that it worked as expected.

TheBlueMatt commented at 11:15 pm on December 23, 2013: member

doesn’t mean it’s not pull testers not broken… It certainly doesn’t take kindly to changing the download algorithm.

sipa commented at 11:19 pm on December 23, 2013: member

Right the now, the rule this branch should be following is that in case of multiple valid equal-work chains, the one where the tip block was received first is chosen.

TheBlueMatt commented at 11:26 pm on December 23, 2013: member

I’m not sure that that’s the same as master in all cases? though I doubt pull tester would identify the difference.

sipa commented at 11:30 pm on December 23, 2013: member

I’m not sure that’s the same as master either, though I can’t immediately comeup with a scenario where it differs.

The question is first: is this rule acceptable (imho, if it differs with the current behaviour, i prefer this clearer rule). If so, can we have pulltester tolerate it? :)

TheBlueMatt commented at 11:34 pm on December 23, 2013: member

If the rule is different on any more than non existent cases it’s a different network consensus which could be problematic. Ideally pull tester should identify any difference in network consensus unless we can come up with a proof that it can never matter.

sipa commented at 11:43 pm on December 23, 2013: member

Right, agree. Though it feels like we’re not actually understanding well enough what the behaviour of the current code is, in non-trivial reorganization cases. My intuition says that as long as you select one of the valid highest-pow chains, and there is no way to make a node switch to an equal-work chain when it already has one, we should always converge - but perhaps we need to think harder about that.

In any case, I like the rule “the earliest seen of all highest-pow valid chains”. Perhaps this needs to be discussed outside of this pullreq though.

TheBlueMatt commented at 0:03 am on December 24, 2013: member

Yes, no question this needs simulation and study. Until then, I’m not comfortable with any, even subtle, changes to the best chain selection.

laanwj commented at 7:52 am on December 24, 2013: member

Does headers-first download need a behavior change there, or is it just by accident and can it be corrected?

sipa commented at 8:04 pm on December 25, 2013: member

@laanwj I’m pretty sure it’s possible to recreate the old behavior in a headers-first compatible implementation, but I’d rather not. I like having a clear rule about what the intended behavior is, and have that implemented.

After having thought a bit about this, this is a case where the old and new implementation differ, IIRC:

The following setup exists: A->B and A->C. Now an orphan E is announced (with unknown parent D that builds on B), D is requested, but in the mean time block F (building on C) arrives. We switch to chain A->C->F in any case, but if now D arrives, and E turns out to be invalid, the old implementation would remain on A->C->F, while the new implementation will switch to A->B->D as D arrived before F. I doubt this is the simplest scenario to trigger a difference, and it would surprise me if that was what PullTester observes.

I still like the “the earliest received of all valid maximal-PoW chains” rule, as it’s easy to implement and stateless. The current rules depend on what the current best chain is.

TheBlueMatt commented at 8:26 pm on December 25, 2013: member

Yes, actually I believe this (and similar cases) are what pull tester is tickling. The latest run tickles a few cases:

b8 is an invalid block built on an equal-work fork (b7). pull-tester expects to stay on b6 (the previous best chain), but this pull appears to switch to b7.
b11 is the same case with b11 being invalid in a different way (too much fee vs double-spend).
b13/b14 is:

0        //     genesis -> b1 (0) -> b2 (1) -> b5 (2) -> b6  (3)
1        //                                          \-> b12 (3) -> b13 (4) -> b14 (5)
2        //                                              (b12 added last)

Only b14 is invalid so pull tester expects to select b13 but this pull differs somehow (its not entirely clear from the logs what the difference is, and this one is very likely to be pull-tester responding incorrectly to getblocks/getheaders, confusing the download process to be confused)

sipa commented at 10:41 pm on December 25, 2013: member

Seems there was a bug in my code - the Comparator for CBlockIndex objects compared pb->nSequenceId with itself rather than with pa->nSequenceId. I remember fixing this bug before - perhaps I lost some git commit. Let’s see.

sipa commented at 10:56 pm on December 25, 2013: member

Ha…

TheBlueMatt commented at 11:05 pm on December 25, 2013: member

Works for me

sipa commented at 3:40 pm on December 27, 2013: member

Merged two commits, and added some comments.

Also some earlier changes, which got lost because they were commented on by @mikehearn in commits that have since been rebased:

Changed to a global sequence number for received blocks instead of a timestamp.
Removed interruption points that could result in a non-best-known-chain to be observed externally.

Move only: extract WriteChainState and UpdatedTip from SetBestChain. 0ec16f35d6

Prepare block connection logic for headers-first.

This changes the block processing logic from "try to atomically switch
to a new block" to a continuous "(dis)connect a block, aiming for the
assumed best chain".

This means the smallest atomic operations on the chainstate become
individual block connections or disconnections, instead of entire
reorganizations. It may mean that we try to reorganize to one block,
fail, and rereorganize again to the old block. This is slower, but
doesn't require unbounded RAM.

It also means that a ConnectBlock which fails may be no longer called
from the ProcessBlock which knows which node sent it. To deal with that,
a mapBlockSource is kept, and invalid blocks cause asynchronous "reject"
messages and banning (if necessary).

75f51f2a63

BitcoinPullTester commented at 9:35 pm on January 27, 2014: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/75f51f2a63e0ebe34ab290c2b7141dd240b98c3b for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

gavinandresen commented at 9:48 pm on January 29, 2014: contributor

ACK.

gavinandresen commented at 9:49 pm on January 29, 2014: contributor

Merging; got ACKs from me and @jgarzik in #3514

gavinandresen referenced this in commit 3581abdd46 on Jan 29, 2014

gavinandresen merged this on Jan 29, 2014

gavinandresen closed this on Jan 29, 2014

Bushstar referenced this in commit f2ece1031f on Apr 8, 2020

MarcoFalke referenced this in commit 7be143a960 on Aug 30, 2021

sidhujag referenced this in commit 16d4b8d9dc on Aug 30, 2021

DrahtBot locked this on Sep 8, 2021

Prepare block connection logic for headers-first #3370