linera_execution/
committee.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2// Copyright (c) Zefchain Labs, Inc.
3// SPDX-License-Identifier: Apache-2.0
4
5use std::{borrow::Cow, collections::BTreeMap, sync::Arc};
6
7use allocative::Allocative;
8use linera_base::{
9    crypto::{AccountPublicKey, CryptoHash, ValidatorPublicKey},
10    data_types::ArithmeticError,
11};
12use serde::{Deserialize, Serialize};
13
14use crate::policy::ResourceControlPolicy;
15
16/// Public state of a validator.
17#[derive(Eq, PartialEq, Hash, Clone, Debug, Serialize, Deserialize, Allocative)]
18pub struct ValidatorState {
19    /// The network address (in a string format understood by the networking layer).
20    pub network_address: String,
21    /// The voting power.
22    pub votes: u64,
23    /// The public key of the account associated with the validator.
24    pub account_public_key: AccountPublicKey,
25}
26
27/// A set of validators (identified by their public keys) and their voting rights.
28#[derive(Eq, PartialEq, Hash, Clone, Debug, Default, Allocative)]
29#[cfg_attr(with_graphql, derive(async_graphql::InputObject))]
30pub struct Committee {
31    /// The validators in the committee.
32    pub validators: BTreeMap<ValidatorPublicKey, ValidatorState>,
33    /// The sum of all voting rights.
34    total_votes: u64,
35    /// The threshold to form a quorum.
36    quorum_threshold: u64,
37    /// The threshold to prove the validity of a statement. I.e. the assumption is that strictly
38    /// less than `validity_threshold` are faulty.
39    validity_threshold: u64,
40    /// The policy agreed on for this epoch.
41    policy: ResourceControlPolicy,
42}
43
44impl Serialize for Committee {
45    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
46    where
47        S: serde::ser::Serializer,
48    {
49        if serializer.is_human_readable() {
50            CommitteeFull::from(self).serialize(serializer)
51        } else {
52            CommitteeMinimal::from(self).serialize(serializer)
53        }
54    }
55}
56
57impl<'de> Deserialize<'de> for Committee {
58    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
59    where
60        D: serde::de::Deserializer<'de>,
61    {
62        if deserializer.is_human_readable() {
63            let committee_full = CommitteeFull::deserialize(deserializer)?;
64            Committee::try_from(committee_full).map_err(serde::de::Error::custom)
65        } else {
66            let committee_minimal = CommitteeMinimal::deserialize(deserializer)?;
67            Committee::try_from(committee_minimal).map_err(serde::de::Error::custom)
68        }
69    }
70}
71
72#[derive(Serialize, Deserialize)]
73#[serde(rename = "Committee")]
74struct CommitteeFull<'a> {
75    validators: Cow<'a, BTreeMap<ValidatorPublicKey, ValidatorState>>,
76    total_votes: u64,
77    quorum_threshold: u64,
78    validity_threshold: u64,
79    policy: Cow<'a, ResourceControlPolicy>,
80}
81
82#[derive(Serialize, Deserialize)]
83#[serde(rename = "Committee")]
84struct CommitteeMinimal<'a> {
85    validators: Cow<'a, BTreeMap<ValidatorPublicKey, ValidatorState>>,
86    policy: Cow<'a, ResourceControlPolicy>,
87}
88
89impl TryFrom<CommitteeFull<'static>> for Committee {
90    type Error = String;
91
92    fn try_from(committee_full: CommitteeFull) -> Result<Committee, Self::Error> {
93        let CommitteeFull {
94            validators,
95            total_votes,
96            quorum_threshold,
97            validity_threshold,
98            policy,
99        } = committee_full;
100        let committee = Committee::new(validators.into_owned(), policy.into_owned())
101            .map_err(|e| e.to_string())?;
102        if total_votes != committee.total_votes {
103            Err(format!(
104                "invalid committee: total_votes is {}; should be {}",
105                total_votes, committee.total_votes,
106            ))
107        } else if quorum_threshold != committee.quorum_threshold {
108            Err(format!(
109                "invalid committee: quorum_threshold is {}; should be {}",
110                quorum_threshold, committee.quorum_threshold,
111            ))
112        } else if validity_threshold != committee.validity_threshold {
113            Err(format!(
114                "invalid committee: validity_threshold is {}; should be {}",
115                validity_threshold, committee.validity_threshold,
116            ))
117        } else {
118            Ok(committee)
119        }
120    }
121}
122
123impl<'a> From<&'a Committee> for CommitteeFull<'a> {
124    fn from(committee: &'a Committee) -> CommitteeFull<'a> {
125        let Committee {
126            validators,
127            total_votes,
128            quorum_threshold,
129            validity_threshold,
130            policy,
131        } = committee;
132        CommitteeFull {
133            validators: Cow::Borrowed(validators),
134            total_votes: *total_votes,
135            quorum_threshold: *quorum_threshold,
136            validity_threshold: *validity_threshold,
137            policy: Cow::Borrowed(policy),
138        }
139    }
140}
141
142impl TryFrom<CommitteeMinimal<'static>> for Committee {
143    type Error = ArithmeticError;
144
145    fn try_from(committee_min: CommitteeMinimal) -> Result<Committee, ArithmeticError> {
146        let CommitteeMinimal { validators, policy } = committee_min;
147        Committee::new(validators.into_owned(), policy.into_owned())
148    }
149}
150
151impl<'a> From<&'a Committee> for CommitteeMinimal<'a> {
152    fn from(committee: &'a Committee) -> CommitteeMinimal<'a> {
153        let Committee {
154            validators,
155            total_votes: _,
156            quorum_threshold: _,
157            validity_threshold: _,
158            policy,
159        } = committee;
160        CommitteeMinimal {
161            validators: Cow::Borrowed(validators),
162            policy: Cow::Borrowed(policy),
163        }
164    }
165}
166
167impl Committee {
168    pub fn new(
169        validators: BTreeMap<ValidatorPublicKey, ValidatorState>,
170        policy: ResourceControlPolicy,
171    ) -> Result<Self, ArithmeticError> {
172        let mut total_votes: u64 = 0;
173        for state in validators.values() {
174            total_votes = total_votes
175                .checked_add(state.votes)
176                .ok_or(ArithmeticError::Overflow)?;
177        }
178        // The validity threshold is f + 1, where f is maximal so that it is less than a third.
179        // So the threshold is N / 3, rounded up.
180        let validity_threshold = total_votes.div_ceil(3);
181        // The quorum threshold is minimal such that any two quorums intersect in at least one
182        // validity threshold.
183        let quorum_threshold = total_votes
184            .checked_add(validity_threshold)
185            .ok_or(ArithmeticError::Overflow)?
186            .div_ceil(2);
187
188        Ok(Committee {
189            validators,
190            total_votes,
191            quorum_threshold,
192            validity_threshold,
193            policy,
194        })
195    }
196
197    #[cfg(with_testing)]
198    pub fn make_simple(keys: Vec<(ValidatorPublicKey, AccountPublicKey)>) -> Self {
199        let map = keys
200            .into_iter()
201            .map(|(validator_key, account_key)| {
202                (
203                    validator_key,
204                    ValidatorState {
205                        network_address: "Tcp:localhost:8080".to_string(),
206                        votes: 100,
207                        account_public_key: account_key,
208                    },
209                )
210            })
211            .collect();
212        Committee::new(map, ResourceControlPolicy::default())
213            .expect("test committee votes should not overflow")
214    }
215
216    pub fn weight(&self, author: &ValidatorPublicKey) -> u64 {
217        match self.validators.get(author) {
218            Some(state) => state.votes,
219            None => 0,
220        }
221    }
222
223    pub fn account_keys_and_weights(&self) -> impl Iterator<Item = (AccountPublicKey, u64)> + '_ {
224        self.validators
225            .values()
226            .map(|validator| (validator.account_public_key, validator.votes))
227    }
228
229    pub fn quorum_threshold(&self) -> u64 {
230        self.quorum_threshold
231    }
232
233    pub fn validity_threshold(&self) -> u64 {
234        self.validity_threshold
235    }
236
237    pub fn validators(&self) -> &BTreeMap<ValidatorPublicKey, ValidatorState> {
238        &self.validators
239    }
240
241    pub fn validator_addresses(&self) -> impl Iterator<Item = (ValidatorPublicKey, &str)> {
242        self.validators
243            .iter()
244            .map(|(name, validator)| (*name, &*validator.network_address))
245    }
246
247    pub fn total_votes(&self) -> u64 {
248        self.total_votes
249    }
250
251    pub fn policy(&self) -> &ResourceControlPolicy {
252        &self.policy
253    }
254
255    /// Returns a mutable reference to this committee's [`ResourceControlPolicy`].
256    pub fn policy_mut(&mut self) -> &mut ResourceControlPolicy {
257        &mut self.policy
258    }
259}
260
261/// Process-global, append-only cache of committees keyed by their blob hash.
262///
263/// Committees are network-global state (created by the admin chain, agreed
264/// on by every validator), so caching them once per process avoids holding a
265/// separate copy in every chain's execution state. The map is populated
266/// lazily by `get_or_load_committee_by_hash` in the storage layer.
267#[derive(Clone, Debug, Default)]
268pub struct SharedCommittees {
269    map: Arc<papaya::HashMap<CryptoHash, Arc<Committee>>>,
270}
271
272impl SharedCommittees {
273    pub fn new() -> Self {
274        Self::default()
275    }
276
277    /// Returns the cached committee for `hash`, if any.
278    pub fn get(&self, hash: CryptoHash) -> Option<Arc<Committee>> {
279        self.map.pin().get(&hash).cloned()
280    }
281
282    /// Inserts `committee` under `hash`. If an entry was already present, the
283    /// existing value wins and is returned (avoiding spurious clones when two
284    /// callers race to populate the same hash).
285    pub fn insert(&self, hash: CryptoHash, committee: Arc<Committee>) -> Arc<Committee> {
286        let pinned = self.map.pin();
287        match pinned.try_insert(hash, committee) {
288            Ok(inserted) => inserted.clone(),
289            Err(e) => e.current.clone(),
290        }
291    }
292}
293
294#[cfg(test)]
295mod tests {
296    use super::*;
297
298    #[test]
299    fn shared_committees_insert_and_get() {
300        let shared = SharedCommittees::new();
301        let hash = CryptoHash::test_hash("c0");
302        assert!(shared.get(hash).is_none());
303        let committee = Arc::new(Committee::default());
304        let inserted = shared.insert(hash, committee.clone());
305        assert!(Arc::ptr_eq(&inserted, &committee));
306        let fetched = shared.get(hash).unwrap();
307        assert!(Arc::ptr_eq(&fetched, &committee));
308    }
309
310    #[test]
311    fn shared_committees_insert_is_first_writer_wins() {
312        let shared = SharedCommittees::new();
313        let hash = CryptoHash::test_hash("c1");
314        let first = Arc::new(Committee::default());
315        let second = Arc::new(Committee::default());
316        let winner = shared.insert(hash, first.clone());
317        assert!(Arc::ptr_eq(&winner, &first));
318        let loser = shared.insert(hash, second.clone());
319        assert!(Arc::ptr_eq(&loser, &first));
320        assert!(!Arc::ptr_eq(&loser, &second));
321    }
322
323    #[test]
324    fn shared_committees_clones_share_storage() {
325        let a = SharedCommittees::new();
326        let b = a.clone();
327        let hash = CryptoHash::test_hash("c2");
328        let committee = Arc::new(Committee::default());
329        a.insert(hash, committee.clone());
330        let fetched = b.get(hash).unwrap();
331        assert!(Arc::ptr_eq(&fetched, &committee));
332    }
333}
linera_execution/committee.rs

linera_execution/
committee.rs
