Headers-first synchronization by sipa · Pull Request #4468 · bitcoin/bitcoin

sipa · 2014-07-05T23:09:10Z

Here's a first (well, second) version of a fully-functional headers-first synchronization.

Many changes:

Do not use 'getblocks', but 'getheaders', and use it to build a headers tree.
Blocks are fetched in parallel from all available outbound peers, using a limited moving window. When one peer stalls the movement of the window, it is disconnected.
No more orphan blocks. At all. We only ever request a block for which we have verified the headers, and store it to disk immediately. This means that a disk-fill attack would require PoW.
Some new fields in getpeerinfo:
- 'syncheight': the height up to which we've validated this peer's headers.
- 'commonheight': the height up to which we have all blocks in common with this peer.
- 'inflight': the heights we're currently requesting from this peer.
Require protocol version 31800 for every peer (released in december 2010).
No more syncnode (we sync from everyone we can, though limited to 1 during initial headers sync).
Introduce some extra named constants and comments.
Reindexing support for out-of-order blocks on disk.

gmaxwell · 2014-07-06T04:34:38Z

While syncing with this code from a pair of local peers:

2014-07-06 04:26:28 UpdateTip: new best=000000001ee1d3053357a374d6d9746e80d56a666f3827c92e80e0d1b3f2f2a1 height=1888 log2_work=42.883429 tx=1917 date=2009-01-26 03:
21:12 progress=0.000023
2014-07-06 04:26:28 nActualTimespan = 942027 before bounds
2014-07-06 04:26:28 GetNextWorkRequired RETARGET
2014-07-06 04:26:28 Params().TargetTimespan() = 1209600 nActualTimespan = 942027
2014-07-06 04:26:28 Before: 1a016164 0000000000000161640000000000000000000000000000000000000000000000
2014-07-06 04:26:28 After: 1a011337 000000000000011337c4f5c28f5c28f5c28f5c28f5c28f5c28f5c28f5c28f5c2
2014-07-06 04:26:28 ERROR: AcceptBlock() : prev block not found
2014-07-06 04:26:28 ERROR: ProcessBlock() : AcceptBlock FAILED
2014-07-06 04:26:28 Misbehaving: 192.168.42.76 (0 -> 10)
2014-07-06 04:26:28 UpdateTip: new best=00000000bf3fc4c4ab6737df907f613b5aa86373d426b5e86a1009030852f129 height=1889 log2_work=42.884193 tx=1918 date=2009-01-26 03:26:22 progress=0.000023

(not the Misbehaving)

Also, it seems to only be pulling from one so far:

{
    "addr" : "192.168.42.76",
    "services" : "0000000000000001",
    "lastsend" : 1404621016,
    "lastrecv" : 1404621016,
    "bytessent" : 7131512,
    "bytesrecv" : 131870355,
    "conntime" : 1404620769,
    "pingtime" : 0.07961100,
    "version" : 70002,
    "subver" : "/Satoshi:0.9.99/",
    "inbound" : false,
    "startingheight" : 309423,
    "banscore" : 10,
    "syncheight" : 309424,
    "commonheight" : 113772,
    "inflight" : [
        113773,
        113774,
        113775,
        113776,
        113777,
        113778,
        113779,
        113780,
        113781,
        113782,
        113783,
        113784,
        113785,
        113786,
        113787,
        113788
    ]
},
{
    "addr" : "192.168.42.87",
    "services" : "0000000000000001",
    "lastsend" : 1404621015,
    "lastrecv" : 1404621009,
    "bytessent" : 1442,
    "bytesrecv" : 2342,
    "conntime" : 1404620769,
    "pingtime" : 0.04079200,
    "version" : 70002,
    "subver" : "/Satoshi:0.9.99/",
    "inbound" : false,
    "startingheight" : 309423,
    "banscore" : 0,
    "syncheight" : -1,
    "commonheight" : -1,
    "inflight" : [
    ]
}

It started pulling from it eventually, perhaps when a block came in?

gmaxwell · 2014-07-06T05:13:47Z

2014-07-06 04:38:07 Leaving block file 0: CBlockFileInfo(blocks=119950, size=134216038, heights=0...309426, time=2009-01-03...2014-07-06)
2014-07-06 04:38:37 Leaving block file 1: CBlockFileInfo(blocks=11284, size=134206314, heights=119942...131232, time=2011-04-24...2011-06-16)

The first range looks wrong. :)

sipa · 2014-07-06T07:46:44Z

@gmaxwell The 'prev block not found' should be fixed; there is a code path to fetch blocks directly (ignoring the headers-based fetching), in case we're very close to being synced (to avoid an extra roundtrip for newly inv'ed blocks)... but the time comparison used < instead of >.

gmaxwell · 2014-07-06T13:45:11Z

3hr 46 minute resync over the network here. I'm a bit confused that the ping time to the two peers I was pulling from was still >10 seconds even when the sync was well into the cpu bound part (for their own part, the peers were fairly low on cpu utilization).

sipa · 2014-07-06T15:57:40Z

4h21m here, from random peers, and default dbcache.

laanwj · 2014-07-07T05:04:53Z

