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.

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

Different calculation logic for majority and supermajority #2100

Closed
fed-franz opened this issue Aug 9, 2024 · 2 comments · Fixed by #2160
Closed

Different calculation logic for majority and supermajority #2100

fed-franz opened this issue Aug 9, 2024 · 2 comments · Fixed by #2160
Assignees
Labels
module:consensus Issues related to consensus module type:enhancement Issues concerning code or feature improvement (performance, refactoring, etc)

Comments

@fed-franz
Copy link
Contributor

From Oak's audit:

For the supermajority, the credits are determined by multiplying the committee credits with 
the threshold and taking the ceiling of this result. For the majority, the committee credits are 
also multiplied with the majority threshold, but this is then casted to a usize and 1 is added to 
the result. In most cases, these two approaches are equivalent. However, when the committee 
credits are an exact multiple of MAJORITY_THRESHOLD, the required credits are higher by one. 
For instance if there are 4 committee credits with the MAJORITY_THRESHOLD set to 0.5 and the
SUPERMAJORITY_THRESHOLD set to 0.67, the required credits will be 3 for both.
If the MAJORITY_THRESHOLD and SUPERMAJORITY_THRESHOLD were set to the same
value, this would also mean that the required credits for the majority would be higher than for
the supermajority, which does not make sense. Moreover, if it was set to 1.0, it would never be
reachable.

We recommend using ceil for both values.
@fed-franz
Copy link
Contributor Author

fed-franz commented Aug 9, 2024

I generally disagree on the audit's remark and recommendation. There is no way majority will ever be less than supermajority. And using ceil without the +1 for majority would lead to a wrong threshold: for instance, ceil(4 x 0.5) would be 2, which is not a majority; at the same time, using ceil with the +1 can also lead to wrong results: for instance, ceil(11 x 0.5)+1 would be 7, which is 1 more than needed.

However, the use of MAJORITY_THRESHOLD and SUPERMAJORITY_THRESHOLD is inconsistent (which is probably the reason for the confusion in the audit's report): one (the majority) is the last invalid value to which we need to add 1 to get the actual target; the other is directly used (with ceil) as the target.

We should make these two values consistent: the threshold should be either target value to reach or a value to which to add 1.

I suggest we change MAJORITY_THRESHOLD to be 0.51 and use ceil (without the +1) to get the actual value.


In addition, we currently calculate supermajority quorums in two different places.

In the Committee structure we do:

let super_majority = (committee_credits
            * config::SUPERMAJORITY_THRESHOLD)
            .ceil() as usize;
        let majority =
            (committee_credits * config::MAJORITY_THRESHOLD) as usize + 1;

Then in config.rs, we have one quorum function for both validation and ratification committee.

We should unify calculations throughout the code

@HDauven HDauven added type:enhancement Issues concerning code or feature improvement (performance, refactoring, etc) module:consensus Issues related to consensus module labels Aug 10, 2024
@HDauven HDauven added this to Audits Aug 16, 2024
@HDauven HDauven moved this to Discussion in Audits Aug 16, 2024
@fed-franz
Copy link
Contributor Author

In hindsight, using ceil for majority is always "risky" as it's not 100% equivalent to floor(value/2)+1.
For instance, floor(99/2)+1 = 50, which is correct, but ceil(99 x 0.51) = 51, which is wrong.

So we should keep the majority as is.

@fed-franz fed-franz moved this from Discussion to In Progress in Audits Aug 20, 2024
@fed-franz fed-franz linked a pull request Aug 20, 2024 that will close this issue
@github-project-automation github-project-automation bot moved this from In Review to Done in Audits Aug 20, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
module:consensus Issues related to consensus module type:enhancement Issues concerning code or feature improvement (performance, refactoring, etc)
Projects
Status: Done
Development

Successfully merging a pull request may close this issue.

4 participants