diem_types/
epoch_change.rs

1// Copyright (c) The Diem Core Contributors
2// SPDX-License-Identifier: Apache-2.0
3
4// Copyright 2021 Conflux Foundation. All rights reserved.
5// Conflux is free software and distributed under GNU General Public License.
6// See http://www.gnu.org/licenses/
7
8#![forbid(unsafe_code)]
9
10use crate::ledger_info::{LedgerInfo, LedgerInfoWithSignatures};
11use anyhow::{ensure, format_err, Result};
12#[cfg(any(test, feature = "fuzzing"))]
13use proptest::{collection::vec, prelude::*};
14use serde::{Deserialize, Serialize};
15use std::fmt::Debug;
16
17/// The verification of the epoch change proof starts with verifier that is
18/// trusted by the client: could be either a waypoint (upon startup) or a known
19/// epoch info.
20pub trait Verifier: Debug + Send + Sync {
21    /// Verify if the ledger_info is trust worthy.
22    fn verify(&self, ledger_info: &LedgerInfoWithSignatures) -> Result<()>;
23
24    /// Returns true in case the given epoch is larger than the existing
25    /// verifier can support. In this case the EpochChangeProof should be
26    /// verified and the verifier updated.
27    fn epoch_change_verification_required(&self, epoch: u64) -> bool;
28
29    /// Returns true if the given [`LedgerInfo`] is stale and probably in our
30    /// trusted prefix.
31    ///
32    /// For example, if we have a waypoint with version 5, an epoch change
33    /// ledger info with version 3 < 5 is already in our trusted prefix and
34    /// so we can ignore it.
35    ///
36    /// Likewise, if we're in epoch 10 with the corresponding validator set, an
37    /// epoch change ledger info with epoch 6 can be safely ignored.
38    fn is_ledger_info_stale(&self, ledger_info: &LedgerInfo) -> bool;
39}
40
41#[derive(Clone, Debug, Deserialize, Eq, PartialEq, Serialize)]
42/// A vector of LedgerInfo with contiguous increasing epoch numbers to prove a
43/// sequence of epoch changes from the first LedgerInfo's epoch.
44pub struct EpochChangeProof {
45    pub ledger_info_with_sigs: Vec<LedgerInfoWithSignatures>,
46    pub more: bool,
47}
48impl EpochChangeProof {
49    pub fn new(
50        ledger_info_with_sigs: Vec<LedgerInfoWithSignatures>, more: bool,
51    ) -> Self {
52        Self {
53            ledger_info_with_sigs,
54            more,
55        }
56    }
57
58    /// The first/lowest epoch of the proof to indicate which epoch this proof
59    /// is helping with
60    pub fn epoch(&self) -> Result<u64> {
61        self.ledger_info_with_sigs
62            .first()
63            .map(|li| li.ledger_info().epoch())
64            .ok_or_else(|| format_err!("Empty EpochChangeProof"))
65    }
66
67    /// Verify the proof is correctly chained with known epoch and validator
68    /// verifier and return the [`LedgerInfoWithSignatures`] to start target
69    /// epoch.
70    ///
71    /// In case a waypoint is present, it's going to be used for verifying the
72    /// very first epoch change (it's the responsibility of the caller to not
73    /// pass a waypoint in case it's not needed).
74    ///
75    /// We will also skip any stale ledger info's in the [`EpochChangeProof`].
76    pub fn verify(
77        &self, verifier: &dyn Verifier,
78    ) -> Result<&LedgerInfoWithSignatures> {
79        ensure!(
80            !self.ledger_info_with_sigs.is_empty(),
81            "The EpochChangeProof is empty"
82        );
83        ensure!(
84            !verifier.is_ledger_info_stale(
85                self.ledger_info_with_sigs.last().unwrap().ledger_info()
86            ),
87            "The EpochChangeProof is stale as our verifier is already ahead \
88             of the entire EpochChangeProof"
89        );
90        let mut verifier_ref = verifier;
91
92        for ledger_info_with_sigs in self
93            .ledger_info_with_sigs
94            .iter()
95            // Skip any stale ledger infos in the proof prefix. Note that with
96            // the assertion above, we are guaranteed there is at least one
97            // non-stale ledger info in the proof.
98            //
99            // It's useful to skip these stale ledger infos to better allow for
100            // concurrent client requests.
101            //
102            // For example, suppose the following:
103            //
104            // 1. My current trusted state is at epoch 5.
105            // 2. I make two concurrent requests to two validators A and B, who
106            //    live at epochs 9 and 11 respectively.
107            //
108            // If A's response returns first, I will ratchet my trusted state
109            // to epoch 9. When B's response returns, I will still be able to
110            // ratchet forward to 11 even though B's EpochChangeProof
111            // includes a bunch of stale ledger infos (for epochs 5, 6, 7, 8).
112            //
113            // Of course, if B's response returns first, we will reject A's
114            // response as it's completely stale.
115            .skip_while(|&ledger_info_with_sigs| {
116                verifier
117                    .is_ledger_info_stale(ledger_info_with_sigs.ledger_info())
118            })
119        {
120            // Try to verify each (epoch -> epoch + 1) jump in the
121            // EpochChangeProof.
122            verifier_ref.verify(ledger_info_with_sigs)?;
123            // While the original verification could've been via waypoints,
124            // all the next epoch changes are verified using the (already
125            // trusted) validator sets.
126            verifier_ref = ledger_info_with_sigs
127                .ledger_info()
128                .next_epoch_state()
129                .ok_or_else(|| {
130                    format_err!("LedgerInfo doesn't carry a ValidatorSet")
131                })?;
132        }
133
134        Ok(self.ledger_info_with_sigs.last().unwrap())
135    }
136
137    pub fn ledger_info_with_sigs(&self) -> &[LedgerInfoWithSignatures] {
138        &self.ledger_info_with_sigs
139    }
140
141    pub fn get_all_ledger_infos(&self) -> Vec<LedgerInfoWithSignatures> {
142        self.ledger_info_with_sigs.clone()
143    }
144}
145
146#[cfg(any(test, feature = "fuzzing"))]
147impl Arbitrary for EpochChangeProof {
148    type Parameters = ();
149    type Strategy = BoxedStrategy<Self>;
150
151    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
152        (vec(any::<LedgerInfoWithSignatures>(), 0..10), any::<bool>())
153            .prop_map(|(ledger_infos_with_sigs, more)| {
154                Self::new(ledger_infos_with_sigs, more)
155            })
156            .boxed()
157    }
158}
159
160#[cfg(test)]
161mod tests {
162    use super::*;
163    use crate::{block_info::BlockInfo, epoch_state::EpochState};
164
165    #[test]
166    fn verify_epoch_change_proof() {
167        use crate::{
168            ledger_info::LedgerInfo,
169            validator_verifier::random_validator_verifier,
170        };
171        use diem_crypto::hash::HashValue;
172        use std::collections::BTreeMap;
173
174        let all_epoch: Vec<u64> = (1..=10).collect();
175        let mut valid_ledger_info = vec![];
176        let mut validator_verifier = vec![];
177
178        // We generate end-epoch ledger info for epoch 1 to 10, each signed by
179        // the current validator set and carrying the next epoch info.
180        let (mut current_signers, mut current_verifier) =
181            random_validator_verifier(1, None, true);
182        let mut current_version = 123;
183        for epoch in &all_epoch {
184            validator_verifier.push(current_verifier.clone());
185            let (next_signers, next_verifier) =
186                random_validator_verifier((*epoch + 1) as usize, None, true);
187            let epoch_state =
188                EpochState::new(*epoch + 1, next_verifier.clone(), vec![]);
189            let ledger_info = LedgerInfo::new(
190                BlockInfo::new(
191                    *epoch,
192                    0,
193                    HashValue::zero(),
194                    HashValue::zero(),
195                    current_version,
196                    0,
197                    Some(epoch_state),
198                    None,
199                ),
200                HashValue::zero(),
201            );
202            let signatures = current_signers
203                .iter()
204                .map(|s| (s.author(), s.sign(&ledger_info)))
205                .collect();
206            valid_ledger_info
207                .push(LedgerInfoWithSignatures::new(ledger_info, signatures));
208            current_signers = next_signers;
209            current_verifier = next_verifier;
210            current_version += 1;
211        }
212
213        // Test well-formed proof will succeed
214        let proof_1 = EpochChangeProof::new(
215            valid_ledger_info.clone(),
216            /* more = */ false,
217        );
218        assert!(proof_1
219            .verify(&EpochState::new(
220                all_epoch[0],
221                validator_verifier[0].clone(),
222                vec![]
223            ))
224            .is_ok());
225
226        let proof_2 = EpochChangeProof::new(
227            valid_ledger_info[2..5].to_vec(),
228            /* more = */ false,
229        );
230        assert!(proof_2
231            .verify(&EpochState::new(
232                all_epoch[2],
233                validator_verifier[2].clone(),
234                vec![]
235            ))
236            .is_ok());
237
238        // Test proof with stale prefix will verify
239        assert!(proof_1
240            .verify(&EpochState::new(
241                all_epoch[4],
242                validator_verifier[4].clone(),
243                vec![]
244            ))
245            .is_ok());
246
247        // Test empty proof will fail verification
248        let proof_3 = EpochChangeProof::new(vec![], /* more = */ false);
249        assert!(proof_3
250            .verify(&EpochState::new(
251                all_epoch[0],
252                validator_verifier[0].clone(),
253                vec![]
254            ))
255            .is_err());
256
257        // Test non contiguous proof will fail
258        let mut list = valid_ledger_info[3..5].to_vec();
259        list.extend_from_slice(&valid_ledger_info[8..9]);
260        let proof_4 = EpochChangeProof::new(list, /* more = */ false);
261        assert!(proof_4
262            .verify(&EpochState::new(
263                all_epoch[3],
264                validator_verifier[3].clone(),
265                vec![]
266            ))
267            .is_err());
268
269        // Test non increasing proof will fail
270        let mut list = valid_ledger_info.clone();
271        list.reverse();
272        let proof_5 = EpochChangeProof::new(list, /* more = */ false);
273        assert!(proof_5
274            .verify(&EpochState::new(
275                all_epoch[9],
276                validator_verifier[9].clone(),
277                vec![]
278            ))
279            .is_err());
280
281        // Test proof with invalid signatures will fail
282        let proof_6 = EpochChangeProof::new(
283            vec![LedgerInfoWithSignatures::new(
284                valid_ledger_info[0].ledger_info().clone(),
285                BTreeMap::new(),
286            )],
287            /* more = */ false,
288        );
289        assert!(proof_6
290            .verify(&EpochState::new(
291                all_epoch[0],
292                validator_verifier[0].clone(),
293                vec![]
294            ))
295            .is_err());
296    }
297}
diem_types/epoch_change.rs

diem_types/
epoch_change.rs
