light-client-verifier: avoid checking signatures multiple times

[mina86]

Rework VerificationPredicates and VotingPowerCalculator by introducing methods which check validators and signers overlap at once. The motivation of this is to avoid checking the same signature multiple times.

Consider a validator is in old and new set. Previously their signature would be verified twice. Once by call to has_sufficient_validators_overlap method and second time by call to has_sufficient_signers_overlap method.

With the new interface, has_sufficient_validators_and_signers_overlap is called and it can be implemented to remember which signatures have been verified.

As a side effect of those changes, signatures are now verified in the order of validator’s power which may further reduce number of signatures which need to be verified.

Furthermore, this commit also changes the signature verification such that it completely ignores signatures which don’t contribute to voting power, i.e. nil votes. This means that now an invalid nil signature won’t cause an error.

• [ ] Referenced an issue explaining the need for the change
• [x] Updated all relevant documentation in docs
• [x] Updated all code comments where relevant
• [x] Wrote tests
• [x] Added entry in .changelog/

[mina86]

@romac, could you give a quick review of this code? We’re continuing to hit performance limits and so need to continue trying to optimise the code. With this change I’m trying to make it so that a) no signature is verified twice and b) signatures are verified from one with most power so hopefully fewer signatures overall will need verification.

One thing to keep in mind is that this is API breaking.

[romac]

Thanks for the PR! These are some quite substantial changes to the logic so I unfortunately won't be able to properly review them this week, sorry about that. At first glance this looks alright to me though, I and don't mind the API changes. I'll take a closer look first thing next week.

[mina86]

Thanks. One more thing that may be noteworthy is that I’ve filtered out non-commit votes. They didn’t contribute to voting power so I figured it’s fine to just ignore them.

[mina86]

Do you have any numbers as to how much these changes improve gas efficiency compared to your previous PR?

Sorry, forgot about this question. At this moment I don’t have concrete numbers. We were testing various optimisations to get things working on Solana and that was one of them. At the moment I’ve no numbers for this change in isolation. I’ll try to get some numbers today but cannot promise.

[romac]

@mina86 Great work, thanks a lot for the care you've put into this PR and for bearing with me, much appreciated!