sync: Implement backwards sync

[renaynay]

What is backwards syncing

Backwards syncing would allow the syncer to subjectively initialise and then sync backwards sequentially from subjectiveHead.Height down to header at height 1

Design

This issue serves as a placeholder for what should be a more descriptive design of backwards syncing.

Issue breakdown

(go-header)

• syncer (hard)
  • skip verification from subjectiveHead --> networkHead to verify netHead as valid sync target (potentially using bifurcation from tendermint light)
  • backwards sync down from subjectiveHead --> storeHead (head of contiguous chain)
    • this still needs robustness design such that it can handle syncing gaps of the chain that might be missing (for example, [50:100] can be flushed to store and then node shuts down, how does syncer understand it still needs to sync (0:50)?)
  • able to accept incoming network heads with forward adjacent verification
• store (breaking - hard)
  • must be able to apply headers backwards (remove forwards-adjacency requirement from store.Append)
  • breaks heightsub completely (TODO - audit what is touched by heightsub in terms of assumption)
  • ability to init store from a subjective head instead of genesis height
• p2p/exchange (breaking - easy)
  • GetVerifiedRange will need to be able to verify backwards instead of forwards (shouldn’t be too difficult, but will require refactoring the method itself since now requests will be done such that:
GetRangeByHeight(ctx context.Context, from H, to uint64) such that from.Height() > to.
Method signature can stay the same but underlying behaviour will break as it will request + verify backwards, so it is breaking.
• verify.go
  • Verify needs to be able to accept an untrusted header of height trusted.Height()-1 and verify it backwards (easy) -- can be done by adding a switch case inside Verify to check whether it’s forwards adjacent, backwards adjacent, or skipping verification (forwards non-adjacent)

(celestia-node ?)

• ensure that any components that rely on store's heightsub implementation can be modified around the new store non-adjacency design

Implications

Backwards sync will:

• do away with unnecessary verification logic that is only needed during forward syncing
• eliminate the need for the fork-following prevention solution introduced in feat(sync): Implement a subjectiveHead atomic pointer on the node to use #108
• require the header store to drop the adjacency requirement for insertions
• etc. etc. etc.