Closed feezybabee closed 8 months ago
It will also make it hard to validate BatchPropose
and Certificate
. See this thread: https://github.com/AleoHQ/snarkOS/pull/2956#issuecomment-1870903382
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 bond_public
calls. The assumption here is that nobody else on the network is calling bond_public
or unbond_public
when the attack is being performed.
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 BatchPropose
, I can get and simulate all the transactions in the causal certificate. Then I can find the target BatchPropose
that makes me a leader in future rounds. The problem is that the leader is the block producer. It can choose specific parent certificates, add transactions in its batch as it likes, and simulate the block in advance. Therefore, no matter what transaction other validators have included, the malicious leader can always make itself a leader in future rounds.
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 O(4**k)
times to make them leaders in k
consecutive even rounds. Then in the first k-1 consecutive even rounds, the malicious can halt the chain by not broadcasting certificates. This means they can easily delay block production as they like. This may cause more problems if you consider the PoW part.
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 current_round - COMMITTEE_LAG_ROUND
.
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 COMMITTEE_LAG_ROUND
:
Let'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 https://github.com/AleoHQ/snarkVM/pull/2213 shows atomic_post_ratify
is slow with thousands of delegators, we may consider keeping the same committee during the whole epoch. Only update committee and stake reward at epoch boundary.
Let'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:
let current_epoch = r / N
let last_epoch = last_block.epoch
if current_epoch == last_epoch:
return
// every epoch must have committed at least one block
assert(current_epoch == last_epoch+1)
finalize the reward for Epoch(last_epoch)
compute the committee for Epoch(current_epoch + 1)
Suppose in the current round, I am the leader of the committee. While proposing the BatchPropose, I can get and simulate all the transactions in the causal certificate. Then I can find the target BatchPropose that makes me a leader in future rounds. The problem is that the leader is the block producer. It can choose specific parent certificates, add transactions in its batch as it likes, and simulate the block in advance. Therefore, no matter what transaction other validators have included, the malicious leader can always make itself a leader in future rounds.
The intuition here is not correct.
BlockDAGs behave differently from traditional PBFT leaders. The leader only has batch_timeout
time to propose a valid batch and have it be certified by at least 2f+1
validators. In addition, leaders do NOT know in advance that they will be the leader. Bullshark only elects leaders in the following round, meaning they look backwards in time to determine if a leader was elected, based on f+1
votes from validators in the future round.
In addition, leaders do NOT know in advance that they will be the leader. Bullshark only elects leaders in the following round, meaning they look backwards in time to determine if a leader was elected, based on f+1 votes from validators in the future round.
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: https://github.com/randomsleep/snarkOS/commit/2e8cbe4b7e9d009be2be4d6c270c7a4afac385c8
In the example, Validator 0 is malicious. Validator 1, 2, and 3 are honest and they randomly send bond_public
transactions. While proposing batch, Validator 0 will speculate all the transactions and then insert bond_public
transactions with specific amount. This makes Validator 0 always leader in future rounds.
git clone https://github.com/randomsleep/snarkOS.git
git checkout perfect_leader_manipulation
./devnet
with the default setting.elected a leader - aleo1rhgdu77hgyqd3xjj8ucu3jj9r2krwz6mnzyd80gncr5fxcwlh5rsvzp9px
)Here is the log sample: logs-20240129114403.zip
@randomsleep Great job! I found the leader is deterministic as well, but I thought it is safe at that time.
Closing this issue as it is resolved as a byproduct of - https://github.com/AleoHQ/snarkOS/pull/3065.
The reason we needed the change is because we need consistent and predictable leader selection in the block-per-anchor
model, but just so happens to address the current concerns above.
@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 committee
in the map.
In this case, the committee
should refer to the next committed block (as described here: https://github.com/AleoHQ/snarkOS/issues/2986#issuecomment-1905278290)
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 get_committee_for_round
in snarkVM, you'll see that even if there is no committee/block being created at that round, there is still a committee selected, which is the committee of the previous committed block.
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!
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.
The insert(&self, next_height: u32, committee: Committee<N>)
function will set the height of round 11-15 to the same height at round 10. I am curious why not set the height of round 11-15 to the same height at round 16? Logically round 11-15 is committed by the block at round 16.
I don't think this resolves issue of the leader manipulation. The leader is elected with a random seed total_stake
and it manipulatable in the same way: https://github.com/AleoHQ/snarkOS/issues/2986#issuecomment-1913932490
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 get_leader
deterministic algorithm, instead it is to introduce a new topological sort over the transmissions that are committed into the block.
For instance, we can sort all of the transmissions which go into the block based on:
For instance, we can sort all of the transmissions which go into the block based on:
- Bucket transmissions into the rounds that they are committed in
- For each bucket, sort them based on the solution IDs & transaction IDs (i.e. order the field element representing the ID)
@howardwu This is still manipulatable because the leader can always include specific transactions in its own BatchPropose
and simulate the block in advance.
The root cause is that get_leader
includes total_stake
as a random seed. I guess the initial purpose is to introduce more randomness in leader election, which, turns out to be manipulatable. Full randomness is not a must in the leader election with Bullshark. Instead, fairness should be kept. I would suggest:
total_stake
and self.starting_round
in get_leader
. Only use current_round
as seed.sorted_members
sort validators with the index they join the committee.This will make get_leader
hard to manipulate the chance is very low that a validator be the leader in many consecutive rounds.
@randomsleep Would sorting the member based on the x-coordinate of the validator address be sufficient to replace the sorted_members
? We currently do not have an easy way to track the order that validators joined/left the committee.
We have a proposed change here - https://github.com/AleoHQ/snarkVM/pull/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 unbonding
period, it is impractical to do that frequently.
Hi @howardwu @raychu86, this issue has been resolved but the report was closed with a downgraded severity level referencing the outdated comment: https://github.com/AleoHQ/snarkOS/issues/2986#issuecomment-1902476801. 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