hotshot_types/
vote.rs

1// Copyright (c) 2021-2024 Espresso Systems (espressosys.com)
2// This file is part of the HotShot repository.
3
4// You should have received a copy of the MIT License
5// along with the HotShot repository. If not, see <https://mit-license.org/>.
6
7//! Vote, Accumulator, and Certificate Types
8
9use std::{
10    collections::{BTreeMap, HashMap},
11    future::Future,
12    marker::PhantomData,
13};
14
15use alloy::primitives::U256;
16use bitvec::{bitvec, vec::BitVec};
17use committable::{Commitment, Committable};
18use hotshot_utils::anytrace::*;
19use tracing::error;
20
21use crate::{
22    epoch_membership::EpochMembership,
23    light_client::{LightClientState, StakeTableState},
24    message::UpgradeLock,
25    simple_certificate::{LightClientStateUpdateCertificate, Threshold},
26    simple_vote::{LightClientStateUpdateVote, VersionedVoteData, Voteable},
27    stake_table::{HSStakeTable, StakeTableEntries},
28    traits::{
29        node_implementation::{NodeType, Versions},
30        signature_key::{SignatureKey, StakeTableEntryType, StateSignatureKey},
31    },
32    PeerConfig,
33};
34
35/// A simple vote that has a signer and commitment to the data voted on.
36pub trait Vote<TYPES: NodeType>: HasViewNumber<TYPES> {
37    /// Type of data commitment this vote uses.
38    type Commitment: Voteable<TYPES>;
39
40    /// Get the signature of the vote sender
41    fn signature(&self) -> <TYPES::SignatureKey as SignatureKey>::PureAssembledSignatureType;
42    /// Gets the data which was voted on by this vote
43    fn date(&self) -> &Self::Commitment;
44    /// Gets the Data commitment of the vote
45    fn data_commitment(&self) -> Commitment<Self::Commitment>;
46
47    /// Gets the public signature key of the votes creator/sender
48    fn signing_key(&self) -> TYPES::SignatureKey;
49}
50
51/// Any type that is associated with a view
52pub trait HasViewNumber<TYPES: NodeType> {
53    /// Returns the view number the type refers to.
54    fn view_number(&self) -> TYPES::View;
55}
56
57/**
58The certificate formed from the collection of signatures a committee.
59The committee is defined by the `Membership` associated type.
60The votes all must be over the `Commitment` associated type.
61*/
62pub trait Certificate<TYPES: NodeType, T>: HasViewNumber<TYPES> {
63    /// The data commitment this certificate certifies.
64    type Voteable: Voteable<TYPES>;
65
66    /// Threshold Functions
67    type Threshold: Threshold<TYPES>;
68
69    /// Build a certificate from the data commitment and the quorum of signers
70    fn create_signed_certificate<V: Versions>(
71        vote_commitment: Commitment<VersionedVoteData<TYPES, Self::Voteable, V>>,
72        data: Self::Voteable,
73        sig: <TYPES::SignatureKey as SignatureKey>::QcType,
74        view: TYPES::View,
75    ) -> Self;
76
77    /// Checks if the cert is valid in the given epoch
78    fn is_valid_cert<V: Versions>(
79        &self,
80        stake_table: &[<TYPES::SignatureKey as SignatureKey>::StakeTableEntry],
81        threshold: U256,
82        upgrade_lock: &UpgradeLock<TYPES, V>,
83    ) -> impl std::future::Future<Output = Result<()>>;
84    /// Returns the amount of stake needed to create this certificate
85    // TODO: Make this a static ratio of the total stake of `Membership`
86    fn threshold(membership: &EpochMembership<TYPES>) -> impl Future<Output = U256> + Send;
87
88    /// Get  Stake Table from Membership implementation.
89    fn stake_table(
90        membership: &EpochMembership<TYPES>,
91    ) -> impl Future<Output = HSStakeTable<TYPES>> + Send;
92
93    /// Get Total Nodes from Membership implementation.
94    fn total_nodes(membership: &EpochMembership<TYPES>) -> impl Future<Output = usize> + Send;
95
96    /// Get  `StakeTableEntry` from Membership implementation.
97    fn stake_table_entry(
98        membership: &EpochMembership<TYPES>,
99        pub_key: &TYPES::SignatureKey,
100    ) -> impl Future<Output = Option<PeerConfig<TYPES>>> + Send;
101
102    /// Get the commitment which was voted on
103    fn data(&self) -> &Self::Voteable;
104
105    /// Get the vote commitment which the votes commit to
106    fn data_commitment<V: Versions>(
107        &self,
108        upgrade_lock: &UpgradeLock<TYPES, V>,
109    ) -> impl std::future::Future<Output = Result<Commitment<VersionedVoteData<TYPES, Self::Voteable, V>>>>;
110}
111/// Mapping of vote commitment to signatures and bitvec
112type SignersMap<COMMITMENT, KEY> = HashMap<
113    COMMITMENT,
114    (
115        BitVec,
116        Vec<<KEY as SignatureKey>::PureAssembledSignatureType>,
117    ),
118>;
119
120#[allow(clippy::type_complexity)]
121/// Accumulates votes until a certificate is formed.  This implementation works for all simple vote and certificate pairs
122pub struct VoteAccumulator<
123    TYPES: NodeType,
124    VOTE: Vote<TYPES>,
125    CERT: Certificate<TYPES, VOTE::Commitment, Voteable = VOTE::Commitment>,
126    V: Versions,
127> {
128    /// Map of all signatures accumulated so far
129    pub vote_outcomes: VoteMap2<
130        Commitment<VersionedVoteData<TYPES, <VOTE as Vote<TYPES>>::Commitment, V>>,
131        TYPES::SignatureKey,
132        <TYPES::SignatureKey as SignatureKey>::PureAssembledSignatureType,
133    >,
134    /// A bitvec to indicate which node is active and send out a valid signature for certificate aggregation, this automatically do uniqueness check
135    /// And a list of valid signatures for certificate aggregation
136    pub signers: SignersMap<
137        Commitment<VersionedVoteData<TYPES, <VOTE as Vote<TYPES>>::Commitment, V>>,
138        TYPES::SignatureKey,
139    >,
140    /// Phantom data to specify the types this accumulator is for
141    pub phantom: PhantomData<(TYPES, VOTE, CERT)>,
142    /// version information
143    pub upgrade_lock: UpgradeLock<TYPES, V>,
144}
145
146impl<
147        TYPES: NodeType,
148        VOTE: Vote<TYPES>,
149        CERT: Certificate<TYPES, VOTE::Commitment, Voteable = VOTE::Commitment>,
150        V: Versions,
151    > VoteAccumulator<TYPES, VOTE, CERT, V>
152{
153    /// Add a vote to the total accumulated votes for the given epoch.
154    /// Returns the accumulator or the certificate if we
155    /// have accumulated enough votes to exceed the threshold for creating a certificate.
156    pub async fn accumulate(
157        &mut self,
158        vote: &VOTE,
159        membership: EpochMembership<TYPES>,
160    ) -> Option<CERT> {
161        let key = vote.signing_key();
162
163        let vote_commitment = match VersionedVoteData::new(
164            vote.date().clone(),
165            vote.view_number(),
166            &self.upgrade_lock,
167        )
168        .await
169        {
170            Ok(data) => data.commit(),
171            Err(e) => {
172                tracing::warn!("Failed to generate versioned vote data: {e}");
173                return None;
174            },
175        };
176
177        if !key.validate(&vote.signature(), vote_commitment.as_ref()) {
178            error!("Invalid vote! Vote Data {:?}", vote.date());
179            return None;
180        }
181
182        let stake_table_entry = CERT::stake_table_entry(&membership, &key).await?;
183        let stake_table = CERT::stake_table(&membership).await;
184        let total_nodes = CERT::total_nodes(&membership).await;
185        let threshold = CERT::threshold(&membership).await;
186
187        let vote_node_id = stake_table
188            .iter()
189            .position(|x| *x == stake_table_entry.clone())?;
190
191        let original_signature: <TYPES::SignatureKey as SignatureKey>::PureAssembledSignatureType =
192            vote.signature();
193
194        let (total_stake_casted, total_vote_map) = self
195            .vote_outcomes
196            .entry(vote_commitment)
197            .or_insert_with(|| (U256::from(0), BTreeMap::new()));
198
199        // Check for duplicate vote
200        if total_vote_map.contains_key(&key) {
201            return None;
202        }
203        let (signers, sig_list) = self
204            .signers
205            .entry(vote_commitment)
206            .or_insert((bitvec![0; total_nodes], Vec::new()));
207        if signers.get(vote_node_id).as_deref() == Some(&true) {
208            error!("Node id is already in signers list");
209            return None;
210        }
211        signers.set(vote_node_id, true);
212        sig_list.push(original_signature);
213
214        *total_stake_casted += stake_table_entry.stake_table_entry.stake();
215        total_vote_map.insert(key, (vote.signature(), vote_commitment));
216
217        if *total_stake_casted >= threshold {
218            // Assemble QC
219            let stake_table_entries = StakeTableEntries::<TYPES>::from(stake_table).0;
220            let real_qc_pp: <<TYPES as NodeType>::SignatureKey as SignatureKey>::QcParams<'_> =
221                <TYPES::SignatureKey as SignatureKey>::public_parameter(
222                    &stake_table_entries,
223                    threshold,
224                );
225
226            let real_qc_sig = <TYPES::SignatureKey as SignatureKey>::assemble(
227                &real_qc_pp,
228                signers.as_bitslice(),
229                &sig_list[..],
230            );
231
232            let cert = CERT::create_signed_certificate::<V>(
233                vote_commitment,
234                vote.date().clone(),
235                real_qc_sig,
236                vote.view_number(),
237            );
238            return Some(cert);
239        }
240        None
241    }
242}
243
244/// Mapping of commitments to vote tokens by key.
245type VoteMap2<COMMITMENT, PK, SIG> = HashMap<COMMITMENT, (U256, BTreeMap<PK, (SIG, COMMITMENT)>)>;
246
247/// Accumulator for light client state update vote
248#[allow(clippy::type_complexity)]
249pub struct LightClientStateUpdateVoteAccumulator<TYPES: NodeType> {
250    pub vote_outcomes: HashMap<
251        (LightClientState, StakeTableState),
252        (
253            U256,
254            HashMap<
255                TYPES::StateSignatureKey,
256                <TYPES::StateSignatureKey as StateSignatureKey>::StateSignature,
257            >,
258        ),
259    >,
260}
261
262impl<TYPES: NodeType> LightClientStateUpdateVoteAccumulator<TYPES> {
263    /// Add a vote to the total accumulated votes for the given epoch.
264    /// Returns the accumulator or the certificate if we
265    /// have accumulated enough votes to exceed the threshold for creating a certificate.
266    pub async fn accumulate(
267        &mut self,
268        key: &TYPES::SignatureKey,
269        vote: &LightClientStateUpdateVote<TYPES>,
270        membership: &EpochMembership<TYPES>,
271    ) -> Option<LightClientStateUpdateCertificate<TYPES>> {
272        let epoch = membership.epoch()?;
273        let threshold = membership.success_threshold().await;
274        let PeerConfig {
275            stake_table_entry,
276            state_ver_key,
277        } = membership.stake(key).await?;
278
279        if !state_ver_key.verify_state_sig(
280            &vote.signature,
281            &vote.light_client_state,
282            &vote.next_stake_table_state,
283        ) {
284            error!("Invalid light client state update vote {:?}", vote);
285            return None;
286        }
287        let (total_stake_casted, vote_map) = self
288            .vote_outcomes
289            .entry((vote.light_client_state, vote.next_stake_table_state))
290            .or_insert_with(|| (U256::from(0), HashMap::new()));
291
292        // Check for duplicate vote
293        if vote_map.contains_key(&state_ver_key) {
294            tracing::warn!("Duplicate vote (key: {:?}, vote: {:?})", key, vote);
295            return None;
296        }
297
298        *total_stake_casted += stake_table_entry.stake();
299        vote_map.insert(state_ver_key.clone(), vote.signature.clone());
300
301        if *total_stake_casted >= threshold {
302            return Some(LightClientStateUpdateCertificate {
303                epoch,
304                light_client_state: vote.light_client_state,
305                next_stake_table_state: vote.next_stake_table_state,
306                signatures: Vec::from_iter(vote_map.iter().map(|(k, v)| (k.clone(), v.clone()))),
307            });
308        }
309        None
310    }
311}
hotshot_types/vote.rs

hotshot_types/
vote.rs
