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 get_all_ledger_infos(&self) -> Vec<LedgerInfoWithSignatures> {
138        self.ledger_info_with_sigs.clone()
139    }
140}
141
142#[cfg(any(test, feature = "fuzzing"))]
143impl Arbitrary for EpochChangeProof {
144    type Parameters = ();
145    type Strategy = BoxedStrategy<Self>;
146
147    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
148        (vec(any::<LedgerInfoWithSignatures>(), 0..10), any::<bool>())
149            .prop_map(|(ledger_infos_with_sigs, more)| {
150                Self::new(ledger_infos_with_sigs, more)
151            })
152            .boxed()
153    }
154}
155
156#[cfg(test)]
157mod tests {
158    use super::*;
159    use crate::{
160        block_info::BlockInfo, epoch_state::EpochState, waypoint::Waypoint,
161    };
162
163    #[test]
164    fn verify_epoch_change_proof() {
165        use crate::{
166            ledger_info::LedgerInfo,
167            validator_verifier::random_validator_verifier,
168        };
169        use diem_crypto::hash::HashValue;
170        use std::collections::BTreeMap;
171
172        let all_epoch: Vec<u64> = (1..=10).collect();
173        let mut valid_ledger_info = vec![];
174        let mut validator_verifier = vec![];
175
176        // We generate end-epoch ledger info for epoch 1 to 10, each signed by
177        // the current validator set and carrying the next epoch info.
178        let (mut current_signers, mut current_verifier) =
179            random_validator_verifier(1, None, true);
180        let mut current_version = 123;
181        for epoch in &all_epoch {
182            validator_verifier.push(current_verifier.clone());
183            let (next_signers, next_verifier) =
184                random_validator_verifier((*epoch + 1) as usize, None, true);
185            let epoch_state =
186                EpochState::new(*epoch + 1, next_verifier.clone(), vec![]);
187            let ledger_info = LedgerInfo::new(
188                BlockInfo::new(
189                    *epoch,
190                    0,
191                    HashValue::zero(),
192                    HashValue::zero(),
193                    current_version,
194                    0,
195                    Some(epoch_state),
196                    None,
197                ),
198                HashValue::zero(),
199            );
200            let signatures = current_signers
201                .iter()
202                .map(|s| (s.author(), s.sign(&ledger_info)))
203                .collect();
204            valid_ledger_info
205                .push(LedgerInfoWithSignatures::new(ledger_info, signatures));
206            current_signers = next_signers;
207            current_verifier = next_verifier;
208            current_version += 1;
209        }
210
211        // Test well-formed proof will succeed
212        let proof_1 = EpochChangeProof::new(
213            valid_ledger_info.clone(),
214            /* more = */ false,
215        );
216        assert!(proof_1
217            .verify(&EpochState::new(
218                all_epoch[0],
219                validator_verifier[0].clone(),
220                vec![]
221            ))
222            .is_ok());
223
224        let proof_2 = EpochChangeProof::new(
225            valid_ledger_info[2..5].to_vec(),
226            /* more = */ false,
227        );
228        assert!(proof_2
229            .verify(&EpochState::new(
230                all_epoch[2],
231                validator_verifier[2].clone(),
232                vec![]
233            ))
234            .is_ok());
235
236        // Test proof with stale prefix will verify
237        assert!(proof_1
238            .verify(&EpochState::new(
239                all_epoch[4],
240                validator_verifier[4].clone(),
241                vec![]
242            ))
243            .is_ok());
244
245        // Test empty proof will fail verification
246        let proof_3 = EpochChangeProof::new(vec![], /* more = */ false);
247        assert!(proof_3
248            .verify(&EpochState::new(
249                all_epoch[0],
250                validator_verifier[0].clone(),
251                vec![]
252            ))
253            .is_err());
254
255        // Test non contiguous proof will fail
256        let mut list = valid_ledger_info[3..5].to_vec();
257        list.extend_from_slice(&valid_ledger_info[8..9]);
258        let proof_4 = EpochChangeProof::new(list, /* more = */ false);
259        assert!(proof_4
260            .verify(&EpochState::new(
261                all_epoch[3],
262                validator_verifier[3].clone(),
263                vec![]
264            ))
265            .is_err());
266
267        // Test non increasing proof will fail
268        let mut list = valid_ledger_info.clone();
269        list.reverse();
270        let proof_5 = EpochChangeProof::new(list, /* more = */ false);
271        assert!(proof_5
272            .verify(&EpochState::new(
273                all_epoch[9],
274                validator_verifier[9].clone(),
275                vec![]
276            ))
277            .is_err());
278
279        // Test proof with invalid signatures will fail
280        let proof_6 = EpochChangeProof::new(
281            vec![LedgerInfoWithSignatures::new(
282                valid_ledger_info[0].ledger_info().clone(),
283                BTreeMap::new(),
284            )],
285            /* more = */ false,
286        );
287        assert!(proof_6
288            .verify(&EpochState::new(
289                all_epoch[0],
290                validator_verifier[0].clone(),
291                vec![]
292            ))
293            .is_err());
294
295        // Test proof with waypoint corresponding to the first epoch change
296        // succeeds.
297        let waypoint_for_1_to_2 =
298            Waypoint::new_epoch_boundary(valid_ledger_info[0].ledger_info())
299                .unwrap();
300        assert!(proof_1.verify(&waypoint_for_1_to_2).is_ok());
301
302        // Test proof with stale prefix will verify with a Waypoint
303        let waypoint_for_5_to_6 =
304            Waypoint::new_epoch_boundary(valid_ledger_info[4].ledger_info())
305                .unwrap();
306        assert!(proof_1.verify(&waypoint_for_5_to_6).is_ok());
307
308        // Waypoint before proof range will fail to verify
309        let waypoint_for_3_to_4 =
310            Waypoint::new_epoch_boundary(valid_ledger_info[2].ledger_info())
311                .unwrap();
312        let proof_7 = EpochChangeProof::new(
313            valid_ledger_info[4..8].to_vec(),
314            /* more */ false,
315        );
316        assert!(proof_7.verify(&waypoint_for_3_to_4).is_err());
317
318        // Waypoint after proof range will fail to verify
319        let proof_8 = EpochChangeProof::new(
320            valid_ledger_info[..1].to_vec(),
321            /* more */ false,
322        );
323        assert!(proof_8.verify(&waypoint_for_3_to_4).is_err());
324    }
325}
diem_types/epoch_change.rs

diem_types/
epoch_change.rs
