New public API for the light client by ebuchman · Pull Request #114 · cometbft/tendermint-rs

ebuchman · 2019-12-29T02:37:29Z

As per some points in #110, #111, and #113 , I think I've hit upon a much simplified logic for the light client and the bisection. This diverges from the spec and thus shouldn't be merged yet, but I think we can update the spec to match this and have something easier to reason about all around.

The essential idea is to have two primary public functions:

verify_and_update_single: This attempts to verify a single header and update the store. It does not use a requester (all data is provided as args). It performs all checks and verification. It is intended for use by IBC handlers.
verify_and_update_bisection: This attempts to verify and update to some height, using a requester to request intermediate heights as necessary, according to bisection. It is intended for use by a light node.

Both functions use a common pure function called verify_single which is not exposed, but which performs the core verification logic to determine if we can update from one header to another. It is not exposed because it does not check for expiry. Expiry checking is the responsibility of the public functions.

As per #113, we can now focus most of our testing on verify_single, as this is the work horse of both public functions. For verify_and_update_single, we should additionally test for expiry and for properly updating the store. For verify_and_update_bisection, we should additionally test for expiry and properly updating the store with the right set of intermediate headers.

Note that by making all the validation and verification explicit in verify_single, we eliminate the need for the verify and check_support functions. Instead we call verify_commit_full and verify_commit_trusting directly in verify_single. We can then delete all of verify, check_support, can_trust_bisection and verify_header. None of the functions in verifier.rs should be exposed to users of the crate.

Note for simplicity I'm also assuming here we can get the latest trusted state by requesting height 0 (see #111).

Referenced an issue explaining the need for the change
Updated all relevant documentation in docs
Updated all code comments where relevant
Wrote tests
Updated CHANGES.md

tendermint/src/lite.rs

tendermint/src/lite/public.rs

liamsi

This is much better than the prev. API! Thanks for taking over @ebuchman!

ebuchman · 2019-12-29T21:21:40Z

Awesome thanks - would love a review from @ancazamfir / @josef-widder / @milosevic before we merge since we'll then need to update the spec to match. If it seems good, then here we'd still need:

Remove the old functions
Update docs for the .get(0) semantics and remove get_smaller...
Unexpose all the other functions in lite.rs

tendermint/src/lite/public.rs

ebuchman · 2019-12-31T00:40:29Z

Ok, I merged #115 into this so we have some tests, and addressed all the feedback above. There's a bunch of TODO's in the PR and I've added them all into #110 for followup, so I think we can otherwise move forward with merging this :)

xla

Lots of small style remarks, nothing major.

It would be interesting to explore if there is an entity that owns to ensure that the right order of operations are performend and exposes a clean surface of dependencies, instead of having pub functions doing multiple things.

xla · 2019-12-31T16:22:43Z

tendermint/src/lite/types.rs

 }

-#[derive(Debug, PartialEq)]
+// NOTE: Copy/Clone for convenience in testing ...


Suggested change

// NOTE: Copy/Clone for convenience in testing ...

Is this comment to avoid someone removing the derives and tests breaking?

Possibly, but also an explanation of why we need to derive those traits and a reminder to maybe find a way to not need to do that ?

Then we should track it as a TODO/follow-up if we think it should be addressed.

tendermint/src/lite/types.rs

tendermint/src/lite/verifier.rs

tendermint/src/lite.rs

tendermint/src/lite/verifier.rs

Co-Authored-By: Alexander Simmerl <a.simmerl@gmail.com>

Co-Authored-By: Ethan Buchman <ethan@coinculture.info>

xla

👍 🐙 💃 🍡

ancazamfir

Sorry for the delay with this. I know it's been merged but couldn't find a better place to comment :)
In general it looks good, just a few comments.

ancazamfir · 2020-01-03T12:25:53Z

tendermint/src/lite/verifier.rs

+        // TODO(EB): Use a different error from
+        // verify_commit_trusting else bisection
+        // will happen when the commit is actually just invalid!


Can we fix this?

Yes it's tracked in #110

ancazamfir · 2020-01-03T12:26:20Z

tendermint/src/lite/verifier.rs

-    let pivot_header = req.signed_header(pivot)?;
-    let pivot_vals = req.validator_set(pivot)?;
+    // All validation passed successfully. Verify the validators correctly committed the block.
+    verify_commit_full(untrusted_vals, untrusted_sh.commit())


I would move this after validate_untrusted() and even combine them as they perform signed header validation.
Also isn't verify_commit_full() same as verify_commit_trusting() with different trust_threshold.

Yeah, actually something is not right. First, I think it is important that verify_single() does both validate_untrusted() and verify_commit_full() first. Any errors from these functions are fatal and bisection should not proceed. As it is right now, verify_single() may return early with error from verify_commit_trusting() which causes the bisection caller to start bisecting even if this header/commit is not fully verified. For the second issue, see next comment...

