Hello protocol and practical secure bootstrapping

[anorth]

When a new node joins a network it must determine the head of the chain which it will download and validate, before it has a validated chain to test against (obviously). Downloading, and especially validating, are a significant amount of work so it's highly desirable to pick the "right" chain, at least up to a point fairly close to the consensus head. After syncing up to "pretty close", a node can sync all chains branching after that point.

The spec provides for the Hello protocol, in which nodes exchange a single head tipset key and heightweight once upon connection, and a chain syncing protocol which can traverse backwards from some head (in flux, see #461). [Edit: I think the change from height to weight must be recent, and makes the below even more difficult].

While most of the policy here should be left to implementations, they can only work with what the protocol provides. A simple approach (for illustration) might be to take the chain specified by a majority of a trusted set of peers. However, since the chain moves, these peers will disagree about the very tip of the chain quite often, despite good behaviour; blocks take some time to propagate across the network, may be withheld temporarily, and nodes may temporarily disagree on the contents of the head tipset. Discovering and querying a large set of peers will take some time, during which the chain will move on, so later peers will almost certainly disagree with earlier ones, despite in fact having the same chain.

This all makes a simple majority painful to determine. With the spec as-is, implementations must do something like attempt to fetch some head length of the chain from each peer (despite being unable to fully validate it) and seek a consensus at some earlier block height.

Some proposals:

• Quantize the tipset reported in Hello, e.g. to an exact multiple of 10 blocks. This would cause well-behaved nodes to agree exactly most of the time
• Report multiple tipsets in Hello, e.g. head, a quantized head - 10, and quantized head - 100
• Some explicit notion of finality and/or checkpoints past which nodes will not accept a re-org, and then sync (or state-fetch) that finality-horizon or checkpoint before then syncing all chains after that point.

I'm open to all of these being rejected in favour of the implementation-complex but spec-simple method of concurrently syncing unvalidated chain segments from many peers.

Note that this issues is (trying to be) only about determining which tipset to sync a full chain from, not actually fetching it. After using, say, some trusted bootstrap nodes to determine a head, a node should then fetch the blocks from random peers to avoid DOSing the bootstrap nodes.

For background see some discussion in #106 and https://github.com/filecoin-project/specs/pull/196/files (mostly since reverted as being too prescriptive on implementations)

[jbenet]

noting that in lists like this, reporting back tipsets at log intervals (log_2 or log_10) is a good choice.

<tipset at head>
<tipset at last quantized head>
<tipset at quantized head - 10>
<tipset at quantized head - 100>
<tipset at quantized head - 1,000>
<tipset at quantized head - 10,000>
<tipset at quantized head - 100,000>
<tipset at quantized head - 1,000,000>
...
<genesis>

[jbenet]

or to make it easier to calculate, can use the block epoch and zero out places, from most specific to least specific. it's a log list, but at rounded intervals.

<tipset at epoch #1,891,353> # head tipset
<tipset at epoch #1,891,350> # <10 away
<tipset at epoch #1,891,300> # <100 away
<tipset at epoch #1,891,000> # <1,000 away
<tipset at epoch #1,890,000> # <10,000 away
<tipset at epoch #1,800,000> # <100,000 away
<tipset at epoch #1,000,000> # <1,000,000 away
<genesis>

a binary-friendly version of this could use bit masks, and base 16, instead of base 10. (base16 because it's much faster/shorter list than base2). easier to compute, though a bit harder for humans

<tipset at epoch 0x1CDC19> # head tipset
<tipset at epoch 0x1CDC10> # <16 away
<tipset at epoch 0x1CDC00> # <256
<tipset at epoch 0x1CD000> # <4,096 away
<tipset at epoch 0x1C0000> # <65,536 away
<tipset at epoch 0x100000> # <1,048,576 away
<genesis>