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

hotshot_types/
vote.rs
