# Validator Set Speculation - Implementation
## `BlockTree` - new fields
1. `resigning_validator_set: Option<ValidatorSet>`
- previous `committed_validator_set`, set on updating the `committed_validator_set` on seeing a `commitQC`, and reset to `None` after seeing a `decideQC` for the same block.
3. `validator_set_updating_block: Option<CryptoHash>`
- most recent committed, but not yet decided, validator-set-updating block.
## Types module (updates)
The changes in the module concern adding a new `decideQC`, they mostly apply to the `QuorumCertificate` struct and its methods, as well as the `VoteCollector`.
#### Extra "decide" phase:
```rust
pub enum Phase {
// ↓↓↓ For pipelined flow ↓↓↓ //
Generic,
// ↓↓↓ For phased flow ↓↓↓ //
Prepare,
// The inner view number is the view number of the *prepare* qc contained in the nudge which triggered the
// vote containing this phase.
Precommit(ViewNumber),
// The inner view number is the view number of the *precommit* qc contained in the nudge which triggered the
// vote containing this phase.
Commit(ViewNumber),
// The inner view number is the view number of the *commit* qc contained in the nudge which triggered the
// vote containing this phase.
Decide(ViewNumber),
}
```
We also define the `Ord` trait for `Phase`.
#### `is_correct_and_complete` method for `QuorumCertificate` (update)
Or call it `is_valid` for the sake of brevity.
This method is simply a wrapper for `is_correct`, that takes into account the `validator_set_state`, and tells us how decideQCs should be validated.
Note that this method is designed such that a syncing replica can validate future QCs, even if it does not have an up-to-date `validator_set_state` that would have been required to validate a given QC during the progress mode.
```rust
fn is_correct_and_complete(&self, validator_set_state: ValidatorSetState) -> bool {
if let StableValidatorSet{vs} = validator_set_state {
match self.phase {
Decide(_) => {
let (_, vs_qc) = self.split(vs', vs);
vs_qc.is_correct(vs) &&
vs_qc.phase.is_decide()
// todo: verify if this can be abused, since the decideQC half
// from vs' is not verified
},
_ => self.is_correct(vs)
}
} else if let ValidatorSetUpdate{vs', vs, b} = validator_set_state {
if self.block = b {
Commit(_) | Precommit(_) | Prepare(_) => self.is_correct(vs),
Decide(_) => {
let (vs'_qc, vs_qc) = self.split(vs', vs, Decide, Commit);
vs'_qc.is_correct(vs') && vs_qc.is_correct(vs) &&
vs'_qc.phase.is_decide() && vs_qc.phase.is_decide()
},
Generic => panic!("Validator-set-updating block cannot have a generic QC!"),
} else {
// Assumes that the replica doesn't have to validate blocks older than B,
// so this case corresponds to a block with height > B.height,
// which is should be cryptographically correct for vs'.
self.is_correct(vs')
}
}
}
```
Consider making this a method of the `ValidatorSetState`.
#### `merge` method for `QuorumCertificate`
```rust
fn merge(qc1: QuorumCertificate, qc2: QuorumCertificate) -> QuorumCertificate {
// merges qc1 and qc2 into a single QuorumCertificate
// where the SignatureSet vector consists
// of qc1's and qc2's signature vectors merged
// panics if either qc1 or qc2 is not in "decide" phase
}
```
#### `split` method for `QuorumCertificate`
```rust
fn split(qc: QuorumCertificate, index: u32) -> (QuorumCertificate, QuorumCertificate) {
// splits the given qc into two qc's with
// all fields identical but the SignatureSet vector
// split between the two qc's according to the given index
// panics if qc is nt=ot in "decide" phase
}
```
#### `peek` method for `VoteCollector`
This method is required when on seeing a "decide" phase QC returned by one `VoteCollector`'s collect method, we need to peek and see if the other `VoteCollector` also collected a "decide" phase QC.
```rust
fn peek(self, phase: Phase, block: CryptoHash) -> Option<QuorumCertificate> {
}
```
## `ValidatorSets` module (new)
### #1 `ValidatorSetState` struct
**Note:** alternatively the following code can be part of some other module.
```rust
enum ValidatorSetState = {
StableValidatorSet { validator_set: ValidatorSet},
ValidatorSetUpdate { new_validator_set: ValidatorSet,
old_validator_set: ValidatorSet,
block: CryptoHash,
}
}
```
**Methods:**
#### `i_am_leader`
For `StableValidatorSet{vs}`, a validator is a leader of the current view if it is the leader of the current view for`vs`.
For `ValidatorSetUpdate{vs', vs, b}` a validator is a leader of the current view if and only if:
1. The validator is a leader of the current view for `vs` or `vs'`, and
2. The validator has a `highest_qc` on top of which it can propose or nudge given its membership in the committed or resigning validator set.
```rust
fn i_am_leader(self, cur_view: ViewNumber, highest_qc: QuorumCertificate, pacemaker: impl Pacemaker) -> bool {
match self {
StableValidatorSet(vs) => {
pacemaker.view_leader(cur_view, &vs) == me.public()
},
ValidatorSetUpdate{vs', vs, b} => {
let i_am_leader_of_vs = pacemaker.view_leader(cur_view, &vs) == me.public();
let i_am_leader_of_vs' = pacemaker.view_leader(cur_view, &vs') == me.public();
if i_am_leader_of_vs {
highest_qc.block == b &&
highest_qc.phase <= Commit)
} else if i_am_leader_of_vs' {
highest_qc.block == b &&
highest_qc.phase >= Commit
} else { false }
}
}
```
#### `i_am_voter`
For `StableValidatorSet{vs}`, a validator from `vs` is always a voter (unless the vote is for the "decide" phase in which case the validator set state should have been updated to `ValidatorSetUpdate{vs', vs, b}`).
For `ValidatorSetUpdate{vs', vs, b}` a validator can be a voter for a given nudge or proposal depending on its membership in `vs` or `vs'` and the `justify` QC of the proposal or the nudge.
```rust
fn i_am_voter(self, cur_view: ViewNumber, justify: QuorumCertificate) -> bool {
match self {
StableValidatorSet(_) => true,
ValidatorSetUpdate{vs', vs, b} => {
if (vs.contains(me) && !vs'.contains(me) {
justify.block == b &&
justify.phase <= Commit
} else if (vs'.contains(me) && !vs.contains(me) {
justify.block == b &&
qc.phase >= Commit
} else {
vs.contains(me) && vs'.contains(me)
}
}
}
}
```
#### `next_leader`
By `next_leader` we mean the intended recipient of a given `Vote` message.
For `StableValidatorSet{vs}`, the next leader is simply the leader of the next view for `vs`.
For `ValidatorSetUpdate{vs', vs, b}` the next leader, to whom the vote is addressed, depends on the phase of the vote.
```rust
fn next_leader(self, cur_view, vote: &Vote) -> VerifyingKey {
match self {
StableValidatorSet(vs) => {
pacemaker.view_leader(cur_view+1, &vs)
},
ValidatorSetUpdate{vs', vs, b} => {
if vote.block == b {
match vote.phase {
Prepare | Precommit(_) | Commit(_) => pacemaker.view_leader(cur_view+1, &vs),
Decide(_) => pacemaker.view_leader(cur_view+1, &vs')
}
} else {
panic!("During the Validator Set Update phase a validator can only vote for the validator-set-updating block!")
}
}
}
```
#### `next_leaders`
By `next_leader` we mean the intended recipient(s) (max. 2) of a given `NewView` message.
For `StableValidatorSet{vs}`, the next leader is simply the leader of the next view for `vs`.
For `ValidatorSetUpdate{vs', vs, b}`, the next leaders are the leaders of the next view for `vs'` and `vs` respectively. This means that during the validator set speculation period a NewView message should be sent to both leaders of `vs` and `vs'`, to update both on the `highest_qc` which reflects the state of the protocol.
```rust
fn next_leader(self, cur_view, vote: Vote) -> Vec<VerifyingKey> {
match self {
StableValidatorSet(vs) => {
vec![pacemaker.view_leader(cur_view+1, &vs)]
},
ValidatorSetUpdate{vs', vs, b} => {
vec![pacemaker.view_leader(cur_view+1, &vs'),
pacemaker.view_leader(cur_view+1, &vs)]
}
}
```
## `State` module (update)
We would like to preserve the following **invariant**:
1. After commiting a validator-set-updating block (say block `b` that updates the validator set from `vs` to `vs'`) but before deciding it, `validatorset_state = ValidatorSetUpdate{vs', vs, b}`, and
2. After deciding `b`, but before committing any other validator-set-updating block `validator_set_state = StableValidatorSet{vs'}`.
### `safe_qc`
We add a requirement that `decideQC` must be for a validator-set-updating block:
```rust
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() || qc.phase.is_decide()) && self.pending_validator_set_updates(&qc.block).is_some()) ||
/* 5 */ (qc.phase.is_generic() && self.pending_validator_set_updates(&qc.block).is_none()))
}
```
### `insert_block`
Currently in `insert_block`:
```rust
let committed_blocks = match block.justify.phase {
// ...
Phase::Commit(precommit_qc_view) => {
// Consider setting locked view to precommit_qc_view.
if precommit_qc_view > self.locked_view() {
wb.set_locked_view(precommit_qc_view);
update_locked_view = Some(precommit_qc_view);
}
let parent = block.justify.block;
// Commit parent if not committed yet.
self.commit_block(&mut wb, &parent)
}
}
```
Now `block.justify.phase` must be `Commit(precommit_view)` or `Decide(commit_view)`.
in principle, we no longer need to commit the parent block, since it should have been committed on seeing `Nudge(commitQC)`. However, in case the parent block hasn't been committed yet, because it was received via sync, we commit the parent block.
Hence, on seeing `block.justify.phase = Decide(commit_view)`:
* We commit the parent if it hasn't been committed yet.
* We decide the parent if it has been committed but not decided yet.
```rust
let committed_blocks = match block.justify.phase {
// ...
Phase::Decide(commit_qc_view) => {
let parent = block.justify.block;
// Commit parent if not committed yet.
self.commit_block(&mut wb, &parent)
}
}
// new
let decided_block = match block.justify.phase {
Phase::Decide(commit_qc_view) => {
if let self.validator_set_state() = ValidatorSetUpdate{vs', vs, b} {
if b != block.hash {
panic!("The decided block must be the block causing the
currently considered validator-set-update!")
}
self.remove_resigning_validator_set(&mut wb)
}
// else the block should have been decided by now
}
}
```
Note: alternatively this can be abstracted into a `decide_block` method, for the sake of consistency with `commit_block`.
### `commit_block`
Now on updating the `committed_validator_set`, `commit_block` will also set the `resigning_validator_set`.
```rust
let mut committed_validator_set = self.committed_validator_set();
let resigning_validator_set = self.committed_validator_set();
committed_validator_set.apply_updates(&pending_validator_set_updates);
wb.set_committed_validator_set(&committed_validator_set);
wb.set_resigning_validator_set(&resigning_validator_set);
wb.delete_pending_validator_set_updates(block);
```
### Resolve the issue with `pending_validator_set_updates()`
**Issue**
As seen above, on inserting a block B with a validator-set-updating parent, the `pending_validator_set_updates` associated with the block are deleted.
Hence, if the proposal for B fails and some other block is inserted as a sibling of B, the `safe_qc` check will fail for that block - since the block has a decideQC as the justify but `self.pending_validator_set_updates(B) = None`.
See [the following issue in our GitHub repo](https://github.com/parallelchain-io/hotstuff_rs/issues/28) for more details.
**Solution**
1. One simple solution is to have `self.validator_set_updates(B)` and never delete them, but that's sub-optimal.
2. When can we delete the pending validator set updates associated with a block B? Once, a block with `justify = decideQC for B` becomes committed. But then they shouldn't be called `pending_validator_set_updates`, since they are no longer pending.
3. `self.validator_set_updates(B)` can return a value of type:
```rust
enum ValidatorSetUpdatesState {
Pending{updates: ValidatorSetUpdates},
Resolved,
NoUpdates,
}
```
### `set_resigning_validator_set` and `remove_resigning_validator_set`
Two simple methods to set and empty the resigning validator set field in the `BlockTree`.
## `Algorithm` module (update)
### Two `VoteCollector`s and `NewViewCollector`s
In one view a replica might be collecting votes from two validator sets, for example of the validator is in both resigning and the newly committed validator sets, or the validator is in the newly committed validator set and is collecting "decide" votes from both validator sets.
```rust
let cur_validators = block_tree.committed_validator_set();
//...
// 2. If I am a voter or the next leader, receive and progress messages until view timeout.
let mut committed_vs_vote_collector = VoteCollector::new(chain_id, view, cur_validators.clone());
let mut committed_vs_new_view_collector = NewViewCollector::new(cur_validators.clone());
let mut resigning_vs_vote_collector =
block_tree.resigning_validator_set()
.map(|vs| VoteCollector::new(chain_id, view, vs));
let mut resigning_vs_new_view_collector =
block_tree.resigning_validator_set()
.map(|vs| NewView::new(vs));
```
However, in a view in which a validator receives `Nudge(commitQC)` the new validators can only be created on seeing the `Nudge(commitQC)`.
Hence, the two extra collectors can be created in `on_receive_nudge`.
### `on_receive_nudge`
On receiving `Nudge(commitQC)`:
1. Call `commit_block` on `nudge.justify.block`, and
2. Create a new `VoteCollector` and `NewViewCollector`.
```rust
fn on_receive_nudge<K: KVStore, N: Network>(
origin: &VerifyingKey,
nudge: &Nudge,
me: &Keypair,
chain_id: ChainID,
cur_view: ViewNumber,
block_tree: &mut BlockTree<K>,
pacemaker: &mut impl Pacemaker,
pm_stub: &mut ProgressMessageStub<N>,
event_publisher: &Option<Sender<Event>>,
) -> (bool, bool) {
// ...
if let nudge.justify.phase = Commit(_) {
// commit block if it has not been committed yet
block_tree.commit_block(&mut wb, nudge.justify.block);
// create a new vote collector if not created yet,
if resigning_vs_vote_collector.is_none() && resigning_vs_new_view_collector.is_none() {
resigning_vs_vote_collector =
Some(committed_vs_vote_collector.clone());
resigning_vs_new_view_collector =
Some(committed_vs_new_view_collector.clone());
let mut committed_vs_vote_collector =
VoteCollector::new(chain_id, view, cur_validators.clone());
let mut committed_vs_new_view_collector =
NewViewCollector::new(cur_validators.clone());
}
}
}
```
## Epoch Timeout
As part of the View Sync Protocol implementation, we will introduce an `EpochTimeoutCollector` to collect `EpochTimeout` messages.
Hence, just like with `VoteCollector` and `NewViewCollector`, on seeing `Nudge(commitQC)` an extra `EpochTimeoutCollector` will be created.
We also add an `is_correct` method for `TimeoutCertificate`:
```rust
fn is_correct(self, validator_set_state: ValidatorSetState) -> bool {
// if ValidatorSetUpdate{vs', vs, b}
// then a TC is correct if it is either
// cryptographically correct for vs or vs'
}
```
## Generalizing message collectors
Define a Collectors struct to store all message collectors, and with associated methods to:
1. Create collectors for the current view, and
2. Update the collectors on seeing a `Nudge(commitQC)`.
## Sync
TODO
Note: a decideQC for a block that updates the validator-set from vs to vs' should be validated against both vs and vs'.
Sign in with Wallet
Connect another wallet