Repository: informalsystems/tendermint-rs (language: rust)

Issue:
light-client: Verification fails for target height between two trusted heights
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](https://github.com/tendermint/tendermint/blob/49502dae92047cd1fa8cf3b6b2ba348fb6de8da3/light/client.go#L594-L602).

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:
```rust
    /// 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.


Discussion / hints:
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 :)

Fix patch:
diff --git a/.changelog/unreleased/bug-fixes/1246-verify-between-trusted.md b/.changelog/unreleased/bug-fixes/1246-verify-between-trusted.md
new file mode 100644
index 000000000..900eec65a
--- /dev/null
+++ b/.changelog/unreleased/bug-fixes/1246-verify-between-trusted.md
@@ -0,0 +1,3 @@
+- `[tendermint-light-client]` Fix verification of blocks between two trusted
+  heights
+  ([#1246](https://github.com/informalsystems/tendermint-rs/issues/1246))
diff --git a/light-client/src/components/scheduler.rs b/light-client/src/components/scheduler.rs
index 568784377..1d613a2ea 100644
--- a/light-client/src/components/scheduler.rs
+++ b/light-client/src/components/scheduler.rs
@@ -20,7 +20,7 @@ pub trait Scheduler: Send + Sync {
     ///
     /// ## Postcondition
     /// - The resulting height must be valid according to `valid_schedule`. [LCV-SCHEDULE-POST.1]
-    #[requires(light_store.highest_trusted_or_verified().is_some())]
+    #[requires(light_store.highest_trusted_or_verified_before(target_height).is_some())]
     #[ensures(valid_schedule(ret, target_height, current_height, light_store))]
     fn schedule(
         &self,
@@ -61,7 +61,7 @@ pub fn basic_bisecting_schedule(
     target_height: Height,
 ) -> Height {
     let trusted_height = light_store
-        .highest_trusted_or_verified()
+        .highest_trusted_or_verified_before(target_height)
         .map(|lb| lb.height())
         .unwrap();
 
@@ -105,7 +105,7 @@ pub fn valid_schedule(
     light_store: &dyn LightStore,
 ) -> bool {
     let latest_trusted_height = light_store
-        .highest_trusted_or_verified()
+        .highest_trusted_or_verified_before(target_height)
         .map(|lb| lb.height())
         .unwrap();
 
diff --git a/light-client/src/light_client.rs b/light-client/src/light_client.rs
index 3ebb58498..71dc8ccde 100644
--- a/light-client/src/light_client.rs
+++ b/light-client/src/light_client.rs
@@ -161,7 +161,8 @@ impl LightClient {
         // Get the highest trusted state
         let highest = state
             .light_store
-            .highest_trusted_or_verified()
+            .highest_trusted_or_verified_before(target_height)
+            .or_else(|| state.light_store.lowest_trusted_or_verified())
             .ok_or_else(Error::no_initial_trusted_state)?;
 
         if target_height >= highest.height() {
@@ -187,7 +188,7 @@ impl LightClient {
             // Get the latest trusted state
             let trusted_block = state
                 .light_store
-                .highest_trusted_or_verified()
+                .highest_trusted_or_verified_before(target_height)
                 .ok_or_else(Error::no_initial_trusted_state)?;
 
             if target_height < trusted_block.height() {
@@ -267,7 +268,8 @@ impl LightClient {
     ) -> Result<LightBlock, Error> {
         let trusted_state = state
             .light_store
-            .highest_trusted_or_verified()
+            .highest_trusted_or_verified_before(target_height)
+            .or_else(|| state.light_store.lowest_trusted_or_verified())
             .ok_or_else(Error::no_initial_trusted_state)?;
 
         Err(Error::target_lower_than_trusted_state(
@@ -304,7 +306,8 @@ impl LightClient {
 
         let root = state
             .light_store
-            .highest_trusted_or_verified()
+            .highest_trusted_or_verified_before(target_height)
+            .or_else(|| state.light_store.lowest_trusted_or_verified())
             .ok_or_else(Error::no_initial_trusted_state)?;
 
         assert!(root.height() >= target_height);
diff --git a/light-client/src/store.rs b/light-client/src/store.rs
index f9f395cf3..b3ae062d6 100644
--- a/light-client/src/store.rs
+++ b/light-client/src/store.rs
@@ -43,6 +43,9 @@ pub trait LightStore: Debug + Send + Sync {
     /// Get the light block of greatest height with the given status.
     fn highest(&self, status: Status) -> Option<LightBlock>;
 
+    /// 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 light block of lowest height with the given status.
     fn lowest(&self, status: Status) -> Option<LightBlock>;
 
@@ -76,6 +79,16 @@ pub trait LightStore: Debug + Send + Sync {
         })
     }
 
+    /// 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> {
+        let highest_trusted = self.highest_before(height, Status::Trusted);
+        let highest_verified = self.highest_before(height, Status::Verified);
+
+        std_ext::option::select(highest_trusted, highest_verified, |t, v| {
+            std_ext::cmp::max_by_key(t, v, |lb| lb.height())
+        })
+    }
+
     /// Get the light block of lowest height with the trusted or verified status.
     fn lowest_trusted_or_verified(&self) -> Option<LightBlock> {
         let lowest_trusted = self.lowest(Status::Trusted);
diff --git a/light-client/src/store/memory.rs b/light-client/src/store/memory.rs
index 463948b4c..2b7aa520c 100644
--- a/light-client/src/store/memory.rs
+++ b/light-client/src/store/memory.rs
@@ -72,6 +72,15 @@ impl LightStore for MemoryStore {
             .map(|(_, e)| e.light_block.clone())
     }
 
+    fn highest_before(&self, height: Height, status: Status) -> Option<LightBlock> {
+        self.store
+            .iter()
+            .filter(|(_, e)| e.status == status)
+            .filter(|(h, _)| h <= &&height)
+            .max_by_key(|(&height, _)| height)
+            .map(|(_, e)| e.light_block.clone())
+    }
+
     fn lowest(&self, status: Status) -> Option<LightBlock> {
         self.store
             .iter()
diff --git a/light-client/src/store/sled.rs b/light-client/src/store/sled.rs
index a749fa7de..8a6be662c 100644
--- a/light-client/src/store/sled.rs
+++ b/light-client/src/store/sled.rs
@@ -79,6 +79,10 @@ impl LightStore for SledStore {
         self.db(status).iter().next_back()
     }
 
+    fn highest_before(&self, height: Height, status: Status) -> Option<LightBlock> {
+        self.db(status).range(..=height).next_back()
+    }
+
     fn lowest(&self, status: Status) -> Option<LightBlock> {
         self.db(status).iter().next()
     }
@@ -109,6 +113,24 @@ mod tests {
         })
     }
 
+    #[test]
+    fn highest_before_returns_correct_block() {
+        with_blocks(10, |mut db, blocks| {
+            for block in blocks {
+                db.insert(block.clone(), Status::Verified);
+                assert_eq!(
+                    db.highest_before(block.height(), Status::Verified).as_ref(),
+                    Some(&block)
+                );
+                assert_eq!(
+                    db.highest_before(block.height().increment(), Status::Verified)
+                        .as_ref(),
+                    Some(&block)
+                );
+            }
+        })
+    }
+
     #[test]
     fn lowest_returns_earliest_block() {
         with_blocks(10, |mut db, blocks| {
diff --git a/light-client/src/store/sled/utils.rs b/light-client/src/store/sled/utils.rs
index 66857e76b..2caa273ce 100644
--- a/light-client/src/store/sled/utils.rs
+++ b/light-client/src/store/sled/utils.rs
@@ -3,6 +3,7 @@
 //! CBOR binary encoding.
 
 use std::marker::PhantomData;
+use std::ops::{Bound, RangeBounds};
 
 use serde::{de::DeserializeOwned, Serialize};
 
@@ -32,6 +33,15 @@ fn key_bytes(height: Height) -> [u8; 8] {
     height.value().to_be_bytes()
 }
 
+// Can be removed once bound_map is stabilized. See https://github.com/rust-lang/rust/issues/86026
+fn map_bound(bound: Bound<&Height>) -> Bound<[u8; 8]> {
+    match bound {
+        Bound::Included(h) => Bound::Included(key_bytes(*h)),
+        Bound::Excluded(h) => Bound::Excluded(key_bytes(*h)),
+        Bound::Unbounded => Bound::Unbounded,
+    }
+}
+
 impl<V> HeightIndexedDb<V>
 where
     V: Serialize + DeserializeOwned,
@@ -85,6 +95,19 @@ where
             .flatten()
             .flat_map(|(_, v)| serde_cbor::from_slice(&v))
     }
+
+    /// Return an iterator over the given range
+    pub fn range<R>(&self, range: R) -> impl DoubleEndedIterator<Item = V>
+    where
+        R: RangeBounds<Height>,
+    {
+        let range = (map_bound(range.start_bound()), map_bound(range.end_bound()));
+
+        self.tree
+            .range(range)
+            .flatten()
+            .flat_map(|(_, v)| serde_cbor::from_slice(&v))
+    }
 }
 
 #[cfg(test)]
diff --git a/light-client/src/supervisor.rs b/light-client/src/supervisor.rs
index 297f8463d..fb44ad40b 100644
--- a/light-client/src/supervisor.rs
+++ b/light-client/src/supervisor.rs
@@ -483,6 +483,14 @@ mod tests {
         let mut light_store = MemoryStore::new();
         light_store.insert(trusted_state, Status::Trusted);
 
+        for extra_trusted_height in trust_options.extra_heights {
+            let trusted_state = io
+                .fetch_light_block(AtHeight::At(extra_trusted_height))
+                .expect("could not 'request' light block");
+
+            light_store.insert(trusted_state, Status::Trusted);
+        }
+
         let state = State {
             light_store: Box::new(light_store),
             verification_trace: HashMap::new(),
@@ -526,17 +534,12 @@ mod tests {
         )
     }
 
-    fn make_peer_list(
+    fn make_peer_list_opts(
         primary: Option<Vec<LightBlock>>,
         witnesses: Option<Vec<Vec<LightBlock>>>,
         now: Time,
+        trust_options: TrustOptions,
     ) -> PeerList<Instance> {
-        let trust_options = TrustOptions {
-            period: DurationStr(Duration::new(604800, 0)),
-            height: Height::try_from(1_u64).expect("Error while making height"),
-            trust_level: TrustThresholdFraction::TWO_THIRDS,
-        };
-
         let mut peer_list = PeerList::builder();
 
         if let Some(primary) = primary {
@@ -559,6 +562,24 @@ mod tests {
         peer_list.build()
     }
 
+    fn make_peer_list(
+        primary: Option<Vec<LightBlock>>,
+        witnesses: Option<Vec<Vec<LightBlock>>>,
+        now: Time,
+    ) -> PeerList<Instance> {
+        make_peer_list_opts(
+            primary,
+            witnesses,
+            now,
+            TrustOptions {
+                period: DurationStr(Duration::new(604800, 0)),
+                height: Height::try_from(1_u64).expect("Error while making height"),
+                extra_heights: vec![],
+                trust_level: TrustThresholdFraction::TWO_THIRDS,
+            },
+        )
+    }
+
     fn change_provider(
         mut light_blocks: Vec<LightBlock>,
         peer_id: Option<&str>,
@@ -859,4 +880,38 @@ mod tests {
             .iter()
             .any(|&peer| peer == primary[0].provider));
     }
+
+    #[test]
+    fn test_bisection_between_trusted_heights() {
+        let chain = LightChain::default_with_length(10);
+        let primary = chain
+            .light_blocks
+            .into_iter()
+            .map(|lb| lb.generate().unwrap().into_light_block())
+            .collect::<Vec<LightBlock>>();
+
+        let witness = change_provider(primary.clone(), None);
+
+        // Specify two trusted heights (1 and 8), then attempt to verify target height 4 which
+        // falls between the two. Verification should use regular bisection.
+
+        let peer_list = make_peer_list_opts(
+            Some(primary.clone()),
+            Some(vec![witness]),
+            get_time(11).unwrap(),
+            TrustOptions {
+                period: DurationStr(Duration::new(604800, 0)),
+                height: Height::try_from(1_u64).expect("Error while making height"),
+                extra_heights: vec![Height::try_from(8_u64).expect("Error while making height")],
+                trust_level: TrustThresholdFraction::TWO_THIRDS,
+            },
+        );
+
+        let (result, _) = run_bisection_test(peer_list, 4);
+
+        let expected_state = primary[3].clone();
+        let new_state = result.unwrap();
+
+        assert_eq!(expected_state, new_state);
+    }
 }


Test patch:
diff --git a/.github/workflows/test.yml b/.github/workflows/test.yml
index 4aea8308d..ab533a5c5 100644
--- a/.github/workflows/test.yml
+++ b/.github/workflows/test.yml
@@ -81,7 +81,14 @@ jobs:
         with:
           toolchain: stable
           override: true
+      # NOTE: We test with default features to make sure things work without "unstable".
       - uses: actions-rs/cargo@v1
+        name: Test with default features
+        with:
+          command: test
+          args: -p tendermint-light-client
+      - uses: actions-rs/cargo@v1
+        name: Test with all features
         with:
           command: test-all-features
           args: -p tendermint-light-client
diff --git a/light-client/src/tests.rs b/light-client/src/tests.rs
index 1bfeede80..b90f7a1bb 100644
--- a/light-client/src/tests.rs
+++ b/light-client/src/tests.rs
@@ -77,6 +77,8 @@ pub struct Provider<LB> {
 pub struct TrustOptions {
     pub period: DurationStr,
     pub height: HeightStr,
+    #[serde(default)]
+    pub extra_heights: Vec<HeightStr>,
     pub trust_level: TrustThreshold,
 }