So I was actually thinking the opposite, which was that we shouldn't bother trying to fully verify a future header (which is expensive) until we know we can skip to it.

I suppose it's a question of compute vs bandwidth. But even if we did the verification first, a full node who wanted to trick us into using a lot of bandwidth could always give us headers that are well signed by themselves so we'd waste time verifying them and not find out until much later that they're not actually valid from previous ones. So it doesn't really make sense to me to be verifying the commit of a header until we know we can skip to it and that was one of the key points I wanted to effect in these changes.

Sorry, I should have written that up more explicitly somewhere.

And yes, verify_commit_full and _trusting are the same now except the later uses the threshold trait and the former is just fixed to 2/3

So I was actually thinking the opposite, which was that we shouldn't bother trying to fully verify a future header (which is expensive) until we know we can skip to it.

yes, but the problem is that if we know we can skip it, we start recursive bisection which involves downloading and fully verifying all the pivots...so both bandwidth and cpu, only to fail once we are done.

as discussed, this is ok, because the in between headers are being verified fully and hence trusted, even if the node turns out to be bad at the end of the run, so that bandwidth and cpu isn't really wasted.

ancazamfir · 2020-01-03T12:26:52Z

tendermint/src/lite/verifier.rs

+    // this get is redundant the first time.
+    // TODO: possibly refactor so this func takes and returns
+    // trusted_state.
+    let trusted_state = store.get(Height::from(0))?;


Yeh, this is a bit inefficient as we keep getting the trusted state from the store for all pivots that we just added in L#311. It would be maybe better if the trusted state is passed in as parameter. And easier to read.

The other question is about store implementation. I expect there is some background routine that runs periodically and purges expired headers from the store. This would interfere with bisection runs and needs to be analyzed as getting a trusted header from the store might fail.

Yes I thought it would be easiest to read and write first like this. And also figured stores would have caching so it wouldn't be inefficient. But see discussion with xla about not passing in store into these functions #110 (comment)

Been thinking about a Client state machine and functions that return TrustedState so that it's the users responsibility to make the store updates but they can't do it wrong.

Pruning should be guaranteed to not interfere - ie. it can only apply outside the trusting period.

ancazamfir

A couple more doubts...

ancazamfir · 2020-01-03T13:08:06Z

tendermint/src/lite/verifier.rs

-    let pivot_header = req.signed_header(pivot)?;
-    let pivot_vals = req.validator_set(pivot)?;
+    // All validation passed successfully. Verify the validators correctly committed the block.
+    verify_commit_full(untrusted_vals, untrusted_sh.commit())


Yeah, actually something is not right. First, I think it is important that verify_single() does both validate_untrusted() and verify_commit_full() first. Any errors from these functions are fatal and bisection should not proceed. As it is right now, verify_single() may return early with error from verify_commit_trusting() which causes the bisection caller to start bisecting even if this header/commit is not fully verified. For the second issue, see next comment...

ancazamfir · 2020-01-03T13:08:21Z

tendermint/src/lite/verifier.rs

+    let untrusted_next_vals = &req.validator_set(untrusted_height.increment())?;
+
+    // check if we can skip to this height and if it verifies.
+    match verify_single(


...second issue: looks like we call verify_single() multiple times for the untrusted signed header. We expect this to be called with different (higher) trusted singed header but still we do the untrusted header verification (independent of the trusted one) multiple times and this is expensive.

We're only doing the validation, which is just hash checks. the hashes can be memoized so this would be cheap equality testing.

We do end up running verify_commit_trusting multiple times which is expensive and it would be interesting to see how we can optimize that but it will start to mess with our traits again

This was referenced Dec 29, 2019

Update specification of light client algorithm to align with the code tendermint/spec#61

Merged

Lite: complete test mocks and start some tests #115

Merged

ebuchman changed the base branch from bucky/some-light-follow-up to master December 29, 2019 18:46

ebuchman force-pushed the bucky/spec-reorg branch from f2bd282 to ae32577 Compare December 29, 2019 19:10

ebuchman added 11 commits December 29, 2019 14:10

new verify_and_update_single func

40f374b

verify_and_update funcs

5930e7c

fmt

d8e4120

clippy

ae32577

simplest test for verify_single

a8867d2

test_verify_single_1_val_skip

30796ab

convenience funcs and more tests

30c3850

cleanup and more tests

bd72fc0

fmt

d988689

comments

8f75582

clippy

f8f9e88

liamsi reviewed Dec 29, 2019

View reviewed changes

tendermint/src/lite.rs Outdated Show resolved Hide resolved

liamsi reviewed Dec 29, 2019

View reviewed changes