Woohoo!
Testing...

rebroad · 2014-07-07T05:30:12Z

src/main.cpp

Why wait until a complete block is received before marking it as not stalling? Wouldn't it be better to consider it as not stalling as long as a block is being downloaded (even if it takes a while on a slow connection)?

"Stalling" is already a rather strong condition: it means all blocks in
flight are from a single peer, and we can't ask any peer for other blocks
because they are outside the download window. It does not just mean that
we're not receiving anything from this peer, it means we can't download
anything from anyone because of this peer. The 2 second delay before
actually connecting is to give us some chance to act on blocks that were
already received while we were busy.

That said, this is certainly not perfect. We'll need some tracking of
peers' speed and latency to adjust window sizes, for example. I really just
want something that reasonably well in now.

laanwj · 2014-07-07T10:55:51Z

Synced in 3:43 here, and with lots of other things running on the same computer.

I do get this error when running with -checkblocks=0 -checklevel=4 afterwards (after shutting down with 'stop'):

2014-07-07 10:48:02 Verifying last 309612 blocks at level 4
2014-07-07 10:48:03 ERROR: ReadFromDisk : Deserialize or I/O error - CAutoFile::read : end of file
2014-07-07 10:48:03 ERROR: VerifyDB() : *** found bad undo data at 309606, hash=000000000000000013e7146f5a1f63a188935bedc491b8b5bf5ab823f6ec0d9c

Oh I get the same without any checklevel options. I'll keep this copy of the blocks data and database in case it's interesting for debuging.

sipa · 2014-07-07T12:22:45Z

src/main.cpp

We already download every block that peers advertize. In PR changes it to
first ask for headers, and only asks for the block immediately if we're
close to being synced. Validating the header first would require an extra
roundtrip, which can hurt network propagation time.

sipa · 2014-07-08T15:04:36Z

Changed the code to use block-first-seen rather than header-first-seen to distinguish between equal-work branches.

sipa · 2014-07-11T15:37:00Z

Rebased on top of #4496 and #4497 (which were already included here).

sipa · 2014-07-11T22:23:29Z

Moved RPC changes to a separate commit (now the actual headers-first commit is a net negative in lines, while adding comments!).

gmaxwell · 2014-07-14T13:10:48Z

Needs rebase.

sipa · 2014-07-14T14:21:14Z

Rebased.

laanwj · 2014-07-15T06:52:53Z

I retried my testing, now with a non-corrupting destination, and found no issues. I tickled it in various ways with -checklevel -checkblocks and it completed fine.

rebroad · 2014-07-16T10:34:21Z

Ok, I have a thought/question. With this pull, won't it effectively mean that the average height of the average node be less than without this pull? I.e. detrimental to the bitcoin network?

gmaxwell · 2014-07-16T11:55:26Z

@rebroad I can't figure out why you'd think that. Once synchronized the heights of all nodes will be the best available to them, and this change makes the system synchronize much faster.

rebroad · 2014-07-17T10:51:36Z

It's not the headers first aspect that makes them sync faster but rather the use of concurrent block downloads. The getting of headers first and the downloading of blocks that aren't necessarily in the best chain will delay nodes getting up to date.

laanwj · 2014-07-17T11:04:36Z

I'm not convinced by your claim @rebroad. Let's look at the evidence here: with this code, new nodes get up to speed much faster. With a decent internet connection this is scarcely longer than a -reindex would take. I don't see one single case of a user reporting that this makes a node get up to date slower.

gmaxwell · 2014-07-17T11:48:46Z

@rebroad Part of the whole point is that it can use the headers to determine the best chain (with very high probability— only invalidated if the majority hashrate chain is invalidated) very fast, then it only downloads blocks in the best chain. New blocks at the tip are downloaded like they've always been.

laanwj · 2014-07-17T11:51:12Z

Right, this mostly avoids downloading blocks not on the best chain unlike before. No more orphans...

sipa · 2014-10-14T23:37:58Z

I added a commit that AFAICT should allow >2000 deep reorgs. I tried to enable the reorg test in Travis, but that fails due to >4Mbyte of produced log.

laanwj · 2014-10-17T08:48:57Z

Tested ACK

gmaxwell · 2014-10-17T08:56:25Z

Tested ACK.

I've reviewed this at many points in time and tried many cases (and hit a number of issues which have been fixed). I expect that it still has some remaining bugs, but our behavior without it is almost uselessly bad in the common case... getting some wider usage (in master) will help shake out issues. We know we're going to have a long cycle of testing in master on this version, so lets get that started.

ghost · 2014-10-17T09:41:44Z

Seems to function fine on ARMv6.

e11b2ce Fix large reorgs (Pieter Wuille) afc32c5 Fix rebuild-chainstate feature and improve its performance (Pieter Wuille) 16d5194 Skip reindexed blocks individually (Pieter Wuille) ad96e7c Make -reindex cope with out-of-order blocks (Wladimir J. van der Laan) e17bd58 Rename setBlockIndexValid to setBlockIndexCandidates (Pieter Wuille) 1af838b Add height to "Requesting block" debug (R E Broadley) 1bcee67 Better logging of stalling (R E Broadley) 4c93322 Improve getheaders (sending) logging (R E Broadley) f244c99 Remove CheckMinWork, as we always know all parent headers (Pieter Wuille) ad6e601 RPC additions after headers-first (Pieter Wuille) 341735e Headers-first synchronization (Pieter Wuille)

