Filecoin bootstrapping proposal

[whyrusleeping]

Filecoin Bootstrapping Routine

Connect

If a node has never connected to the network before, They will need to connect to initial set of trusted peers. This will generally be a list of bootstrap peers from the config file, though each individual could come up with a set of peers they explicitly trust.

On successive connects, we can augment the ‘initial connect set’ with randomly selected peers remembered from the previous session.

Peer Set Expansion

Once connected into some portion of the network, a node will need to expand their peer set in order to get a good sample of the network. This can be accomplished many different ways, the simplest for us will be to use the DHT to do random ‘FindPeer’ requests.

Once the node is connected to a sufficiently diverse set of peers, they should then move on to chain selection.

Chain Selection

Sample what each of your peers thinks of as the latest chain head. If there are no significant disagreements (an insignificant disagreement would be if two peers have different heads, but one is the parent of the other, or some other similar ancestry chain) then that chain should be given to the syncer routine.

If there are disagreements, then the node should watch both chains for some time, syncing enough data to validate them moving forward, but not historically yet. After a ‘trial period’ has elapsed, the node should select the chain that has included valid proofs for the most storage. The other chain(s) should be marked as bad. The selected chain should be passed to the syncer, and the ‘initial sync’ should begin.

[sternhenri]

I think this is a very good place to start indeed. It's straightforward and strikes the appropriate balance in leaving appropriate things out of the spec (e.g. out-of-band work that will likely happen but we needn't directly account for yet).

Some pieces I think we may want to add here:

• Can you work to quantify "sufficiently diverse set of peers" with an initial heuristic/strategy?
  • Can we link the peers to some version of the power table for instance to ensure some significant peer coverage, for instance?
• Expand the section on chain selection with a current list of "insignificant disagreements" precisely stated, thereby also precisely defining significant ones (by exclusion).
  • I expect we would want to extend common parents to some depth beyond one.
  • Beyond doing forward validation in a 'trial period' in case of disagreement, would it make sense to introduce some notion of a threshold here: ie if all but one peer agrees on the chain, we move forward with that chain.
    • I reckon it is bad to do the above, but then perhaps you could state why you need unanimous consent on the chain state.
• Should we point to some potential peer repair in the future in the case where "chain(s) are marked as bad?" Potentially could help them fix state or put them on some sort of blacklist for a bit of time (assuming we decide to augment the random 'find peer' process)

[whyrusleeping]

@sternhenri thanks for the feedback! I’ll try and address that soon.

Also, i realize that I keep making new issues for everything, but this is really a continuation of
filecoin-project/research#49

[ZenGround0]

the node should select the chain that has included valid proofs for the most storage

I think this is key to provide stronger guarantees against proof-of-stake style "posterior corruption attacks" and think it is the right direction.

I think this needs to be co-designed with the weighting function / finality rules, i.e. the chain selection rule during syncing "caught up mode". For example there is little point syncing to the chain with the most storage during bootstrap if the syncing protocol will immediately switch to a different chain once it is caught up.

Calling out a specific issue: the benefits of bootstrapping off of chains with more storage should be balanced carefully against the possibility of an attacker temporarily flooding a fork with storage to cause an attacker chain to reorg (and double spend for example). In my paranoia I can image a situation where an attacker assembles coalitions of bootstrapping nodes by adding epsilon more storage than the main chain on a fork. It's not obvious to me that this attack is that hard (depends on bounds on rate of change of storage on the main chain, and bounds on number of bootstrapping nodes and the latency between bootstrap and mining).

[whyrusleeping]

In my paranoia I can image a situation where an attacker assembles coalitions of bootstrapping nodes by adding epsilon more storage than the main chain on a fork.

Yeah, thats definitely something to worry about. A mitigation here though is that PoSts are bound to a specific chain (due to challenge reseeding). If an attacker is attemping to have more storage proofs on their fork, they will need to have more storage than the rest of the network combined, not just increase the total storage on their fork over the total storage in the main chain.

[whyrusleeping]

@tomaka is experimenting with Brahms for peer discovery: https://gnunet.org/sites/default/files/Brahms-Comnet-Mar09.pdf
This could be very useful for the 'peer set expansion' phase (probably more secure than relying on kademlia)

[sternhenri]

If an attacker is attemping to have more storage proofs on their fork, they will need to have more storage than the rest of the network combined, not just increase the total storage on their fork over the total storage in the main chain.

Can you elaborate on this @whyrusleeping I don't understand this.

This entire discussion makes me believe our weighting conclusion from research week (filecoin-project/consensus#27) is kind of off. We do need to include power in the chain as part of the weight function, but as we discussed this opens a huge can of worms.

Can we maybe take this as an opportunity to go over the weighting function as currently done in the spec?

[whyrusleeping]

@sternhenri

After a ‘trial period’ has elapsed, the node should select the chain that has included valid proofs for the most storage.

I should clear this up, but by this i mean: the node should select the chain for which they have seen the most new PoSts appear during their wait. Given a wait period of ~1 proving period, they should see PoSt submissions for all the active storage committed to each chain. I'm not saying just to look at the total power in each chain as reported by the storage market actor.

[whyrusleeping]

relevant: filecoin-project/consensus#41

@sternhenri and I also discussed that it makes more sense for the person joining the network to simply select the chain with the highest weight at the end of 'waiting' period instead of looking at new PoSt proofs. (assuming we fix the weighting function as described above)

[sternhenri]

@whyrusleeping, related to our conversation from yesterday.

In much the same way that we would want weight to be the source-of-truth for chain selection both at joining time and stable state, we would conversely want some peer discovery/update process (that you proposed above for joining) in stable state.

All of the following assumes bootstrapping has you find at least one honest peer, and seeks to ensure that you maintain one honest peer at all times thereafter, protecting you from eclipse attacks.

I am thinking something like this:

• v0 (what we have right now): peers just keep their set of peers from bootstrapping and update the set as peers drop off through random peer discovery.
  Assuming you have at least one honest peer, chain weight should mean you are selecting the appropriate chain to mine off of. However that peer could disconnect (or you could get eclipsed).

• v1 (proposal): each peer in your peer-set is associated to a timestamp (for when you peered) and gets cycled out of your peer-set on some expiration time (round robin) and replaced by a randomly found peer. This hopefully has us find some eclipse resolution after some set duration.

• v2 (proposal): same as v1, but we include an option to put in a negative timestamp to signal non-expiring (trusted peers). As other nodes expire we alternate between drawing a new peer from the random set, and having trusted peers pass off one of their own peers. The set of trusted peers does not grow.
  These could be set by the user, but PL Fil-implementations ship with a couple of default "trusted nodes" run by say Filecoin foundation or other network-trusted actors to ensure there are always sources of honest nodes available. This is an implementation default that can be changed.

[sternhenri]

Also I question whether we still need the "waiting" period assuming we have a functional weight function and good peer discovery process

[whyrusleeping]

some amount of this has been added in #151

[whyrusleeping]

closed by #196