Light client: iterative / non-recursive bisection

[liamsi]

We should implement a non-recursive version of the bisection.

The current recursive bisection logic in the (light client) verifier module was a good start towards an MPV light node but #171 surfaced that we should probably change this into a non-recursive method rather sooner than later. This could be part of general overhaul of the currentl light module that further decouples and separates concerns.

[gterzian]

Ok, maybe that's a good one for me to look into, to get started on something...

[gterzian]

I'm thinking of doing this as an actual Stream, which would produce one TrustedState at a time and could be used in iteration.

cc @brapse It was mentioned you had been thinking about this and had some ideas?

In any case, I should have something to look at fairly quickly.

Another way to do this would be to have a separate "verification" task(which doesn't mean it would actually have to run in parallel, you could still run everything on a single-threaded runtime), which could write one TrustedState at a time into a channel.

It's kind of the same thing, implementing a Stream vs having a separate task write into a channel(which would implement Stream)...

[gterzian]

Ok the WIP is over at #180

So this was actually much more complicated than I thought so far, for a couple of reasons:

1. Too much use of generics(in my opinion).
2. Too much use of generic parameters, as opposed to trait objects(in my opinion).

So for example having Header, Commit, ValidatorSet as traits, as opposed to simple structs, seems unnecessarily complicated. It makes it harder to refactor something because not all traits are boxable. Fore example ValidatorSet is not, I'm not even sure why(maybe because of the Clone bound?), but it's one of those problems that are best avoided rather than solved.

It also seems easy enough for the RPCRequester to simply return a Set, since it imports stuff from tendermint already(I guess it does make sense for tendermint to be using a Requester trait, and that trait can simply return a struct from within tendermint I would say).

In terms of moving code around, it would be much more convenient to use structs at this stage, and only add traits later to add boundaries. Right now the complexity cost seems not worth it.

Also, and this is perhaps personal, I much rather like to think of traits as objects, and pass them around as Box<dyn Trait>, as opposed to having all those parametrized functions. At the end of the day those functions use the traits passed to them mostly as objects it seems. But just passing a struct when you can is off-course superior than a trait. A function with a signature like verify_bisection_inner<'a, H, C, L, R> seems like a bit too much...

On another note I also tried to use a separate task for the verification, and that was even harder with all those traits as you get lots of error about them not being Send and so on, and having to mark them a such. I think you can again avoid this by passing structs around, since they will be Send by default most of the time.

[gterzian]

Mmh, I now also see the unit tests are dependent on those traits...

This is turning into quite a big change, and it might not be worth it.

I could fallback to implement the iterative version with a function similar to the current recursive one, however I'm not sure if it would really add a lot of value.

I think the Stream idea sort of made sense, since if we're using async that is a good way to implement an iterative algorithm, and I also liked separating the "updating of data" using the requester, from the actual verification, however this is increasing looking like something requiring a large change, one that others might actually not agree with.

In general my advice would be to lighten up on the generic stuff, because it seems to be making it harder to change stuff at this point. It might indeed be a good idea to have some traits in there that various clients could implement. You could also have a tendermint_traits crate that would include the public stuff that tenderming-lite would use, and actually that stuff doesn't always have to be generic. You can have a Commit struct that would be part of the public API, it doesn't have to be a trait for that. Different types of commits could be modelled with an enum, instead of various structs implementing a trait.

I think a trait is only necessary is you want users of the public API to actually have the possibility to extend the protocol for their own use case, and that seems like a very advanced use case perhaps not requiring making everything generic from the start(cross that bridge when you get there).

Even at the unit-test level, while those mocks might make sense, they also mean the unit test are almost as complicated as the actual code(who's going to write tests for the unit tests?), and I also wonder if they could not give a false sense of security, because in the real-usage you won't be using the mock code. I understand you're not testing the mocks, you're testing the stuff surrounded by the mocks, however using the mocks does introduce opportunities for weird stuff, since the real-world implementer of the traits might show slightly different behaviors in their interaction with the stuff you are testing. Again unit-tests could be simpler, and perhaps more effective, if they were just using the actual structs as opposed to mocks implementing traits.

So anyway, I don't expect everyone to agree with this, so perhaps take a look at the WIP, let me know what you think, and then we can either drop the current approach if it goes against the strategy of the project, or find a way to make it work with further changes...

[liamsi]

Many good points @gterzian! I'll hope to address some in more detail later this week as well as review the WIP PR.

[gterzian]

@liamsi Cool, yes I think the WIP might be worth taking a look, and then probably the overall structure of stuff could be revisited in the light of https://github.com/informalsystems/tendermint-rs/pull/185/files

I'm not sure if it's worth it making large changes like in the WIP before then...

[romac]

I concur with @gterzian that perhaps the current use of traits for the purpose of mocking is not ideal, and that we should perhaps investigate other ways of achieving the same result (the mockall crate being one potential candidate).

[gterzian]

Ok so I think I'll my WIP PR where it is for now, and instead I'll try to refactor the requester/verifier flow to try to make a step in the direction of #185

Basically as a way to isolate the requester and the verifier (and the "main routine" of the node) into separate components so we can run them and test them independently... Stay tuned for a PR.

[liamsi]

Should we close the PR then?

[gterzian]

Yes probably, although I'm in no particular rush to close PRs.