Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

light-client: consider optimizing voting power calculation by stopping after verifying +1/3 or +2/3 #235

Closed
melekes opened this issue Apr 23, 2020 · 2 comments · Fixed by #1395
Closed

light-client: consider optimizing voting power calculation by stopping after verifying +1/3 or +2/3 #235

melekes opened this issue Apr 23, 2020 · 2 comments · Fixed by #1395
Labels
light-client Issues/features which involve the light client

Comments

@melekes
Copy link
Contributor

melekes commented Apr 23, 2020

voting_power_in(&self, validators: &Set)

tendermint-rs/tendermint/src/lite_impl/signed_header.rs

Line 15 in efadd8b

fn voting_power_in(&self, validators: &Set) -> Result<u64, Error> {
function is suboptimal.

You don’t have to calculate all the voting power. What you want is to verify that trust threshold (⅔+ in sequential verification or configurable ⅓+ in skipping verification) signed this commit.

In Go Tendermint, Verify function returns as soon as threshold is reached. https://github.com/tendermint/tendermint/blob/7b717c72df1e9d38cdaf110cdbdaa57459272dc1/types/validator_set.go#L664
@romac romac added the light-client Issues/features which involve the light client label May 25, 2020
@romac romac mentioned this issue May 25, 2020
Closed
19 tasks
This was referenced Jun 11, 2020
Open
Closed
@brapse brapse mentioned this issue Jun 18, 2020
Merged
10 tasks
romac added a commit that referenced this issue Jun 18, 2020
@romac
Mention #235 in TODO comment
8c0c5e6
brapse pushed a commit that referenced this issue Jun 19, 2020
@romac
Fix VotingPowerCalculator::voting_power_in (#306)
8ab1989 
* Fix `VotingPowerCalculator::voting_power_in`.

- Provide two helper methods for checking validators overlap and if
  there is enough trust w.r.t. the trusted state.
- Only count `Commit` signatures towards the voting power.
- Do not rely on `signed_votes` method to get the votes.

* Don't add voting power of the same validator multiple times

* Cleanup and comments

* Remove debug statements

* Add a constant for a trust threshold of 2/3

* Fix clippy warnings

* Mention #235 in TODO comment

* Small refactor

* Fix clippy warnings and a typo

* Address Stevan's comments

* Remove debug condition

* Raise error when seeing duplicate validator in voting power computation
@ebuchman ebuchman changed the title lite_impl: Commit#voting_power_in func is suboptimal light-client: consider optimizing voting power calculation by stopping after verifying +1/3 or +2/3 Aug 28, 2020
@ebuchman
Copy link
Member

This will be especially relevant once #506 is done

@tac0turtle
Copy link
Contributor

This could be further optimized by utilizing batch verification from dalek or zebra.

@romac romac mentioned this issue Oct 12, 2020
Open
@i-m-aditya i-m-aditya mentioned this issue Feb 22, 2024
Merged
5 tasks
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
light-client Issues/features which involve the light client
Projects
None yet
Milestone
No milestone
4 participants
@romac @melekes @ebuchman @tac0turtle