diem_types/
term_state.rs

1// Copyright 2021 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5use std::{
6    cmp::Ordering,
7    collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque},
8    convert::TryFrom,
9    fmt::{Debug, Formatter},
10};
11
12use anyhow::{anyhow, bail, ensure, Result};
13#[cfg(any(test, feature = "fuzzing"))]
14use proptest_derive::Arbitrary;
15use serde::{Deserialize, Serialize};
16
17use cfx_types::H256;
18use diem_crypto::{
19    bls::deserialize_bls_public_key_unchecked, vrf_number_with_nonce,
20    HashValue, Signature, VRFProof,
21};
22use diem_logger::prelude::*;
23pub use incentives::*;
24use lock_status::NodeLockStatus;
25use move_core_types::vm_status::DiscardedVMStatus;
26use pos_state_config::{PosStateConfigTrait, POS_STATE_CONFIG};
27use pow_types::StakingEvent;
28
29use crate::{
30    account_address::{from_consensus_public_key, AccountAddress},
31    account_config,
32    block_info::{PivotBlockDecision, Round, View},
33    contract_event::ContractEvent,
34    epoch_state::EpochState,
35    event::EventKey,
36    transaction::{DisputePayload, ElectionPayload},
37    validator_config::{
38        ConsensusPublicKey, ConsensusVRFPublicKey, MultiConsensusPublicKey,
39        MultiConsensusSignature,
40    },
41    validator_verifier::{ValidatorConsensusInfo, ValidatorVerifier},
42};
43
44pub mod lock_status;
45pub mod pos_state_config;
46
47pub const TERM_LIST_LEN: usize = 6;
48pub const ROUND_PER_TERM: Round = 60;
49pub const IN_QUEUE_LOCKED_VIEWS: u64 = 10080;
50pub const OUT_QUEUE_LOCKED_VIEWS: u64 = 10080;
51// The view to start election in the whole PoS consensus protocol.
52
53pub const TERM_MAX_SIZE: usize = 10000;
54pub const TERM_ELECTED_SIZE: usize = 50;
55
56mod incentives {
57    use super::{TERM_ELECTED_SIZE, TERM_LIST_LEN, TERM_MAX_SIZE};
58    use crate::term_state::pos_state_config::{
59        PosStateConfigTrait, POS_STATE_CONFIG,
60    };
61
62    const BONUS_VOTE_MAX_SIZE: u64 = 100;
63
64    pub const MAX_TERM_POINTS: u64 = 6_000_000;
65
66    const ELECTION_PERCENTAGE: u64 = 20;
67    const COMMITTEE_PERCENTAGE: u64 = 75;
68    const LEADER_PERCENTAGE: u64 = 3;
69    const BONUS_VOTE_PERCENTAGE: u64 = 2;
70
71    pub const ELECTION_POINTS: u64 =
72        MAX_TERM_POINTS * ELECTION_PERCENTAGE / 100 / (TERM_MAX_SIZE as u64);
73    pub const COMMITTEE_POINTS: u64 = MAX_TERM_POINTS * COMMITTEE_PERCENTAGE
74        / 100
75        / (TERM_ELECTED_SIZE as u64)
76        / (TERM_LIST_LEN as u64);
77
78    pub fn leader_points(view: u64) -> u64 {
79        MAX_TERM_POINTS * LEADER_PERCENTAGE
80            / 100
81            / POS_STATE_CONFIG.round_per_term(view)
82    }
83
84    pub fn bonus_vote_points(view: u64) -> u64 {
85        MAX_TERM_POINTS * BONUS_VOTE_PERCENTAGE
86            / 100
87            / POS_STATE_CONFIG.round_per_term(view)
88            / BONUS_VOTE_MAX_SIZE
89    }
90}
91
92#[derive(Copy, Clone, Eq, PartialEq, Serialize, Deserialize, Debug)]
93#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
94pub enum NodeStatus {
95    Accepted,
96    Retired,
97    Unlocked,
98}
99
100#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
101#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
102pub struct NodeData {
103    /// This struct is only used locally, so loaded public keys must be valid.
104    #[serde(deserialize_with = "deserialize_bls_public_key_unchecked")]
105    public_key: ConsensusPublicKey,
106    vrf_public_key: Option<ConsensusVRFPublicKey>,
107    lock_status: NodeLockStatus,
108}
109
110impl NodeData {
111    pub fn lock_status(&self) -> &NodeLockStatus { &self.lock_status }
112}
113
114/// A node becomes its voting power number of ElectionNodes for election.
115#[derive(
116    Clone, Debug, Eq, PartialEq, Serialize, Deserialize, Ord, PartialOrd,
117)]
118#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
119pub struct ElectionNodeID {
120    node_id: NodeID,
121    nonce: u64,
122}
123
124impl ElectionNodeID {
125    pub fn new(node_id: NodeID, nonce: u64) -> Self {
126        ElectionNodeID { node_id, nonce }
127    }
128}
129
130#[derive(Clone, Default, Debug, Serialize, Deserialize)]
131#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
132pub struct ElectingHeap(
133    BinaryHeap<(HashValue, ElectionNodeID)>,
134    HashSet<AccountAddress>,
135);
136
137#[derive(Clone, Default, Debug, Eq, PartialEq, Serialize, Deserialize)]
138#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
139pub struct ElectedMap(BTreeMap<AccountAddress, u64>);
140
141pub type CandyMap = ElectedMap;
142
143#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
144#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
145pub enum NodeList {
146    Electing(ElectingHeap),
147    Elected(ElectedMap),
148}
149
150impl Default for NodeList {
151    fn default() -> Self { NodeList::Electing(Default::default()) }
152}
153
154impl NodeList {
155    fn len(&self) -> usize {
156        match self {
157            NodeList::Electing(heap) => heap.0.len(),
158            NodeList::Elected(map) => map.0.len(),
159        }
160    }
161
162    fn add_node(&mut self, vrf_output: HashValue, node_id: ElectionNodeID) {
163        if let NodeList::Electing(heap) = self {
164            heap.add_node(vrf_output, node_id);
165        } else {
166            panic!("The term is finalized");
167        }
168    }
169
170    #[must_use]
171    fn finalize_elect(&mut self) -> CandyMap {
172        if let NodeList::Electing(heap) = self {
173            let electing_heap = std::mem::take(heap);
174            let (elected_heap, candy_map) = electing_heap.finalize();
175            *self = NodeList::Elected(elected_heap);
176            return candy_map;
177        } else {
178            panic!("The term is finalized");
179        }
180    }
181
182    fn has_elected(&self, addr: &AccountAddress) -> bool {
183        if let NodeList::Electing(heap) = self {
184            heap.1.contains(addr)
185        } else {
186            panic!("The term is finalized");
187        }
188    }
189
190    fn serving_votes(&self, address: &AccountAddress) -> u64 {
191        if let NodeList::Elected(map) = self {
192            map.0.get(address).cloned().unwrap_or(0)
193        } else {
194            panic!("The term is not finalized");
195        }
196    }
197
198    fn committee(&self) -> &ElectedMap {
199        if let NodeList::Elected(map) = self {
200            map
201        } else {
202            panic!("The term is not finalized");
203        }
204    }
205}
206
207impl ElectedMap {
208    pub fn inner(&self) -> &BTreeMap<AccountAddress, u64> { &self.0 }
209}
210
211impl ElectingHeap {
212    pub fn read_top_electing(&self) -> BTreeMap<AccountAddress, u64> {
213        let mut top_electing: BTreeMap<AccountAddress, u64> = BTreeMap::new();
214        let mut clone = self.clone();
215        let mut count = 0usize;
216        while let Some((_, node_id)) = clone.0.pop() {
217            *top_electing.entry(node_id.node_id.addr).or_insert(0) += 1;
218            count += 1;
219            if count >= POS_STATE_CONFIG.term_elected_size() {
220                break;
221            }
222        }
223        top_electing
224    }
225
226    fn finalize(mut self) -> (ElectedMap, CandyMap) {
227        let mut elected_map = ElectedMap::default();
228        let mut count = 0usize;
229        while let Some((_, node_id)) = self.0.pop() {
230            *elected_map.0.entry(node_id.node_id.addr).or_insert(0) += 1;
231            count += 1;
232            if count >= POS_STATE_CONFIG.term_elected_size() {
233                break;
234            }
235        }
236        let mut candy_map = elected_map.clone();
237        for (_, node_id) in self.0.into_vec().drain(..) {
238            *candy_map.0.entry(node_id.node_id.addr).or_insert(0) += 1;
239        }
240        (elected_map, candy_map)
241    }
242
243    pub fn add_node(&mut self, hash: HashValue, node_id: ElectionNodeID) {
244        let is_not_full_set = self.0.len() < POS_STATE_CONFIG.term_max_size();
245        self.1.insert(node_id.node_id.addr.clone());
246        if self
247            .0
248            .peek()
249            .map_or(true, |(max_value, _)| is_not_full_set || hash < *max_value)
250        {
251            self.0.push((hash, node_id.clone()));
252            if self.0.len() > POS_STATE_CONFIG.term_max_size() {
253                self.0.pop();
254            }
255        }
256    }
257}
258
259#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
260#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
261pub struct TermData {
262    start_view: Round,
263    seed: Vec<u8>,
264    /// (VRF.val, NodeID)
265    node_list: NodeList,
266}
267
268impl TermData {
269    pub fn start_view(&self) -> u64 { self.start_view }
270
271    pub fn get_term(&self) -> u64 {
272        POS_STATE_CONFIG.get_term_view(self.start_view).0
273    }
274
275    pub fn node_list(&self) -> &NodeList { &self.node_list }
276}
277
278impl PartialEq for ElectingHeap {
279    fn eq(&self, other: &Self) -> bool {
280        if self.1 != other.1 {
281            return false;
282        }
283        let mut iter_self = self.0.iter();
284        let mut iter_other = other.0.iter();
285        while let Some(node) = iter_self.next() {
286            match iter_other.next() {
287                None => return false,
288                Some(other_node) => {
289                    if node != other_node {
290                        return false;
291                    }
292                }
293            }
294        }
295        iter_other.next().is_none()
296    }
297}
298
299impl Eq for ElectingHeap {}
300
301impl TermData {
302    fn next_term(&self, node_list: NodeList, seed: Vec<u8>) -> Self {
303        TermData {
304            start_view: self.start_view
305                + POS_STATE_CONFIG.round_per_term(self.start_view),
306            seed,
307            node_list,
308        }
309    }
310}
311
312#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
313#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
314pub struct TermList {
315    /// The current active term.
316    /// After the first `TERM_LIST_LEN` terms, it should be the term of
317    /// `term_list[TERM_LIST_LEN-1]`
318    current_term: u64,
319    /// The maintained term list. It should always have a length `TERM_LIST_LEN
320    /// + 2`. The first `TERM_LIST_LEN` terms are used to validate new
321    /// election transactions, and the last 2 terms are open for election.
322    term_list: Vec<TermData>,
323    candy_rewards: CandyMap,
324    electing_index: usize,
325}
326
327impl TermList {
328    fn start_term(&self) -> u64 {
329        self.current_term.saturating_sub(TERM_LIST_LEN as u64 - 1)
330    }
331
332    fn committee_for_term(&self, term: u64) -> &[TermData] {
333        let first_term = term.saturating_sub(TERM_LIST_LEN as u64 - 1) as usize;
334        let last_term = first_term + TERM_LIST_LEN - 1;
335        if first_term < self.start_term() as usize
336            || last_term >= self.electing_term_number() as usize
337        {
338            panic!(
339                "Can not get committee for term {}, current term {}",
340                term, self.current_term
341            );
342        }
343        let start_offset = first_term - self.start_term() as usize;
344        let end_offset = last_term - self.start_term() as usize;
345        &self.term_list[start_offset..=end_offset]
346    }
347
348    fn get_term_by_number(&self, term_number: u64) -> Option<&TermData> {
349        let start_term = self.start_term();
350        if term_number < start_term {
351            return None;
352        }
353        self.term_list.get((term_number - start_term) as usize)
354    }
355
356    fn electing_term_number(&self) -> u64 {
357        self.start_term() + self.electing_index as u64
358    }
359
360    fn electing_term_mut(&mut self) -> &mut TermData {
361        &mut self.term_list[self.electing_index]
362    }
363
364    fn electing_term(&self) -> &TermData {
365        &self.term_list[self.electing_index]
366    }
367
368    pub fn term_list(&self) -> &Vec<TermData> { &self.term_list }
369}
370
371impl TermList {
372    /// Add a new node to term list after a valid Election transaction has been
373    /// executed.
374    pub fn new_node_elected(
375        &mut self, event: &ElectionEvent, voting_power: u64,
376    ) -> anyhow::Result<()> {
377        if event.start_term != self.electing_term_number() {
378            bail!("term is not open for election, opening term {}, election term {}", self.electing_term_number(),event.start_term);
379        }
380        let term = self.electing_term_mut();
381
382        if term.node_list.has_elected(&event.node_id.addr) {
383            diem_warn!(
384                "The author {} has participated election for term {}",
385                event.node_id.addr,
386                event.start_term
387            );
388            return Ok(());
389        }
390
391        for nonce in 0..voting_power {
392            // Hash after appending the nonce to get multiple identifier for
393            // election.
394            let priority = vrf_number_with_nonce(&event.vrf_output, nonce);
395            term.node_list.add_node(
396                priority,
397                ElectionNodeID::new(event.node_id.clone(), nonce),
398            );
399        }
400        Ok(())
401    }
402
403    pub fn new_term(&mut self, new_term: u64, new_seed: Vec<u8>) {
404        diem_debug!(
405            "new_term={}, start_view:{:?}",
406            new_term,
407            self.term_list
408                .iter()
409                .map(|t| (t.start_view, t.node_list.len()))
410                .collect::<Vec<_>>()
411        );
412        self.current_term = new_term;
413        if new_term < TERM_LIST_LEN as u64 {
414            // The initial terms are not open for election.
415            return;
416        }
417        // This double-check should always pass.
418        debug_assert!(
419            Some(self.term_list[TERM_LIST_LEN].start_view)
420                == POS_STATE_CONFIG.get_starting_view_for_term(new_term)
421        );
422        self.term_list.remove(0);
423        let new_term = self
424            .term_list
425            .last()
426            .unwrap()
427            .next_term(Default::default(), new_seed);
428        self.term_list.push(new_term);
429        self.electing_index -= 1;
430        assert_eq!(self.electing_index, 6);
431    }
432
433    pub fn finalize_election(&mut self) {
434        diem_debug!(
435            "Finalize election of term {}",
436            self.electing_term_number()
437        );
438        let finalize_term = self.electing_term_mut();
439        let candy_map = finalize_term.node_list.finalize_elect();
440        self.candy_rewards = candy_map;
441        self.electing_index += 1;
442        assert_eq!(self.electing_index, 7);
443    }
444
445    fn serving_votes(
446        &self, target_term_offset: usize, author: &AccountAddress,
447    ) -> u64 {
448        assert!(target_term_offset < TERM_LIST_LEN + 2);
449        // TODO(lpl): Optimize by adding hash set to each term or adding another
450        // field to node_map.
451        let start_term_offset =
452            target_term_offset as usize - (TERM_LIST_LEN - 1);
453
454        // The checking of `target_view` ensures that this is in range of
455        // `term_list`.
456        // For any valid `target_term_offset`, always checks to the end of
457        // `term_list` because it's within the service time of
458        // `target_term`.
459        let mut serving_votes = Vec::with_capacity(TERM_LIST_LEN);
460        for i in start_term_offset..target_term_offset {
461            let term = &self.term_list[i as usize];
462            serving_votes.push(term.node_list.serving_votes(author));
463        }
464        return serving_votes.iter().sum();
465    }
466}
467
468#[derive(Clone, Serialize, Eq, PartialEq, Deserialize)]
469#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
470pub struct PosState {
471    /// All the nodes that have staked in PoW.
472    /// Nodes are only inserted and will never be removed.
473    node_map: HashMap<AccountAddress, NodeData>,
474    /// `current_view / TERM_LIST_LEN == term_list.current_term` is always
475    /// true. This is not the same as `RoundState.current_view` because the
476    /// view does not increase for blocks following a pending
477    /// reconfiguration block.
478    current_view: Round,
479    /// Current epoch state
480    epoch_state: EpochState,
481    term_list: TermList,
482
483    /// Track the nodes that have retired and are waiting to be unlocked.
484    /// Nodes that are enqueued early will also become unlocked early.
485    retiring_nodes: VecDeque<AccountAddress>,
486    /// Current pivot decision.
487    pivot_decision: PivotBlockDecision,
488
489    node_map_hint: HashMap<View, HashSet<AccountAddress>>,
490    unlock_event_hint: HashSet<AccountAddress>,
491
492    /// If `skipped` is `true`, this PosState belongs to a block following a
493    /// reconfiguration block, so this block is not executed and the
494    /// PosState is the same as its parent. These skipped blocks have the
495    /// same view as their parents and should not be saved as `CommittedBlock`.
496    skipped: bool,
497}
498
499impl Debug for PosState {
500    fn fmt(
501        &self, f: &mut Formatter<'_>,
502    ) -> std::result::Result<(), std::fmt::Error> {
503        f.debug_struct("PosState")
504            .field("view", &self.current_view)
505            .field("node_map_size", &self.node_map.len())
506            .field("term_list", &self.term_list)
507            .field("epoch_state", &self.epoch_state)
508            .finish()
509    }
510}
511
512impl PosState {
513    pub fn new(
514        initial_seed: Vec<u8>, initial_nodes: Vec<(NodeID, u64)>,
515        initial_committee: Vec<(AccountAddress, u64)>,
516        genesis_pivot_decision: PivotBlockDecision,
517    ) -> Self {
518        let mut node_map = HashMap::new();
519        let mut node_list = BTreeMap::default();
520        for (node_id, total_voting_power) in initial_nodes {
521            let mut lock_status = NodeLockStatus::default();
522            // The genesis block should not have updates for lock status.
523            lock_status.new_lock(0, total_voting_power, true, &mut Vec::new());
524            node_map.insert(
525                node_id.addr.clone(),
526                NodeData {
527                    public_key: node_id.public_key.clone(),
528                    vrf_public_key: Some(node_id.vrf_public_key.clone()),
529                    lock_status,
530                },
531            );
532        }
533        for (addr, voting_power) in initial_committee {
534            // VRF output of initial terms will not be used, because these terms
535            // are not open for election.
536            node_list.insert(addr, voting_power);
537        }
538        let mut term_list = Vec::new();
539        let initial_term = TermData {
540            start_view: 0,
541            seed: initial_seed.clone(),
542            node_list: NodeList::Elected(ElectedMap(node_list.clone())),
543        };
544        term_list.push(initial_term);
545        // TODO(lpl): The initial terms can have different node list.
546        // Duplicate the initial term for the first TERM_LIST_LEN + 2 terms.
547        for i in 0..(TERM_LIST_LEN + 1) {
548            let last_term = term_list.last().unwrap();
549            let mut next_term =
550                last_term.next_term(Default::default(), initial_seed.clone());
551            if i < TERM_LIST_LEN - 1 {
552                let _ = next_term.node_list.finalize_elect();
553            }
554            term_list.push(next_term);
555        }
556        let mut pos_state = PosState {
557            node_map,
558            current_view: 0,
559            epoch_state: EpochState::empty(),
560            term_list: TermList {
561                current_term: 0,
562                term_list,
563                electing_index: TERM_LIST_LEN,
564                candy_rewards: ElectedMap(node_list),
565            },
566            retiring_nodes: Default::default(),
567            pivot_decision: genesis_pivot_decision,
568            node_map_hint: Default::default(),
569            unlock_event_hint: Default::default(),
570            skipped: false,
571        };
572        let (verifier, vrf_seed) = pos_state.get_committee_at(0).unwrap();
573        pos_state.epoch_state = EpochState::new(0, verifier, vrf_seed);
574        pos_state
575    }
576
577    pub fn new_empty() -> Self {
578        Self {
579            node_map: Default::default(),
580            current_view: 0,
581            epoch_state: EpochState::empty(),
582            term_list: TermList {
583                current_term: 0,
584                term_list: Default::default(),
585                electing_index: 0,
586                candy_rewards: Default::default(),
587            },
588            retiring_nodes: Default::default(),
589            node_map_hint: Default::default(),
590            unlock_event_hint: Default::default(),
591            pivot_decision: PivotBlockDecision {
592                block_hash: Default::default(),
593                height: 0,
594            },
595            skipped: false,
596        }
597    }
598
599    pub fn set_skipped(&mut self, skipped: bool) { self.skipped = skipped; }
600
601    pub fn set_pivot_decision(&mut self, pivot_decision: PivotBlockDecision) {
602        self.pivot_decision = pivot_decision;
603    }
604
605    pub fn pivot_decision(&self) -> &PivotBlockDecision { &self.pivot_decision }
606
607    // pub fn current_term_seed(&self) -> &Vec<u8> {
608    //     self.target_term_seed(self.term_list.current_term)
609    // }
610
611    pub fn target_term_seed(&self, target_term: u64) -> &Vec<u8> {
612        &self
613            .term_list
614            .get_term_by_number(target_term)
615            .expect("term not in term list")
616            .seed
617    }
618
619    pub fn epoch_state(&self) -> &EpochState { &self.epoch_state }
620
621    pub fn term_list(&self) -> &TermList { &self.term_list }
622
623    pub fn account_node_data(
624        &self, account_address: AccountAddress,
625    ) -> Option<&NodeData> {
626        self.node_map.get(&account_address)
627    }
628}
629
630/// Read-only functions use in `TransactionValidator`
631impl PosState {
632    pub fn validate_election_simple(
633        &self, election_tx: &ElectionPayload,
634    ) -> Option<DiscardedVMStatus> {
635        let node_id = NodeID::new(
636            election_tx.public_key.clone(),
637            election_tx.vrf_public_key.clone(),
638        );
639        diem_trace!(
640            "validate_election_simple: {:?} {}",
641            node_id.addr,
642            election_tx.target_term
643        );
644        let node = match self.node_map.get(&node_id.addr) {
645            Some(node) => node,
646            None => {
647                return Some(DiscardedVMStatus::ELECTION_NON_EXISITENT_NODE);
648            }
649        };
650
651        let target_view = match POS_STATE_CONFIG
652            .get_starting_view_for_term(election_tx.target_term)
653        {
654            None => {
655                return Some(DiscardedVMStatus::ELECTION_TERGET_TERM_NOT_OPEN)
656            }
657            Some(v) => v,
658        };
659
660        if node.lock_status.available_votes() == 0 {
661            return Some(DiscardedVMStatus::ELECTION_WITHOUT_VOTES);
662        }
663        // Do not check `ELECTION_TERM_END_ROUND` because we are using the
664        // committed state in this simple validation.
665        if target_view
666            <= self.current_view
667                + POS_STATE_CONFIG.election_term_end_round(self.current_view)
668        {
669            return Some(DiscardedVMStatus::ELECTION_TERGET_TERM_NOT_OPEN);
670        }
671        None
672    }
673
674    pub fn validate_pivot_decision_simple(
675        &self, pivot_decision_tx: &PivotBlockDecision,
676    ) -> Option<DiscardedVMStatus> {
677        if pivot_decision_tx.height <= self.pivot_decision.height {
678            return Some(DiscardedVMStatus::PIVOT_DECISION_HEIGHT_TOO_OLD);
679        }
680        None
681    }
682}
683
684/// Read-only functions used in `execute_block`
685impl PosState {
686    pub fn validate_election(
687        &self, election_tx: &ElectionPayload,
688    ) -> Result<()> {
689        let node_id = NodeID::new(
690            election_tx.public_key.clone(),
691            election_tx.vrf_public_key.clone(),
692        );
693        diem_trace!(
694            "validate_election: {:?} {}",
695            node_id.addr,
696            election_tx.target_term
697        );
698        let node = match self.node_map.get(&node_id.addr) {
699            Some(node) => node,
700            None => return Err(anyhow!("Election for non-existent node.")),
701        };
702
703        if node.lock_status.available_votes() == 0 {
704            bail!("Election without any votes");
705        }
706        let target_view = match POS_STATE_CONFIG
707            .get_starting_view_for_term(election_tx.target_term)
708        {
709            None => {
710                bail!("target view overflows, election_tx={:?}", election_tx)
711            }
712            Some(v) => v,
713        };
714        if target_view
715            > self.current_view
716                + POS_STATE_CONFIG.election_term_start_round(self.current_view)
717            || target_view
718                <= self.current_view
719                    + POS_STATE_CONFIG
720                        .election_term_end_round(self.current_view)
721        {
722            bail!(
723                "Target term is not open for election: target={} current={}",
724                target_view,
725                self.current_view
726            );
727        }
728
729        let target_term_offset =
730            (election_tx.target_term - self.term_list.start_term()) as usize;
731        assert_eq!(target_term_offset, self.term_list.electing_index);
732
733        let target_term = &self.term_list.electing_term();
734        if election_tx
735            .vrf_proof
736            .verify(&target_term.seed, node.vrf_public_key.as_ref().unwrap())
737            .is_err()
738        {
739            bail!("Invalid VRF proof for election")
740        }
741
742        if target_term.node_list.has_elected(&node_id.addr) {
743            bail!("The sender has elected for this term")
744        }
745
746        if node.lock_status.available_votes()
747            <= self
748                .term_list
749                .serving_votes(target_term_offset, &node_id.addr)
750        {
751            bail!("Election without enough votes");
752        }
753
754        Ok(())
755    }
756
757    pub fn validate_pivot_decision(
758        &self, pivot_decision_tx: &PivotBlockDecision,
759        signature: MultiConsensusSignature,
760    ) -> Result<()> {
761        if pivot_decision_tx.height <= self.pivot_decision.height {
762            return Err(anyhow!(format!(
763                "Pivot Decision height too small, found[{}], expect[{}]",
764                pivot_decision_tx.height, self.pivot_decision.height
765            )));
766        }
767        let senders = self
768            .epoch_state
769            .verifier()
770            .address_to_validator_info()
771            .keys();
772        let public_keys: Vec<ConsensusPublicKey> = senders
773            .map(|sender| {
774                self.epoch_state.verifier().get_public_key(sender).unwrap()
775            })
776            .collect();
777        let public_key = MultiConsensusPublicKey::new(public_keys);
778        if let Err(e) = signature.verify(pivot_decision_tx, &public_key) {
779            return Err(anyhow!(format!(
780                "Pivot Decision verification failed [{:?}]",
781                e
782            )));
783        }
784        // TODO(linxi): check voting power
785        Ok(())
786    }
787
788    pub fn validate_dispute(
789        &self, dispute_payload: &DisputePayload,
790    ) -> Result<()> {
791        if let Some(node_status) = self.node_map.get(&dispute_payload.address) {
792            if node_status.lock_status.exempt_from_forfeit().is_none() {
793                Ok(())
794            } else {
795                bail!(
796                    "Dispute a forfeited node: {:?}",
797                    dispute_payload.address
798                );
799            }
800        } else {
801            bail!("Unknown dispute node: {:?}", dispute_payload.address);
802        }
803    }
804
805    /// Return `(validator_set, term_seed)`.
806    pub fn get_committee_at(
807        &self, term: u64,
808    ) -> Result<(ValidatorVerifier, Vec<u8>)> {
809        diem_debug!(
810            "Get committee at term {} in view {}, term list start at {}",
811            term,
812            self.current_view,
813            self.term_list.start_term()
814        );
815        let mut voting_power_map = BTreeMap::new();
816        for term_data in self.term_list.committee_for_term(term) {
817            for (addr, votes) in term_data.node_list.committee().0.iter() {
818                *voting_power_map.entry(addr.clone()).or_insert(0 as u64) +=
819                    votes;
820            }
821        }
822        let mut address_to_validator_info = BTreeMap::new();
823        for (addr, voting_power) in voting_power_map {
824            let node_data = self.node_map.get(&addr).expect("node in node_map");
825            // Retired nodes are not removed from term_list,
826            // but we do not include them in the new committee.
827            let voting_power = std::cmp::min(
828                voting_power,
829                node_data.lock_status.available_votes(),
830            );
831            if voting_power > 0 {
832                address_to_validator_info.insert(
833                    addr,
834                    ValidatorConsensusInfo::new(
835                        node_data.public_key.clone(),
836                        node_data.vrf_public_key.clone(),
837                        voting_power,
838                    ),
839                );
840            }
841        }
842
843        Ok((
844            ValidatorVerifier::new(address_to_validator_info),
845            self.term_list.term_list[0].seed.clone(),
846        ))
847    }
848
849    /// TODO(lpl): Return VDF seed for the term.
850    /// Return `Some(target_term)` if `author` should send its election
851    /// transaction.
852    pub fn next_elect_term(&self, author: &AccountAddress) -> Option<u64> {
853        if self.current_view
854            < POS_STATE_CONFIG.first_start_election_view() as u64
855        {
856            return None;
857        }
858
859        if self.term_list.electing_term().node_list.has_elected(author) {
860            return None;
861        }
862
863        if let Some(node) = self.node_map.get(author) {
864            let available_votes = node.lock_status.available_votes();
865            let serving_votes = self
866                .term_list
867                .serving_votes(self.term_list.electing_index, author);
868
869            return if available_votes > serving_votes {
870                Some(self.term_list.electing_term_number())
871            } else {
872                None
873            };
874        }
875
876        None
877    }
878
879    pub fn final_serving_view(&self, author: &AccountAddress) -> Option<Round> {
880        let mut final_elected_term = None;
881        for term in self.term_list.term_list.iter().rev() {
882            match &term.node_list {
883                NodeList::Electing(heap) => {
884                    if heap.1.contains(author) {
885                        final_elected_term = Some(term.get_term());
886                        break;
887                    }
888                }
889                NodeList::Elected(map) => {
890                    if map.0.contains_key(author) {
891                        final_elected_term = Some(term.get_term());
892                        break;
893                    }
894                }
895            }
896        }
897        final_elected_term.map(|t| {
898            POS_STATE_CONFIG
899                .get_starting_view_for_term(t + TERM_LIST_LEN as u64)
900                .expect("checked term")
901                + 1
902        })
903    }
904
905    pub fn get_unlock_events(&self) -> Vec<ContractEvent> {
906        let mut unlocked_nodes = Vec::new();
907        for addr in &self.unlock_event_hint {
908            let node = self.node_map.get(&addr).expect("exists");
909            let unlock_event = ContractEvent::new(
910                UnlockEvent::event_key(),
911                bcs::to_bytes(&UnlockEvent {
912                    node_id: *addr,
913                    unlocked: node.lock_status.unlocked_votes(),
914                })
915                .unwrap(),
916            );
917            unlocked_nodes.push(unlock_event);
918        }
919
920        return unlocked_nodes;
921    }
922
923    pub fn current_view(&self) -> u64 { self.current_view }
924
925    pub fn skipped(&self) -> bool { self.skipped }
926
927    pub fn next_evicted_term(&mut self) -> BTreeMap<H256, u64> {
928        let candy_rewards = std::mem::take(&mut self.term_list.candy_rewards);
929        candy_rewards
930            .0
931            .iter()
932            .map(|(id, cnt)| (H256::from(id.to_u8()), *cnt))
933            .collect()
934    }
935}
936
937/// Write functions used apply changes (process events in PoS and PoW)
938impl PosState {
939    pub fn register_node(&mut self, node_id: NodeID) -> Result<()> {
940        diem_trace!("register_node: {:?}", node_id);
941        ensure!(
942            !self.node_map.contains_key(&node_id.addr),
943            "register an already registered address"
944        );
945        self.node_map.insert(
946            node_id.addr,
947            NodeData {
948                public_key: node_id.public_key,
949                vrf_public_key: Some(node_id.vrf_public_key),
950                lock_status: NodeLockStatus::default(),
951            },
952        );
953        Ok(())
954    }
955
956    pub fn update_voting_power(
957        &mut self, addr: &AccountAddress, increased_voting_power: u64,
958    ) -> Result<()> {
959        diem_trace!(
960            "update_voting_power: {:?} {}",
961            addr,
962            increased_voting_power
963        );
964        let mut update_views = Vec::new();
965        match self.node_map.get_mut(addr) {
966            Some(node_status) => node_status.lock_status.new_lock(
967                self.current_view,
968                increased_voting_power,
969                false,
970                &mut update_views,
971            ),
972            None => bail!("increase voting power of a non-existent node!"),
973        };
974        self.record_update_views(addr, update_views);
975        Ok(())
976    }
977
978    pub fn new_node_elected(&mut self, event: &ElectionEvent) -> Result<()> {
979        diem_debug!(
980            "new_node_elected: {:?} {:?}",
981            event.node_id,
982            event.start_term
983        );
984        let author = &event.node_id.addr;
985        let available_votes = self
986            .node_map
987            .get(author)
988            .expect("checked in execution")
989            .lock_status
990            .available_votes();
991        let target_term_offset =
992            (event.start_term - self.term_list.start_term()) as usize;
993        let serving_votes =
994            self.term_list.serving_votes(target_term_offset, author);
995        let voting_power = available_votes.saturating_sub(serving_votes);
996        if voting_power > 0 {
997            // A workaround for too much staked CFX in Testnet.
998            let bounded_power = std::cmp::min(
999                voting_power,
1000                POS_STATE_CONFIG.max_nonce_per_account(self.current_view()),
1001            );
1002            self.term_list.new_node_elected(event, bounded_power)?;
1003        } else {
1004            diem_warn!("No votes can be elected: {:?} {:?}. available: {}, serving: {}.", event.node_id,
1005            event.start_term,available_votes,serving_votes);
1006        }
1007        Ok(())
1008    }
1009
1010    /// `get_new_committee` has been called before this to produce an
1011    /// EpochState. And `next_view` will not be called for blocks following
1012    /// a pending reconfiguration block.
1013    pub fn next_view(&mut self) -> Result<Option<EpochState>> {
1014        // Increase view after updating node status above to get a correct
1015        // `status_start_view`.
1016        self.current_view += 1;
1017
1018        diem_debug!("current view {}", self.current_view);
1019
1020        // Update the status for the all.
1021        self.unlock_event_hint.clear();
1022
1023        if let Some(addresses) = self.node_map_hint.remove(&self.current_view) {
1024            for address in addresses {
1025                let node = self.node_map.get_mut(&address).expect("exists");
1026                let new_votes_unlocked =
1027                    node.lock_status.update(self.current_view);
1028                if new_votes_unlocked {
1029                    self.unlock_event_hint.insert(address);
1030                }
1031            }
1032        }
1033
1034        let epoch_state = if self.current_view == 1 {
1035            let (verifier, term_seed) = self.get_committee_at(0)?;
1036            // genesis
1037            Some(EpochState::new(1, verifier, term_seed.clone()))
1038        } else {
1039            let (term, view_in_term) =
1040                POS_STATE_CONFIG.get_term_view(self.current_view);
1041            if view_in_term == 0 {
1042                let new_term = term;
1043                let (verifier, term_seed) = self.get_committee_at(new_term)?;
1044                // generate new epoch for new term.
1045                self.term_list.new_term(
1046                    new_term,
1047                    self.pivot_decision.block_hash.as_bytes().to_vec(),
1048                );
1049                // TODO(lpl): If we allow epoch changes within a term, this
1050                // should be updated.
1051                Some(EpochState::new(new_term + 1, verifier, term_seed.clone()))
1052            } else if self.current_view
1053                >= POS_STATE_CONFIG.first_end_election_view()
1054                && view_in_term
1055                    == POS_STATE_CONFIG.round_per_term(self.current_view) / 2
1056            {
1057                self.term_list.finalize_election();
1058                None
1059            } else {
1060                None
1061            }
1062        };
1063        if let Some(epoch_state) = &epoch_state {
1064            self.epoch_state = epoch_state.clone();
1065        }
1066        Ok(epoch_state)
1067    }
1068
1069    pub fn retire_node(
1070        &mut self, addr: &AccountAddress, votes: u64,
1071    ) -> Result<()> {
1072        diem_trace!("retire_node: {:?} {}", addr, votes);
1073        let mut update_views = Vec::new();
1074        match self.node_map.get_mut(&addr) {
1075            Some(node) => {
1076                node.lock_status.new_unlock(
1077                    self.current_view,
1078                    votes,
1079                    &mut update_views,
1080                );
1081            }
1082            None => bail!("Retiring node does not exist"),
1083        };
1084        self.record_update_views(addr, update_views);
1085        Ok(())
1086    }
1087
1088    pub fn force_retire_node(&mut self, addr: &AccountAddress) -> Result<()> {
1089        diem_trace!("force_retire_node: {:?}", addr);
1090        let mut update_views = Vec::new();
1091        match self.node_map.get_mut(&addr) {
1092            Some(node) => node
1093                .lock_status
1094                .force_retire(self.current_view, &mut update_views),
1095            None => bail!("Force retiring node does not exist"),
1096        };
1097        self.record_update_views(addr, update_views);
1098        Ok(())
1099    }
1100
1101    pub fn forfeit_node(&mut self, addr: &AccountAddress) -> Result<()> {
1102        diem_trace!("forfeit_node: {:?}", addr);
1103        let mut update_views = Vec::new();
1104        match self.node_map.get_mut(&addr) {
1105            Some(node) => node
1106                .lock_status
1107                .forfeit(self.current_view, &mut update_views),
1108            None => bail!("Forfeiting node does not exist"),
1109        }
1110        self.record_update_views(addr, update_views);
1111        Ok(())
1112    }
1113}
1114
1115impl PosState {
1116    pub fn record_update_views(
1117        &mut self, address: &AccountAddress, views: Vec<View>,
1118    ) {
1119        for view in views {
1120            diem_trace!(
1121                "{:?} will update lock status at view {}",
1122                address,
1123                view
1124            );
1125            self.node_map_hint.entry(view).or_default().insert(*address);
1126        }
1127    }
1128}
1129
1130// impl Default for PosState {
1131//     fn default() -> Self {
1132//         Self {
1133//             node_map: Default::default(),
1134//             current_view: 0,
1135//             term_list: TermList {
1136//                 current_term: 0,
1137//                 term_list: Default::default(),
1138//             },
1139//         }
1140//     }
1141// }
1142
1143#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
1144pub struct ElectionEvent {
1145    node_id: NodeID,
1146    vrf_output: HashValue,
1147    start_term: u64,
1148}
1149
1150impl ElectionEvent {
1151    pub fn new(
1152        public_key: ConsensusPublicKey, vrf_public_key: ConsensusVRFPublicKey,
1153        vrf_output: HashValue, start_term: u64,
1154    ) -> Self {
1155        Self {
1156            node_id: NodeID::new(public_key, vrf_public_key),
1157            vrf_output,
1158            start_term,
1159        }
1160    }
1161}
1162
1163impl ElectionEvent {
1164    pub fn event_key() -> EventKey {
1165        EventKey::new_from_address(
1166            &account_config::election_select_address(),
1167            3,
1168        )
1169    }
1170
1171    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
1172        bcs::from_bytes(bytes).map_err(Into::into)
1173    }
1174}
1175
1176#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
1177pub struct RetireEvent {
1178    pub node_id: AccountAddress,
1179    pub votes: u64,
1180}
1181
1182impl RetireEvent {
1183    pub fn new(node_id: AccountAddress, votes: u64) -> Self {
1184        RetireEvent { node_id, votes }
1185    }
1186
1187    pub fn event_key() -> EventKey {
1188        EventKey::new_from_address(&account_config::retire_address(), 4)
1189    }
1190
1191    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
1192        bcs::from_bytes(bytes).map_err(Into::into)
1193    }
1194
1195    pub fn matches_staking_event(
1196        &self, staking_event: &StakingEvent,
1197    ) -> Result<bool> {
1198        match staking_event {
1199            StakingEvent::Retire(addr_h256, _votes) => {
1200                let addr = AccountAddress::from_bytes(addr_h256)?;
1201                Ok(self.node_id == addr)
1202            }
1203            _ => Ok(false),
1204        }
1205    }
1206}
1207
1208#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
1209pub struct RegisterEvent {
1210    pub node_id: NodeID,
1211}
1212
1213impl RegisterEvent {
1214    pub fn new(
1215        public_key: ConsensusPublicKey, vrf_public_key: ConsensusVRFPublicKey,
1216    ) -> Self {
1217        Self {
1218            node_id: NodeID::new(public_key, vrf_public_key),
1219        }
1220    }
1221
1222    pub fn event_key() -> EventKey {
1223        EventKey::new_from_address(&account_config::register_address(), 5)
1224    }
1225
1226    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
1227        bcs::from_bytes(bytes).map_err(Into::into)
1228    }
1229
1230    pub fn matches_staking_event(
1231        &self, staking_event: &StakingEvent,
1232    ) -> Result<bool> {
1233        match staking_event {
1234            StakingEvent::Register(
1235                addr_h256,
1236                bls_pub_key_bytes,
1237                vrf_pub_key_bytes,
1238            ) => {
1239                let addr = AccountAddress::from_bytes(addr_h256)?;
1240                let public_key =
1241                    ConsensusPublicKey::try_from(bls_pub_key_bytes.as_slice())?;
1242                let vrf_public_key = ConsensusVRFPublicKey::try_from(
1243                    vrf_pub_key_bytes.as_slice(),
1244                )?;
1245                let node_id =
1246                    NodeID::new(public_key.clone(), vrf_public_key.clone());
1247                ensure!(
1248                    node_id.addr == addr,
1249                    "register event has unmatching address and keys"
1250                );
1251                Ok(self.node_id == node_id)
1252            }
1253            _ => Ok(false),
1254        }
1255    }
1256}
1257
1258#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
1259pub struct UpdateVotingPowerEvent {
1260    pub node_address: AccountAddress,
1261    pub voting_power: u64,
1262}
1263
1264impl UpdateVotingPowerEvent {
1265    pub fn new(node_address: AccountAddress, voting_power: u64) -> Self {
1266        Self {
1267            node_address,
1268            voting_power,
1269        }
1270    }
1271
1272    pub fn event_key() -> EventKey {
1273        EventKey::new_from_address(
1274            &account_config::update_voting_power_address(),
1275            6,
1276        )
1277    }
1278
1279    pub fn from_bytes(bytes: &[u8]) -> Result<Self> {
1280        bcs::from_bytes(bytes).map_err(Into::into)
1281    }
1282
1283    pub fn matches_staking_event(
1284        &self, staking_event: &StakingEvent,
1285    ) -> Result<bool> {
1286        match staking_event {
1287            StakingEvent::IncreaseStake(addr_h256, updated_voting_power) => {
1288                let addr = AccountAddress::from_bytes(addr_h256)?;
1289                Ok(self.node_address == addr
1290                    && self.voting_power == *updated_voting_power)
1291            }
1292            _ => Ok(false),
1293        }
1294    }
1295}
1296
1297#[derive(Clone, Debug, Eq, PartialEq, Serialize, Deserialize)]
1298#[cfg_attr(any(test, feature = "fuzzing"), derive(Arbitrary))]
1299pub struct NodeID {
1300    pub public_key: ConsensusPublicKey,
1301    pub vrf_public_key: ConsensusVRFPublicKey,
1302
1303    /// Computed based on other fields.
1304    pub addr: AccountAddress,
1305}
1306
1307impl NodeID {
1308    pub fn new(
1309        public_key: ConsensusPublicKey, vrf_public_key: ConsensusVRFPublicKey,
1310    ) -> Self {
1311        let addr = from_consensus_public_key(&public_key, &vrf_public_key);
1312        Self {
1313            public_key,
1314            vrf_public_key,
1315            addr,
1316        }
1317    }
1318}
1319
1320impl Ord for NodeID {
1321    fn cmp(&self, other: &Self) -> Ordering { self.addr.cmp(&other.addr) }
1322}
1323
1324impl PartialOrd for NodeID {
1325    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1326        Some(self.cmp(other))
1327    }
1328}
1329
1330#[derive(Clone, Serialize, Deserialize)]
1331pub struct UnlockEvent {
1332    /// The node id to unlock.
1333    ///
1334    /// The management contract should unlock the corresponding account.
1335    pub node_id: AccountAddress,
1336    pub unlocked: u64,
1337}
1338
1339impl UnlockEvent {
1340    pub fn event_key() -> EventKey {
1341        EventKey::new_from_address(&account_config::unlock_address(), 5)
1342    }
1343
1344    pub fn from_bytes(bytes: &[u8]) -> anyhow::Result<Self> {
1345        bcs::from_bytes(bytes).map_err(Into::into)
1346    }
1347}
1348
1349#[derive(Clone, Serialize, Deserialize)]
1350pub struct DisputeEvent {
1351    /// The node id to dispute.
1352    pub node_id: AccountAddress,
1353}
1354
1355impl DisputeEvent {
1356    pub fn event_key() -> EventKey {
1357        EventKey::new_from_address(&account_config::dispute_address(), 6)
1358    }
1359
1360    pub fn from_bytes(bytes: &[u8]) -> anyhow::Result<Self> {
1361        bcs::from_bytes(bytes).map_err(Into::into)
1362    }
1363}
diem_types/term_state.rs

diem_types/
term_state.rs
