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
[Bug] Updating validator committee every two rounds will cause leader manipulation and permanent chain state split #2986
Comments
It will also make it hard to validate This issue has an important impact on the Committee update and Leader election. So I would suggest fixing this issue first. |
This is a valid/known problem, however is of lower impact. In theory an attack like this could occur, however this doesn't take into account possible changes to committee stakes from external In addition, the proposed fix using an older committee (COMMITTEE_LAG_ROUND) is not sound. Using old committee sets may include validators that are not in the committee, thereby electing leaders that do not exist. |
@raychu86 The code provided is just a proof of concept. The vulnerability does exist in practice: Suppose in the current round, I am the leader of the committee. While proposing the An example of the harm of leader manipulation: The malicious validators can easily enumerate blocks to make it a leader for many consecutive even rounds. Assuming 1/4 of validators are malicious, they only need to enumerate |
About using an older committee (COMMITTEE_LAG_ROUND): Yes, we should not use old committee sets. I mean we can define the current round committee as generated from Nonetheless, to resolve the ambiguity of the latest committee, we may need to decide on the committee in the earlier round (COMMITTEE_LAG_ROUND). This means the validator has to wait for specific rounds after they request to quit the committee. To ease leader manipulation, we may need to avoid using latest_state as a random seed. |
More details about using Update Committee at Every BlockLet's define COMMITTEE_LAG_ROUND=1000. The idea is that at round(r), try to use the committee generated at round(r-1000). The committee is deterministic if the chain has committed a block with block.round >= round(r-1000). This resolves the ambiguity of the latest committee. It's possible that round(r-1000) didn't produce a block. In this case, we use the committee generated at the first block whose round >= round(r-1000). Refer to this graph for more operations: |
As AleoNet/snarkVM#2213 shows Keep the Same Committee during EpochLet's define PoS Epoch = 1000 rounds. Divide round into Epoch. The Epoch of Round(r) is Epoch(r/1000). At the first block of Epoch(i+1), generate the committee for Epoch(i+2). Panic if there is no block in the whole Epoch. In this way, the committee is deterministic while entering a new epoch. Once commit a new block at around r, the validator will try to update the committee for the next epoch:
|
The intuition here is not correct. BlockDAGs behave differently from traditional PBFT leaders. The leader only has |
In the current implementation, the leader is deterministic, based on the previous committee: // Retrieve the previous committee of the current round.
let previous_committee = match self.ledger().get_previous_committee_for_round(current_round) {
Ok(committee) => committee,
Err(e) => {
error!("BFT failed to retrieve the previous committee for the even round {current_round} - {e}");
return false;
}
};
// Determine the leader of the current round.
let leader = match previous_committee.get_leader(current_round) {
Ok(leader) => leader,
Err(e) => {
error!("BFT failed to compute the leader for the even round {current_round} - {e}");
return false;
}
}; I have created another example to demonstrate perfect leader manipulation: randomsleep@2e8cbe4 In the example, Validator 0 is malicious. Validator 1, 2, and 3 are honest and they randomly send Step To Reporduce:
Here is the log sample: |
@randomsleep Great job! |
Closing this issue as it is resolved as a byproduct of - #3065. The reason we needed the change is because we need consistent and predictable leader selection in the |
@raychu86 Great work! It resolves the ambiguity of the committee. This issue hasn't been fully fixed though. Not very even round will commit a block. The round leader may fail to create a Certificate in time. Therefore, it's possible that some rounds don't have a corresponding In this case, the |
It appears that the issue of the leader manipulation issue is still unresolved. Please correct me if I am missing something. |
@randomsleep If you look at the code for If round 10 has a block and round 16 has a block. The committee at round 11-15 will be the committee created at round 10. I believe this should be sufficient for addressing the issue. Please let me know if you still have concerns. |
@raychu86 Got it, thanks!
The |
I don't think this resolves issue of the leader manipulation. The leader is elected with a random seed |
With the introduction of the committee lookback design (which now makes the leader election predictable up to GC depth), the manipulation concern is indeed more prevalent than before. To clarify:
To mitigate this concern according to the Bullshark paper, the solution isn't to change the For instance, we can sort all of the transmissions which go into the block based on:
|
@howardwu This is still manipulatable because the leader can always include specific transactions in its own The root cause is that
This will make |
@randomsleep Would sorting the member based on the x-coordinate of the validator address be sufficient to replace the We have a proposed change here - AleoNet/snarkVM#2378 |
@raychu86 I think this is sufficient to address the issue. In theory, the malicious validators can quit and rejoin the committee to manipulate x-coordinate of the address. However, due to the |
Hi @howardwu @raychu86, this issue has been resolved but the report was closed with a downgraded severity level referencing the outdated comment: #2986 (comment). This report shows two issues that are both critical. This was submitted on December 17, 2023, before the public announcement of audits. Please rejudge the severity level based on the new progress. |
I'll share a message with the bug bounty team at the Foundation regarding the severity level. Just a heads up that the bug bounty process is unaffiliated to Provable (where Ray and I are). |
https://hackerone.com/reports/2289066
Summary:
AleoBFT updates the committee (stake, status, etc) with every block. At each even round, elect the leader from the committee with latest committed block. This will introduce two issues:
** Issue a. Leader Manipulation **:
The leader is selected from the committee by the seed which is composed of
self.starting_round, current_round, total_stake
. However, the current leader can manipulatetotal_stake
by addingbond_public
transactions in its batch. The leader can easily find the targettotal_stake
which make itself the leader for the next round. Thus, a leader can keep itself as a leader forever.** Issue b. Permanent Chain State Split **
In current AleoBFT, the leader election directly depends on the latest committed block. However, for asynchronous network, some validators may have committed a block but some others not, making validators elect different leaders. This will cause permanent chain state split.
I will provide Steps To Reproduce for Issue a and Proof-of-Concept for Issue b.
Steps To Reproduce:
For Issue a.
validator-0.log
and find that the validator 0 has been leader for most even rounds. (Just count the line by searchingelected a leader - aleo1rhgdu77hgyqd3xjj8ucu3jj9r2krwz6mnzyd80gncr5fxcwlh5rsvzp9px
and compare that by count the lineelected a leader
)Also see the example
validator-0.log
at the attachment.Note that, in our code, Validator 0 only send the transaction with best effort. In practice, the the leader can directly simulate and add the transaction to the batch. This will 100% make itself the leader of future rounds and other validator can not do anything to prevent this.
For issue b.
Take the picture in the bullshark blog as example.
Suppose we are in Round 3, while deciding the leader for current round, Validator 1 will find that Round 1 hasn't been committed so it will use committee in the round before Round 1. However, in Validator 4's view, Round 1 has been committed so it just decide the leader from Round 1's committee. This will cause permanent chain state split.
Additional considerations
The ambiguous of latest committee will also introduce other tricky problems:
If last block haven't been committed, we can't tell if the current round
BatchCertificate
(either from other peers or from myself) has reached quorum. Because the committe will change once the last block is committed. This function inLedgerService
makes the committee ambiguous.I think we can fix this by:
current_round
, use the committe fromcurrent_round - COMMITTEE_LAG_ROUND
round. (COMMITTEE_LAG_ROUND could be large enough like 100 or 1000) The function will be like:In this way, the concensue will stall if the latest
COMMITTEE_LAG_ROUND
round hasn't been committed.Supporting Material/References:
See the attachment
Fix Suggestions:
The problem here is that AleoBFT's committee directly depends on the latest committed state. However, the
latest state
is easy to manipulate and can temporarily mismatch.It's suggested to fix the committee for some fixed rounds. Also, while choosing leader, only use random seed that is hard to manipulate.
In SUI, the validator committee is fixed for the whole epoh (~24h). In the codebase of bullshark paper, it directly use round-robin: https://github.com/asonnino/narwhal/blob/667595d9dc82a472bade5afd59993d8479047a48/consensus/src/lib.rs#L205
Impact
Current AleoBFT implementation will cause: (a) leader manipulation and (b) permanent chain state split
The text was updated successfully, but these errors were encountered: