Light client reorg mechanism

[hwwhww]

Follow-up of #2147 (comment):

@vbuterin:

I think the light client being capable of reorging is reasonable. Definitely an okay response especially in cases of high network latency.

This is making me realize that it would take some cleverness to make light clients capable of reorging. Here is one rough proposal. The LightClientStore keeps track of a series of heads, which must always satisfy the following invariants:

• store.heads[0] must be finalized (if we want, if a block has been part of store.heads for >= 24 hours we can "finalize" it locally)
• store.heads[n+1] must be a descendant of store.heads[n]
• vote_count(store.heads[n+1]) < vote_count(store.heads[n])

Essentially, it is the client's best guess of the current chain, with confidence naturally decreasing as you get closer to the tip.

When a client receives a light client update, the update must reference an ancestor that is in store.heads. The update must satisfy the properties:

1. votes(update.block) < votes(update.ancestor)
2. update.ancestor == store.heads[-1] or votes(update.block) > votes(store.heads[store.heads.index(update.ancestor) + 1])

In other words, it must be a better alternative than whatever block it is replacing. If the update is accepted, then all elements from store.heads after update.ancestor are removed, and update.block is added to the end.

[ralexstokes]

I think it is fine (as I believe @djrtwo mentioned) we can make a note in the current doc that this version of the light client prefers to track the finalized chain (at the cost of having the most up-to-date chain state). And then in another PR, we can add an extension to the light client that implements the the ability to track the best head seen -- the above sketch from @vbuterin seems like a great place to start!

[djrtwo]

Yeah, so I think we should have two types of light clients (at least) -- one that is very simple and just follows finality updates, and one that can follow the head and reorg if needed. The former would likely be what we'd see in cross-chain bridges and/or the eth1 beacon chain light client contract.

---

Is votes the LMD-GHOST vote count? I assume so because of vote_count(store.heads[n+1]) < vote_count(store.heads[n]).

Now that I think about it, I'm worried the algorithm proposed above can get stuck (until new finalized).

• light client sees block P with ~100% sync committee vote
• then sees block A (child of P) with ~33% sync committee vote [new head]
• then sees block B (also child of P) with ~66% sync committee vote [new head]
• then block A' (child of A) is built and begins to win favor over B with normal fork choice, so sync committee moves back and is near 100% on it. If A' is given to the light client, it can't switch back to this branch because it would first have to switch to A which can't beat out B. That is unless A and A' can be batch updated to show a cumulative higher weight. Even then you would definitely need to bring in a notion of LMD or it could still get stuck on the orphaned side of two equal branches.

[ralexstokes]

I interpret both vote_count and votes above as just the sum of the sync_committee_bits in a given block.

Yeah, it does seem that the light client would get stuck under the scenario you give under the above rules.

I see two options:

1. Add some interactive protocol at the network level to let a light client fetch missing ancestors. In this case, the light client above would fetch A upon receiving the majority update to A' and not finding A in its store. It could then compute the higher weight and switch to A'.
2. Provide a sync committee proof from the finalized block (as we know the light client trusts this one) to the new head, in the event of a re-org. This route is non-interactive but implies efficient light client servers will be tracking which light clients have seen which states of the chain (as you can get away w/ the above rules if there is no re-org).

Some variation here involves the light server providing an update to a block (A') with an unknown ancestor (A) and then upon getting an error response from the light client, turn around and serve the proof of the full chain like in (2). Much like a "force push" in git.

[vbuterin]

then block A' (child of A) is built and begins to win favor over B with normal fork choice, so sync committee moves back and is near 100% on it. If A' is given to the light client, it can't switch back to this branch because it would first have to switch to A which can't beat out B.

Ah, maybe I was not being clear enough. A' would be able to compete with B directly. There's no requirement that heads[n+1] must be a direct child of heads[n].

[djrtwo]

Yeah okay, I missed that.

One complication in a server being able to serve such requests is that they need to know two things

1. That light-client is on another branch and thus need to generate a proof from some prior block
2. To know at least a single block in lightclient's tree so that they may construct a proof from it (thus convince you that they are sending an ancestor for your local view)

(1) can be satisfied with some sort of Status network message saying the light-client's head.

As for (2), a simple Status saying the head wouldn't suffice because it doesn't give the server info on which prior block in the chain it can make a fork proof on. It could say or imply what your latest finalized root is. The server could construct the reorg proof(s) from there. It would be a single proof if it didn't need to walk through a committee update(s) in the middle. Otherwise would need to be one per committee update.