light-client: Verification fails for target height between two trusted heights

[kostko]

Imagine the light store contains two trusted light blocks at heights H1 and H2 (where H2 > H1). Attempting to verify a light block at height V that falls between H1 and H2 (e.g., H1 < V < H2) will incorrectly fall back to backwards verification and in case the unstable feature is not enabled, it will incorrectly fail with the target_lower_than_trusted_state error.

Given that both H1 and H2 are trusted, there is actually no reason to need backwards verification in this case as it should be enough to start at H1 and perform the usual bisection verification algorithm. It seems this is also what the Go implementation does.

The Rust implementation does not seem to have a nicely-contained implementation of bisection, but it instead relies on the light block store for tracking the "highest trusted light block" and all the various places are querying it.

My proposal for implementing this with minimum disruption is to add two methods to the LightStore trait, namely:

    /// Get the light block of greatest hight before the given height with the given status.
    fn highest_before(&self, height: Height, status: Status) -> Option<LightBlock>;

    /// Get the first light block before the given height with the trusted or verified status.
    fn highest_trusted_or_verified_before(&self, height: Height) -> Option<LightBlock>;

Where the second method is provided as a default implementation on the LightStore trait (similar to the other ones).

Then only slight modifications are needed to the stores, light client and scheduler to make this work. I have a draft implementation of this in a local branch but need to figure out how to add some longer verification tests with the current framework.

[romac]

Good catch! Your proposal sounds good to me, so feel free to open a PR already and we can then discuss how best to test it. Thanks :)

[kostko]

@romac Added tests, please take a look.

In order for the failure to be evident with the unpatched code I needed to add a step in the test workflow that tests without the unstable feature as otherwise, with all features enabled, it would just enable backward verification and make the test appear to pass.