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, str::FromStr};
6
7use async_graphql::InputObject;
8use linera_base::{
9    crypto::{CryptoError, PublicKey},
10    data_types::ArithmeticError,
11};
12use serde::{Deserialize, Serialize};
13
14use crate::policy::ResourceControlPolicy;
15
16/// A number identifying the configuration of the chain (aka the committee).
17#[derive(Eq, PartialEq, Ord, PartialOrd, Copy, Clone, Hash, Default, Debug)]
18pub struct Epoch(pub u32);
19
20impl Epoch {
21    pub const ZERO: Epoch = Epoch(0);
22}
23
24impl Serialize for Epoch {
25    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
26    where
27        S: serde::ser::Serializer,
28    {
29        if serializer.is_human_readable() {
30            serializer.serialize_str(&self.0.to_string())
31        } else {
32            serializer.serialize_newtype_struct("Epoch", &self.0)
33        }
34    }
35}
36
37impl<'de> Deserialize<'de> for Epoch {
38    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
39    where
40        D: serde::de::Deserializer<'de>,
41    {
42        if deserializer.is_human_readable() {
43            let s = String::deserialize(deserializer)?;
44            Ok(Epoch(u32::from_str(&s).map_err(serde::de::Error::custom)?))
45        } else {
46            #[derive(Deserialize)]
47            #[serde(rename = "Epoch")]
48            struct EpochDerived(u32);
49
50            let value = EpochDerived::deserialize(deserializer)?;
51            Ok(Self(value.0))
52        }
53    }
54}
55
56/// The identity of a validator.
57#[derive(Eq, PartialEq, Ord, PartialOrd, Copy, Clone, Hash, Debug)]
58pub struct ValidatorName(pub PublicKey);
59
60impl Serialize for ValidatorName {
61    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
62    where
63        S: serde::ser::Serializer,
64    {
65        if serializer.is_human_readable() {
66            serializer.serialize_str(&self.to_string())
67        } else {
68            serializer.serialize_newtype_struct("ValidatorName", &self.0)
69        }
70    }
71}
72
73impl<'de> Deserialize<'de> for ValidatorName {
74    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
75    where
76        D: serde::de::Deserializer<'de>,
77    {
78        if deserializer.is_human_readable() {
79            let s = String::deserialize(deserializer)?;
80            let value = Self::from_str(&s).map_err(serde::de::Error::custom)?;
81            Ok(value)
82        } else {
83            #[derive(Deserialize)]
84            #[serde(rename = "ValidatorName")]
85            struct ValidatorNameDerived(PublicKey);
86
87            let value = ValidatorNameDerived::deserialize(deserializer)?;
88            Ok(Self(value.0))
89        }
90    }
91}
92
93/// Public state of validator.
94#[derive(Eq, PartialEq, Hash, Clone, Debug, Default, Serialize, Deserialize)]
95pub struct ValidatorState {
96    /// The network address (in a string format understood by the networking layer).
97    pub network_address: String,
98    /// The voting power.
99    pub votes: u64,
100}
101
102/// A set of validators (identified by their public keys) and their voting rights.
103#[derive(Eq, PartialEq, Hash, Clone, Debug, Default, InputObject)]
104pub struct Committee {
105    /// The validators in the committee.
106    validators: BTreeMap<ValidatorName, ValidatorState>,
107    /// The sum of all voting rights.
108    total_votes: u64,
109    /// The threshold to form a quorum.
110    quorum_threshold: u64,
111    /// The threshold to prove the validity of a statement.
112    validity_threshold: u64,
113    /// The policy agreed on for this epoch.
114    policy: ResourceControlPolicy,
115}
116
117impl Serialize for Committee {
118    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
119    where
120        S: serde::ser::Serializer,
121    {
122        if serializer.is_human_readable() {
123            CommitteeFull::from(self).serialize(serializer)
124        } else {
125            CommitteeMinimal::from(self).serialize(serializer)
126        }
127    }
128}
129
130impl<'de> Deserialize<'de> for Committee {
131    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
132    where
133        D: serde::de::Deserializer<'de>,
134    {
135        if deserializer.is_human_readable() {
136            let committee_full = CommitteeFull::deserialize(deserializer)?;
137            Committee::try_from(committee_full).map_err(serde::de::Error::custom)
138        } else {
139            let committee_minimal = CommitteeMinimal::deserialize(deserializer)?;
140            Ok(Committee::from(committee_minimal))
141        }
142    }
143}
144
145#[derive(Serialize, Deserialize)]
146#[serde(rename = "Committee")]
147struct CommitteeFull<'a> {
148    validators: Cow<'a, BTreeMap<ValidatorName, ValidatorState>>,
149    total_votes: u64,
150    quorum_threshold: u64,
151    validity_threshold: u64,
152    policy: Cow<'a, ResourceControlPolicy>,
153}
154
155#[derive(Serialize, Deserialize)]
156#[serde(rename = "Committee")]
157struct CommitteeMinimal<'a> {
158    validators: Cow<'a, BTreeMap<ValidatorName, ValidatorState>>,
159    policy: Cow<'a, ResourceControlPolicy>,
160}
161
162impl TryFrom<CommitteeFull<'static>> for Committee {
163    type Error = String;
164
165    fn try_from(committee_full: CommitteeFull) -> Result<Committee, Self::Error> {
166        let CommitteeFull {
167            validators,
168            total_votes,
169            quorum_threshold,
170            validity_threshold,
171            policy,
172        } = committee_full;
173        let committee = Committee::new(validators.into_owned(), policy.into_owned());
174        if total_votes != committee.total_votes {
175            Err(format!(
176                "invalid committee: total_votes is {}; should be {}",
177                total_votes, committee.total_votes,
178            ))
179        } else if quorum_threshold != committee.quorum_threshold {
180            Err(format!(
181                "invalid committee: quorum_threshold is {}; should be {}",
182                quorum_threshold, committee.quorum_threshold,
183            ))
184        } else if validity_threshold != committee.validity_threshold {
185            Err(format!(
186                "invalid committee: validity_threshold is {}; should be {}",
187                validity_threshold, committee.validity_threshold,
188            ))
189        } else {
190            Ok(committee)
191        }
192    }
193}
194
195impl<'a> From<&'a Committee> for CommitteeFull<'a> {
196    fn from(committee: &'a Committee) -> CommitteeFull<'a> {
197        let Committee {
198            validators,
199            total_votes,
200            quorum_threshold,
201            validity_threshold,
202            policy,
203        } = committee;
204        CommitteeFull {
205            validators: Cow::Borrowed(validators),
206            total_votes: *total_votes,
207            quorum_threshold: *quorum_threshold,
208            validity_threshold: *validity_threshold,
209            policy: Cow::Borrowed(policy),
210        }
211    }
212}
213
214impl From<CommitteeMinimal<'static>> for Committee {
215    fn from(committee_min: CommitteeMinimal) -> Committee {
216        let CommitteeMinimal { validators, policy } = committee_min;
217        Committee::new(validators.into_owned(), policy.into_owned())
218    }
219}
220
221impl<'a> From<&'a Committee> for CommitteeMinimal<'a> {
222    fn from(committee: &'a Committee) -> CommitteeMinimal<'a> {
223        let Committee {
224            validators,
225            total_votes: _,
226            quorum_threshold: _,
227            validity_threshold: _,
228            policy,
229        } = committee;
230        CommitteeMinimal {
231            validators: Cow::Borrowed(validators),
232            policy: Cow::Borrowed(policy),
233        }
234    }
235}
236
237impl std::fmt::Display for ValidatorName {
238    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::result::Result<(), std::fmt::Error> {
239        self.0.fmt(f)
240    }
241}
242
243impl std::str::FromStr for ValidatorName {
244    type Err = CryptoError;
245
246    fn from_str(s: &str) -> Result<Self, Self::Err> {
247        Ok(ValidatorName(PublicKey::from_str(s)?))
248    }
249}
250
251impl std::fmt::Display for Epoch {
252    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::result::Result<(), std::fmt::Error> {
253        write!(f, "{}", self.0)
254    }
255}
256
257impl std::str::FromStr for Epoch {
258    type Err = CryptoError;
259
260    fn from_str(s: &str) -> Result<Self, Self::Err> {
261        Ok(Epoch(s.parse()?))
262    }
263}
264
265impl From<u32> for Epoch {
266    fn from(value: u32) -> Self {
267        Epoch(value)
268    }
269}
270
271impl From<PublicKey> for ValidatorName {
272    fn from(value: PublicKey) -> Self {
273        Self(value)
274    }
275}
276
277impl Epoch {
278    #[inline]
279    pub fn try_add_one(self) -> Result<Self, ArithmeticError> {
280        let val = self.0.checked_add(1).ok_or(ArithmeticError::Overflow)?;
281        Ok(Self(val))
282    }
283
284    #[inline]
285    pub fn try_add_assign_one(&mut self) -> Result<(), ArithmeticError> {
286        self.0 = self.0.checked_add(1).ok_or(ArithmeticError::Overflow)?;
287        Ok(())
288    }
289}
290
291impl Committee {
292    pub fn new(
293        validators: BTreeMap<ValidatorName, ValidatorState>,
294        policy: ResourceControlPolicy,
295    ) -> Self {
296        let total_votes = validators.values().fold(0, |sum, state| sum + state.votes);
297        // Let N = 3f + 1 + k such that 0 <= k <= 2. (Notably ⌊k / 3⌋ = 0 and ⌊(2 - k) / 3⌋ = 0.)
298        // The following thresholds verify:
299        // * ⌊2 N / 3⌋ + 1 = ⌊(6f + 2 + 2k) / 3⌋ + 1 = 2f + 1 + k + ⌊(2 - k) / 3⌋ = N - f
300        // * ⌊(N + 2) / 3⌋= ⌊(3f + 3 + k) / 3⌋ = f + 1 + ⌊k / 3⌋ = f + 1
301        let quorum_threshold = 2 * total_votes / 3 + 1;
302        let validity_threshold = (total_votes + 2) / 3;
303
304        Committee {
305            validators,
306            total_votes,
307            quorum_threshold,
308            validity_threshold,
309            policy,
310        }
311    }
312
313    #[cfg(with_testing)]
314    pub fn make_simple(keys: Vec<ValidatorName>) -> Self {
315        let map = keys
316            .into_iter()
317            .map(|k| {
318                (
319                    k,
320                    ValidatorState {
321                        network_address: k.to_string(),
322                        votes: 1,
323                    },
324                )
325            })
326            .collect();
327        Committee::new(map, ResourceControlPolicy::default())
328    }
329
330    pub fn weight(&self, author: &ValidatorName) -> u64 {
331        match self.validators.get(author) {
332            Some(state) => state.votes,
333            None => 0,
334        }
335    }
336
337    pub fn keys_and_weights(&self) -> impl Iterator<Item = (PublicKey, u64)> + '_ {
338        self.validators
339            .iter()
340            .map(|(name, validator)| (name.0, validator.votes))
341    }
342
343    pub fn network_address(&self, author: &ValidatorName) -> Option<&str> {
344        self.validators
345            .get(author)
346            .map(|state| state.network_address.as_ref())
347    }
348
349    pub fn quorum_threshold(&self) -> u64 {
350        self.quorum_threshold
351    }
352
353    pub fn validity_threshold(&self) -> u64 {
354        self.validity_threshold
355    }
356
357    pub fn validators(&self) -> &BTreeMap<ValidatorName, ValidatorState> {
358        &self.validators
359    }
360
361    pub fn validator_addresses(&self) -> impl Iterator<Item = (ValidatorName, &str)> {
362        self.validators
363            .iter()
364            .map(|(name, validator)| (*name, &*validator.network_address))
365    }
366
367    pub fn total_votes(&self) -> u64 {
368        self.total_votes
369    }
370
371    pub fn policy(&self) -> &ResourceControlPolicy {
372        &self.policy
373    }
374}
linera_execution/committee.rs

linera_execution/
committee.rs