rebroad · 2016-11-06T09:10:26Z

src/main.cpp

+
+        if (nCount == MAX_HEADERS_RESULTS && pindexLast) {
+            // Headers message had its maximum size; the peer may have more headers.
+            // TODO: optimize: if pindexLast is an ancestor of chainActive.Tip or pindexBestHeader, continue


continue form "there"? there being chainActive.Tip() or pindexBestHeader?

ah, I get it... ok, coding this...

pindexBestHeader Needed since bitcoin#4468

sipa mentioned this pull request Jul 6, 2014

Fix a bug in CChain::GetLocator #4470

Merged

sipa mentioned this pull request Jul 6, 2014

Use pong receive time rather than processing time #4472

Merged

rebroad reviewed Jul 7, 2014
View reviewed changes

sipa reviewed Jul 7, 2014
View reviewed changes

sipa mentioned this pull request Jul 9, 2014

Bugfix: only remove actualy failed blocks from setBlockIndexValid #4496

Merged

rdponticelli mentioned this pull request Jul 11, 2014

Add a switch to allow running in a pruned state #4481

Closed

laanwj added this to the 0.10.0 milestone Jul 14, 2014

sipa force-pushed the headersfirst8 branch from f38f7af to fe0f332 Compare October 14, 2014 22:42

Fix large reorgs

e11b2ce

sipa force-pushed the headersfirst8 branch from fe0f332 to e11b2ce Compare October 14, 2014 23:16

laanwj merged commit e11b2ce into bitcoin:master Oct 17, 2014

This was referenced Oct 17, 2014

Bitcoin Headers First Patch bitcoin-abe/bitcoin-abe#149

Open

Bitcoin Headers First Patch bitpay/insight-api#210

Closed

btcdrak mentioned this pull request Oct 26, 2014

As of Bitcoin Core 0.10, block database can be out of order CounterpartyXCP/counterparty-core#374

Closed

sipa mentioned this pull request Apr 17, 2015

Add a -maxoutbound option for use on pool servers to increase bitcoin network connectivity. #6014

Closed

maflcko mentioned this pull request Sep 4, 2015

Introduce -maxuploadtarget #6622

Merged

Cryptoslave mentioned this pull request Mar 6, 2016

Initial Block Download (IBD) issues - Important! Anoncoin/oldrepo-backup#97

Closed

rebroad reviewed Nov 6, 2016

View reviewed changes

rebroad mentioned this pull request Nov 6, 2016

Optimize sending of getheaders when pindexLast is an ancestor of pindexBestHeader #9091

Closed

rebroad added a commit to rebroad/bitcoin that referenced this pull request Nov 7, 2016

Optimize sending of getheaders when pindexLast is an ancestor of

6d2b1ea

pindexBestHeader Needed since bitcoin#4468

sesam mentioned this pull request Jan 18, 2018

Add header-first block propagation mimblewimble/grin#257

Closed

hebasto mentioned this pull request Dec 19, 2019

p2p: GetBlocks message response #17776

Closed

Conversation

sipa commented Jul 5, 2014

Uh oh!

gmaxwell commented Jul 6, 2014

Uh oh!

gmaxwell commented Jul 6, 2014

Uh oh!

sipa commented Jul 6, 2014

Uh oh!

gmaxwell commented Jul 6, 2014

Uh oh!

sipa commented Jul 6, 2014

Uh oh!

laanwj commented Jul 7, 2014

Uh oh!

rebroad Jul 7, 2014

Choose a reason for hiding this comment

Uh oh!

sipa Jul 7, 2014

Choose a reason for hiding this comment

Uh oh!

laanwj commented Jul 7, 2014

Uh oh!

sipa Jul 7, 2014

Choose a reason for hiding this comment

Uh oh!

sipa commented Jul 8, 2014

Uh oh!

sipa commented Jul 11, 2014

Uh oh!

sipa commented Jul 11, 2014

Uh oh!

gmaxwell commented Jul 14, 2014

Uh oh!

sipa commented Jul 14, 2014

Uh oh!

laanwj commented Jul 15, 2014

Uh oh!

rebroad commented Jul 16, 2014

Uh oh!

gmaxwell commented Jul 16, 2014

Uh oh!

rebroad commented Jul 17, 2014

Uh oh!

laanwj commented Jul 17, 2014

Uh oh!

gmaxwell commented Jul 17, 2014

Uh oh!

laanwj commented Jul 17, 2014

Uh oh!

sipa commented Oct 14, 2014

Uh oh!

laanwj commented Oct 17, 2014

Uh oh!

gmaxwell commented Oct 17, 2014

Uh oh!

ghost commented Oct 17, 2014

Uh oh!

rebroad Nov 6, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

rebroad Nov 6, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

13 participants

rebroad Nov 6, 2016 •

edited

Loading

rebroad Nov 6, 2016 •

edited

Loading