hotshot_new_protocol/vote/
accumulate.rs

1use std::{any::type_name, mem};
2
3use committable::Committable;
4use hotshot_types::{
5    epoch_membership::EpochMembership,
6    message::UpgradeLock,
7    simple_certificate::{SimpleCertificate, Threshold},
8    simple_vote::{HasEpoch, VersionedVoteData},
9    stake_table::StakeTableEntries,
10    traits::{
11        node_implementation::NodeType,
12        signature_key::{SignatureKey, StakeTableEntryType},
13    },
14    vote::{Certificate, HasViewNumber, Vote, VoteAccumulator},
15};
16use hotshot_utils::anytrace;
17use tracing::{info, warn};
18
19use crate::cert_verifier::verify_signatures;
20
21/// The certificate formed from votes of type `V` under threshold `Th`.
22pub type Cert<T, V, Th> = SimpleCertificate<T, <V as Vote<T>>::Commitment, Th>;
23
24/// A [`VoteAccumulator`] that validates certificates before emitting them.
25///
26/// Votes are accumulated without checking their signatures. If the resulting
27/// certificate is invalid, votes with invalid signatures are discarded, the
28/// remaining ones are accumulated again, and every subsequent vote is verified
29/// before it is accumulated.
30pub struct CheckedAccumulator<T, V, Th>
31where
32    T: NodeType,
33    V: Vote<T>,
34    Th: Threshold<T>,
35    Cert<T, V, Th>: Certificate<T, V::Commitment, Voteable = V::Commitment> + HasEpoch,
36{
37    accumulator: VoteAccumulator<T, V, Cert<T, V, Th>>,
38
39    /// Votes accumulated so far, kept for recovery from an invalid certificate.
40    votes: Vec<V>,
41
42    /// Verify votes before accumulating them?
43    ///
44    /// Set after an invalid certificate.
45    verify_votes: bool,
46
47    membership: EpochMembership<T>,
48
49    upgrade_lock: UpgradeLock<T>,
50}
51
52impl<T, V, Th> CheckedAccumulator<T, V, Th>
53where
54    T: NodeType,
55    V: Vote<T>,
56    V::Commitment: 'static,
57    Th: Threshold<T>,
58    Cert<T, V, Th>: Certificate<T, V::Commitment, Voteable = V::Commitment> + HasEpoch,
59{
60    pub fn new(membership: EpochMembership<T>, lock: UpgradeLock<T>) -> Self {
61        Self {
62            accumulator: VoteAccumulator::new(lock.clone()),
63            votes: Vec::new(),
64            verify_votes: false,
65            membership,
66            upgrade_lock: lock,
67        }
68    }
69
70    /// Accumulate a vote.
71    ///
72    /// Returns a valid certificate once enough votes have been collected.
73    pub fn add(&mut self, vote: V) -> Option<Cert<T, V, Th>> {
74        if self.verify_votes {
75            if !self.is_valid_vote(&vote) {
76                return None;
77            }
78            let cert = self
79                .accumulator
80                .accumulate(&vote, self.membership.clone())?;
81            debug_assert!(self.validate(&cert).is_ok());
82            info!(view = %cert.view_number(), cert = type_name::<Cert<T, V, Th>>(), "certificate formed");
83            return Some(cert);
84        }
85
86        let Some(cert) = self.accumulator.accumulate(&vote, self.membership.clone()) else {
87            self.votes.push(vote);
88            return None;
89        };
90
91        match self.validate(&cert) {
92            Ok(()) => {
93                info!(view = %cert.view_number(), cert = type_name::<Cert<T, V, Th>>(), "certificate formed");
94                Some(cert)
95            },
96            Err(err) => {
97                warn!(view = %cert.view_number(), %err, "invalid certificate formed");
98                self.votes.push(vote);
99                self.recover()
100            },
101        }
102    }
103
104    /// The fewest votes that could reach the threshold.
105    ///
106    /// A vote carries at most the largest stake in the table, so fewer than
107    /// this many can never certify anything. Clamped to the size of that same
108    /// table: the quotient stays below it only while the threshold and the
109    /// stake table come from one snapshot, and the caller sizes an allocation
110    /// with the result.
111    pub fn min_votes(&self) -> usize {
112        let table = Cert::<T, V, Th>::stake_table(&self.membership);
113        let largest = table
114            .0
115            .iter()
116            .map(|peer| peer.stake_table_entry.stake())
117            .max()
118            .unwrap_or_default();
119        if largest.is_zero() {
120            return 1;
121        }
122        let nodes = table.0.len().max(1);
123        let votes = Cert::<T, V, Th>::threshold(&self.membership).div_ceil(largest);
124        usize::try_from(votes).unwrap_or(nodes).clamp(1, nodes)
125    }
126
127    /// Discard votes with invalid signatures and accumulate the rest again.
128    fn recover(&mut self) -> Option<Cert<T, V, Th>> {
129        self.verify_votes = true;
130        self.accumulator.clear();
131        for vote in mem::take(&mut self.votes) {
132            if !self.is_valid_vote(&vote) {
133                continue;
134            }
135            if let Some(cert) = self.accumulator.accumulate(&vote, self.membership.clone()) {
136                debug_assert!(self.validate(&cert).is_ok());
137                info!(view = %cert.view_number(), cert = type_name::<Cert<T, V, Th>>(), "certificate formed");
138                return Some(cert);
139            }
140        }
141        None
142    }
143
144    /// Check the certificate's aggregate signature against the stake table.
145    fn validate(&self, cert: &Cert<T, V, Th>) -> anytrace::Result<()> {
146        let table = StakeTableEntries::from(Cert::<T, V, Th>::stake_table(&self.membership));
147        let thresh = Cert::<T, V, Th>::threshold(&self.membership);
148        verify_signatures(cert, &table.0, thresh, &self.upgrade_lock)
149    }
150
151    /// Check the vote's signature.
152    fn is_valid_vote(&self, vote: &V) -> bool {
153        let commit = match VersionedVoteData::new(
154            vote.date().clone(),
155            vote.view_number(),
156            &self.upgrade_lock,
157        ) {
158            Ok(data) => data.commit(),
159            Err(err) => {
160                warn!(%err, "failed to generate versioned vote data");
161                return false;
162            },
163        };
164        let valid = vote
165            .signing_key()
166            .validate(&vote.signature(), commit.as_ref());
167        if !valid {
168            warn!(
169                view = %vote.view_number(),
170                cert = type_name::<Cert<T, V, Th>>(),
171                signer = %vote.signing_key(),
172                "invalid vote"
173            );
174        }
175        valid
176    }
177}
hotshot_new_protocol/vote/accumulate.rs

hotshot_new_protocol/vote/
accumulate.rs
