use super::{super::Kind, round::Round};
use crate::{
Viewable,
simplex::{
Floor, Lookahead, Viewport,
actors::span::MISSING_SPAN,
elector::{Elector, Mode as _},
metrics::{HandoffAbandonedReason, Leader, Timeout, TimeoutReason},
scheme::Scheme,
types::{
Artifact, Certificate, Context, Finalization, Finalize, Notarization, Notarize,
Nullification, Nullify, Proposal,
},
},
types::{Epoch, Participant, Round as Rnd, TermLength, View, ViewDelta},
};
use commonware_cryptography::{Digest, PublicKey, certificate};
use commonware_runtime::{
Clock, Metrics,
telemetry::metrics::{Counter, CounterFamily, Gauge, GaugeExt, MetricsExt as _},
};
use commonware_utils::futures::Aborter;
use rand_core::CryptoRng;
use std::{
collections::{BTreeMap, BTreeSet},
mem::{replace, take},
time::{Duration, SystemTime},
};
use tracing::{Span, debug, warn};
const GENESIS_VIEW: View = View::zero();
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
enum ParentPayloadError {
#[error("proposal view {proposal_view} is not after parent view {parent_view}")]
ParentNotBeforeProposal {
proposal_view: View,
parent_view: View,
},
#[error(
"intra-term proposal view {proposal_view} skips views between parent view {parent_view} and itself"
)]
IntraTermProposalSkipsViews {
proposal_view: View,
parent_view: View,
},
#[error(
"proposal view {proposal_view} references parent view {parent_view} below last finalized view {last_finalized}"
)]
ParentBeforeFinalized {
proposal_view: View,
parent_view: View,
last_finalized: View,
},
#[error(
"proposal view {proposal_view} references parent view {parent_view} but view {missing_view} is not nullified"
)]
MissingNullification {
proposal_view: View,
parent_view: View,
missing_view: View,
},
#[error(
"proposal view {proposal_view} references parent view {parent_view} but the parent is not certified"
)]
ParentNotCertified {
proposal_view: View,
parent_view: View,
},
}
impl ParentPayloadError {
const fn invalid_proposal(self) -> bool {
match self {
Self::ParentNotBeforeProposal { .. }
| Self::IntraTermProposalSkipsViews { .. }
| Self::ParentBeforeFinalized { .. } => true,
Self::MissingNullification { .. } | Self::ParentNotCertified { .. } => false,
}
}
}
pub(super) enum ProposalRequest<D: Digest, P: PublicKey> {
Prepare(Context<D, P>),
Propose(Context<D, P>),
}
impl<D: Digest, P: PublicKey> ProposalRequest<D, P> {
pub(super) const fn is_handoff(&self) -> bool {
matches!(self, Self::Prepare(_))
}
pub(super) const fn context(&self) -> &Context<D, P> {
match self {
Self::Prepare(context) | Self::Propose(context) => context,
}
}
pub(super) fn into_context(self) -> Context<D, P> {
match self {
Self::Prepare(context) | Self::Propose(context) => context,
}
}
}
impl<D: Digest, P: PublicKey> Viewable for ProposalRequest<D, P> {
fn view(&self) -> View {
self.context().view()
}
}
pub enum Verify<S: Scheme<D>, D: Digest> {
Ready(Context<D, S::PublicKey>, Proposal<D>),
Resolve {
proposal: View,
view: View,
kind: Kind,
target: S::PublicKey,
},
Wait,
}
pub struct CertificateFetch {
pub proposal: View,
pub view: View,
}
pub struct Config<S: certificate::Scheme, L: Elector<S>> {
pub scheme: S,
pub elector: L,
pub epoch: Epoch,
pub view_retention: ViewDelta,
pub leader_timeout: Duration,
pub certification_timeout: Duration,
pub timeout_retry: Duration,
pub skip_budget: u64,
}
pub struct State<E: Clock + CryptoRng + Metrics, S: Scheme<D>, L: Elector<S>, D: Digest> {
context: E,
scheme: S,
elector: L,
epoch: Epoch,
lookahead: Lookahead,
view_retention: ViewDelta,
leader_timeout: Duration,
certification_timeout: Duration,
timeout_retry: Duration,
skip_budget: u64,
view: View,
last_finalized: View,
genesis: Option<D>,
views: BTreeMap<View, Round<S, D>>,
stall_anchor: View,
nullify_views: BTreeSet<View>,
nullification_views: BTreeSet<View>,
failed_certifications: BTreeSet<View>,
certification_candidates: BTreeSet<View>,
outstanding_certifications: BTreeSet<View>,
current_view: Gauge,
tracked_views: Gauge,
issuance_window_probes: Counter,
timeouts: CounterFamily<Timeout>,
nullifications: CounterFamily<Leader<S::PublicKey>>,
}
impl<E: Clock + CryptoRng + Metrics, S: Scheme<D>, L: Elector<S>, D: Digest> State<E, S, L, D> {
fn in_issuance_window(&self, view: View) -> bool {
let Some(floor) = self.lookahead.issuance_floor(view) else {
return false;
};
if floor == GENESIS_VIEW {
return true;
}
let mut probes = 0;
let in_window = self.views.range(floor..view).any(|(_, round)| {
probes += 1;
round.is_directly_notarized()
});
self.issuance_window_probes.inc_by(probes);
in_window
}
fn in_issuance_window_from(&self, anchor: View, pending: View) -> bool {
anchor < pending
&& self
.lookahead
.issuance_floor(pending)
.is_some_and(|floor| floor <= anchor)
}
fn next_tracked_view(&self, from: View) -> Option<View> {
self.views.range(from..).next().map(|(&view, _)| view)
}
pub fn new(context: E, cfg: Config<S, L>) -> Self {
let current_view = context.gauge("current_view", "current view");
let tracked_views = context.gauge("tracked_views", "tracked views");
let issuance_window_probes = context.counter(
"issuance_window_probes",
"rounds inspected for optimistic issuance anchors",
);
let timeouts = context.family("timeouts", "timed out views");
let nullifications = context.family("nullifications", "nullifications");
let lookahead = Lookahead::new(&cfg.elector.terms());
Self {
context,
scheme: cfg.scheme,
elector: cfg.elector,
epoch: cfg.epoch,
lookahead,
view_retention: cfg.view_retention,
leader_timeout: cfg.leader_timeout,
certification_timeout: cfg.certification_timeout,
timeout_retry: cfg.timeout_retry,
skip_budget: cfg.skip_budget,
view: GENESIS_VIEW,
last_finalized: GENESIS_VIEW,
genesis: None,
views: BTreeMap::new(),
stall_anchor: GENESIS_VIEW,
nullify_views: BTreeSet::new(),
nullification_views: BTreeSet::new(),
failed_certifications: BTreeSet::new(),
certification_candidates: BTreeSet::new(),
outstanding_certifications: BTreeSet::new(),
current_view,
tracked_views,
issuance_window_probes,
timeouts,
nullifications,
}
}
pub fn set_genesis(&mut self, genesis: D) {
self.genesis = Some(genesis);
self.enter_view(GENESIS_VIEW.next());
self.set_leader(GENESIS_VIEW.next(), None);
}
pub fn set_floor(&mut self, floor: Floor<S, D>) -> Option<Finalization<S, D>> {
match floor {
Floor::Genesis(genesis) => {
self.set_genesis(genesis);
None
}
Floor::Finalized(finalization) => {
let view = finalization.view();
self.add_finalization(finalization);
self.broadcast_finalization(view)
}
}
}
pub const fn epoch(&self) -> Epoch {
self.epoch
}
pub const fn current_view(&self) -> View {
self.view
}
pub const fn last_finalized(&self) -> View {
self.last_finalized
}
pub const fn min_active(&self) -> View {
self.viewport().floor()
}
const fn term_length(&self) -> TermLength {
self.lookahead.term_length
}
const fn viewport(&self) -> Viewport {
Viewport {
finalized: self.last_finalized,
current: self.view,
view_retention: self.view_retention,
lookahead: self.lookahead,
}
}
pub fn admits_vote(&self, pending: View) -> bool {
self.viewport().admits_vote(pending)
}
pub const fn admits_certificate(&self, pending: View) -> bool {
self.viewport().admits_certificate(pending)
}
fn admits_outbound(&self, view: View) -> bool {
self.lookahead.admits_outbound(self.view, view)
}
pub fn is_me(&self, idx: Participant) -> bool {
self.scheme.me().is_some_and(|m| m.signer() == Some(idx))
}
fn enter_view(&mut self, view: View) -> bool {
if view <= self.view {
return false;
}
let now = self.context.current();
let leader_deadline = now + self.leader_timeout;
let certification_deadline = now + self.certification_timeout;
let stall_deadline = self
.elector
.terms()
.stall_timeout()
.map(|timeout| now + timeout);
let round = self.create_round(view);
round.mark_entered(now);
round.open_span();
round.set_deadlines(leader_deadline, certification_deadline, stall_deadline);
self.view = view;
let _ = self.current_view.try_set(view.get());
true
}
fn leader_is_set(&self, view: View) -> bool {
self.views
.get(&view)
.is_some_and(|round| round.leader().is_some())
}
fn set_leader(&mut self, view: View, certificate: Option<&S::Certificate>) {
if self.leader_is_set(view) {
return;
}
let leader = self
.elector
.elect(Rnd::new(self.epoch, view), L::Mode::input(certificate));
self.create_round(view).set_leader(leader);
}
fn inherit_leader(&mut self, from: View, to: View) {
if self.leader_is_set(to) {
return;
}
let Some(leader) = self
.views
.get(&from)
.and_then(|round| round.leader())
.map(|leader| leader.idx)
else {
return;
};
self.create_round(to).set_leader(leader);
}
fn create_round(&mut self, view: View) -> &mut Round<S, D> {
self.views
.entry(view)
.or_insert_with(|| Round::new(self.scheme.clone(), Rnd::new(self.epoch, view)))
}
pub fn view_span(&self, view: View) -> &Span {
self.views
.get(&view)
.map_or(&MISSING_SPAN, |round| round.span())
}
pub fn close_decided_spans(&mut self) {
for (_, round) in self.views.range_mut(..=self.last_finalized) {
round.close_span();
}
}
pub fn next_timeout(&mut self) -> (SystemTime, TimeoutReason) {
let now = self.context.current();
let timeout_retry = self.timeout_retry;
let allow_latched_timeout = self.has_skip_budget();
let round_timeout = {
let round = self
.views
.get_mut(&self.view)
.expect("current round must exist");
round
.next_timeout(now, timeout_retry, allow_latched_timeout)
.expect("current round must always have a timeout")
};
if matches!(round_timeout.1, TimeoutReason::Retry) {
return round_timeout;
}
self.next_stall_timeout()
.filter(|&deadline| deadline <= round_timeout.0 && now < round_timeout.0)
.map(|deadline| (deadline, TimeoutReason::StallTimeout))
.unwrap_or(round_timeout)
}
const fn has_skip_budget(&self) -> bool {
let term_length = self.term_length();
let first_unfinalized = self.last_finalized.next().term_index(term_length);
let current = self.view.term_index(term_length);
let spent = current
.checked_sub(first_unfinalized)
.expect("current term must not precede the first unfinalized term");
spent < self.skip_budget
}
fn next_stall_timeout(&mut self) -> Option<SystemTime> {
let term_start = self.view.term_start(self.term_length());
let unfinalized_view = self.last_finalized.next().max(term_start);
let start = self.stall_anchor.max(unfinalized_view);
let (anchor, deadline) = self
.views
.range(start..=self.view)
.find_map(|(view, round)| round.stall_deadline().map(|d| (*view, d)))?;
self.stall_anchor = anchor;
Some(deadline)
}
pub fn construct_nullify(
&mut self,
view: View,
reason: TimeoutReason,
) -> Option<(bool, Nullify<S>)> {
if view != self.view {
return None;
}
let (is_retry, leader) = {
let round = self.create_round(view);
(round.construct_nullify()?, round.leader().cloned())
};
let nullify = Nullify::sign::<D>(&self.scheme, Rnd::new(self.epoch, view))?;
self.nullify_views.insert(view);
if !is_retry && let Some(leader) = leader {
self.timeouts
.get_or_create(&Timeout::new(&leader.key, reason))
.inc();
}
Some((is_retry, nullify))
}
pub fn get_best_certificate(&self) -> Option<Certificate<S, D>> {
let prev = self
.view
.previous()
.expect("we should never be in the genesis view");
if prev == GENESIS_VIEW {
return None;
}
if let Some(finalization) = self.finalization(prev).cloned() {
return Some(Certificate::Finalization(finalization));
}
if self.view.is_term_start(self.term_length())
&& let Some(nullification) = self
.highest_nullification_in_term(prev)
.and_then(|v| self.nullification(v).cloned())
{
return Some(Certificate::Nullification(nullification));
}
if let Some(notarization) = self.notarization(prev).cloned() {
return Some(Certificate::Notarization(notarization));
}
warn!(%prev, "entry certificate not found");
None
}
pub fn add_notarization(
&mut self,
notarization: Notarization<S, D>,
) -> (bool, Option<S::PublicKey>) {
let view = notarization.view();
self.set_leader(view.next(), Some(¬arization.certificate));
let result = self.create_round(view).add_notarization(notarization);
if result.0 {
if view > self.last_finalized {
self.certification_candidates.insert(view);
}
self.slide_optimistic_frontier(view);
}
result
}
pub fn add_nullification(&mut self, nullification: Nullification<S>) -> bool {
let view = nullification.view();
let next_view = view.next_term_start(self.term_length());
self.enter_view(next_view);
self.set_leader(next_view, Some(&nullification.certificate));
let round = self.create_round(view);
let added = round.add_nullification(nullification);
let leader = added.then(|| round.leader().cloned()).flatten();
self.nullification_views.insert(view);
if let Some(leader) = leader {
self.nullifications.get_or_create_by(&leader.key).inc();
}
added
}
pub fn add_finalization(
&mut self,
finalization: Finalization<S, D>,
) -> (bool, Option<S::PublicKey>) {
let view = finalization.view();
if view > self.last_finalized {
self.last_finalized = view;
self.failed_certifications = self.failed_certifications.split_off(&view.next());
self.certification_candidates.retain(|v| *v > view);
let keep = self.outstanding_certifications.split_off(&view.next());
for v in replace(&mut self.outstanding_certifications, keep) {
if let Some(round) = self.views.get_mut(&v) {
round.abort_certify();
}
}
}
self.enter_view(view.next());
self.set_leader(view.next(), Some(&finalization.certificate));
let result = self.create_round(view).add_finalization(finalization);
if result.0 {
self.wake_certification_child(view);
self.slide_optimistic_frontier(view);
}
result
}
fn optimistic_parent_ready(&self, view: View) -> bool {
let Some(parent) = self.previous_in_term(view) else {
return true;
};
self.optimistic_ancestry_payload(parent).is_some()
}
pub fn construct_notarize(&mut self, view: View) -> Option<Notarize<S, D>> {
if !self.admits_outbound(view) {
return None;
}
if !self.views.get(&view)?.can_construct_notarize() {
return None;
}
if self.in_issuance_window(view) && !self.optimistic_parent_ready(view) {
return None;
}
if !self.verification_matches(view) {
return None;
}
let candidate = self
.views
.get_mut(&view)
.and_then(|round| round.construct_notarize().cloned())?;
self.prepare_optimistic_successor(view);
Notarize::sign(&self.scheme, candidate)
}
pub fn construct_finalize(&mut self, view: View) -> Option<Finalize<S, D>> {
if view <= self.last_finalized {
return None;
}
if !self.admits_outbound(view) {
return None;
}
if let Some(nullified) = self
.highest_local_nullify_in_term(view)
.filter(|nullified| *nullified > self.last_finalized)
{
debug!(%view, %nullified, "withholding finalize vote due to same-term nullify");
return None;
}
let proposal = self.views.get(&view)?.proposal()?;
if !self.explicit_parent_ready(proposal) {
return None;
}
let candidate = self.views.get_mut(&view)?.construct_finalize()?.clone();
Finalize::sign(&self.scheme, candidate)
}
pub fn broadcast_notarization(&mut self, view: View) -> Option<Notarization<S, D>> {
self.views
.get_mut(&view)
.and_then(|round| round.broadcast_notarization())
}
pub fn notarization(&self, view: View) -> Option<&Notarization<S, D>> {
self.views.get(&view).and_then(|round| round.notarization())
}
pub fn nullification(&self, view: View) -> Option<&Nullification<S>> {
self.views
.get(&view)
.and_then(|round| round.nullification())
}
pub fn finalization(&self, view: View) -> Option<&Finalization<S, D>> {
self.views.get(&view).and_then(|round| round.finalization())
}
pub fn forwardable_proposal(&self, view: View) -> Option<Proposal<D>> {
self.views.get(&view)?.forwardable_proposal().cloned()
}
pub fn broadcast_nullification(&mut self, view: View) -> Option<Nullification<S>> {
self.views
.get_mut(&view)
.and_then(|round| round.broadcast_nullification())
}
pub fn broadcast_finalization(&mut self, view: View) -> Option<Finalization<S, D>> {
self.views
.get_mut(&view)
.and_then(|round| round.broadcast_finalization())
}
pub fn replay(&mut self, artifact: &Artifact<S, D>) {
if let Artifact::Nullify(n) = artifact {
self.nullify_views.insert(n.view());
}
if let Artifact::Nullification(n) = artifact {
self.nullification_views.insert(n.view());
}
if matches!(artifact, Artifact::Certification(_, false))
&& artifact.view() > self.last_finalized
{
self.failed_certifications.insert(artifact.view());
}
let binding = if let Artifact::Notarize(notarize) = artifact {
self.views
.get(¬arize.proposal.parent)
.filter(|parent| !parent.is_directly_notarized())
.and_then(|parent| parent.proposal())
.map(|parent| (notarize.proposal.clone(), parent.payload))
} else {
None
};
let round = self.create_round(artifact.view());
round.replay(artifact);
if let Some((proposal, parent_payload)) = binding {
round.set_verifying(proposal, parent_payload);
}
if matches!(artifact, Artifact::Notarize(_)) {
self.prepare_optimistic_successor(artifact.view());
}
}
pub fn leader_index(&self, view: View) -> Option<Participant> {
self.views
.get(&view)
.and_then(|round| round.leader().map(|leader| leader.idx))
}
pub fn elapsed_since_start(&self, view: View) -> Option<Duration> {
let now = self.context.current();
self.views
.get(&view)
.and_then(|round| round.elapsed_since_start(now))
}
pub fn elapsed_since_entry(&self, view: View) -> Option<Duration> {
let now = self.context.current();
self.views
.get(&view)
.and_then(|round| round.elapsed_since_entry(now))
}
pub fn trigger_timeout(&mut self, view: View, reason: TimeoutReason) {
if view < self.view {
return;
}
let now = self.context.current();
let Some(round) = self.views.get_mut(&view) else {
return;
};
if matches!(reason, TimeoutReason::Inactivity) && round.has_unequivocated_proposal() {
return;
}
round.latch_timeout(now, reason);
}
pub(super) fn try_propose(&mut self) -> Option<ProposalRequest<D, S::PublicKey>> {
let limit = self.view.next_term_start(self.term_length());
let mut cursor = self.view;
while let Some(view) = self.next_tracked_view(cursor) {
if view > limit {
break;
}
cursor = view.next();
if view == GENESIS_VIEW {
continue;
}
if !self.admits_outbound(view) {
continue;
}
if !self
.views
.get(&view)
.is_some_and(|round| round.should_propose())
{
continue;
}
let (parent_view, parent_payload) = match self.find_parent(view) {
Ok(parent) => parent,
Err(missing) => {
debug!(%view, %missing, "missing parent during proposal");
continue;
}
};
let is_handoff = view.is_term_start(self.term_length())
&& !self.parent_certified((parent_view, parent_payload));
if is_handoff && self.voted_nullify(self.view) {
continue;
}
let Some(leader) = self
.views
.get_mut(&view)
.and_then(|round| round.try_propose())
else {
continue;
};
let context = Context {
round: Rnd::new(self.epoch, view),
leader: leader.key,
parent: (parent_view, parent_payload),
};
return Some(if is_handoff {
ProposalRequest::Prepare(context)
} else {
ProposalRequest::Propose(context)
});
}
None
}
pub(super) fn parent_certified(&self, (view, payload): (View, D)) -> bool {
self.explicit_ancestry_payload(view) == Some(&payload)
}
pub(super) fn voted_nullify(&self, view: View) -> bool {
self.nullify_views.contains(&view)
}
pub(super) fn pending_handoff_abandonment(
&self,
context: &Context<D, S::PublicKey>,
) -> Option<HandoffAbandonedReason> {
if self.parent_certified(context.parent) {
return None;
}
if self.voted_nullify(self.view) {
return Some(HandoffAbandonedReason::ParentNullify);
}
(!self.captured_parent_valid(context, self.find_parent(context.view())))
.then_some(HandoffAbandonedReason::AncestryInvalidated)
}
pub fn proposed(&mut self, context: &Context<D, S::PublicKey>, payload: D) -> bool {
if !self.captured_parent_valid(context, self.find_parent(context.view())) {
return false;
}
let proposal = Proposal::new(context.round, context.parent.0, payload);
if !self.record_proposed(proposal.clone()) {
return false;
}
if let Some(round) = self.views.get_mut(&proposal.view()) {
assert_eq!(round.proposal(), Some(&proposal));
round.set_verifying(proposal, context.parent.1);
}
true
}
pub fn supersede_proposal_request(&mut self, context: &Context<D, S::PublicKey>) -> bool {
let preferred = self.find_parent(context.view());
if preferred.is_err() || self.captured_parent_valid(context, preferred) {
return false;
}
self.release_proposal_request(context.view());
true
}
pub(super) fn release_proposal_request(&mut self, view: View) {
if let Some(round) = self.views.get_mut(&view) {
round.clear_proposal_request();
}
}
fn captured_parent_valid(
&self,
context: &Context<D, S::PublicKey>,
preferred: Result<(View, D), View>,
) -> bool {
preferred == Ok(context.parent)
|| self.parent_payload_for(context.view(), context.parent.0) == Ok(context.parent.1)
}
fn record_proposed(&mut self, proposal: Proposal<D>) -> bool {
let now = self.context.current();
self.views
.get_mut(&proposal.view())
.map(|round| round.proposed(now, proposal))
.unwrap_or(false)
}
pub fn set_proposal(&mut self, view: View, proposal: &Proposal<D>) -> bool {
self.prepare_optimistic_successor(view);
self.create_round(view).set_proposal(proposal)
}
fn resolve_ancestry(&self, err: &ParentPayloadError) -> Option<(View, Kind)> {
match err {
ParentPayloadError::MissingNullification { missing_view, .. } => {
Some((*missing_view, Kind::Nullification))
}
ParentPayloadError::ParentNotCertified {
proposal_view,
parent_view,
} => {
if self.in_issuance_window(*proposal_view) {
return None;
}
Some((*parent_view, Kind::Notarization))
}
_ => None,
}
}
pub fn try_verify(&mut self) -> Verify<S, D> {
let limit = self.view.next_term_start(self.term_length());
let mut cursor = self.view;
while let Some(view) = self.next_tracked_view(cursor) {
if view > limit {
break;
}
cursor = view.next();
if !self.admits_outbound(view) {
continue;
}
let Some((leader, proposal)) = self
.views
.get(&view)
.and_then(|round| round.pending_verification())
else {
continue;
};
let parent_payload = match self.parent_payload(&proposal) {
Ok(parent_payload) => parent_payload,
Err(err) => {
if err.invalid_proposal() {
warn!(round = ?proposal.round, ?err, "proposal failed verification");
self.trigger_timeout(view, TimeoutReason::InvalidProposal);
continue;
}
debug!(
%view,
?proposal,
?err,
"proposal exists but ancestry is not yet certified"
);
let Some((missing, kind)) = self.resolve_ancestry(&err) else {
continue;
};
if !self
.views
.get_mut(&view)
.expect("tracked round must exist")
.request(missing)
{
continue;
}
return Verify::Resolve {
proposal: proposal.view(),
view: missing,
kind,
target: leader.key,
};
}
};
let Some(round) = self.views.get_mut(&view) else {
continue;
};
if !round.request_verify() {
continue;
}
round.set_verifying(proposal.clone(), parent_payload);
return Verify::Ready(
Context {
round: proposal.round,
leader: leader.key,
parent: (proposal.parent, parent_payload),
},
proposal,
);
}
Verify::Wait
}
fn verification_is_stale(&mut self, view: View) -> bool {
if self.verification_matches(view) {
return false;
}
if let Some(round) = self.views.get_mut(&view) {
round.clear_verifying();
}
true
}
pub fn verified(&mut self, view: View) -> bool {
if self.verification_is_stale(view) {
return false;
}
self.views
.get_mut(&view)
.map(|round| round.verified())
.unwrap_or(false)
}
pub fn verification_failed(&mut self, view: View, reason: TimeoutReason) {
if self.verification_is_stale(view) {
return;
}
self.trigger_timeout(view, reason);
}
pub fn set_certify_handle(&mut self, view: View, handle: Aborter) {
let Some(round) = self.views.get_mut(&view) else {
return;
};
round.set_certify_handle(handle);
self.outstanding_certifications.insert(view);
}
fn wake_certification_child(&mut self, parent: View) {
let child = parent.next();
if child <= self.last_finalized {
return;
}
let Some(round) = self.views.get(&child) else {
return;
};
let Some(proposal) = round.proposal() else {
return;
};
if round.notarization().is_none()
|| self.required_certification_parent(proposal) != Some(parent)
{
return;
}
self.certification_candidates.insert(child);
}
pub fn certify_candidates(&mut self) -> (Vec<Proposal<D>>, Vec<CertificateFetch>) {
let candidates = take(&mut self.certification_candidates);
let mut ready = Vec::new();
let mut fetches = Vec::new();
for view in candidates {
if view <= self.last_finalized {
continue;
}
let Some(proposal) = self
.views
.get(&view)
.and_then(|round| round.proposal())
.cloned()
else {
continue;
};
if let Err(err) = self.certification_parent_ready(&proposal) {
if err.invalid_proposal() {
warn!(round = ?proposal.round, ?err, "proposal failed certification precheck");
} else {
assert!(
matches!(err, ParentPayloadError::ParentNotCertified { .. }),
"blocked candidate has no wake: {err:?}"
);
fetches.extend(self.certification_fetch(&err));
}
continue;
}
if let Some(candidate) = self
.views
.get(&view)
.and_then(|round| round.pending_certification())
{
ready.push(candidate);
}
}
(ready, fetches)
}
fn certification_fetch(&self, err: &ParentPayloadError) -> Option<CertificateFetch> {
let ParentPayloadError::ParentNotCertified {
proposal_view,
parent_view,
} = err
else {
return None;
};
if self.notarization(*parent_view).is_some() {
return None;
}
Some(CertificateFetch {
proposal: *proposal_view,
view: *parent_view,
})
}
pub fn certified(&mut self, view: View, is_success: bool) -> Option<Notarization<S, D>> {
let round = self.views.get_mut(&view)?;
round.certified(is_success);
let notarization = round
.notarization()
.cloned()
.expect("notarization must exist for certified view");
self.outstanding_certifications.remove(&view);
if !is_success && view > self.last_finalized {
self.failed_certifications.insert(view);
}
if is_success {
self.enter_view(view.next());
self.wake_certification_child(view);
} else {
self.trigger_timeout(view, TimeoutReason::FailedCertification);
}
Some(notarization)
}
pub fn prune(&mut self) -> Vec<View> {
let min = self.min_active();
let kept = self.views.split_off(&min);
let removed = replace(&mut self.views, kept).into_keys().collect();
self.nullification_views = self.nullification_views.split_off(&min);
self.nullify_views = self.nullify_views.split_off(&min);
let _ = self.tracked_views.try_set(self.views.len());
removed
}
fn explicit_ancestry_payload(&self, view: View) -> Option<&D> {
if view == GENESIS_VIEW {
return Some(self.genesis.as_ref().expect("genesis must be present"));
}
self.views.get(&view)?.certified_payload()
}
fn highest_nullification_in_term(&self, view: View) -> Option<View> {
self.nullification_views
.range(view.covering_range(self.term_length()))
.next_back()
.copied()
}
fn highest_local_nullify_in_term(&self, view: View) -> Option<View> {
let term_start = view.term_start(self.term_length());
self.nullify_views
.range(term_start..view)
.next_back()
.copied()
}
fn ancestry_payload_for_child(&self, child: View, parent: View) -> Option<&D> {
if self.in_issuance_window(child) {
return self.optimistic_ancestry_payload(parent);
}
self.explicit_ancestry_payload(parent)
}
fn has_failed_optimistic_ancestry(&self, view: View) -> bool {
self.failed_certifications
.range(view.term_start(self.term_length())..=view)
.next()
.is_some()
}
fn handoff_leader(&self, view: View) -> Option<Participant> {
if !view.is_term_start(self.term_length()) {
return None;
}
let input = L::Mode::early()?;
Some(self.elector.elect(Rnd::new(self.epoch, view), input))
}
fn is_handoff_parent(&self, parent: View) -> bool {
self.handoff_leader(parent.next())
.is_some_and(|leader| self.is_me(leader))
&& self.highest_nullification_in_term(parent).is_none()
}
fn optimistic_ancestry_payload(&self, view: View) -> Option<&D> {
if view == GENESIS_VIEW {
return Some(self.genesis.as_ref().expect("genesis must be present"));
}
let round = self.views.get(&view)?;
if round.is_directly_notarized() {
if self.has_failed_optimistic_ancestry(view) {
return None;
}
return round.certificate_ancestry_payload();
}
if !self.in_issuance_window(view.next()) && !self.is_handoff_parent(view) {
return None;
}
if !round.has_unequivocated_proposal()
|| !round.broadcast_notarize()
|| !round.is_verified()
{
return None;
}
let proposal = round.proposal()?;
if proposal.parent < self.last_finalized {
return None;
}
if let Some(missing_view) = self.first_unnullified_view(proposal.parent, proposal.view()) {
debug!(%view, %missing_view, "optimistic ancestor missing nullification");
return None;
}
let parent_payload = self.optimistic_ancestry_payload(proposal.parent)?;
if let Some((_, expected_parent)) = round.verifying()
&& parent_payload != expected_parent
{
return None;
}
Some(&proposal.payload)
}
fn prepare_optimistic_successor(&mut self, view: View) {
let next = view.next();
if self.in_issuance_window(next) {
self.inherit_leader(view, next);
return;
}
if !self
.views
.get(&view)
.is_some_and(|round| round.broadcast_notarize())
{
return;
}
if let Some(leader) = self
.handoff_leader(next)
.filter(|leader| self.is_me(*leader))
&& !self.leader_is_set(next)
{
self.create_round(next).set_leader(leader);
}
}
fn slide_optimistic_frontier(&mut self, view: View) {
let mut frontier = view;
let mut next = frontier.next();
while self.in_issuance_window_from(view, next) {
self.inherit_leader(frontier, next);
frontier = next;
next = frontier.next();
}
}
fn verification_matches(&self, view: View) -> bool {
let Some(round) = self.views.get(&view) else {
return true;
};
let Some((verifying, parent_payload)) = round.verifying() else {
return true;
};
let Some(proposal) = round.proposal() else {
return false;
};
if proposal != verifying {
return false;
}
self.parent_payload(proposal)
.is_ok_and(|payload| payload == *parent_payload)
|| (self
.leader_index(view)
.is_some_and(|leader| self.is_me(leader))
&& self.find_parent(view) == Ok((proposal.parent, *parent_payload)))
}
fn previous_in_term(&self, view: View) -> Option<View> {
if view == GENESIS_VIEW || view.is_term_start(self.term_length()) {
return None;
}
Some(
view.previous()
.expect("non-genesis non-term-start views must have a predecessor"),
)
}
fn first_unnullified_view(&self, after: View, before: View) -> Option<View> {
let mut cursor = after.next();
while cursor < before {
if self.highest_nullification_in_term(cursor).is_none() {
return Some(cursor);
}
cursor = cursor.next_term_start(self.term_length());
}
None
}
#[cfg(test)]
pub fn is_certify_aborted(&self, view: View) -> bool {
self.views
.get(&view)
.is_some_and(|round| round.is_certify_aborted())
}
fn find_parent(&self, view: View) -> Result<(View, D), View> {
if !view.is_term_start(self.term_length()) {
let parent = view
.previous()
.expect("non-genesis views must have a previous view");
let payload = self.ancestry_payload_for_child(view, parent);
return payload
.copied()
.map(|payload| (parent, payload))
.ok_or(parent);
}
let result = self
.views
.range(..view)
.rev()
.find_map(|(&v, round)| round.certified_payload().map(|p| (v, p)));
let (candidate, payload) = match result {
Some((v, p)) => (v, p),
None => (
GENESIS_VIEW,
self.genesis
.as_ref()
.expect("genesis must be set when finding parent with no certified views"),
),
};
if let Some(missing_view) = self.first_unnullified_view(candidate, view) {
let parent = view
.previous()
.expect("non-genesis views must have a previous view");
if self.is_handoff_parent(parent)
&& let Some(payload) = self.optimistic_ancestry_payload(parent)
{
return Ok((parent, *payload));
}
return Err(missing_view);
}
Ok((candidate, *payload))
}
fn parent_payload(&self, proposal: &Proposal<D>) -> Result<D, ParentPayloadError> {
self.parent_payload_for(proposal.view(), proposal.parent)
}
fn parent_payload_for(&self, view: View, parent: View) -> Result<D, ParentPayloadError> {
self.validate_parent_span(view, parent)?;
let payload = self.ancestry_payload_for_child(view, parent);
payload
.copied()
.ok_or(ParentPayloadError::ParentNotCertified {
proposal_view: view,
parent_view: parent,
})
}
fn certification_parent_ready(&self, proposal: &Proposal<D>) -> Result<(), ParentPayloadError> {
let (view, parent) = (proposal.view(), proposal.parent);
Self::ensure_parent_precedes(view, parent)?;
let Some(required) = self.required_certification_parent(proposal) else {
return Ok(());
};
self.validate_parent_span(view, parent)?;
if self.explicit_ancestry_payload(required).is_some() {
return Ok(());
}
Err(ParentPayloadError::ParentNotCertified {
proposal_view: view,
parent_view: parent,
})
}
fn required_certification_parent(&self, proposal: &Proposal<D>) -> Option<View> {
let view = proposal.view();
self.previous_in_term(view).or_else(|| {
let previous = view.previous()?;
(proposal.parent == previous
&& self
.handoff_leader(view)
.is_some_and(|leader| self.is_me(leader))
&& self
.views
.get(&view)
.is_some_and(|round| round.broadcast_notarize()))
.then_some(previous)
})
}
fn explicit_parent_ready(&self, proposal: &Proposal<D>) -> bool {
self.required_certification_parent(proposal)
.is_none_or(|parent| self.explicit_ancestry_payload(parent).is_some())
}
fn ensure_parent_precedes(view: View, parent: View) -> Result<(), ParentPayloadError> {
if view <= parent {
return Err(ParentPayloadError::ParentNotBeforeProposal {
proposal_view: view,
parent_view: parent,
});
}
Ok(())
}
fn validate_parent_span(&self, view: View, parent: View) -> Result<(), ParentPayloadError> {
Self::ensure_parent_precedes(view, parent)?;
if parent < self.last_finalized {
return Err(ParentPayloadError::ParentBeforeFinalized {
proposal_view: view,
parent_view: parent,
last_finalized: self.last_finalized,
});
}
if !view.is_term_start(self.term_length()) && view != parent.next() {
return Err(ParentPayloadError::IntraTermProposalSkipsViews {
proposal_view: view,
parent_view: parent,
});
}
if let Some(missing_view) = self.first_unnullified_view(parent, view) {
return Err(ParentPayloadError::MissingNullification {
proposal_view: view,
parent_view: parent,
missing_view,
});
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
Automaton as _,
simplex::{
elector::{Config as _, Dynamic, RoundRobin, RoundRobinElector, Terms},
mocks,
scheme::ed25519,
types::{
Finalization, Finalize, Notarization, Notarize, Nullification, Nullify, Proposal,
},
},
};
use commonware_codec::Encode as _;
use commonware_cryptography::{
Hasher as _,
certificate::{Scheme as _, mocks::Fixture},
sha256::{Digest as Sha256Digest, Sha256},
};
use commonware_macros::test_traced;
use commonware_p2p::Recipients;
use commonware_parallel::Sequential;
use commonware_runtime::{Runner, Supervisor as _, deterministic};
use commonware_utils::{NZU32, futures::AbortablePool, non_empty};
use std::{marker::PhantomData, sync::Arc, time::Duration};
fn round_robin<S: certificate::Scheme>(scheme: &S) -> RoundRobinElector<S> {
<RoundRobin>::default().build(scheme.participants())
}
fn round_robin_with_term<S: certificate::Scheme>(
scheme: &S,
term_length: TermLength,
stall_timeout: Duration,
optimistic_views: ViewDelta,
) -> RoundRobinElector<S> {
<RoundRobin>::default()
.with_term(term_length, stall_timeout, optimistic_views)
.build(scheme.participants())
}
fn test_genesis() -> Sha256Digest {
Sha256Digest::from([0u8; 32])
}
fn fetch_proposal(view: u64, parent: u64, payload: u8) -> Proposal<Sha256Digest> {
Proposal::new(
Rnd::new(Epoch::new(9), View::new(view)),
View::new(parent),
Sha256Digest::from([payload; 32]),
)
}
fn certify_first_view(
state: &mut TestState,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
) {
let proposal = fetch_proposal(1, 0, 101);
let notarization = build_notarization(verifier, schemes, &proposal);
assert!(state.add_notarization(notarization).0);
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready.len(), 1);
assert!(fetches.is_empty());
assert!(state.certified(View::new(1), true).is_some());
}
fn build_notarization(
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
proposal: &Proposal<Sha256Digest>,
) -> Notarization<ed25519::Scheme, Sha256Digest> {
let votes: Vec<_> = schemes
.iter()
.map(|scheme| Notarize::sign(scheme, proposal.clone()).expect("notarize"))
.collect();
Notarization::from_notarizes(verifier, non_empty![@votes.iter()], &Sequential)
.expect("notarization")
}
fn build_nullification(
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
round: Rnd,
) -> Nullification<ed25519::Scheme> {
let votes: Vec<_> = schemes
.iter()
.map(|scheme| Nullify::sign::<Sha256Digest>(scheme, round).expect("nullify"))
.collect();
Nullification::from_nullifies(verifier, non_empty![@&votes], &Sequential)
.expect("nullification")
}
fn build_finalization(
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
proposal: &Proposal<Sha256Digest>,
) -> Finalization<ed25519::Scheme, Sha256Digest> {
let votes: Vec<_> = schemes
.iter()
.map(|scheme| Finalize::sign(scheme, proposal.clone()).expect("finalize"))
.collect();
Finalization::from_finalizes(verifier, non_empty![@votes.iter()], &Sequential)
.expect("finalization")
}
#[test_traced]
fn decided_views_close_their_view_span() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(7);
let mut state = State::new(
context,
Config {
scheme: verifier.clone(),
elector: round_robin(&verifier),
epoch,
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: verifier.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let finalize_view = View::new(2);
let finalize_round = Rnd::new(epoch, finalize_view);
let proposal =
Proposal::new(finalize_round, GENESIS_VIEW, Sha256Digest::from([7u8; 32]));
let finalization = build_finalization(&verifier, &schemes, &proposal);
state.add_finalization(finalization);
assert_eq!(state.last_finalized(), finalize_view);
assert!(!state.view_span(View::new(1)).is_none());
assert!(state.view_span(finalize_view).is_none());
assert!(!state.view_span(View::new(3)).is_none());
state.close_decided_spans();
assert!(state.view_span(View::new(1)).is_none());
assert!(state.view_span(finalize_view).is_none());
assert!(!state.view_span(View::new(3)).is_none());
});
}
type TestState = State<
deterministic::Context,
ed25519::Scheme,
RoundRobinElector<ed25519::Scheme>,
Sha256Digest,
>;
fn setup_state(
context: &mut deterministic::Context,
validators: usize,
epoch: u64,
view_retention: u64,
term_length: u32,
skip_budget: u64,
) -> (Fixture<ed25519::Scheme>, TestState) {
let namespace = b"ns".to_vec();
let fixture = ed25519::fixture(
context,
&namespace,
validators.try_into().expect("validator count fits in u32"),
);
let elector = match term_length {
1 => round_robin(&fixture.verifier),
_ => round_robin_with_term(
&fixture.verifier,
TermLength::new(NZU32!(term_length)),
Duration::from_secs(30),
ViewDelta::new(0),
),
};
let state = State::new(
context.child("state"),
Config {
scheme: fixture.verifier.clone(),
elector,
epoch: Epoch::new(epoch),
view_retention: ViewDelta::new(view_retention),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget,
},
);
let mut state = state;
state.set_genesis(test_genesis());
(fixture, state)
}
#[allow(clippy::too_many_arguments)]
fn setup_state_with(
context: &mut deterministic::Context,
validators: usize,
signer: usize,
epoch: u64,
view_retention: u64,
term_length: TermLength,
optimistic_views: ViewDelta,
skip_budget: u64,
) -> (Fixture<ed25519::Scheme>, TestState) {
let namespace = b"ns".to_vec();
let fixture = ed25519::fixture(
context,
&namespace,
validators.try_into().expect("validator count fits in u32"),
);
let state = build_state(
context.child("state"),
fixture.schemes[signer].clone(),
epoch,
view_retention,
term_length,
optimistic_views,
skip_budget,
);
(fixture, state)
}
fn build_state(
context: deterministic::Context,
scheme: ed25519::Scheme,
epoch: u64,
view_retention: u64,
term_length: TermLength,
optimistic_views: ViewDelta,
skip_budget: u64,
) -> TestState {
let elector = if term_length == TermLength::ONE {
round_robin(&scheme)
} else {
round_robin_with_term(
&scheme,
term_length,
Duration::from_secs(4),
optimistic_views,
)
};
let mut state = State::new(
context,
Config {
scheme,
elector,
epoch: Epoch::new(epoch),
view_retention: ViewDelta::new(view_retention),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget,
},
);
state.set_genesis(test_genesis());
state
}
fn propose_and_notarize_view1(state: &mut TestState, payload: u8) -> Proposal<Sha256Digest> {
let proposal = Proposal::new(
Rnd::new(state.epoch(), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([payload; 32]),
);
state.create_round(View::new(1));
assert!(state.record_proposed(proposal.clone()));
assert!(state.construct_notarize(View::new(1)).is_some());
proposal
}
#[derive(Clone)]
struct RequireCertificateElector<S> {
term_length: TermLength,
_phantom: PhantomData<S>,
}
impl<S: certificate::Scheme> Elector<S> for RequireCertificateElector<S> {
type Mode = Dynamic;
fn terms(&self) -> Terms {
Terms::stable(self.term_length, Duration::from_secs(30), ViewDelta::new(1))
}
fn elect(&self, round: Rnd, certificate: Option<&S::Certificate>) -> Participant {
assert!(
certificate.is_some() || round.view() == View::new(1),
"certificate required after view 1"
);
Participant::new(0)
}
}
#[test]
fn certificate_candidates_respect_force_flag() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let mut state = State::new(
context,
Config {
scheme: verifier.clone(),
elector: round_robin(&verifier),
epoch: Epoch::new(11),
view_retention: ViewDelta::new(6),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: verifier.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let notarize_view = View::new(3);
let notarize_round = Rnd::new(Epoch::new(11), notarize_view);
let notarize_proposal =
Proposal::new(notarize_round, GENESIS_VIEW, Sha256Digest::from([50u8; 32]));
let notarization = build_notarization(&verifier, &schemes, ¬arize_proposal);
state.add_notarization(notarization);
assert!(state.broadcast_notarization(notarize_view).is_some());
assert!(state.broadcast_notarization(notarize_view).is_none());
assert!(state.notarization(notarize_view).is_some());
let nullify_view = View::new(4);
let nullify_round = Rnd::new(Epoch::new(11), nullify_view);
let nullification = build_nullification(&verifier, &schemes, nullify_round);
state.add_nullification(nullification);
assert!(state.broadcast_nullification(nullify_view).is_some());
assert!(state.broadcast_nullification(nullify_view).is_none());
assert!(state.nullification(nullify_view).is_some());
let finalize_view = View::new(5);
let finalize_round = Rnd::new(Epoch::new(11), finalize_view);
let finalize_proposal =
Proposal::new(finalize_round, GENESIS_VIEW, Sha256Digest::from([51u8; 32]));
let finalization = build_finalization(&verifier, &schemes, &finalize_proposal);
state.add_finalization(finalization);
assert!(state.broadcast_finalization(finalize_view).is_some());
assert!(state.broadcast_finalization(finalize_view).is_none());
assert!(state.finalization(finalize_view).is_some());
});
}
#[test]
fn timeout_helpers_reuse_and_reset_deadlines() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { schemes, .. } = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[0].clone(); let retry = Duration::from_secs(3);
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(4),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: retry,
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let first = state.next_timeout();
let second = state.next_timeout();
assert_eq!(first, second, "cached timeout should be reused");
let (was_retry, _) = state
.construct_nullify(state.current_view(), TimeoutReason::LeaderTimeout)
.expect("first timeout nullify should exist");
assert!(!was_retry, "first timeout is not a retry");
context.sleep(Duration::from_secs(2)).await;
let later = context.current();
let third = state.next_timeout();
assert_eq!(
third,
(later + retry, TimeoutReason::Retry),
"new retry scheduled after timeout"
);
let fourth = state.next_timeout();
assert_eq!(fourth, third, "retry deadline should be set");
context.sleep(Duration::from_secs(10)).await;
let fifth = state.next_timeout();
assert_eq!(
fifth,
(later + retry, TimeoutReason::Retry),
"retry deadline should be set"
);
let (was_retry, _) = state
.construct_nullify(state.current_view(), TimeoutReason::Retry)
.expect("retry timeout nullify should exist");
assert!(was_retry, "subsequent timeout should be treated as retry");
let sixth = state.next_timeout();
let later = context.current();
assert_eq!(
sixth,
(later + retry, TimeoutReason::Retry),
"retry deadline should be set"
);
});
}
#[test]
fn nullify_preserves_retry_backoff_after_first_timeout_vote() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes,
participants,
..
} = ed25519::fixture(&mut context, &namespace, 4);
let retry = Duration::from_secs(3);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(30),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: retry,
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
let (was_retry, _) = state
.construct_nullify(view, TimeoutReason::LeaderTimeout)
.expect("first timeout nullify should exist");
assert!(!was_retry, "first timeout should not be marked as retry");
let leader = state.leader_index(view).expect("leader must be set");
let leader_key = &participants[leader.get() as usize];
let label = Timeout::new(leader_key, TimeoutReason::LeaderTimeout);
assert_eq!(
state.timeouts.get_or_create(&label).get(),
1,
"first nullify should record a leader-timeout metric"
);
context.sleep(Duration::from_secs(2)).await;
let now = context.current();
let retry_deadline = state.next_timeout();
assert_eq!(
retry_deadline,
(now + retry, TimeoutReason::Retry),
"first retry should honor configured nullify backoff"
);
state.trigger_timeout(view, TimeoutReason::LeaderNullify);
assert_eq!(
state.next_timeout(),
retry_deadline,
"retry backoff should be preserved after repeated timeout hints"
);
});
}
#[test]
fn nullify_records_reason_from_next_timeout() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes,
participants,
..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(31),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
state.trigger_timeout(view, TimeoutReason::MissingProposal);
let (_, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::MissingProposal);
let (was_retry, _) = state
.construct_nullify(view, reason)
.expect("first timeout nullify should exist");
assert!(!was_retry);
let leader = state.leader_index(view).expect("leader must be set");
let leader_key = &participants[leader.get() as usize];
let missing = Timeout::new(leader_key, TimeoutReason::MissingProposal);
let leader_timeout = Timeout::new(leader_key, TimeoutReason::LeaderTimeout);
assert_eq!(state.timeouts.get_or_create(&missing).get(), 1);
assert_eq!(state.timeouts.get_or_create(&leader_timeout).get(), 0);
let (_, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::Retry);
let (was_retry, _) = state
.construct_nullify(view, reason)
.expect("retry timeout nullify should exist");
assert!(was_retry);
assert_eq!(state.timeouts.get_or_create(&missing).get(), 1);
});
}
#[test]
fn notarization_keeps_certification_timeout_pending_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(32),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
let proposal = Proposal::new(
Rnd::new(state.epoch(), view),
GENESIS_VIEW,
Sha256Digest::from([52u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
let certification_deadline = state.next_timeout();
assert_eq!(
certification_deadline,
(
context.current() + Duration::from_secs(2),
TimeoutReason::CertificationTimeout,
)
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, equivocator) = state.add_notarization(notarization);
assert!(added);
assert!(equivocator.is_none());
assert_eq!(
state.next_timeout(),
certification_deadline,
"certification timeout must continue to bound certification latency"
);
context.sleep(Duration::from_secs(3)).await;
assert!(
state.next_timeout().0 <= context.current(),
"stalled certification should leave the view timed out"
);
});
}
#[test]
fn stall_timeout_tracks_oldest_unfinalized_view() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(33),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let oldest_deadline = context.current() + Duration::from_secs(4);
let certify_view = |state: &mut TestState,
schemes: &[ed25519::Scheme],
verifier: &ed25519::Scheme,
view: View,
parent: View,
payload: [u8; 32]| {
let proposal = Proposal::new(
Rnd::new(Epoch::new(33), view),
parent,
Sha256Digest::from(payload),
);
assert!(state.set_proposal(view, &proposal));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(view));
let notarization = build_notarization(verifier, schemes, &proposal);
assert!(state.add_notarization(notarization).0);
};
certify_view(
&mut state,
&schemes,
&verifier,
View::new(1),
GENESIS_VIEW,
[1u8; 32],
);
context.sleep(Duration::from_secs(1)).await;
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
certify_view(
&mut state,
&schemes,
&verifier,
View::new(2),
View::new(1),
[2u8; 32],
);
context.sleep(Duration::from_millis(1500)).await;
assert!(state.certified(View::new(2), true).is_some());
assert_eq!(state.current_view(), View::new(3));
let v3_certification_deadline = context.current() + Duration::from_secs(2);
let proposal_v3 = Proposal::new(
Rnd::new(Epoch::new(33), View::new(3)),
View::new(2),
Sha256Digest::from([3u8; 32]),
);
assert!(state.set_proposal(View::new(3), &proposal_v3));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(3)));
assert_eq!(
state.next_timeout(),
(oldest_deadline, TimeoutReason::StallTimeout,),
"oldest unfinalized view in the term should drive the timeout"
);
context.sleep(Duration::from_secs(2)).await;
assert_eq!(
state.next_timeout(),
(
v3_certification_deadline,
TimeoutReason::CertificationTimeout,
)
);
});
}
#[test]
fn stall_timeout_ignores_prior_terms() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(12),
ViewDelta::new(0),
),
epoch: Epoch::new(34),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(11),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
context.sleep(Duration::from_secs(3)).await;
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(34), View::new(1)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(4));
let leader_deadline = context.current() + Duration::from_secs(10);
context.sleep(Duration::from_millis(9500)).await;
assert_eq!(
state.next_timeout(),
(leader_deadline, TimeoutReason::LeaderTimeout)
);
});
}
#[test]
fn retry_takes_precedence_over_expired_same_term_timeout() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let retry = Duration::from_millis(3);
let same_term_timeout = Duration::from_millis(30);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
same_term_timeout,
ViewDelta::new(0),
),
epoch: Epoch::new(35),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_millis(10),
certification_timeout: Duration::from_millis(20),
timeout_retry: retry,
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let oldest_deadline = context.current() + same_term_timeout;
let view_1 = View::new(1);
let proposal = Proposal::new(
Rnd::new(Epoch::new(35), view_1),
GENESIS_VIEW,
Sha256Digest::from([35u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
context.sleep(Duration::from_millis(25)).await;
assert!(state.certified(view_1, true).is_some());
assert_eq!(state.current_view(), View::new(2));
context.sleep(Duration::from_millis(5)).await;
assert_eq!(
state.next_timeout(),
(oldest_deadline, TimeoutReason::StallTimeout,)
);
let view_2 = state.current_view();
let (was_retry, _) = state
.construct_nullify(view_2, TimeoutReason::StallTimeout)
.expect("same-term timeout should nullify current view");
assert!(!was_retry);
assert_eq!(
state.next_timeout(),
(context.current() + retry, TimeoutReason::Retry),
"expired same-term deadline must not override nullify retry cadence"
);
});
}
#[test]
fn local_nullify_preserves_stall_timeout() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let same_term_timeout = Duration::from_secs(4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
same_term_timeout,
ViewDelta::new(0),
),
epoch: Epoch::new(36),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view_1 = state.current_view();
let oldest_deadline = context.current() + same_term_timeout;
state.trigger_timeout(view_1, TimeoutReason::LeaderTimeout);
let (was_retry, _) = state
.construct_nullify(view_1, TimeoutReason::LeaderTimeout)
.expect("first timeout nullify should exist");
assert!(!was_retry);
let proposal = Proposal::new(
Rnd::new(Epoch::new(36), view_1),
GENESIS_VIEW,
Sha256Digest::from([36u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
context.sleep(same_term_timeout).await;
assert!(state.certified(view_1, true).is_some());
assert_eq!(state.current_view(), View::new(2));
assert_eq!(
state.next_timeout(),
(oldest_deadline, TimeoutReason::StallTimeout,),
"oldest unfinalized view should remain tracked after local nullify"
);
});
}
#[test]
fn stall_timeout_survives_certificate_jump() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let stall_timeout = Duration::from_secs(4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
stall_timeout,
ViewDelta::new(0),
),
epoch: Epoch::new(7),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
assert_eq!(state.current_view(), View::new(1));
let proposal = Proposal::new(
Rnd::new(Epoch::new(7), View::new(7)),
GENESIS_VIEW,
Sha256Digest::from([7u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
let entered = context.current();
assert!(state.certified(View::new(7), true).is_some());
assert_eq!(state.current_view(), View::new(8));
assert_eq!(
state.next_stall_timeout(),
Some(entered + stall_timeout),
"jumped-over views must not disable the stall timeout"
);
});
}
#[test]
fn no_stall_deadline_when_unconfigured() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { schemes, .. } = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(33),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let entered = context.current();
assert_eq!(state.next_stall_timeout(), None);
assert_eq!(
state.next_timeout(),
(
entered + Duration::from_secs(1),
TimeoutReason::LeaderTimeout
)
);
});
}
#[test]
fn expired_latch_keeps_reason_over_expired_anchor() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { schemes, .. } = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(9),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(10),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
context.sleep(Duration::from_secs(5)).await;
let view = state.current_view();
state.trigger_timeout(view, TimeoutReason::LeaderNullify);
let (_, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::LeaderNullify);
});
}
#[test]
fn expire_old_round_is_noop() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(12),
view_retention: ViewDelta::new(3),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let deadline_v1 = state.next_timeout();
state.trigger_timeout(View::zero(), TimeoutReason::Inactivity);
assert_eq!(state.current_view(), View::new(1));
assert_eq!(state.next_timeout(), deadline_v1);
assert!(
!state.views.contains_key(&View::zero()),
"old round should not be created when expire is ignored"
);
let view_1 = View::new(1);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(state.epoch(), view_1));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(2));
let deadline_v2 = state.next_timeout();
state.trigger_timeout(view_1, TimeoutReason::Inactivity);
assert_eq!(state.current_view(), View::new(2));
assert_eq!(state.next_timeout(), deadline_v2);
});
}
#[test]
fn inactivity_timeout_ignores_buffered_current_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let certification_timeout = Duration::from_secs(10);
let mut state = State::new(
context.child("state"),
Config {
scheme: schemes[1].clone(),
elector: round_robin_with_term(
&schemes[1],
TermLength::new(NZU32!(5)),
Duration::from_secs(20),
ViewDelta::new(1),
),
epoch: Epoch::new(15),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(10),
certification_timeout,
timeout_retry: Duration::from_secs(30),
skip_budget: schemes[1].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let parent = propose_and_notarize_view1(&mut state, 118);
let finalization = build_finalization(&verifier, &schemes, &parent);
assert!(state.add_finalization(finalization).0);
assert_eq!(state.current_view(), View::new(2));
let child = Proposal::new(
Rnd::new(Epoch::new(15), View::new(2)),
View::new(1),
Sha256Digest::from([119u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let now = context.current();
state.trigger_timeout(View::new(2), TimeoutReason::Inactivity);
let (deadline, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::CertificationTimeout);
assert_eq!(deadline, now + certification_timeout);
state.trigger_timeout(View::new(2), TimeoutReason::LeaderNullify);
let (deadline, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::LeaderNullify);
assert_eq!(deadline, now);
});
}
#[test]
fn inactivity_timeout_latches_on_equivocated_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
15,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let parent = propose_and_notarize_view1(&mut state, 120);
let finalization = build_finalization(&verifier, &schemes, &parent);
assert!(state.add_finalization(finalization).0);
assert_eq!(state.current_view(), View::new(2));
let child = |payload: u8| {
Proposal::new(
Rnd::new(Epoch::new(15), View::new(2)),
View::new(1),
Sha256Digest::from([payload; 32]),
)
};
assert!(state.set_proposal(View::new(2), &child(121)));
assert!(!state.set_proposal(View::new(2), &child(122)));
let now = context.current();
state.trigger_timeout(View::new(2), TimeoutReason::Inactivity);
let (deadline, reason) = state.next_timeout();
assert_eq!(reason, TimeoutReason::Inactivity);
assert_eq!(deadline, now);
});
}
#[test]
fn entering_next_view_resets_expired_timeout_state() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let leader_timeout = Duration::from_secs(1);
let retry = Duration::from_secs(3);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(13),
view_retention: ViewDelta::new(3),
leader_timeout,
certification_timeout: Duration::from_secs(2),
timeout_retry: retry,
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view_1 = state.current_view();
assert_eq!(view_1, View::new(1));
state.trigger_timeout(view_1, TimeoutReason::LeaderTimeout);
assert!(
state.next_timeout().0 <= context.current(),
"current view should be expired after timeout is triggered"
);
let (was_retry, _) = state
.construct_nullify(view_1, TimeoutReason::LeaderTimeout)
.expect("first timeout nullify should exist");
assert!(!was_retry);
let retry_deadline = state.next_timeout();
assert_eq!(
retry_deadline,
(context.current() + retry, TimeoutReason::Retry),
"timed-out view should schedule a retry"
);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(state.epoch(), view_1));
assert!(state.add_nullification(nullification));
let view_2 = state.current_view();
assert_eq!(view_2, View::new(2));
let next_deadline = state.next_timeout();
assert_eq!(
next_deadline,
(
context.current() + leader_timeout,
TimeoutReason::LeaderTimeout
),
"next view should start with a fresh leader timeout"
);
assert_ne!(
next_deadline, retry_deadline,
"next view must not inherit the previous view retry deadline"
);
});
}
#[test]
fn skip_budget_allows_repeated_leaders() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_state_with(
&mut context,
2,
0,
7,
10,
TermLength::ONE,
ViewDelta::zero(),
3,
);
let Fixture {
schemes, verifier, ..
} = fixture;
let first_leader = state.leader_index(View::new(1));
for view in 1..=3 {
let view = View::new(view);
assert_eq!(state.current_view(), view);
let now = context.current();
state.trigger_timeout(view, TimeoutReason::Inactivity);
assert_eq!(state.next_timeout(), (now, TimeoutReason::Inactivity));
assert!(
!state
.construct_nullify(view, TimeoutReason::Inactivity)
.expect("skip nullify")
.0
);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(state.epoch(), view));
assert!(state.add_nullification(nullification));
}
assert_eq!(state.leader_index(View::new(3)), first_leader);
let view = View::new(4);
let now = context.current();
state.trigger_timeout(view, TimeoutReason::Inactivity);
assert_eq!(
state.next_timeout(),
(now + Duration::from_secs(1), TimeoutReason::LeaderTimeout)
);
});
}
#[test]
fn skip_budget_counts_terms() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_state_with(
&mut context,
4,
0,
7,
10,
TermLength::new(NZU32!(5)),
ViewDelta::zero(),
2,
);
let Fixture {
schemes, verifier, ..
} = fixture;
for view in [View::new(1), View::new(6)] {
assert_eq!(state.current_view(), view);
let now = context.current();
state.trigger_timeout(view, TimeoutReason::Inactivity);
assert_eq!(state.next_timeout(), (now, TimeoutReason::Inactivity));
assert!(
state
.construct_nullify(view, TimeoutReason::Inactivity)
.is_some()
);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(state.epoch(), view));
assert!(state.add_nullification(nullification));
}
let view = View::new(11);
let now = context.current();
state.trigger_timeout(view, TimeoutReason::Inactivity);
assert_eq!(
state.next_timeout(),
(now + Duration::from_secs(1), TimeoutReason::LeaderTimeout)
);
});
}
#[test]
fn finalization_restores_pending_skip() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_state(&mut context, 4, 9, 10, 1, 1);
let Fixture {
schemes, verifier, ..
} = fixture;
let proposal = Proposal::new(
Rnd::new(state.epoch(), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([123u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
assert_eq!(state.certify_candidates().0, vec![proposal.clone()]);
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
let now = context.current();
state.trigger_timeout(View::new(2), TimeoutReason::Inactivity);
assert_eq!(
state.next_timeout(),
(now + Duration::from_secs(1), TimeoutReason::LeaderTimeout)
);
let finalization = build_finalization(&verifier, &schemes, &proposal);
assert!(state.add_finalization(finalization).0);
assert_eq!(state.current_view(), View::new(2));
assert_eq!(state.next_timeout(), (now, TimeoutReason::Inactivity));
});
}
#[test]
fn disabled_skip_defers_inactivity_to_leader_deadline() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state(&mut context, 4, 7, 10, 1, 0);
let view = state.current_view();
let now = context.current();
state.trigger_timeout(view, TimeoutReason::Inactivity);
assert_eq!(
state.next_timeout(),
(now + Duration::from_secs(1), TimeoutReason::LeaderTimeout)
);
});
}
#[test]
fn disabled_skip_defers_leader_nullify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state(&mut context, 4, 7, 10, 1, 0);
let view = state.current_view();
let now = context.current();
let proposal = Proposal::new(
Rnd::new(state.epoch(), view),
GENESIS_VIEW,
Sha256Digest::from([124u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
state.trigger_timeout(view, TimeoutReason::LeaderNullify);
assert_eq!(
state.next_timeout(),
(
now + Duration::from_secs(2),
TimeoutReason::CertificationTimeout
)
);
});
}
#[test]
fn nullify_only_records_metric_once() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes,
participants,
..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(12),
view_retention: ViewDelta::new(3),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
let leader = state.leader_index(view).unwrap();
let leader_key = &participants[leader.get() as usize];
let label = Timeout::new(leader_key, TimeoutReason::LeaderNullify);
state.trigger_timeout(view, TimeoutReason::LeaderNullify);
let expired_at = state.next_timeout();
context.sleep(Duration::from_secs(1)).await;
state.trigger_timeout(view, TimeoutReason::LeaderTimeout);
assert_eq!(
state.next_timeout(),
expired_at,
"repeated timeout hints should not reset the expired deadline"
);
assert_eq!(state.timeouts.get_or_create(&label).get(), 0);
let (was_retry, _) = state
.construct_nullify(view, TimeoutReason::LeaderNullify)
.expect("first timeout nullify should exist");
assert!(!was_retry);
assert_eq!(state.timeouts.get_or_create(&label).get(), 1);
state.trigger_timeout(view, TimeoutReason::LeaderTimeout);
let (was_retry, _) = state
.construct_nullify(view, TimeoutReason::Retry)
.expect("retry timeout nullify should exist");
assert!(was_retry);
assert_eq!(state.timeouts.get_or_create(&label).get(), 1);
let retry_label = Timeout::new(leader_key, TimeoutReason::Retry);
assert_eq!(state.timeouts.get_or_create(&retry_label).get(), 0);
});
}
#[test]
fn construct_nullify_current_view_only() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[0].clone();
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(4),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let current = state.current_view();
let next = current.next();
assert!(
state
.construct_nullify(next, TimeoutReason::LeaderTimeout)
.is_none()
);
let current_round = Rnd::new(Epoch::new(4), current);
let current_nullification = build_nullification(&verifier, &schemes, current_round);
assert!(state.add_nullification(current_nullification));
assert_eq!(state.current_view(), next);
assert!(
state
.construct_nullify(current, TimeoutReason::LeaderTimeout)
.is_none()
);
let (was_retry, _) = state
.construct_nullify(next, TimeoutReason::LeaderTimeout)
.expect("first timeout nullify for current view should be emitted");
assert!(!was_retry);
let (was_retry, _) = state
.construct_nullify(next, TimeoutReason::Retry)
.expect("retry timeout nullify for current view should be emitted");
assert!(was_retry);
});
}
#[test]
fn round_prunes_with_min_active() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(7),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
for view in 0..5 {
state.create_round(View::new(view));
}
let proposal_a = Proposal::new(
Rnd::new(Epoch::new(1), View::new(20)),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_a);
state.add_finalization(finalization);
let removed = state.prune();
assert_eq!(
removed,
vec![
View::new(0),
View::new(1),
View::new(2),
View::new(3),
View::new(4)
]
);
assert_eq!(state.views.len(), 2); });
}
#[test]
fn parent_payload_returns_parent_digest() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[2].clone(); let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(4),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let parent_view = View::new(1);
let parent_payload = Sha256Digest::from([1u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
parent_view,
Sha256Digest::from([9u8; 32]),
);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::ParentNotCertified {
proposal_view: View::new(2),
parent_view,
})
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::ParentNotCertified {
proposal_view: View::new(2),
parent_view,
})
);
let mut pool = AbortablePool::<()>::default();
let handle = pool.push(futures::future::pending());
state.set_certify_handle(parent_view, handle);
state.certified(parent_view, true);
assert_eq!(state.parent_payload(&proposal), Ok(parent_payload));
});
}
#[test]
fn parent_payload_errors_without_nullification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 5, 1, 4);
let parent_view = View::new(1);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
Sha256Digest::from([2u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
state.create_round(View::new(2));
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(3)),
parent_view,
Sha256Digest::from([3u8; 32]),
);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::MissingNullification {
proposal_view: View::new(3),
parent_view,
missing_view: View::new(2),
})
);
});
}
#[test]
fn parent_payload_uses_term_skip_nullification_anchors() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let parent_view = View::new(3);
let parent_payload = Sha256Digest::from([42u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
assert!(state.certified(parent_view, true).is_some());
for v in [View::new(4), View::new(6)] {
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), v));
assert!(state.add_nullification(nullification));
}
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(11)),
parent_view,
Sha256Digest::from([7u8; 32]),
);
assert_eq!(state.parent_payload(&proposal), Ok(parent_payload));
});
}
#[test]
fn parent_payload_uses_term_skip_nullification_anchors_across_multiple_terms() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let parent_view = View::new(3);
let parent_payload = Sha256Digest::from([42u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
assert!(state.certified(parent_view, true).is_some());
for v in [View::new(4), View::new(6), View::new(11)] {
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), v));
assert!(state.add_nullification(nullification));
}
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(16)),
parent_view,
Sha256Digest::from([7u8; 32]),
);
assert_eq!(state.parent_payload(&proposal), Ok(parent_payload));
});
}
#[test]
fn parent_payload_accepts_certified_parent_covered_by_nullification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let parent_view = View::new(3);
let parent_payload = Sha256Digest::from([42u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
assert!(state.certified(parent_view, true).is_some());
for v in [parent_view, View::new(6)] {
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), v));
assert!(state.add_nullification(nullification));
}
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(11)),
parent_view,
Sha256Digest::from([7u8; 32]),
);
assert_eq!(state.parent_payload(&proposal), Ok(parent_payload));
});
}
#[test]
fn parent_payload_reports_missing_term_anchor() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let parent_view = View::new(3);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
Sha256Digest::from([9u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
assert!(state.certified(parent_view, true).is_some());
{
let v = View::new(4);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), v));
assert!(state.add_nullification(nullification));
}
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(11)),
parent_view,
Sha256Digest::from([10u8; 32]),
);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::MissingNullification {
proposal_view: View::new(11),
parent_view,
missing_view: View::new(6),
})
);
});
}
#[test]
fn optimistic_views_zero_disables_intra_term_lookahead() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(0),
4,
);
let parent = propose_and_notarize_view1(&mut state, 93);
let parent_notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(parent_notarization).0);
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([94u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
assert!(matches!(
state.try_verify(),
Verify::Resolve { view, kind: Kind::Notarization, .. } if view == View::new(1)
));
let child_notarization = build_notarization(&verifier, &schemes, &child);
assert!(state.add_notarization(child_notarization).0);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(1));
assert!(state.certified(View::new(1), true).is_some());
assert!(matches!(state.try_verify(), Verify::Ready(..)));
});
}
#[test]
fn try_verify_requests_uncertified_cross_term_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
participants,
schemes,
verifier,
..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(9), View::new(3)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(6)),
View::new(2),
Sha256Digest::from([44u8; 32]),
);
assert!(state.set_proposal(View::new(6), &child));
let leader =
participants[usize::from(state.leader_index(View::new(6)).unwrap())].clone();
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Notarization,
target,
}
if proposal == View::new(6)
&& view == View::new(2)
&& target == leader
));
assert!(matches!(state.try_verify(), Verify::Wait));
let parent = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([43u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(2), true).is_some());
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("proposal should verify once the parent certifies");
};
assert_eq!(ctx.parent, (View::new(2), parent.payload));
assert_eq!(proposal, child);
});
}
#[test]
fn optimistic_child_certification_waits_for_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent = propose_and_notarize_view1(&mut state, 101);
let parent_notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(parent_notarization).0);
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([102u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(2)));
let child_notarization = build_notarization(&verifier, &schemes, &child);
assert!(state.add_notarization(child_notarization).0);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert!(
candidates
.iter()
.any(|proposal| proposal.round.view() == View::new(1))
);
assert!(state.certified(View::new(1), false).is_some());
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(9), View::new(1)));
assert!(state.add_nullification(nullification));
assert_eq!(
state.find_parent(View::new(6)),
Ok((GENESIS_VIEW, test_genesis()))
);
let next_term_proposal = Proposal::new(
Rnd::new(Epoch::new(9), View::new(6)),
View::new(2),
Sha256Digest::from([103u8; 32]),
);
assert_eq!(
state.parent_payload(&next_term_proposal),
Err(ParentPayloadError::ParentNotCertified {
proposal_view: View::new(6),
parent_view: View::new(2),
})
);
assert!(state.certify_candidates().0.is_empty());
});
}
#[test]
fn certification_fetch_widens_targeted_verification_request() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
participants,
schemes,
verifier,
..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(0),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let p3 = fetch_proposal(3, 2, 103);
state.set_leader(View::new(3), None);
assert!(state.set_proposal(View::new(3), &p3));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Notarization,
target,
} if proposal == View::new(3)
&& view == View::new(2)
&& target == participants[2]
));
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &p3))
.0
);
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert_eq!(fetches.len(), 1);
assert_eq!(fetches[0].proposal, View::new(3));
assert_eq!(fetches[0].view, View::new(2));
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert!(fetches.is_empty());
let p2 = fetch_proposal(2, 1, 102);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &p2))
.0
);
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready.len(), 1);
assert_eq!(ready[0].round.view(), View::new(2));
assert!(fetches.is_empty());
assert!(state.certified(View::new(2), true).is_some());
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready.len(), 1);
assert_eq!(ready[0].round.view(), View::new(3));
assert!(fetches.is_empty());
});
}
#[test]
fn certify_candidates_fetches_across_wide_gap() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
20,
TermLength::new(NZU32!(10)),
ViewDelta::new(2),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let p6 = fetch_proposal(6, 5, 106);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &p6))
.0
);
assert!(!state.leader_is_set(View::new(6)));
assert!(!state.leader_is_set(View::new(5)));
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert_eq!(fetches.len(), 1);
assert_eq!(fetches[0].proposal, View::new(6));
assert_eq!(fetches[0].view, View::new(5));
assert!(state.leader_index(View::new(2)).is_some());
let p5 = fetch_proposal(5, 4, 105);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &p5))
.0
);
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert_eq!(fetches.len(), 1);
assert_eq!(fetches[0].proposal, View::new(5));
assert_eq!(fetches[0].view, View::new(4));
});
}
#[test]
fn certify_candidates_fetches_term_end_without_leader() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let p10 = fetch_proposal(10, 9, 110);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &p10))
.0
);
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert_eq!(fetches.len(), 1);
assert_eq!(fetches[0].proposal, View::new(10));
assert_eq!(fetches[0].view, View::new(9));
});
}
#[test]
fn certify_candidates_exempts_term_start_from_parent_precheck() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let term_start = fetch_proposal(6, 1, 61);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &term_start))
.0
);
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready, vec![term_start]);
assert!(fetches.is_empty());
});
}
#[test]
fn certify_candidates_drops_malformed_candidates() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let bad_parent = fetch_proposal(2, 2, 60);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &bad_parent))
.0
);
let skip = fetch_proposal(4, 1, 61);
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &skip))
.0
);
let (ready, fetches) = state.certify_candidates();
assert!(ready.is_empty());
assert!(fetches.is_empty());
assert!(state.certification_candidates.is_empty());
});
}
#[test]
fn optimistic_views_bounds_chain_length() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let first_payload = Sha256Digest::from([95u8; 32]);
let first = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
first_payload,
);
state.create_round(View::new(1));
assert!(state.record_proposed(first));
let second = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([96u8; 32]),
);
assert!(state.set_proposal(View::new(2), &second));
assert!(
matches!(state.try_verify(), Verify::Wait),
"future same-term verification should wait for local parent notarize"
);
assert!(state.construct_notarize(View::new(1)).is_some());
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("future view should verify after local parent notarize");
};
assert_eq!(ctx.round.view(), View::new(2));
assert_eq!(ctx.parent, (View::new(1), first_payload));
assert_eq!(proposal, second);
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
let third = Proposal::new(
Rnd::new(Epoch::new(9), View::new(3)),
View::new(2),
Sha256Digest::from([97u8; 32]),
);
assert!(state.set_proposal(View::new(3), &third));
assert!(
matches!(state.try_verify(), Verify::Wait),
"depth=1 should block a second optimistic hop"
);
});
}
#[test]
fn optimistic_successor_inherits_leader_without_none_election() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { verifier, .. } = ed25519::fixture(&mut context, &namespace, 4);
let skip_budget = verifier.participants().len() as u64;
let mut state = State::new(
context,
Config {
scheme: verifier,
elector: RequireCertificateElector {
term_length: TermLength::new(NZU32!(5)),
_phantom: PhantomData,
},
epoch: Epoch::new(99),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget,
},
);
state.set_genesis(test_genesis());
let proposal = Proposal::new(
Rnd::new(Epoch::new(99), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([9u8; 32]),
);
assert!(state.set_proposal(View::new(1), &proposal));
assert!(
state
.views
.get(&View::new(2))
.and_then(|round| round.leader())
.is_some()
);
});
}
#[test]
fn catch_up_from_parent_finalization_allows_child_notarize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([111u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &parent);
assert!(state.add_finalization(finalization).0);
assert_eq!(state.current_view(), View::new(2));
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([112u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("child should verify");
};
assert_eq!(proposal, child);
assert_eq!(ctx.parent, (View::new(1), parent.payload));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
});
}
#[test]
fn catch_up_from_parent_certification_allows_child_notarize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([113u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([114u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("child should verify");
};
assert_eq!(proposal, child);
assert_eq!(ctx.parent, (View::new(1), parent.payload));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
});
}
#[test]
fn forwardable_proposal_tracks_certificate_state() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 13, 10, 1, 4);
let view = View::new(1);
let proposal = Proposal::new(
Rnd::new(Epoch::new(13), view),
GENESIS_VIEW,
Sha256Digest::from([116u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
assert!(state.forwardable_proposal(view).is_some());
assert!(state.certified(view, false).is_some());
assert!(state.forwardable_proposal(view).is_none());
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(13), view));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(2));
assert!(state.forwardable_proposal(view).is_none());
let finalization = build_finalization(&verifier, &schemes, &proposal);
assert!(state.add_finalization(finalization).0);
assert!(state.forwardable_proposal(view).is_some());
});
}
#[test]
fn pending_optimistic_child_verification_rejects_replaced_parent_notarization() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent_a = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([117u8; 32]),
);
assert!(state.set_proposal(View::new(1), &parent_a));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
assert!(state.construct_notarize(View::new(1)).is_some());
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([118u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("child should verify");
};
assert_eq!(proposal, child);
assert_eq!(ctx.parent, (View::new(1), parent_a.payload));
let parent_b = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([119u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_b);
let (added, equivocator) = state.add_notarization(notarization);
assert!(added);
assert!(equivocator.is_some());
assert_eq!(state.parent_payload(&child), Ok(parent_b.payload));
assert!(!state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_none());
});
}
#[test]
fn failed_optimistic_child_verification_ignores_replaced_parent_verdict() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent_a = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([120u8; 32]),
);
assert!(state.set_proposal(View::new(1), &parent_a));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
assert!(state.construct_notarize(View::new(1)).is_some());
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([121u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let Verify::Ready(ctx, _) = state.try_verify() else {
panic!("child should verify");
};
assert_eq!(ctx.parent, (View::new(1), parent_a.payload));
let parent_b = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([122u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_b);
assert!(state.add_notarization(notarization).0);
assert_eq!(state.parent_payload(&child), Ok(parent_b.payload));
state.verification_failed(View::new(2), TimeoutReason::InvalidProposal);
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
assert!(!matches!(
state.next_timeout(),
(_, TimeoutReason::InvalidProposal)
));
});
}
#[test]
fn verified_optimistic_child_notarize_rejects_replaced_parent_finalization() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent_a = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([120u8; 32]),
);
assert!(state.set_proposal(View::new(1), &parent_a));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
assert!(state.construct_notarize(View::new(1)).is_some());
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([121u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("child should verify");
};
assert_eq!(proposal, child);
assert_eq!(ctx.parent, (View::new(1), parent_a.payload));
assert!(state.verified(View::new(2)));
let parent_b = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([122u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &parent_b);
let (added, equivocator) = state.add_finalization(finalization);
assert!(added);
assert!(equivocator.is_some());
assert_eq!(state.parent_payload(&child), Ok(parent_b.payload));
assert!(state.construct_notarize(View::new(2)).is_none());
});
}
#[test]
fn failed_certification_blocks_optimistic_child_notarize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let parent = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([116u8; 32]),
);
assert!(state.set_proposal(View::new(1), &parent));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
assert!(state.construct_notarize(View::new(1)).is_some());
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([117u8; 32]),
);
assert!(state.set_proposal(View::new(2), &child));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(2)));
assert!(state.certified(View::new(1), false).is_some());
assert!(
state
.construct_nullify(View::new(1), TimeoutReason::FailedCertification)
.is_some()
);
assert!(
state.construct_notarize(View::new(2)).is_none(),
"failed-certified parent must not unlock optimistic child notarize"
);
let child_notarization = build_notarization(&verifier, &schemes, &child);
assert!(state.add_notarization(child_notarization).0);
assert!(state.certify_candidates().0.is_empty());
let finalization = build_finalization(&verifier, &schemes, &parent);
assert!(state.add_finalization(finalization).0);
assert!(state.construct_notarize(View::new(2)).is_some());
assert_eq!(state.certify_candidates().0, vec![child]);
});
}
#[test]
fn replayed_failed_ancestor_blocks_direct_descendant_until_finalization() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let ancestor = fetch_proposal(1, 0, 116);
let descendant = fetch_proposal(2, 1, 117);
for proposal in [&ancestor, &descendant] {
let notarization = build_notarization(&verifier, &schemes, proposal);
assert!(state.add_notarization(notarization).0);
}
state.replay(&Artifact::Certification(ancestor.round, false));
assert!(
state
.optimistic_ancestry_payload(descendant.view())
.is_none()
);
let finalization = build_finalization(&verifier, &schemes, &descendant);
assert!(state.add_finalization(finalization).0);
assert_eq!(
state
.optimistic_ancestry_payload(descendant.view())
.copied(),
Some(descendant.payload)
);
});
}
#[test]
fn failed_certification_blocks_locally_proposed_optimistic_child_notarize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
2,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let parent = propose_and_notarize_view1(&mut state, 118);
let child_context = state
.try_propose()
.expect("optimistic child proposal should start")
.into_context();
assert_eq!(child_context.view(), View::new(2));
assert_eq!(child_context.parent, (View::new(1), parent.payload));
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(1), false).is_some());
assert!(
state
.construct_nullify(View::new(1), TimeoutReason::FailedCertification)
.is_some()
);
let child = Proposal::new(
child_context.round,
child_context.parent.0,
Sha256Digest::from([119u8; 32]),
);
assert!(!state.proposed(&child_context, child.payload));
assert!(state.record_proposed(child));
assert!(
state.construct_notarize(View::new(2)).is_none(),
"failed-certified parent must block a locally proposed optimistic child"
);
});
}
#[test]
fn same_term_notarize_respects_outbound_window() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state_with(
&mut context,
4,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
for view in [View::new(1), View::new(2), View::new(3)] {
let proposal = Proposal::new(
Rnd::new(Epoch::new(9), view),
view.previous().unwrap_or(GENESIS_VIEW),
Sha256Digest::from([view.get() as u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
assert!(state.verified(view));
assert!(
state.construct_notarize(view).is_some(),
"view {view} is in the outbound window from current view 1"
);
}
let view = View::new(4);
let proposal = Proposal::new(
Rnd::new(Epoch::new(9), view),
View::new(3),
Sha256Digest::from([4u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
assert!(state.verified(view));
assert!(
state.construct_notarize(view).is_none(),
"view 4 is outside the outbound window from current view 1"
);
});
}
#[test]
fn certify_candidates_wait_for_parent_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let parent = Proposal::new(
Rnd::new(Epoch::new(9), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([98u8; 32]),
);
let parent_notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(parent_notarization).0);
let child = Proposal::new(
Rnd::new(Epoch::new(9), View::new(2)),
View::new(1),
Sha256Digest::from([99u8; 32]),
);
let child_notarization = build_notarization(&verifier, &schemes, &child);
assert!(state.add_notarization(child_notarization).0);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(1));
assert!(state.certified(View::new(1), true).is_some());
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(2));
});
}
#[test]
fn blocked_certification_candidates_wake_parent_first() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(10)),
ViewDelta::new(3),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let proposals = [
fetch_proposal(2, 1, 102),
fetch_proposal(3, 2, 103),
fetch_proposal(4, 3, 104),
];
for proposal in proposals.iter().rev() {
let notarization = build_notarization(&verifier, &schemes, proposal);
assert!(state.add_notarization(notarization).0);
}
for proposal in proposals {
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready, vec![proposal.clone()]);
assert!(fetches.is_empty());
assert!(
state.certification_candidates.is_empty(),
"parent-blocked descendants must remain dormant"
);
assert!(state.certified(proposal.view(), true).is_some());
}
});
}
#[test]
fn finalization_wakes_child_after_failed_parent_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_first_view(&mut state, &verifier, &schemes);
let parent = fetch_proposal(2, 1, 102);
let child = fetch_proposal(3, 2, 103);
for proposal in [&parent, &child] {
let notarization = build_notarization(&verifier, &schemes, proposal);
assert!(state.add_notarization(notarization).0);
}
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready, vec![parent.clone()]);
assert!(fetches.is_empty());
assert!(state.certification_candidates.is_empty());
assert!(state.certified(parent.view(), false).is_some());
assert!(state.certify_candidates().0.is_empty());
let finalization = build_finalization(&verifier, &schemes, &parent);
assert!(state.add_finalization(finalization).0);
assert_eq!(state.certify_candidates().0, vec![child]);
});
}
#[test]
fn optimistic_frontier_slides_with_direct_notarization() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
10,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
propose_and_notarize_view1(&mut state, 98);
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(10), View::new(2)),
View::new(1),
Sha256Digest::from([99u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
assert!(state.views.contains_key(&View::new(3)));
assert!(
!state.views.contains_key(&View::new(4)),
"issuance window should initially stop at view 3"
);
let notarization = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(state.add_notarization(notarization).0);
assert!(
state.views.contains_key(&View::new(4)),
"direct notarization should slide optimistic frontier"
);
});
}
#[test]
fn optimistic_frontier_walk_does_not_scan_rounds() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
10,
10,
TermLength::new(NZU32!(131)),
ViewDelta::new(64),
4,
);
for view in 1..=65 {
let view = View::new(view);
let proposal = Proposal::new(
Rnd::new(Epoch::new(10), view),
view.previous().unwrap_or(GENESIS_VIEW),
Sha256Digest::from([view.get() as u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
}
let proposal = state
.views
.get(&View::new(65))
.and_then(|round| round.proposal())
.cloned()
.expect("proposal must be tracked");
let notarization = build_notarization(&verifier, &schemes, &proposal);
let probes = state.issuance_window_probes.get();
assert!(state.add_notarization(notarization).0);
for view in 66..=130 {
assert!(
state.leader_index(View::new(view)).is_some(),
"view {view} must inherit the stable leader"
);
}
assert!(state.leader_index(View::new(131)).is_none());
assert_eq!(state.issuance_window_probes.get(), probes);
});
}
#[test]
fn optimistic_frontier_slides_despite_far_future_round() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
10,
10,
TermLength::new(NZU32!(20)),
ViewDelta::new(2),
4,
);
let proposal_v10 = Proposal::new(
Rnd::new(Epoch::new(10), View::new(10)),
View::new(9),
Sha256Digest::from([96u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal_v10);
assert!(state.add_notarization(notarization).0);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(10), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([97u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(state.add_notarization(notarization).0);
for view in 2..=4u64 {
assert!(
state.leader_index(View::new(view)).is_some(),
"view {view} must inherit the stable leader"
);
}
});
}
#[test]
fn indirect_notarization_still_requires_certification_for_finalize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
10,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let parent = propose_and_notarize_view1(&mut state, 101);
let descendant = Proposal::new(
Rnd::new(Epoch::new(10), View::new(2)),
View::new(1),
Sha256Digest::from([102u8; 32]),
);
assert!(state.set_proposal(View::new(2), &descendant));
assert!(state.verified(View::new(2)));
let notarization = build_notarization(&verifier, &schemes, &descendant);
let (added, equivocator) = state.add_notarization(notarization);
assert!(added);
assert!(equivocator.is_none());
assert_eq!(
state.optimistic_ancestry_payload(View::new(1)).copied(),
Some(Sha256Digest::from([101u8; 32]))
);
let round = state.views.get(&View::new(1)).expect("ancestor round");
assert!(round.proposal().is_some());
assert!(round.is_verified());
assert!(state.construct_finalize(View::new(1)).is_none());
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.construct_finalize(View::new(1)).is_none());
assert!(state.certified(View::new(1), true).is_some());
assert!(state.construct_finalize(View::new(1)).is_some());
});
}
#[test]
fn indirect_notarization_requires_verified_unequivocated_ancestors() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
propose_and_notarize_view1(&mut state, 111);
let view2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([112u8; 32]),
);
state.create_round(View::new(2));
assert!(state.record_proposed(view2));
assert!(state.construct_notarize(View::new(2)).is_some());
let conflicting_view2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([113u8; 32]),
);
assert!(!state.set_proposal(View::new(2), &conflicting_view2));
let view3 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(3)),
View::new(2),
Sha256Digest::from([114u8; 32]),
);
assert!(state.set_proposal(View::new(3), &view3));
assert!(state.verified(View::new(3)));
let notarization = build_notarization(&verifier, &schemes, &view3);
assert!(state.add_notarization(notarization).0);
assert!(state.optimistic_ancestry_payload(View::new(2)).is_none());
});
}
#[test]
fn optimistic_notarize_requires_parent_participation_within_term() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state_with(
&mut context,
4,
0,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
assert!(state.enter_view(View::new(2)));
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([118u8; 32]),
);
state.create_round(View::new(2));
assert!(state.record_proposed(proposal_v2));
assert!(state.construct_notarize(View::new(2)).is_none());
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([119u8; 32]),
);
state.create_round(View::new(1));
assert!(state.record_proposed(proposal_v1));
assert!(state.construct_notarize(View::new(1)).is_some());
assert!(state.construct_notarize(View::new(2)).is_some());
});
}
#[test]
fn optimistic_notarize_accepts_directly_notarized_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([120u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes[1..], &proposal_v1);
assert!(state.add_notarization(notarization).0);
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([121u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
});
}
#[test]
fn optimistic_notarize_blocks_on_parent_failed_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([122u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes[1..], &proposal_v1);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(1), false).is_some());
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([123u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_none());
});
}
#[test]
fn finalization_anchors_optimistic_issuance_window() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([130u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_v1);
assert!(state.add_finalization(finalization).0);
assert!(state.notarization(View::new(1)).is_none());
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([131u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
let proposal_v3 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(3)),
View::new(2),
Sha256Digest::from([132u8; 32]),
);
assert!(state.set_proposal(View::new(3), &proposal_v3));
assert!(state.verified(View::new(3)));
assert!(
state.construct_notarize(View::new(3)).is_some(),
"finalized view 1 should anchor the issuance window"
);
});
}
#[test]
fn prune_drops_stale_optimistic_anchors() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
11,
1,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
for (view, payload) in [(1u64, 140u8), (2, 141)] {
let proposal = Proposal::new(
Rnd::new(Epoch::new(11), View::new(view)),
View::new(view - 1),
Sha256Digest::from([payload; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
}
assert!(state.in_issuance_window(View::new(4)));
let proposal_v4 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(4)),
View::new(3),
Sha256Digest::from([142u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_v4);
assert!(state.add_finalization(finalization).0);
let removed = state.prune();
assert_eq!(removed, vec![View::new(1), View::new(2)]);
assert!(
!state.in_issuance_window(View::new(4)),
"pruned views must not anchor the issuance window"
);
});
}
#[test]
fn optimistic_finalize_blocks_on_uncertified_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
11,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([124u8; 32]),
);
let notarization_v1 = build_notarization(&verifier, &schemes[1..], &proposal_v1);
assert!(state.add_notarization(notarization_v1).0);
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(11), View::new(2)),
View::new(1),
Sha256Digest::from([125u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(state.verified(View::new(2)));
assert!(state.construct_notarize(View::new(2)).is_some());
let notarization_v2 = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(state.add_notarization(notarization_v2).0);
assert!(state.certified(View::new(2), true).is_some());
assert!(
state.construct_finalize(View::new(2)).is_none(),
"finalize must wait for the parent's explicit certification"
);
assert!(state.certified(View::new(1), true).is_some());
assert!(state.construct_finalize(View::new(2)).is_some());
});
}
#[test]
fn failed_certification_still_nullifies_current_view() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
13,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let proposal = Proposal::new(
Rnd::new(Epoch::new(13), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([115u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
assert_eq!(state.current_view(), View::new(1));
assert!(state.certified(View::new(1), false).is_some());
let (is_retry, nullify) = state
.construct_nullify(View::new(1), TimeoutReason::FailedCertification)
.expect("failed certification should still nullify the current view");
assert!(!is_retry);
assert_eq!(nullify.view(), View::new(1));
let (is_retry, nullify) = state
.construct_nullify(View::new(1), TimeoutReason::Retry)
.expect("failed certification nullify should allow retry");
assert!(is_retry);
assert_eq!(nullify.view(), View::new(1));
});
}
#[test]
fn nullification_sets_entry_certificate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let view = View::new(1);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), view));
assert!(state.add_nullification(nullification.clone()));
assert_eq!(state.current_view(), View::new(6));
let entry = state.get_best_certificate();
assert!(
matches!(
entry,
Some(Certificate::Nullification(ref cert)) if cert == &nullification
),
"expected nullification entry certificate"
);
});
}
#[test]
fn entry_certificate_prioritizes_finalization_then_nullification_then_notarization() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 1, 4);
let view = View::new(1);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([17u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
state.add_notarization(notarization.clone());
assert!(state.certified(view, true).is_some());
assert!(matches!(
state.get_best_certificate(),
Some(Certificate::Notarization(ref n)) if n == ¬arization
));
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), view));
assert!(state.add_nullification(nullification.clone()));
assert!(matches!(
state.get_best_certificate(),
Some(Certificate::Nullification(ref n)) if n == &nullification
));
let finalization = build_finalization(&verifier, &schemes, &proposal);
let _ = state.add_finalization(finalization.clone());
assert!(matches!(
state.get_best_certificate(),
Some(Certificate::Finalization(ref f)) if f == &finalization
));
});
}
#[test]
fn parent_payload_returns_genesis_payload() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 5, 1, 4);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(1)));
state.add_nullification(nullification);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
GENESIS_VIEW,
Sha256Digest::from([8u8; 32]),
);
let genesis = Sha256Digest::from([0u8; 32]);
assert_eq!(state.parent_payload(&proposal), Ok(genesis));
});
}
#[test]
fn parent_payload_rejects_parent_before_finalized() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 5, 1, 4);
let proposal_a = Proposal::new(
Rnd::new(Epoch::new(1), View::new(3)),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_a);
state.add_finalization(finalization);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(4)),
View::new(2),
Sha256Digest::from([6u8; 32]),
);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::ParentBeforeFinalized {
proposal_view: View::new(4),
parent_view: View::new(2),
last_finalized: View::new(3),
})
);
});
}
#[test]
fn parent_payload_rejects_intra_term_view_skip() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 20, 5, 4);
let parent_view = View::new(1);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
state.add_notarization(notarization);
state.certified(parent_view, true);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(3)),
parent_view,
Sha256Digest::from([2u8; 32]),
);
assert_eq!(
state.parent_payload(&proposal),
Err(ParentPayloadError::IntraTermProposalSkipsViews {
proposal_view: View::new(3),
parent_view,
})
);
});
}
#[test]
fn try_verify_fast_paths_intra_term_view_skip() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(1);
let mut state = State::new(
context.child("state"),
Config {
scheme: verifier.clone(),
elector: round_robin_with_term(
&verifier,
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(2),
),
epoch,
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(10),
timeout_retry: Duration::from_secs(30),
skip_budget: verifier.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let notarization_proposal = Proposal::new(
Rnd::new(epoch, View::new(2)),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, ¬arization_proposal);
state.add_notarization(notarization);
assert!(state.leader_index(View::new(3)).is_some());
let proposal = Proposal::new(
Rnd::new(epoch, View::new(3)),
View::new(1),
Sha256Digest::from([2u8; 32]),
);
assert!(state.set_proposal(View::new(3), &proposal));
let initial_deadline = state.next_timeout();
assert!(initial_deadline.0 > context.current());
assert!(matches!(state.try_verify(), Verify::Wait));
assert!(
state
.construct_nullify(View::new(3), TimeoutReason::LeaderTimeout)
.is_none()
);
assert_eq!(state.next_timeout(), initial_deadline);
});
}
#[test]
fn try_verify_fast_paths_parent_before_finalized() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(1);
let mut state = State::new(
context.child("state"),
Config {
scheme: verifier.clone(),
elector: round_robin(&verifier),
epoch,
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(10),
timeout_retry: Duration::from_secs(30),
skip_budget: verifier.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let finalized_view = View::new(3);
let finalized_proposal = Proposal::new(
Rnd::new(epoch, finalized_view),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &finalized_proposal);
state.add_finalization(finalization);
let view = state.current_view();
assert_eq!(view, View::new(4));
let proposal = Proposal::new(
Rnd::new(epoch, view),
View::new(2),
Sha256Digest::from([6u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
let initial_deadline = state.next_timeout();
assert!(initial_deadline.0 > context.current());
assert!(!matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.next_timeout().0 <= context.current());
});
}
#[test]
fn try_verify_waits_for_missing_parent_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { verifier, .. } = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(1);
let mut state = State::new(
context.child("state"),
Config {
scheme: verifier.clone(),
elector: round_robin(&verifier),
epoch,
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(10),
timeout_retry: Duration::from_secs(30),
skip_budget: verifier.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
assert!(state.enter_view(View::new(2)));
let proposal = Proposal::new(
Rnd::new(epoch, View::new(2)),
View::new(1),
Sha256Digest::from([7u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal));
let initial_deadline = state.next_timeout();
assert!(initial_deadline.0 > context.current());
assert!(!matches!(state.try_verify(), Verify::Ready(..)));
assert_eq!(state.next_timeout(), initial_deadline);
});
}
#[test]
fn replayed_local_notarize_restores_verified_leader_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(2);
let view = View::new(2);
let proposal = Proposal::new(
Rnd::new(epoch, view),
View::new(1),
Sha256Digest::from([42u8; 32]),
);
let local_vote = Notarize::sign(&schemes[0], proposal.clone()).expect("notarize");
let mut state = State::new(
context,
Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch,
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let parent = Proposal::new(
Rnd::new(epoch, View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([41u8; 32]),
);
let parent_notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(parent_notarization).0);
assert!(state.certified(View::new(1), true).is_some());
let _ = state.certify_candidates();
assert_eq!(state.leader_index(view), Some(Participant::new(0)));
state.replay(&Artifact::Notarize(local_vote));
let round = state.views.get(&view).expect("replayed round must exist");
assert_eq!(round.proposal(), Some(&proposal));
assert!(
state.construct_notarize(view).is_none(),
"replay should restore that we already emitted the local notarize vote"
);
assert!(!matches!(state.try_verify(), Verify::Ready(..)));
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), view);
});
}
#[test]
fn replayed_local_notarize_restores_optimistic_child_verification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(12);
let elector = round_robin_with_term(
&verifier,
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(2),
);
let leader_idx = usize::from(elector.elect(Rnd::new(epoch, View::new(1)), ()));
let local_idx = (leader_idx + 1) % schemes.len();
let config = |scheme: ed25519::Scheme, elector| {
let skip_budget = scheme.participants().len() as u64;
Config {
scheme,
elector,
epoch,
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget,
}
};
let mut live = State::new(
context.child("live"),
config(schemes[local_idx].clone(), elector.clone()),
);
live.set_genesis(test_genesis());
let parent = Proposal::new(
Rnd::new(epoch, View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([123u8; 32]),
);
assert!(live.set_proposal(View::new(1), &parent));
assert!(matches!(live.try_verify(), Verify::Ready(..)));
assert!(live.verified(View::new(1)));
let local_vote = live
.construct_notarize(View::new(1))
.expect("local notarize vote");
let child = Proposal::new(
Rnd::new(epoch, View::new(2)),
View::new(1),
Sha256Digest::from([124u8; 32]),
);
assert!(live.set_proposal(View::new(2), &child));
assert!(matches!(live.try_verify(), Verify::Ready(..)));
let mut restarted = State::new(
context.child("restarted"),
config(schemes[local_idx].clone(), elector),
);
restarted.set_genesis(test_genesis());
restarted.replay(&Artifact::Notarize(local_vote));
assert!(restarted.set_proposal(View::new(2), &child));
assert!(
matches!(restarted.try_verify(), Verify::Ready(..)),
"replayed local notarize should preserve optimistic child verification"
);
});
}
#[test]
fn certify_external_candidates_for_leader_controlled_views() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(2);
let view = View::new(2);
let proposal = Proposal::new(
Rnd::new(epoch, view),
View::new(1),
Sha256Digest::from([43u8; 32]),
);
let mut state = State::new(
context,
Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch,
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
assert!(state.enter_view(view));
state.set_leader(view, None);
assert_eq!(state.leader_index(view), Some(Participant::new(0)));
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, equivocator) = state.add_notarization(notarization);
assert!(added);
assert!(equivocator.is_none());
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0], proposal);
});
}
#[test]
fn replay_restores_conflict_state() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let mut scheme_iter = schemes.into_iter();
let local_scheme = scheme_iter.next().unwrap();
let other_schemes: Vec<_> = scheme_iter.collect();
let epoch: Epoch = Epoch::new(3);
let mut state = State::new(
context.child("state"),
Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let view = View::new(4);
let round = Rnd::new(epoch, view);
let proposal_a = Proposal::new(round, GENESIS_VIEW, Sha256Digest::from([21u8; 32]));
let proposal_b = Proposal::new(round, GENESIS_VIEW, Sha256Digest::from([22u8; 32]));
let local_vote = Notarize::sign(&local_scheme, proposal_a).unwrap();
state.replay(&Artifact::Notarize(local_vote.clone()));
let conflicting = build_notarization(&verifier, &other_schemes[..3], &proposal_b);
state.add_notarization(conflicting.clone());
state.replay(&Artifact::Notarization(conflicting.clone()));
assert!(state.construct_finalize(view).is_none());
let mut restarted = State::new(
context.child("state_restarted"),
Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
},
);
restarted.set_genesis(test_genesis());
restarted.replay(&Artifact::Notarize(local_vote));
restarted.add_notarization(conflicting.clone());
restarted.replay(&Artifact::Notarization(conflicting));
assert!(restarted.construct_finalize(view).is_none());
});
}
#[test]
fn restart_equivocation_parent_payload_tracks_finalized_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes,
participants,
verifier,
..
} = ed25519::fixture(&mut context, &namespace, 4);
let epoch = Epoch::new(1);
let mut state = State::new(
context.child("state"),
Config {
scheme: schemes[1].clone(),
elector: round_robin(&verifier),
epoch,
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[1].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let view = View::new(1);
assert_eq!(state.current_view(), view);
assert_eq!(state.leader_index(view), Some(Participant::new(2)));
let proposal_x = Proposal::new(
Rnd::new(epoch, view),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
let local_vote = Notarize::sign(&schemes[1], proposal_x).unwrap();
state.replay(&Artifact::Notarize(local_vote));
let proposal_y = Proposal::new(
Rnd::new(epoch, view),
GENESIS_VIEW,
Sha256Digest::from([2u8; 32]),
);
assert!(!state.set_proposal(view, &proposal_y));
let others = [schemes[0].clone(), schemes[2].clone(), schemes[3].clone()];
let finalization = build_finalization(&verifier, &others, &proposal_y);
let (added, equivocator) = state.add_finalization(finalization);
assert!(added);
assert_eq!(equivocator.unwrap(), participants[2]);
let next = state.current_view();
assert_eq!(next, View::new(2));
let child = Proposal::new(Rnd::new(epoch, next), view, Sha256Digest::from([3u8; 32]));
assert!(state.set_proposal(next, &child));
let Verify::Ready(context, proposal) = state.try_verify() else {
panic!("verification context missing");
};
assert_eq!(proposal, child);
assert_eq!(context.parent, (view, proposal_y.payload));
});
}
#[test]
fn replay_restores_indirect_notarization_state() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[1].clone();
let ancestor = Proposal::new(
Rnd::new(Epoch::new(12), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([121u8; 32]),
);
let descendant = Proposal::new(
Rnd::new(Epoch::new(12), View::new(2)),
View::new(1),
Sha256Digest::from([122u8; 32]),
);
let mut state = State::new(
context.child("initial"),
Config {
scheme: local_scheme.clone(),
elector: round_robin_with_term(
&local_scheme,
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(2),
),
epoch: Epoch::new(12),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
},
);
state.set_genesis(test_genesis());
state.create_round(View::new(1));
assert!(state.record_proposed(ancestor));
let local_vote = state
.construct_notarize(View::new(1))
.expect("local notarize vote");
assert!(state.set_proposal(View::new(2), &descendant));
assert!(state.verified(View::new(2)));
let notarization = build_notarization(&verifier, &schemes, &descendant);
assert!(state.add_notarization(notarization.clone()).0);
assert_eq!(
state.optimistic_ancestry_payload(View::new(1)).copied(),
Some(Sha256Digest::from([121u8; 32]))
);
let mut restarted = State::new(
context.child("restarted"),
Config {
scheme: local_scheme.clone(),
elector: round_robin_with_term(
&local_scheme,
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(2),
),
epoch: Epoch::new(12),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
},
);
restarted.set_genesis(test_genesis());
assert!(restarted.set_proposal(View::new(2), &descendant));
assert!(restarted.verified(View::new(2)));
restarted.add_notarization(notarization.clone());
restarted.replay(&Artifact::Notarization(notarization));
assert!(
restarted
.optimistic_ancestry_payload(View::new(1))
.is_none()
);
restarted.replay(&Artifact::Notarize(local_vote));
assert_eq!(
restarted.optimistic_ancestry_payload(View::new(1)).copied(),
Some(Sha256Digest::from([121u8; 32]))
);
});
}
#[test]
fn trigger_timeout_latches_optimistic_future_view() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_state_with(
&mut context,
4,
0,
14,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(1),
4,
);
let Fixture {
schemes, verifier, ..
} = fixture;
let parent = propose_and_notarize_view1(&mut state, 116);
let future = Proposal::new(
Rnd::new(Epoch::new(14), View::new(2)),
View::new(1),
Sha256Digest::from([117u8; 32]),
);
assert!(state.set_proposal(View::new(2), &future));
assert_eq!(state.current_view(), View::new(1));
let initial_deadline = state.next_timeout();
let latched_at = context.current();
state.trigger_timeout(View::new(2), TimeoutReason::InvalidProposal);
assert!(
state
.construct_nullify(View::new(2), TimeoutReason::InvalidProposal)
.is_none()
);
assert_eq!(state.next_timeout(), initial_deadline);
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
assert_eq!(
state.next_timeout(),
(latched_at, TimeoutReason::InvalidProposal)
);
assert!(
state
.construct_nullify(View::new(2), TimeoutReason::InvalidProposal)
.is_some()
);
});
}
#[test]
fn try_verify_latches_invalid_optimistic_future_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
15,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let parent = Proposal::new(
Rnd::new(Epoch::new(15), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([150u8; 32]),
);
assert!(state.set_proposal(View::new(1), &parent));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
let invalid = Proposal::new(
Rnd::new(Epoch::new(15), View::new(2)),
GENESIS_VIEW,
Sha256Digest::from([151u8; 32]),
);
assert!(state.set_proposal(View::new(2), &invalid));
assert_eq!(state.current_view(), View::new(1));
let initial_deadline = state.next_timeout();
let latched_at = context.current();
assert!(matches!(state.try_verify(), Verify::Wait));
assert_eq!(state.next_timeout(), initial_deadline);
let notarization = build_notarization(&verifier, &schemes, &parent);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(1), true).is_some());
assert_eq!(state.current_view(), View::new(2));
assert_eq!(
state.next_timeout(),
(latched_at, TimeoutReason::InvalidProposal)
);
});
}
#[test]
fn certification_lifecycle() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: verifier.clone(),
elector: round_robin(&verifier),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: verifier.participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let make_notarization = |view: View| {
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([view.get() as u8; 32]),
);
build_notarization(&verifier, &schemes, &proposal)
};
let make_finalization = |view: View| {
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([view.get() as u8; 32]),
);
build_finalization(&verifier, &schemes, &proposal)
};
let mut pool = AbortablePool::<()>::default();
for i in 3..=8u64 {
state.add_notarization(make_notarization(View::new(i)));
}
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 6);
for i in [3u64, 4, 5, 7] {
let handle = pool.push(futures::future::pending());
state.set_certify_handle(View::new(i), handle);
}
assert!(state.certify_candidates().0.is_empty());
let notarization = state.certified(View::new(7), true);
assert!(notarization.is_some());
assert!(!state.is_certify_aborted(View::new(7)));
state.add_finalization(make_finalization(View::new(5)));
assert!(state.is_certify_aborted(View::new(3)));
assert!(state.is_certify_aborted(View::new(4)));
assert!(state.is_certify_aborted(View::new(5)));
assert!(!state.is_certify_aborted(View::new(7)));
assert!(!state.is_certify_aborted(View::new(6)));
assert!(!state.is_certify_aborted(View::new(8)));
assert!(state.certify_candidates().0.is_empty());
state.add_notarization(make_notarization(View::new(9)));
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(9));
let handle9 = pool.push(futures::future::pending());
state.set_certify_handle(View::new(9), handle9);
state.add_notarization(make_notarization(View::new(10)));
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(10));
state.add_finalization(make_finalization(View::new(9)));
assert!(state.is_certify_aborted(View::new(9)));
state.add_notarization(make_notarization(View::new(11)));
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), View::new(11));
});
}
#[test]
fn certify_candidates_skips_views_at_or_below_last_finalized() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let make_notarization = |view: View| {
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([view.get() as u8; 32]),
);
build_notarization(&verifier, &schemes, &proposal)
};
let make_finalization = |view: View| {
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([view.get() as u8; 32]),
);
build_finalization(&verifier, &schemes, &proposal)
};
let stale_view = View::new(2);
let live_view = View::new(3);
state.add_notarization(make_notarization(stale_view));
state.add_notarization(make_notarization(live_view));
state.add_finalization(make_finalization(stale_view));
state.certification_candidates.insert(stale_view);
assert_eq!(state.last_finalized(), stale_view);
assert!(
state
.views
.get(&stale_view)
.expect("stale round must exist")
.pending_certification()
.is_some()
);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), live_view);
});
}
#[test]
fn nullification_keeps_notarization_as_certification_candidate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 10, 1, 4);
let view = View::new(2);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([42u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), view));
assert!(state.add_nullification(nullification));
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), view);
});
}
#[test]
fn nullification_does_not_abort_inflight_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state(&mut context, 4, 1, 10, 1, 4);
let view = View::new(2);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([24u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), view);
let mut pool = AbortablePool::<()>::default();
let handle = pool.push(futures::future::pending());
state.set_certify_handle(view, handle);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), view));
assert!(state.add_nullification(nullification));
assert!(!state.is_certify_aborted(view));
assert!(state.certified(view, true).is_some());
assert!(state.explicit_ancestry_payload(view).is_some());
});
}
#[test]
fn conflicting_parent_headers_share_payload_but_certify_notarized_proposal() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let mut state = State::new(
context,
Config {
scheme: schemes[1].clone(),
elector: round_robin(&verifier),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[1].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let certified_view = View::new(1);
let certified_payload = Sha256Digest::from([31u8; 32]);
let certified_proposal = Proposal::new(
Rnd::new(Epoch::new(1), certified_view),
GENESIS_VIEW,
certified_payload,
);
let certified_notarization =
build_notarization(&verifier, &schemes, &certified_proposal);
assert!(state.add_notarization(certified_notarization).0);
assert!(state.certified(certified_view, true).is_some());
let nullified_view = View::new(2);
let nullified_payload = Sha256Digest::from([32u8; 32]);
let nullified_proposal = Proposal::new(
Rnd::new(Epoch::new(1), nullified_view),
certified_view,
nullified_payload,
);
let nullified_notarization =
build_notarization(&verifier, &schemes, &nullified_proposal);
assert!(state.add_notarization(nullified_notarization).0);
assert_eq!(state.certify_candidates().0, vec![nullified_proposal]);
let mut pool = AbortablePool::<()>::default();
let handle = pool.push(futures::future::pending());
state.set_certify_handle(nullified_view, handle);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), nullified_view));
assert!(state.add_nullification(nullification));
let view = View::new(3);
assert_eq!(state.current_view(), view);
assert_eq!(state.leader_index(view), Some(Participant::new(0)));
let payload = Sha256Digest::from([33u8; 32]);
let bad_proposal =
Proposal::new(Rnd::new(Epoch::new(1), view), certified_view, payload);
let good_proposal =
Proposal::new(Rnd::new(Epoch::new(1), view), nullified_view, payload);
assert_ne!(bad_proposal, good_proposal);
assert_eq!(bad_proposal.payload, good_proposal.payload);
assert!(Notarize::sign(&schemes[0], bad_proposal.clone()).is_some());
assert!(state.set_proposal(view, &bad_proposal));
let Verify::Ready(verify_context, verify_proposal) = state.try_verify() else {
panic!("bad header should reach verification");
};
assert_eq!(verify_proposal, bad_proposal);
assert_eq!(verify_context.parent, (certified_view, certified_payload));
state.trigger_timeout(view, TimeoutReason::InvalidProposal);
let (retry, _) = state
.construct_nullify(view, TimeoutReason::InvalidProposal)
.expect("nullify");
assert!(!retry);
let good_votes: Vec<_> = [0usize, 2, 3]
.into_iter()
.map(|index| {
Notarize::sign(&schemes[index], good_proposal.clone()).expect("notarize")
})
.collect();
let good_notarization = Notarization::from_notarizes(
&verifier,
non_empty![@good_votes.iter()],
&Sequential,
)
.expect("notarization");
let (added, equivocator) = state.add_notarization(good_notarization);
assert!(added);
assert!(equivocator.is_some());
assert_eq!(state.certify_candidates().0, vec![good_proposal]);
});
}
#[test]
fn nullification_then_late_certification_allows_child_to_build_on_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[0].clone();
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let parent_view = View::new(2);
let child_view = parent_view.next();
let payload = Sha256Digest::from([91u8; 32]);
let proposal =
Proposal::new(Rnd::new(Epoch::new(1), parent_view), GENESIS_VIEW, payload);
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), parent_view));
assert!(state.add_nullification(nullification));
assert_eq!(state.leader_index(child_view), Some(Participant::new(0)));
assert!(state.try_propose().is_none());
assert!(state.certified(parent_view, true).is_some());
let propose_context = state
.try_propose()
.expect("child view should be able to build on certified parent")
.into_context();
assert_eq!(propose_context.round.view(), child_view);
assert_eq!(propose_context.parent, (parent_view, payload));
});
}
#[test]
fn nullification_then_late_certification_unblocks_follower_verify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[1].clone();
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let parent_view = View::new(2);
let child_view = parent_view.next();
let parent_payload = Sha256Digest::from([77u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), parent_view));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), child_view);
assert_eq!(state.leader_index(child_view), Some(Participant::new(0)));
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
parent_view,
Sha256Digest::from([78u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(!matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.certified(parent_view, true).is_some());
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("verify context should exist");
};
assert_eq!(ctx.round.view(), child_view);
assert_eq!(ctx.parent, (parent_view, parent_payload));
assert_eq!(proposal, child_proposal);
});
}
#[test]
fn try_propose_requires_immediate_parent_within_term() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let mut state = State::new(
context,
Config {
scheme: schemes[2].clone(),
elector: round_robin_with_term(
&schemes[2],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[2].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let parent_view = View::new(1);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
Sha256Digest::from([93u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(parent_view, true).is_some());
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(2)));
state.replay(&Artifact::Nullification(nullification));
assert!(state.enter_view(View::new(3)));
state.set_leader(View::new(3), None);
assert_eq!(state.leader_index(View::new(3)), Some(Participant::new(2)));
assert!(state.try_propose().is_none());
});
}
#[test]
fn try_propose_allows_cross_term_parent_at_term_start() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let mut state = State::new(
context,
Config {
scheme: schemes[3].clone(),
elector: round_robin_with_term(
&schemes[3],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[3].participants().len() as u64,
},
);
state.set_genesis(test_genesis());
let parent_view = View::new(3);
let parent_payload = Sha256Digest::from([94u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(parent_view, true).is_some());
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(4)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
state.set_leader(View::new(6), None);
assert_eq!(state.leader_index(View::new(6)), Some(Participant::new(3)));
let proposal = state
.try_propose()
.expect("term-start proposal should use prior-term certified parent")
.into_context();
assert_eq!(proposal.round.view(), View::new(6));
assert_eq!(proposal.parent, (parent_view, parent_payload));
});
}
fn prepare_term_boundary(
state: &mut TestState,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
) -> (Proposal<Sha256Digest>, Proposal<Sha256Digest>) {
let certified = certify_view_4(state, verifier, schemes);
assert_eq!(state.current_view(), View::new(5));
let tip = fetch_proposal(5, 4, 65);
assert!(state.set_proposal(View::new(5), &tip));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(5)));
assert_eq!(state.leader_index(View::new(6)), None);
assert!(state.construct_notarize(View::new(5)).is_some());
(certified, tip)
}
fn certify_view_4(
state: &mut TestState,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
) -> Proposal<Sha256Digest> {
let certified = fetch_proposal(4, 3, 64);
let notarization = build_notarization(verifier, schemes, &certified);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(4), true).is_some());
let _ = state.certify_candidates();
certified
}
fn notarize_single_participant_handoff(
state: &mut TestState,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
) -> (Proposal<Sha256Digest>, Proposal<Sha256Digest>) {
certify_view_4(state, verifier, schemes);
let context = state
.try_propose()
.expect("outgoing leader should propose the term tip")
.into_context();
let tip = fetch_proposal(5, 4, 65);
assert!(state.proposed(&context, tip.payload));
assert!(state.construct_notarize(View::new(5)).is_some());
let context = state
.try_propose()
.expect("handoff proposal should use the uncertified tip")
.into_context();
let child = fetch_proposal(6, 5, 66);
assert!(state.proposed(&context, child.payload));
assert!(state.construct_notarize(View::new(6)).is_some());
let tip_notarization = build_notarization(verifier, schemes, &tip);
assert!(state.add_notarization(tip_notarization).0);
let child_notarization = build_notarization(verifier, schemes, &child);
assert!(state.add_notarization(child_notarization).0);
(tip, child)
}
fn journaled_vote(
state: &mut TestState,
proposal: &Proposal<Sha256Digest>,
) -> Artifact<ed25519::Scheme, Sha256Digest> {
assert!(state.set_proposal(proposal.view(), proposal));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(proposal.view()));
Artifact::Notarize(
state
.construct_notarize(proposal.view())
.expect("notarize vote"),
)
}
fn certified_chain(
state: &mut TestState,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
tip: u64,
) -> Vec<Artifact<ed25519::Scheme, Sha256Digest>> {
let mut journal = Vec::new();
for view in 1..=tip {
let proposal = fetch_proposal(view, view - 1, view as u8);
journal.push(journaled_vote(state, &proposal));
let notarization = build_notarization(verifier, schemes, &proposal);
assert!(state.add_notarization(notarization.clone()).0);
assert!(state.certified(proposal.view(), true).is_some());
journal.push(Artifact::Notarization(notarization));
journal.push(Artifact::Certification(proposal.round, true));
}
journal
}
fn replayed_state(
context: deterministic::Context,
scheme: ed25519::Scheme,
journal: &[Artifact<ed25519::Scheme, Sha256Digest>],
) -> TestState {
let mut state = build_state(
context,
scheme,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
for artifact in journal {
state.replay(artifact);
match artifact {
Artifact::Notarization(notarization) => {
assert!(state.add_notarization(notarization.clone()).0);
}
Artifact::Certification(round, success) => {
assert!(state.certified(round.view(), *success).is_some());
}
_ => {}
}
}
state
}
#[test]
fn same_view_replacement_cannot_prepare_displaced_tip() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut live,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let mut journal = certified_chain(&mut live, &verifier, &schemes, 4);
let tip = fetch_proposal(5, 4, 15);
journal.push(journaled_vote(&mut live, &tip));
let stale = live
.try_propose()
.expect("handoff request on the tip")
.into_context();
assert_eq!(stale.parent, (tip.view(), tip.payload));
let replacement = fetch_proposal(5, 4, 25);
let notarization = build_notarization(&verifier, &schemes[..3], &replacement);
journal.push(Artifact::Notarization(notarization));
let mut restarted =
replayed_state(context.child("restarted"), schemes[3].clone(), &journal);
assert_eq!(
restarted.find_parent(View::new(6)),
Ok((replacement.view(), replacement.payload))
);
assert!(!restarted.proposed(&stale, Sha256Digest::from([66u8; 32])));
assert!(restarted.construct_notarize(View::new(6)).is_none());
assert!(restarted.certified(replacement.view(), true).is_some());
let request = restarted
.try_propose()
.expect("ordinary request on the replacement");
assert!(!request.is_handoff());
assert_eq!(
request.context().parent,
(replacement.view(), replacement.payload)
);
});
}
#[test]
fn replayed_descendant_without_binding_can_prepare_dead_chain() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes,
verifier,
participants,
..
},
mut live,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let anchors = certified_chain(&mut live, &verifier, &schemes, 3);
let a4 = fetch_proposal(4, 3, 14);
let a5 = fetch_proposal(5, 4, 15);
let a4_vote = journaled_vote(&mut live, &a4);
let a5_vote = journaled_vote(&mut live, &a5);
let b4 = fetch_proposal(4, 3, 24);
let b4_notarization = build_notarization(&verifier, &schemes[..3], &b4);
assert!(live.add_notarization(b4_notarization.clone()).0);
assert_eq!(live.optimistic_ancestry_payload(a5.view()), None);
let mut journal = anchors.clone();
journal.extend([
a4_vote,
Artifact::Notarization(b4_notarization.clone()),
Artifact::Certification(b4.round, true),
a5_vote,
]);
let mut restarted =
replayed_state(context.child("restarted"), schemes[3].clone(), &journal);
assert!(
restarted
.views
.get(&a5.view())
.unwrap()
.verifying()
.is_none()
);
assert_eq!(restarted.explicit_ancestry_payload(a5.view()), None);
assert_eq!(
restarted.optimistic_ancestry_payload(a5.view()),
Some(&a5.payload)
);
let request = restarted.try_propose().expect("handoff request on a5");
assert!(request.is_handoff());
assert_eq!(request.context().parent, (a5.view(), a5.payload));
let contents = (request.context().round, a5.payload, 66u64).encode();
let c = Proposal::new(
request.context().round,
a5.view(),
Sha256::hash(&[&contents]),
);
assert!(restarted.proposed(request.context(), c.payload));
let c_vote = restarted
.construct_notarize(c.view())
.expect("vote for the handoff candidate");
assert_eq!(c_vote.proposal, c);
let b5 = fetch_proposal(5, 4, 25);
let b5_notarization = build_notarization(&verifier, &schemes[..3], &b5);
assert!(restarted.add_notarization(b5_notarization.clone()).0);
assert!(restarted.certified(b5.view(), true).is_some());
assert_eq!(
restarted.explicit_ancestry_payload(a5.view()),
Some(&b5.payload)
);
let alternate = Context {
round: c.round,
leader: participants[3].clone(),
parent: (b5.view(), b5.payload),
};
restarted.proposed(&alternate, Sha256Digest::from([76u8; 32]));
assert_eq!(restarted.views.get(&c.view()).unwrap().proposal(), Some(&c));
assert!(restarted.construct_notarize(c.view()).is_none());
let mut follower_journal: Vec<_> = anchors
.into_iter()
.filter(|artifact| !matches!(artifact, Artifact::Notarize(_)))
.collect();
follower_journal.extend([
Artifact::Notarization(b4_notarization),
Artifact::Certification(b4.round, true),
Artifact::Notarization(b5_notarization),
Artifact::Certification(b5.round, true),
]);
let mut follower = replayed_state(
context.child("follower"),
schemes[1].clone(),
&follower_journal,
);
assert!(follower.set_proposal(c.view(), &c));
let Verify::Ready(ctx, received) = follower.try_verify() else {
panic!("certified b5 ancestry should be supplied to verification")
};
assert_eq!(received, c);
assert_eq!(ctx.parent, (b5.view(), b5.payload));
assert_ne!(ctx.parent, request.context().parent);
let relay = Arc::new(mocks::relay::Relay::new());
let (application, mut mailbox) = mocks::application::Application::new(
context.child("follower_application"),
mocks::application::Config::<Sha256, _> {
relay: relay.clone(),
me: participants[1].clone(),
propose_latency: (0.0, 0.0),
verify_latency: (0.0, 0.0),
certify_latency: (0.0, 0.0),
should_certify: mocks::application::Certifier::Always,
},
);
let application = application.start();
relay.broadcast(&participants[3], Recipients::All, (c.payload, contents));
assert!(!mailbox.verify(ctx, c.payload).await.await.unwrap());
follower.verification_failed(c.view(), TimeoutReason::InvalidProposal);
assert!(follower.construct_notarize(c.view()).is_none());
application.abort();
assert!(application.await.is_err());
journal.push(Artifact::Notarize(c_vote));
let mut restarted_again = replayed_state(
context.child("restarted_again"),
schemes[3].clone(),
&journal,
);
assert!(restarted_again.try_propose().is_none());
assert!(restarted_again.construct_notarize(c.view()).is_none());
});
}
#[test]
fn pipelined_handoff_proposes_on_uncertified_term_end() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
assert_eq!(state.leader_index(View::new(6)), Some(Participant::new(3)));
let ctx = state
.try_propose()
.expect("handoff proposal should use the uncertified tip")
.into_context();
assert_eq!(ctx.round.view(), View::new(6));
assert_eq!(ctx.parent, (View::new(5), tip.payload));
assert_eq!(state.current_view(), View::new(5));
let ours = fetch_proposal(6, 5, 66);
assert!(state.proposed(&ctx, ours.payload));
let notarize = state
.construct_notarize(View::new(6))
.expect("handoff proposal should notarize before the tip certifies");
assert_eq!(notarize.proposal, ours);
assert_eq!(state.current_view(), View::new(5));
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
assert!(state.add_notarization(tip_notarization).0);
assert!(state.certified(View::new(5), true).is_some());
assert_eq!(state.current_view(), View::new(6));
let ours_notarization = build_notarization(&verifier, &schemes, &ours);
assert!(state.add_notarization(ours_notarization).0);
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert!(ready.iter().any(|p| p.round.view() == View::new(6)));
assert!(state.certified(View::new(6), true).is_some());
assert_eq!(state.current_view(), View::new(7));
});
}
#[test]
fn pipelined_handoff_certified_parent_own_nullify_keeps_pending_build() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, parent) = prepare_term_boundary(&mut state, &verifier, &schemes);
let request = state.try_propose().expect("handoff request");
assert!(request.is_handoff());
let request = request.into_context();
assert_eq!(request.view(), View::new(6));
assert_eq!(request.parent.0, View::new(5));
assert!(
state
.add_notarization(build_notarization(&verifier, &schemes, &parent))
.0
);
assert!(state.certified(parent.view(), true).is_some());
assert_eq!(state.current_view(), request.view());
assert!(
state
.construct_nullify(request.view(), TimeoutReason::LeaderTimeout)
.is_some()
);
assert!(!state.supersede_proposal_request(&request));
assert_eq!(state.pending_handoff_abandonment(&request), None);
assert!(!state.proposed(&request, Sha256Digest::from([91; 32])));
assert!(state.try_propose().is_none());
});
}
#[test]
fn pipelined_handoff_later_certificates_make_request_obsolete() {
for advance in 0..3 {
let runtime = deterministic::Runner::default();
runtime.start(move |mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, parent) = prepare_term_boundary(&mut state, &verifier, &schemes);
let request = state.try_propose().expect("handoff request");
assert!(request.is_handoff());
let request = request.into_context();
let peers = &schemes[..3];
match advance {
0 => {
let certificate = build_nullification(&verifier, peers, request.round);
assert!(state.add_nullification(certificate));
assert_eq!(state.current_view(), View::new(11));
}
1 => {
let proposal = fetch_proposal(11, 10, 91);
assert!(
state
.add_finalization(build_finalization(&verifier, peers, &proposal))
.0
);
assert_eq!(state.current_view(), View::new(12));
}
2 => {
let proposal = fetch_proposal(11, 10, 91);
assert!(
state
.add_notarization(build_notarization(&verifier, peers, &proposal))
.0
);
assert_eq!(state.current_view(), View::new(5));
let (ready, fetches) = state.certify_candidates();
assert!(ready.iter().any(|candidate| candidate == &proposal));
assert!(fetches.is_empty());
assert!(state.certified(proposal.view(), true).is_some());
assert_eq!(state.current_view(), View::new(12));
}
_ => unreachable!(),
}
assert!(!state.parent_certified(request.parent));
assert!(state.highest_nullification_in_term(parent.view()).is_none());
assert!(request.view() < state.current_view());
});
}
}
#[test]
fn pipelined_handoff_certification_waits_for_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
1,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (tip, child) = notarize_single_participant_handoff(&mut state, &verifier, &schemes);
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![tip]);
assert!(state.certified(View::new(5), true).is_some());
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![child]);
});
}
#[test]
fn pipelined_handoff_certification_barrier_survives_restart() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
1,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_view_4(&mut state, &verifier, &schemes);
let tip = fetch_proposal(5, 4, 65);
let tip_vote = Notarize::sign(&schemes[0], tip.clone()).expect("tip vote");
state.replay(&Artifact::Notarize(tip_vote));
let child = fetch_proposal(6, 5, 66);
let child_vote = Notarize::sign(&schemes[0], child.clone()).expect("child vote");
state.replay(&Artifact::Notarize(child_vote));
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
assert!(state.add_notarization(tip_notarization).0);
let child_notarization = build_notarization(&verifier, &schemes, &child);
assert!(state.add_notarization(child_notarization).0);
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![tip]);
assert!(state.certified(View::new(5), true).is_some());
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![child]);
});
}
#[test]
fn singleton_certificate_before_child_vote_keeps_gate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
1,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_view_4(&mut state, &verifier, &schemes);
let tip = fetch_proposal(5, 4, 65);
let tip_vote = Notarize::sign(&schemes[0], tip.clone()).expect("tip vote");
state.replay(&Artifact::Notarize(tip_vote));
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
state.replay(&Artifact::Notarization(tip_notarization.clone()));
assert!(state.add_notarization(tip_notarization).0);
let child = fetch_proposal(6, 5, 66);
let child_vote = Notarize::sign(&schemes[0], child.clone()).expect("child vote");
state.replay(&Artifact::Notarize(child_vote));
assert!(
state
.views
.get(&child.view())
.unwrap()
.verifying()
.is_none()
);
let child_notarization = build_notarization(&verifier, &schemes, &child);
state.replay(&Artifact::Notarization(child_notarization.clone()));
assert!(state.add_notarization(child_notarization).0);
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![tip.clone()]);
assert!(state.construct_finalize(child.view()).is_none());
assert!(state.certified(tip.view(), true).is_some());
let (ready, fetches) = state.certify_candidates();
assert!(fetches.is_empty());
assert_eq!(ready, vec![child]);
});
}
fn certify_conflicting_term_start<L: Elector<ed25519::Scheme>>(
state: &mut State<deterministic::Context, ed25519::Scheme, L, Sha256Digest>,
signer: usize,
verifier: &ed25519::Scheme,
schemes: &[ed25519::Scheme],
) {
let nullification =
build_nullification(verifier, schemes, Rnd::new(Epoch::new(9), View::new(5)));
assert!(state.add_nullification(nullification));
let ours = fetch_proposal(6, 4, 61);
let vote = Notarize::sign(&schemes[signer], ours).expect("local notarize vote");
state.replay(&Artifact::Notarize(vote));
let conflicting = fetch_proposal(6, 5, 62);
let others: Vec<_> = schemes
.iter()
.enumerate()
.filter(|(index, _)| *index != signer)
.map(|(_, scheme)| scheme.clone())
.collect();
let notarization = build_notarization(verifier, &others, &conflicting);
assert!(state.add_notarization(notarization).0);
let (ready, fetches) = state.certify_candidates();
assert_eq!(ready, vec![conflicting]);
assert!(fetches.is_empty());
}
#[test]
fn term_start_gate_skips_non_leader_vote() {
for signer in 0..3 {
let runtime = deterministic::Runner::default();
runtime.start(move |mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
signer,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
assert_eq!(
state.handoff_leader(View::new(6)),
Some(Participant::new(3))
);
certify_conflicting_term_start(&mut state, signer, &verifier, &schemes);
});
}
}
#[test]
fn term_start_gate_skips_dynamic_elector() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, b"ns", 4);
let mut state = State::new(
context.child("state"),
Config {
scheme: schemes[1].clone(),
elector: RequireCertificateElector {
term_length: TermLength::new(NZU32!(5)),
_phantom: PhantomData,
},
epoch: Epoch::new(9),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: 4,
},
);
state.set_genesis(test_genesis());
certify_conflicting_term_start(&mut state, 1, &verifier, &schemes);
});
}
#[test]
fn pipelined_handoff_finalize_waits_for_parent_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
1,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
notarize_single_participant_handoff(&mut state, &verifier, &schemes);
assert!(state.certified(View::new(6), true).is_some());
assert!(state.construct_finalize(View::new(6)).is_none());
assert!(state.certified(View::new(5), true).is_some());
assert!(state.construct_finalize(View::new(6)).is_some());
});
}
#[test]
fn pipelined_handoff_replay_restores_early_leader() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
certify_view_4(&mut state, &verifier, &schemes);
assert_eq!(state.current_view(), View::new(5));
let tip = fetch_proposal(5, 4, 65);
let local_vote = Notarize::sign(&schemes[3], tip.clone()).expect("local notarize vote");
assert_eq!(state.leader_index(View::new(6)), None);
state.replay(&Artifact::Notarize(local_vote));
assert_eq!(state.leader_index(View::new(6)), Some(Participant::new(3)));
let ctx = state
.try_propose()
.expect("replayed outgoing vote should restore the handoff")
.into_context();
assert_eq!(ctx.round.view(), View::new(6));
assert_eq!(ctx.parent, (View::new(5), tip.payload));
let ours = fetch_proposal(6, 5, 66);
assert!(state.proposed(&ctx, ours.payload));
let notarize = state
.construct_notarize(View::new(6))
.expect("recovered handoff proposal should be votable");
assert_eq!(notarize.proposal, ours);
});
}
#[test]
fn pipelined_handoff_child_replay_prevents_rebuild() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes,
participants,
verifier,
..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let certified = certify_view_4(&mut state, &verifier, &schemes);
let tip = fetch_proposal(5, 4, 65);
let tip_vote = Notarize::sign(&schemes[3], tip).expect("tip vote");
state.replay(&Artifact::Notarize(tip_vote));
let child = fetch_proposal(6, 5, 66);
let child_vote = Notarize::sign(&schemes[3], child.clone()).expect("child vote");
state.replay(&Artifact::Notarize(child_vote));
assert!(state.try_propose().is_none());
assert!(state.construct_notarize(View::new(6)).is_none());
let nullification = build_nullification(
&verifier,
&schemes[..3],
Rnd::new(Epoch::new(9), View::new(5)),
);
assert!(state.add_nullification(nullification));
assert_eq!(
state.parent_payload_for(View::new(6), View::new(4)),
Ok(certified.payload)
);
assert!(state.try_propose().is_none());
let alternate = Context {
round: Rnd::new(Epoch::new(9), View::new(6)),
leader: participants[3].clone(),
parent: (View::new(4), certified.payload),
};
state.proposed(&alternate, Sha256Digest::from([67u8; 32]));
assert_eq!(
state.views.get(&View::new(6)).and_then(Round::proposal),
Some(&child)
);
});
}
#[test]
fn pipelined_handoff_conflicting_parent_blocks_same_term_successor() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
let ctx = state
.try_propose()
.expect("handoff proposal should use the uncertified tip")
.into_context();
assert_eq!(ctx.parent, (View::new(5), tip.payload));
let ours = fetch_proposal(6, 5, 66);
assert!(state.proposed(&ctx, ours.payload));
assert!(state.construct_notarize(View::new(6)).is_some());
let conflict = fetch_proposal(5, 4, 75);
let notarization = build_notarization(&verifier, &schemes[..3], &conflict);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(5), true).is_some());
assert_eq!(state.current_view(), View::new(6));
let request = state
.try_propose()
.map(|r| (r.view(), r.is_handoff(), r.context().parent));
assert_eq!(request, None, "proposed on a dead chain");
assert_eq!(state.optimistic_ancestry_payload(View::new(6)), None);
});
}
#[derive(Clone)]
struct RepeatLeaderElector;
impl<S: certificate::Scheme> Elector<S> for RepeatLeaderElector {
type Mode = crate::simplex::elector::Scheduled;
fn terms(&self) -> Terms {
Terms::rotating()
}
fn elect(&self, round: Rnd, _: ()) -> Participant {
match round.view().get() {
6 | 7 => Participant::new(3),
v => Participant::new((v % 3) as u32),
}
}
}
#[test]
fn pipelined_handoff_conflicting_parent_blocks_consecutive_handoff() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, b"ns", 4);
let mut state: State<_, _, RepeatLeaderElector, Sha256Digest> = State::new(
context.child("state"),
Config {
scheme: schemes[3].clone(),
elector: RepeatLeaderElector,
epoch: Epoch::new(9),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: 4,
},
);
state.set_genesis(test_genesis());
let anchor = fetch_proposal(4, 3, 64);
let notarization = build_notarization(&verifier, &schemes, &anchor);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(4), true).is_some());
let _ = state.certify_candidates();
assert_eq!(state.current_view(), View::new(5));
let tip = fetch_proposal(5, 4, 65);
assert!(state.set_proposal(View::new(5), &tip));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(5)));
assert!(state.construct_notarize(View::new(5)).is_some());
let ctx = state
.try_propose()
.expect("handoff proposal should use the uncertified tip")
.into_context();
assert_eq!(ctx.parent, (View::new(5), tip.payload));
let ours = fetch_proposal(6, 5, 66);
assert!(state.proposed(&ctx, ours.payload));
assert!(state.construct_notarize(View::new(6)).is_some());
let conflict = fetch_proposal(5, 4, 75);
let notarization = build_notarization(&verifier, &schemes[..3], &conflict);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(5), true).is_some());
assert_eq!(state.current_view(), View::new(6));
let request = state
.try_propose()
.map(|r| (r.view(), r.is_handoff(), r.context().parent));
assert_eq!(request, None, "proposed on a dead chain");
assert_eq!(state.optimistic_ancestry_payload(View::new(6)), None);
let nullification = build_nullification(
&verifier,
&schemes[..3],
Rnd::new(Epoch::new(9), View::new(6)),
);
assert!(state.add_nullification(nullification));
let request = state.try_propose().map(|r| (r.view(), r.context().parent));
assert_eq!(
request,
Some((View::new(7), (View::new(5), conflict.payload)))
);
});
}
#[test]
fn pipelined_handoff_does_not_require_recovered_parent_leader() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(state.epoch(), View::new(5)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
let tip = fetch_proposal(10, 9, 110);
let notarization = build_notarization(&verifier, &schemes, &tip);
assert!(state.add_notarization(notarization).0);
assert_eq!(state.leader_index(View::new(10)), None);
assert_eq!(state.leader_index(View::new(11)), Some(Participant::new(0)));
let request = state
.try_propose()
.expect("recovered tip should allow a handoff");
assert!(request.is_handoff());
let handoff = request.into_context();
assert_eq!(handoff.round.view(), View::new(11));
assert_eq!(handoff.parent, (View::new(10), tip.payload));
});
}
#[test]
fn pipelined_handoff_keeps_valid_fallback_after_late_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (certified, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
assert!(state.add_notarization(tip_notarization).0);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(9), View::new(5)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
let request = state
.try_propose()
.expect("term-start proposal should use the certified fallback");
assert!(matches!(request, ProposalRequest::Propose(_)));
let ctx = request.into_context();
assert_eq!(ctx.parent, (View::new(4), certified.payload));
assert!(state.certified(View::new(5), true).is_some());
let ours = fetch_proposal(6, 4, 66);
assert!(!state.supersede_proposal_request(&ctx));
assert!(state.proposed(&ctx, ours.payload));
let notarize = state
.construct_notarize(View::new(6))
.expect("still-valid fallback should remain votable");
assert_eq!(notarize.proposal, ours);
});
}
#[test]
fn pipelined_handoff_retries_after_parent_invalidation() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (certified, _) = prepare_term_boundary(&mut state, &verifier, &schemes);
let initial = state
.try_propose()
.expect("handoff proposal should use the outgoing tip")
.into_context();
assert_eq!(initial.parent.0, View::new(5));
assert!(state.try_propose().is_none());
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(9), View::new(5)));
assert!(state.add_nullification(nullification));
assert!(state.supersede_proposal_request(&initial));
let retry = state
.try_propose()
.expect("superseded handoff should retry on certified ancestry");
assert!(matches!(retry, ProposalRequest::Propose(_)));
let retry = retry.into_context();
assert_eq!(retry.round.view(), View::new(6));
assert_eq!(retry.parent, (View::new(4), certified.payload));
assert!(state.try_propose().is_none());
let rebuilt = fetch_proposal(6, 4, 67);
assert!(state.proposed(&retry, rebuilt.payload));
let notarize = state
.construct_notarize(View::new(6))
.expect("rebuilt proposal should be votable");
assert_eq!(notarize.proposal, rebuilt);
});
}
#[test]
fn rejected_build_keeps_single_propose_per_view() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let certified = certify_view_4(&mut state, &verifier, &schemes);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(9), View::new(5)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
let start = state
.try_propose()
.expect("term start should be proposed on certified ancestry")
.into_context();
assert_eq!(start.parent, (View::new(4), certified.payload));
let term_start = fetch_proposal(6, 4, 66);
assert!(state.proposed(&start, term_start.payload));
assert!(state.construct_notarize(View::new(6)).is_some());
let notarization = build_notarization(&verifier, &schemes[..3], &term_start);
assert!(state.add_notarization(notarization).0);
let request = state
.try_propose()
.expect("next view should be proposed on the notarized term start");
assert!(matches!(request, ProposalRequest::Propose(_)));
let ctx = request.into_context();
assert_eq!(ctx.round.view(), View::new(7));
assert_eq!(ctx.parent, (View::new(6), term_start.payload));
assert!(state.certified(View::new(6), false).is_some());
let child = fetch_proposal(7, 6, 67);
assert!(!state.supersede_proposal_request(&ctx));
assert!(!state.proposed(&ctx, child.payload));
let finalization = build_finalization(&verifier, &schemes, &term_start);
assert!(state.add_finalization(finalization).0);
assert!(state.try_propose().is_none());
});
}
#[test]
fn pipelined_handoff_withholds_notarize_after_failed_certification() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
let ctx = state
.try_propose()
.expect("handoff proposal should use the outgoing tip")
.into_context();
let ours = fetch_proposal(6, 5, 66);
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
assert!(state.add_notarization(tip_notarization).0);
assert!(state.certified(View::new(5), false).is_some());
assert!(!state.proposed(&ctx, ours.payload));
assert!(state.construct_notarize(View::new(6)).is_none());
});
}
#[test]
fn pipelined_handoff_withholds_notarize_after_equivocation() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
prepare_term_boundary(&mut state, &verifier, &schemes);
let ctx = state
.try_propose()
.expect("handoff proposal should use the outgoing tip")
.into_context();
let ours = fetch_proposal(6, 5, 66);
assert!(!state.set_proposal(View::new(5), &fetch_proposal(5, 4, 99)));
assert!(!state.proposed(&ctx, ours.payload));
assert!(state.construct_notarize(View::new(6)).is_none());
});
}
#[test]
fn pipelined_handoff_withholds_notarize_after_conflicting_parent_certificate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
let proposal_context = state
.try_propose()
.expect("handoff proposal should use the outgoing tip")
.into_context();
assert_eq!(proposal_context.parent, (View::new(5), tip.payload));
let conflicting = fetch_proposal(5, 4, 99);
let notarization = build_notarization(&verifier, &schemes[..3], &conflicting);
let (added, equivocator) = state.add_notarization(notarization);
assert!(added);
assert!(equivocator.is_some());
assert_eq!(state.current_view(), View::new(5));
let ours = fetch_proposal(6, 5, 66);
assert!(!state.proposed(&proposal_context, ours.payload));
assert!(state.construct_notarize(View::new(6)).is_none());
});
}
enum Arrival {
Proposal,
Notarization,
}
fn peer_verification_stays_explicit(arrival: Arrival) {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
participants,
schemes,
verifier,
..
},
mut state,
) = setup_state_with(
&mut context,
4,
1,
9,
10,
TermLength::new(NZU32!(5)),
ViewDelta::new(2),
4,
);
let (_, tip) = prepare_term_boundary(&mut state, &verifier, &schemes);
assert_eq!(state.leader_index(View::new(6)), None);
assert!(state.try_propose().is_none());
let tip_notarization = build_notarization(&verifier, &schemes, &tip);
let child = fetch_proposal(6, 5, 66);
match arrival {
Arrival::Proposal => {
assert!(state.set_proposal(View::new(6), &child));
assert!(matches!(state.try_verify(), Verify::Wait));
assert!(state.add_notarization(tip_notarization).0);
}
Arrival::Notarization => {
assert!(state.add_notarization(tip_notarization).0);
assert!(state.set_proposal(View::new(6), &child));
}
}
let leader =
participants[usize::from(state.leader_index(View::new(6)).unwrap())].clone();
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Notarization,
target,
}
if proposal == View::new(6)
&& view == View::new(5)
&& target == leader
));
assert!(state.certified(View::new(5), true).is_some());
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("proposal should verify once the tip certifies");
};
assert_eq!(ctx.parent, (View::new(5), tip.payload));
assert_eq!(proposal, child);
});
}
#[test]
fn pipelined_handoff_keeps_peer_verification_explicit() {
peer_verification_stays_explicit(Arrival::Notarization);
}
#[test]
fn pipelined_handoff_keeps_early_peer_proposal_explicit() {
peer_verification_stays_explicit(Arrival::Proposal);
}
#[test]
fn pipelined_handoff_pipelines_rotating_terms() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (_, mut state) = setup_state_with(
&mut context,
4,
3,
9,
10,
TermLength::ONE,
ViewDelta::new(0),
4,
);
let first = fetch_proposal(1, 0, 67);
assert!(state.set_proposal(View::new(1), &first));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
assert!(state.construct_notarize(View::new(1)).is_some());
let ctx = state
.try_propose()
.expect("handoff proposal should pipeline single-view terms")
.into_context();
assert_eq!(ctx.round.view(), View::new(2));
assert_eq!(ctx.parent, (View::new(1), first.payload));
assert_eq!(state.current_view(), View::new(1));
});
}
#[test]
fn late_parent_certificate_unblocks_notarized_chain_after_term_skip() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
3,
1,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(3),
4,
);
let others = &schemes[..3];
let epoch = Epoch::new(1);
let payload_v1 = Sha256Digest::from([1u8; 32]);
let proposal_v1 =
Proposal::new(Rnd::new(epoch, View::new(1)), GENESIS_VIEW, payload_v1);
let notarization_v1 = build_notarization(&verifier, others, &proposal_v1);
assert!(state.add_notarization(notarization_v1).0);
assert!(state.certified(View::new(1), true).is_some());
let payload_v2 = Sha256Digest::from([2u8; 32]);
let proposal_v2 =
Proposal::new(Rnd::new(epoch, View::new(2)), View::new(1), payload_v2);
let proposal_v3 = Proposal::new(
Rnd::new(epoch, View::new(3)),
View::new(2),
Sha256Digest::from([3u8; 32]),
);
let proposal_v4 = Proposal::new(
Rnd::new(epoch, View::new(4)),
View::new(3),
Sha256Digest::from([4u8; 32]),
);
for proposal in [&proposal_v3, &proposal_v4] {
let notarization = build_notarization(&verifier, others, proposal);
assert!(state.add_notarization(notarization).0);
}
assert!(state.certify_candidates().0.is_empty());
let nullification =
build_nullification(&verifier, others, Rnd::new(epoch, View::new(2)));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(6));
assert_eq!(state.leader_index(View::new(6)), Some(Participant::new(3)));
let proposal = state
.try_propose()
.expect("term-start proposal should skip the blocked chain")
.into_context();
assert_eq!(proposal.parent, (View::new(1), payload_v1));
let notarization_v2 = build_notarization(&verifier, others, &proposal_v2);
assert!(state.add_notarization(notarization_v2).0);
for view in [View::new(2), View::new(3)] {
let candidates = state.certify_candidates().0;
assert_eq!(candidates.len(), 1);
assert_eq!(candidates[0].round.view(), view);
assert!(state.certified(view, true).is_some());
}
let finalization = build_finalization(&verifier, others, &proposal_v4);
assert!(state.add_finalization(finalization).0);
assert!(state.certify_candidates().0.is_empty());
assert_eq!(state.current_view(), View::new(6));
});
}
#[test]
fn late_nullification_unblocks_follower_verify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let local_scheme = schemes[1].clone();
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(10),
timeout_retry: Duration::from_secs(30),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let parent_view = View::new(1);
let blocked_view = parent_view.next();
let child_view = blocked_view.next();
let parent_payload = Sha256Digest::from([88u8; 32]);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
parent_payload,
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(parent_view, true).is_some());
assert!(state.enter_view(child_view));
state.set_leader(child_view, None);
assert_eq!(state.current_view(), child_view);
assert_eq!(state.leader_index(child_view), Some(Participant::new(0)));
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
parent_view,
Sha256Digest::from([89u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
let initial_deadline = state.next_timeout();
assert!(initial_deadline.0 > context.current());
assert!(!matches!(state.try_verify(), Verify::Ready(..)));
assert_eq!(state.next_timeout(), initial_deadline);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), blocked_view));
assert!(state.add_nullification(nullification));
let Verify::Ready(ctx, proposal) = state.try_verify() else {
panic!("verify context should exist");
};
assert_eq!(ctx.round.view(), child_view);
assert_eq!(ctx.parent, (parent_view, parent_payload));
assert_eq!(proposal, child_proposal);
});
}
fn setup_follower_state(
context: &mut deterministic::Context,
) -> (Fixture<ed25519::Scheme>, TestState) {
let namespace = b"ns".to_vec();
let fixture = ed25519::fixture(context, &namespace, 4);
let local_scheme = fixture.schemes[1].clone();
let cfg = Config {
scheme: local_scheme.clone(),
elector: round_robin(&local_scheme),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(10),
certification_timeout: Duration::from_secs(10),
timeout_retry: Duration::from_secs(30),
skip_budget: local_scheme.participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
(fixture, state)
}
#[test]
fn resolution_requests_first_missing_view() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let expected_leader = fixture.participants[0].clone();
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let skipped_view = View::new(2);
let skipped_proposal = Proposal::new(
Rnd::new(Epoch::new(1), skipped_view),
GENESIS_VIEW,
Sha256Digest::from([88u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &skipped_proposal);
let (added, _) = state.add_notarization(notarization.clone());
assert!(added);
assert!(state.certified(skipped_view, true).is_some());
let child_view = View::new(3);
state.set_leader(child_view, None);
assert_eq!(state.current_view(), child_view);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
View::new(1),
Sha256Digest::from([89u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Nullification,
target,
}
if proposal == child_view
&& view == skipped_view
&& target == expected_leader
));
let (added, _) = state.add_notarization(notarization);
assert!(!added);
assert!(matches!(state.try_verify(), Verify::Wait));
});
}
#[test]
fn resolution_requests_uncertified_parent() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let parent_view = View::new(1);
let nullification_1 =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), parent_view));
assert!(state.add_nullification(nullification_1.clone()));
let nullification_2 =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(2)));
assert!(state.add_nullification(nullification_2));
let child_view = View::new(3);
assert_eq!(state.current_view(), child_view);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
parent_view,
Sha256Digest::from([90u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Notarization,
..
}
if proposal == child_view
&& view == parent_view
));
assert!(!state.add_nullification(nullification_1));
assert!(matches!(state.try_verify(), Verify::Wait));
});
}
#[test]
fn resolution_silent_for_parent_below_floor() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let finalized_view = View::new(2);
let finalized_proposal = Proposal::new(
Rnd::new(Epoch::new(1), finalized_view),
GENESIS_VIEW,
Sha256Digest::from([91u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &finalized_proposal);
let (added, _) = state.add_finalization(finalization);
assert!(added);
let child_view = View::new(3);
assert_eq!(state.current_view(), child_view);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
View::new(1),
Sha256Digest::from([92u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(state.try_verify(), Verify::Wait));
});
}
#[test]
fn resolution_starts_at_first_gap_before_displaced_certificate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let displaced_view = View::new(3);
let displaced_proposal = Proposal::new(
Rnd::new(Epoch::new(1), displaced_view),
View::new(1),
Sha256Digest::from([95u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &displaced_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(displaced_view, true).is_some());
let nullification_4 =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(4)));
assert!(state.add_nullification(nullification_4));
let child_view = View::new(5);
assert_eq!(state.current_view(), child_view);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
View::new(1),
Sha256Digest::from([96u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Nullification,
..
}
if proposal == child_view
&& view == View::new(2)
));
});
}
#[test]
fn resolution_rearms_in_next_round() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let skipped_view = View::new(2);
let skipped_proposal = Proposal::new(
Rnd::new(Epoch::new(1), skipped_view),
GENESIS_VIEW,
Sha256Digest::from([97u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &skipped_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(skipped_view, true).is_some());
state.set_leader(View::new(3), None);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(3)),
View::new(1),
Sha256Digest::from([98u8; 32]),
);
assert!(state.set_proposal(View::new(3), &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
view,
kind: Kind::Nullification,
..
} if view == skipped_view
));
for view in 3..=4 {
let nullification = build_nullification(
&verifier,
&schemes,
Rnd::new(Epoch::new(1), View::new(view)),
);
assert!(state.add_nullification(nullification));
}
let retry_view = View::new(5);
assert_eq!(state.current_view(), retry_view);
let retry_proposal = Proposal::new(
Rnd::new(Epoch::new(1), retry_view),
View::new(1),
Sha256Digest::from([99u8; 32]),
);
assert!(state.set_proposal(retry_view, &retry_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Nullification,
..
}
if proposal == retry_view
&& view == skipped_view
));
});
}
#[test]
fn resolution_does_not_wait_for_local_conflict() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let skipped_view = View::new(2);
let skipped_proposal = Proposal::new(
Rnd::new(Epoch::new(1), skipped_view),
GENESIS_VIEW,
Sha256Digest::from([100u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &skipped_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
let child_view = View::new(3);
assert!(state.enter_view(child_view));
state.set_leader(child_view, None);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
View::new(1),
Sha256Digest::from([101u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Nullification,
..
}
if proposal == child_view
&& view == skipped_view
));
assert!(state.certified(skipped_view, true).is_some());
assert!(matches!(state.try_verify(), Verify::Wait));
});
}
#[test]
fn resolution_requests_named_parent_with_term_cover() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_state(&mut context, 4, 1, 10, 3, 4);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let nullification_1 =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(1)));
assert!(state.add_nullification(nullification_1));
let child_view = View::new(4);
assert_eq!(state.current_view(), child_view);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
View::new(2),
Sha256Digest::from([102u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Notarization,
..
}
if proposal == child_view
&& view == View::new(2)
));
});
}
#[test]
fn resolution_requests_absent_certificate() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (fixture, mut state) = setup_follower_state(&mut context);
let (schemes, verifier) = (fixture.schemes, fixture.verifier);
let parent_view = View::new(1);
let parent_proposal = Proposal::new(
Rnd::new(Epoch::new(1), parent_view),
GENESIS_VIEW,
Sha256Digest::from([93u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &parent_proposal);
let (added, _) = state.add_notarization(notarization);
assert!(added);
assert!(state.certified(parent_view, true).is_some());
let child_view = View::new(3);
assert!(state.enter_view(child_view));
state.set_leader(child_view, None);
let child_proposal = Proposal::new(
Rnd::new(Epoch::new(1), child_view),
parent_view,
Sha256Digest::from([94u8; 32]),
);
assert!(state.set_proposal(child_view, &child_proposal));
assert!(matches!(
state.try_verify(),
Verify::Resolve {
proposal,
view,
kind: Kind::Nullification,
..
}
if proposal == child_view
&& view == View::new(2)
));
});
}
#[test]
fn only_notarize_before_nullify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture { schemes, .. } = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(5),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([1u8; 32]),
);
state.set_proposal(view, &proposal);
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(view));
let (retry, _) = state
.construct_nullify(view, TimeoutReason::LeaderTimeout)
.expect("timeout nullify should exist");
assert!(!retry);
assert!(state.construct_notarize(view).is_none());
});
}
#[test]
fn nullification_skips_to_next_term_start() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
assert_eq!(state.current_view(), View::new(1));
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(1)));
assert!(state.add_nullification(nullification));
assert_eq!(
state.current_view(),
View::new(6),
"nullification in term should skip to next term start"
);
});
}
#[test]
fn nullification_at_term_end_skips_correctly() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([10u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_v1);
state.add_finalization(finalization);
assert_eq!(state.current_view(), View::new(2));
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([11u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal_v2);
state.add_finalization(finalization);
assert_eq!(state.current_view(), View::new(3));
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(3)));
assert!(state.add_nullification(nullification));
assert_eq!(
state.current_view(),
View::new(4),
"nullification at term end should advance to next term start"
);
});
}
#[test]
fn term_length_one_nullification_advances_by_one() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin(&schemes[0]),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(10),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
assert_eq!(state.current_view(), View::new(1));
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), View::new(1)));
assert!(state.add_nullification(nullification));
assert_eq!(
state.current_view(),
View::new(2),
"term_length=1 should advance by exactly one view"
);
});
}
#[test]
fn term_safety_blocks_finalize_after_nullify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
assert_eq!(view, View::new(1));
let (was_retry, _) = state
.construct_nullify(view, TimeoutReason::LeaderTimeout)
.expect("timeout nullify should exist");
assert!(!was_retry);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([42u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(view, true).is_some());
assert_eq!(state.current_view(), View::new(2));
let view = View::new(2);
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), view),
View::new(1),
Sha256Digest::from([43u8; 32]),
);
assert!(state.set_proposal(view, &proposal_v2));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(view));
let notarization = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(view, true).is_some());
assert!(
state.construct_finalize(view).is_none(),
"should not finalize a later view after nullifying in same term"
);
let finalization = build_finalization(&verifier, &schemes, &proposal_v1);
state.add_finalization(finalization);
assert!(
state.construct_finalize(view).is_some(),
"late-arriving finalization at the nullified view should unblock the finalize vote"
);
});
}
#[test]
fn same_term_nullify_does_not_block_notarize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let view = state.current_view();
let (was_retry, _) = state
.construct_nullify(view, TimeoutReason::LeaderTimeout)
.expect("timeout nullify should exist");
assert!(!was_retry);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), view),
GENESIS_VIEW,
Sha256Digest::from([42u8; 32]),
);
let notarization = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(view, true).is_some());
assert_eq!(state.current_view(), View::new(2));
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([43u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(2)));
assert!(
state.construct_notarize(View::new(2)).is_some(),
"same-term nullify should not block later notarize votes"
);
});
}
#[test]
fn recovered_parent_finalization_allows_same_term_child_finalize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
1,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(0),
4,
);
assert!(state.enter_view(View::new(2)));
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([44u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
let notarization = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(2), true).is_some());
assert!(state.construct_finalize(View::new(2)).is_none());
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([45u8; 32]),
);
let finalization_v1 = build_finalization(&verifier, &schemes, &proposal_v1);
state.add_finalization(finalization_v1);
assert!(state.construct_finalize(View::new(2)).is_some());
});
}
#[test]
fn certified_child_without_parent_anchor_cannot_finalize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let (
Fixture {
schemes, verifier, ..
},
mut state,
) = setup_state_with(
&mut context,
4,
0,
1,
20,
TermLength::new(NZU32!(5)),
ViewDelta::new(0),
4,
);
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([50u8; 32]),
);
let notarization_v1 = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(state.add_notarization(notarization_v1).0);
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([51u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal_v2));
let notarization_v2 = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(state.add_notarization(notarization_v2).0);
state.replay(&Artifact::Certification(
Rnd::new(Epoch::new(1), View::new(2)),
true,
));
assert!(
state.construct_finalize(View::new(2)).is_none(),
"finalize must wait for the parent's explicit certification anchor"
);
assert!(state.certified(View::new(1), true).is_some());
assert!(
state.construct_finalize(View::new(2)).is_some(),
"finalize should proceed once the parent is explicitly certified"
);
});
}
#[test]
fn replay_restores_term_nullify_tracking_for_term_safety() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let build_finalizable_view_2 = |state: &mut State<_, _, _, _>| {
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([98u8; 32]),
);
assert!(state.set_proposal(View::new(1), &proposal_v1));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(View::new(1)));
let notarization_v1 = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(state.add_notarization(notarization_v1).0);
assert!(state.certified(View::new(1), true).is_some());
assert!(state.construct_finalize(View::new(1)).is_some());
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([99u8; 32]),
);
assert!(state.set_proposal(View::new(2), &proposal));
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(View::new(2), true).is_some());
};
let mut baseline = State::new(context.child("baseline"), cfg);
baseline.set_genesis(test_genesis());
build_finalizable_view_2(&mut baseline);
assert!(
baseline.construct_finalize(View::new(2)).is_some(),
"finalize should be allowed without prior nullify"
);
let mut restarted = State::new(
context.child("restarted"),
Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(5)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
},
);
restarted.set_genesis(test_genesis());
let nullify =
Nullify::sign::<Sha256Digest>(&schemes[0], Rnd::new(Epoch::new(1), View::new(1)))
.expect("nullify");
restarted.replay(&Artifact::Nullify(nullify));
let proposal_v1 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([98u8; 32]),
);
let local_notarize_v1 =
Notarize::sign(&schemes[0], proposal_v1.clone()).expect("local notarize");
restarted.replay(&Artifact::Notarize(local_notarize_v1));
let notarization_v1 = build_notarization(&verifier, &schemes, &proposal_v1);
assert!(restarted.add_notarization(notarization_v1).0);
assert!(restarted.certified(View::new(1), true).is_some());
let proposal_v2 = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([99u8; 32]),
);
assert!(restarted.set_proposal(View::new(2), &proposal_v2));
let notarization_v2 = build_notarization(&verifier, &schemes, &proposal_v2);
assert!(restarted.add_notarization(notarization_v2).0);
assert!(restarted.certified(View::new(2), true).is_some());
assert!(
restarted.construct_finalize(View::new(2)).is_none(),
"replayed nullify should restore term-safety lock after restart"
);
});
}
#[test]
fn pruned_inert_nullify_does_not_block_finalize() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(20)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context.child("state"), cfg);
state.set_genesis(test_genesis());
let (was_retry, nullify) = state
.construct_nullify(View::new(1), TimeoutReason::LeaderTimeout)
.expect("timeout nullify should exist");
assert!(!was_retry);
let nullify_artifact = Artifact::Nullify(nullify);
let finalized_view = View::new(10);
let finalized_proposal = Proposal::new(
Rnd::new(Epoch::new(1), finalized_view),
GENESIS_VIEW,
Sha256Digest::from([10u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &finalized_proposal);
let finalization_artifact = Artifact::Finalization(finalization.clone());
state.add_finalization(finalization.clone());
assert_eq!(state.last_finalized(), finalized_view);
assert_eq!(state.min_active(), View::new(8));
let removed = state.prune();
assert!(removed.contains(&View::new(1)));
let certify_view = |state: &mut TestState| {
let view = View::new(11);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), view),
finalized_view,
Sha256Digest::from([11u8; 32]),
);
assert!(state.set_proposal(view, &proposal));
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(view));
let notarization = build_notarization(&verifier, &schemes, &proposal);
assert!(state.add_notarization(notarization).0);
assert!(state.certified(view, true).is_some());
view
};
let view = certify_view(&mut state);
assert!(
state.construct_finalize(view).is_some(),
"inert same-term nullify must not block finalize after pruning"
);
let mut restarted = State::new(
context.child("restarted"),
Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(20)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(2),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
},
);
restarted.set_genesis(test_genesis());
restarted.replay(&nullify_artifact);
restarted.replay(&finalization_artifact);
restarted.add_finalization(finalization);
assert_eq!(restarted.last_finalized(), finalized_view);
let view = certify_view(&mut restarted);
assert!(
restarted.construct_finalize(view).is_some(),
"replayed inert nullify must remain inert after restart"
);
});
}
#[test]
fn term_safety_allows_finalize_in_new_term_after_nullify() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let view1 = View::new(1);
let (was_retry, _) = state
.construct_nullify(view1, TimeoutReason::LeaderTimeout)
.expect("timeout nullify should exist");
assert!(!was_retry);
let nullification =
build_nullification(&verifier, &schemes, Rnd::new(Epoch::new(1), view1));
assert!(state.add_nullification(nullification));
assert_eq!(state.current_view(), View::new(4));
let view4 = View::new(4);
let proposal_v4 = Proposal::new(
Rnd::new(Epoch::new(1), view4),
GENESIS_VIEW,
Sha256Digest::from([55u8; 32]),
);
state.set_proposal(view4, &proposal_v4);
assert!(matches!(state.try_verify(), Verify::Ready(..)));
assert!(state.verified(view4));
let notarization = build_notarization(&verifier, &schemes, &proposal_v4);
state.add_notarization(notarization);
assert!(state.certified(view4, true).is_some());
assert!(
state.construct_finalize(view4).is_some(),
"finalize should be allowed in a new term after prior-term nullify"
);
});
}
#[test]
fn same_leader_within_term() {
let runtime = deterministic::Runner::default();
runtime.start(|mut context| async move {
let namespace = b"ns".to_vec();
let Fixture {
schemes, verifier, ..
} = ed25519::fixture(&mut context, &namespace, 4);
let cfg = Config {
scheme: schemes[0].clone(),
elector: round_robin_with_term(
&schemes[0],
TermLength::new(NZU32!(3)),
Duration::from_secs(4),
ViewDelta::new(0),
),
epoch: Epoch::new(1),
view_retention: ViewDelta::new(20),
leader_timeout: Duration::from_secs(1),
certification_timeout: Duration::from_secs(2),
timeout_retry: Duration::from_secs(3),
skip_budget: schemes[0].participants().len() as u64,
};
let mut state = State::new(context, cfg);
state.set_genesis(test_genesis());
let leader_v1 = state.leader_index(View::new(1)).unwrap();
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(1)),
GENESIS_VIEW,
Sha256Digest::from([10u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal);
state.add_finalization(finalization);
assert_eq!(state.current_view(), View::new(2));
let leader_v2 = state.leader_index(View::new(2)).unwrap();
assert_eq!(
leader_v1, leader_v2,
"views within the same term should have the same leader"
);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(2)),
View::new(1),
Sha256Digest::from([11u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal);
state.add_finalization(finalization);
assert_eq!(state.current_view(), View::new(3));
let leader_v3 = state.leader_index(View::new(3)).unwrap();
assert_eq!(
leader_v1, leader_v3,
"last view in same term should have the same leader"
);
let proposal = Proposal::new(
Rnd::new(Epoch::new(1), View::new(3)),
View::new(2),
Sha256Digest::from([12u8; 32]),
);
let finalization = build_finalization(&verifier, &schemes, &proposal);
state.add_finalization(finalization);
assert_eq!(state.current_view(), View::new(4));
assert!(state.leader_index(View::new(4)).is_some());
});
}
}