parallelchain-io / hotstuff_rs

Rust implementation of the HotStuff consensus algorithm.
38 stars 5 forks source link

`pending_validator_set_updates()` deleted on commit causing `safe_qc` to incorrectly return false #28

Closed karolinagrzeszkiewicz closed 9 months ago

karolinagrzeszkiewicz commented 10 months ago

The issue is twofold.

First, a part that is easier to fix: in this line block should be replaced with b. Note that this line is incorrect with respect to our intention, but in reality it should not cause much trouble, since among the blocks that are committed with a single call to commit_block, only block can have associated validator set updates.

Secondly, even with the fix mentioned above we can face a possibly liveness-threatening situation. On committing a block b, the pending validator set updates associated with b are deleted from the BlockTree. When a child block of b is proposed, safe_qc returns true, since the justify is a commit QC and there are validator set updates associated with b in the BlockTree. Then b is committed and its pending validator set updates deleted. However, if another child block of b is proposed, the safe_qc (and hence safe_block) check will fail because the validator set updates associated with b have already been deleted.

For reference:

pub fn safe_qc(&self, qc: &QuorumCertificate, chain_id: ChainID) -> bool {
        /* 1 */
        (qc.chain_id == chain_id || qc.is_genesis_qc()) &&
        /* 2 */
        (self.contains(&qc.block) || qc.is_genesis_qc()) &&
        /* 3 */ qc.view >= self.locked_view() &&
        /* 4 */ (((qc.phase.is_prepare() || qc.phase.is_precommit() || qc.phase.is_commit()) && self.pending_validator_set_updates(&qc.block).is_some()) ||
        /* 5 */ (qc.phase.is_generic() && self.pending_validator_set_updates(&qc.block).is_none()))
    }

In case the first child of b that was proposed cannot be committed, for instance because the proposal was only broadcasted to selected validators by a byzantine node, the validators that have inserted this block cannot insert any other conflicting block, hence this is a potential liveness threat.

lyulka commented 9 months ago

This seems like it duplicates #16.