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    /// Creates a new committee from the given validators and resource control policy.
169    pub fn new(
170        validators: BTreeMap<ValidatorPublicKey, ValidatorState>,
171        policy: ResourceControlPolicy,
172    ) -> Result<Self, ArithmeticError> {
173        let mut total_votes: u64 = 0;
174        for state in validators.values() {
175            total_votes = total_votes
176                .checked_add(state.votes)
177                .ok_or(ArithmeticError::Overflow)?;
178        }
179        // The validity threshold is f + 1, where f is maximal so that it is less than a third.
180        // So the threshold is N / 3, rounded up.
181        let validity_threshold = total_votes.div_ceil(3);
182        // The quorum threshold is minimal such that any two quorums intersect in at least one
183        // validity threshold.
184        let quorum_threshold = total_votes
185            .checked_add(validity_threshold)
186            .ok_or(ArithmeticError::Overflow)?
187            .div_ceil(2);
188
189        Ok(Committee {
190            validators,
191            total_votes,
192            quorum_threshold,
193            validity_threshold,
194            policy,
195        })
196    }
197
198    /// Creates a simple committee for testing, giving each validator equal voting weight.
199    #[cfg(with_testing)]
200    pub fn make_simple(keys: Vec<(ValidatorPublicKey, AccountPublicKey)>) -> Self {
201        let map = keys
202            .into_iter()
203            .map(|(validator_key, account_key)| {
204                (
205                    validator_key,
206                    ValidatorState {
207                        network_address: "Tcp:localhost:8080".to_string(),
208                        votes: 100,
209                        account_public_key: account_key,
210                    },
211                )
212            })
213            .collect();
214        Committee::new(map, ResourceControlPolicy::default())
215            .expect("test committee votes should not overflow")
216    }
217
218    /// Returns the number of votes held by the given validator, or zero if it is not a member.
219    pub fn weight(&self, author: &ValidatorPublicKey) -> u64 {
220        match self.validators.get(author) {
221            Some(state) => state.votes,
222            None => 0,
223        }
224    }
225
226    /// Returns an iterator over each validator's account public key and its number of votes.
227    pub fn account_keys_and_weights(&self) -> impl Iterator<Item = (AccountPublicKey, u64)> + '_ {
228        self.validators
229            .values()
230            .map(|validator| (validator.account_public_key, validator.votes))
231    }
232
233    /// Returns the number of votes required to reach a quorum.
234    pub fn quorum_threshold(&self) -> u64 {
235        self.quorum_threshold
236    }
237
238    /// Returns the number of votes required to reach the validity threshold.
239    pub fn validity_threshold(&self) -> u64 {
240        self.validity_threshold
241    }
242
243    /// Returns the validators in this committee, keyed by their public key.
244    pub fn validators(&self) -> &BTreeMap<ValidatorPublicKey, ValidatorState> {
245        &self.validators
246    }
247
248    /// Returns an iterator over each validator's public key and network address.
249    pub fn validator_addresses(&self) -> impl Iterator<Item = (ValidatorPublicKey, &str)> {
250        self.validators
251            .iter()
252            .map(|(name, validator)| (*name, &*validator.network_address))
253    }
254
255    /// Returns the total number of votes across all validators.
256    pub fn total_votes(&self) -> u64 {
257        self.total_votes
258    }
259
260    /// Returns the resource control policy of this committee.
261    pub fn policy(&self) -> &ResourceControlPolicy {
262        &self.policy
263    }
264
265    /// Returns a mutable reference to this committee's [`ResourceControlPolicy`].
266    pub fn policy_mut(&mut self) -> &mut ResourceControlPolicy {
267        &mut self.policy
268    }
269}
270
271/// Process-global, append-only cache of committees keyed by their blob hash.
272///
273/// Committees are network-global state (created by the admin chain, agreed
274/// on by every validator), so caching them once per process avoids holding a
275/// separate copy in every chain's execution state. The map is populated
276/// lazily by `get_or_load_committee_by_hash` in the storage layer.
277#[derive(Clone, Debug, Default)]
278pub struct SharedCommittees {
279    map: Arc<papaya::HashMap<CryptoHash, Arc<Committee>>>,
280}
281
282impl SharedCommittees {
283    /// Creates a new, empty committee cache.
284    pub fn new() -> Self {
285        Self::default()
286    }
287
288    /// Returns the cached committee for `hash`, if any.
289    pub fn get(&self, hash: CryptoHash) -> Option<Arc<Committee>> {
290        self.map.pin().get(&hash).cloned()
291    }
292
293    /// Inserts `committee` under `hash`. If an entry was already present, the
294    /// existing value wins and is returned (avoiding spurious clones when two
295    /// callers race to populate the same hash).
296    pub fn insert(&self, hash: CryptoHash, committee: Arc<Committee>) -> Arc<Committee> {
297        let pinned = self.map.pin();
298        match pinned.try_insert(hash, committee) {
299            Ok(inserted) => inserted.clone(),
300            Err(e) => e.current.clone(),
301        }
302    }
303}
304
305#[cfg(test)]
306mod tests {
307    use super::*;
308
309    #[test]
310    fn shared_committees_insert_and_get() {
311        let shared = SharedCommittees::new();
312        let hash = CryptoHash::test_hash("c0");
313        assert!(shared.get(hash).is_none());
314        let committee = Arc::new(Committee::default());
315        let inserted = shared.insert(hash, committee.clone());
316        assert!(Arc::ptr_eq(&inserted, &committee));
317        let fetched = shared.get(hash).unwrap();
318        assert!(Arc::ptr_eq(&fetched, &committee));
319    }
320
321    #[test]
322    fn shared_committees_insert_is_first_writer_wins() {
323        let shared = SharedCommittees::new();
324        let hash = CryptoHash::test_hash("c1");
325        let first = Arc::new(Committee::default());
326        let second = Arc::new(Committee::default());
327        let winner = shared.insert(hash, first.clone());
328        assert!(Arc::ptr_eq(&winner, &first));
329        let loser = shared.insert(hash, second.clone());
330        assert!(Arc::ptr_eq(&loser, &first));
331        assert!(!Arc::ptr_eq(&loser, &second));
332    }
333
334    #[test]
335    fn shared_committees_clones_share_storage() {
336        let a = SharedCommittees::new();
337        let b = a.clone();
338        let hash = CryptoHash::test_hash("c2");
339        let committee = Arc::new(Committee::default());
340        a.insert(hash, committee.clone());
341        let fetched = b.get(hash).unwrap();
342        assert!(Arc::ptr_eq(&fetched, &committee));
343    }
344}
linera_execution/committee.rs

linera_execution/
committee.rs
