Take as the desideratum of our lite client commit verification algorithm that for it to be the case that a lite client which checks in at least once per unbonding period is successfully fooled, it must necessarily be the case that a certain fraction of bonded or unbonding stake has committed an equivocation and will be punished if the lite client publishes that equivocation to the chain. ("fooling a lite client is always costly")

As I understand it, the current mechanism by which our lite client verification algorithm bisects headers, checks the difference in validator sets, and skips intermediary header verification violates this property: it is possible, in certain cases with sufficient validator set flux, for a portion of stake to successfully fool a lite client at zero cost.

Consider the following example:

A Tendermint chain started at block 0 and is currently at block 20, with all blocks within a single unbonding period. At block 10, the chain had some validator set V_10, and at block 20 the chain had some validator set V_20. There is less than 1/3 overlap between V_10 and V_20 - i.e., in between blocks 10 and 20, the validator set has changed by 2/3.

Consider a lite client with the correct root-of-trust for block 10, now connecting to a full node and trying to verify the state at block 20 using the bisection optimization.

An honest full node will report V_20 correctly and the lite client will notice that the validator set has changed by a sufficient amount, request intermediary headers, and check that the appropriate next-validator-set hashes were signed.

However, a dishonest full node working in conjunction with 2/3 of the validator set of block 10 can instead report V'_20 where V'_20 overlaps with V_10 by 2/3. The lite client will calculate that the validator set has changed by less than 1/3, not request intermediary headers, and accept whatever state root V'_20 signed.

The lite client can now be costlessly fooled - V'_20 can sign whatever it wants, without committing any equivocation at all, since at least 2/3 of V'_20 aren't actually bonded at block 20!

I haven't read all the lite client code, so this might not be exactly correct, but I think this class of attack works for any case where the lite client skips intermediary header verification by checking validator set overlap and where a now-unbonded fraction of a validator set of an earlier block could sign a later block header without committing an equivocation.

The only way I see to preserve the safety of bisection is to slash validators for signing headers while unbonding - Tendermint would need to track validators in the unbonding state, and if any signature of a header of a height when they were in that state is discovered (not necessarily a double-signature, any signature at all), Tendermint must consider that a slashable fault and report it to the state machine for punishment (presumably equivalent to punishment for regular equivocation).

As a short term quick fix, we could also disable lite client bisection and verify all headers.

cc @ebuchman @jaekwon @sunnya97