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

hotshot_types/
vote.rs
