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

hotshot_types/
vote.rs
