hotshot_types/simple_certificate/
timeout3.rs

1//! The timeout certificate whose signers each sign the lock they hold.
2
3use std::collections::BTreeMap;
4
5use alloy_primitives::U256;
6use bitvec::prelude::*;
7use committable::{Commitment, Committable};
8use hotshot_utils::anytrace::*;
9use serde::{Deserialize, Serialize};
10
11use super::QuorumCertificate2;
12use crate::{
13    data::{EpochNumber, ViewNumber, serialize_signature2},
14    message::UpgradeLock,
15    simple_vote::{HasEpoch, LockView, TimeoutData3, TimeoutLock, VersionedVoteData},
16    traits::{
17        node_implementation::NodeType,
18        signature_key::{SignatureKey, StakeTableEntryType},
19    },
20    vote::HasViewNumber,
21};
22
23/// A timeout certificate over [`TimeoutData3`].
24///
25/// Every signer signs the lock it held when it timed out, so signers holding
26/// different locks sign different data. Signers holding the same lock form one
27/// group, whose signatures aggregate as in any other certificate. The
28/// certificate's lock is the latest group's, and that group carries the
29/// `Certificate1` that shows the lock exists: a signer cannot claim a lock that
30/// no quorum certified. The lock is read from that certificate, so the two
31/// cannot disagree.
32#[derive(Serialize, Deserialize, Eq, Hash, PartialEq, Debug, Clone)]
33#[serde(bound(deserialize = ""))]
34pub struct TimeoutCertificate3<T: NodeType> {
35    /// The view that timed out.
36    pub view_number: ViewNumber,
37    /// The epoch every signer named.
38    pub epoch: EpochNumber,
39    /// The signers holding the certificate's lock, the latest any signer holds.
40    pub latest: LatestTimeoutSignatures<T>,
41    /// The signers holding earlier locks, one aggregate per lock, earliest first.
42    pub earlier: Vec<TimeoutSignatures<T>>,
43}
44
45/// The signers of a [`TimeoutCertificate3`] that hold its lock.
46#[derive(Serialize, Deserialize, Eq, Hash, PartialEq, Debug, Clone)]
47#[serde(bound(deserialize = ""))]
48pub struct LatestTimeoutSignatures<T: NodeType> {
49    /// The certificate of their lock; `None` if they are locked on nothing
50    /// but genesis.
51    ///
52    /// Its signatures are verified only if the lock is recent
53    /// ([`TimeoutLock::Recent`]). Otherwise only its [`LockView`] is bound, by
54    /// the latest group's signatures, and the rest of it is whatever the
55    /// sender put there.
56    pub lock_cert: Option<QuorumCertificate2<T>>,
57    /// Their aggregate signature and signer bit vector.
58    pub signatures: <T::SignatureKey as SignatureKey>::QcType,
59}
60
61/// The signers of a [`TimeoutCertificate3`] that hold the same lock, earlier
62/// than the certificate's.
63#[derive(Serialize, Deserialize, Eq, Hash, PartialEq, Debug, Clone)]
64#[serde(bound(deserialize = ""))]
65pub struct TimeoutSignatures<T: NodeType> {
66    /// The lock every signer of this group signed.
67    pub lock: Option<LockView>,
68    /// Their aggregate signature and signer bit vector.
69    pub signatures: <T::SignatureKey as SignatureKey>::QcType,
70}
71
72impl<T: NodeType> TimeoutCertificate3<T> {
73    /// Aggregate signed timeout votes into a certificate.
74    ///
75    /// `votes` are each signer's lock and signature over
76    /// `TimeoutData3 { view, epoch, lock }`; they are not checked here.
77    /// `lock_cert` must certify the latest of their locks.
78    pub fn assemble(
79        view: ViewNumber,
80        epoch: EpochNumber,
81        stake_table: &[<T::SignatureKey as SignatureKey>::StakeTableEntry],
82        votes: impl IntoIterator<
83            Item = (
84                Option<LockView>,
85                T::SignatureKey,
86                <T::SignatureKey as SignatureKey>::PureAssembledSignatureType,
87            ),
88        >,
89        lock_cert: Option<QuorumCertificate2<T>>,
90    ) -> Result<Self> {
91        let mut by_lock: BTreeMap<Option<LockView>, BTreeMap<usize, _>> = BTreeMap::new();
92        for (lock, key, signature) in votes {
93            let Some(index) = stake_table
94                .iter()
95                .position(|entry| entry.public_key() == key)
96            else {
97                bail!("timeout vote signer {key} is not in the stake table");
98            };
99            by_lock.entry(lock).or_default().insert(index, signature);
100        }
101        let Some((latest_lock, latest)) = by_lock.pop_last() else {
102            bail!("no timeout votes to assemble");
103        };
104        ensure!(
105            lock_cert.as_ref().map(LockView::of) == latest_lock,
106            "the lock certificate does not certify the latest lock of the votes"
107        );
108        let params = T::SignatureKey::public_parameter(stake_table, U256::ZERO);
109        let aggregate = |signers: BTreeMap<usize, _>| {
110            let mut bits = bitvec![0; stake_table.len()];
111            for index in signers.keys() {
112                bits.set(*index, true);
113            }
114            let signatures: Vec<_> = signers.into_values().collect();
115            T::SignatureKey::assemble(&params, &bits, &signatures)
116        };
117        let earlier = by_lock
118            .into_iter()
119            .map(|(lock, signers)| TimeoutSignatures {
120                lock,
121                signatures: aggregate(signers),
122            })
123            .collect();
124        Ok(Self {
125            view_number: view,
126            epoch,
127            latest: LatestTimeoutSignatures {
128                lock_cert,
129                signatures: aggregate(latest),
130            },
131            earlier,
132        })
133    }
134
135    /// The certificate's lock: the latest lock any of its signers signed.
136    pub fn lock(&self) -> Option<LockView> {
137        self.lock_cert().map(LockView::of)
138    }
139
140    /// The certificate of the certificate's lock.
141    ///
142    /// Only its [`LockView`] is verified unless the lock is recent (see
143    /// [`LatestTimeoutSignatures::lock_cert`]).
144    pub fn lock_cert(&self) -> Option<&QuorumCertificate2<T>> {
145        self.latest.lock_cert.as_ref()
146    }
147
148    /// The certificate's lock, by what is checked of it.
149    pub fn timeout_lock(&self) -> TimeoutLock<'_, T> {
150        TimeoutLock::of(self.lock_cert(), self.epoch)
151    }
152
153    /// The data the signers of the group holding `lock` signed.
154    pub fn data(&self, lock: Option<LockView>) -> TimeoutData3 {
155        TimeoutData3 {
156            view: self.view_number,
157            epoch: self.epoch,
158            lock,
159        }
160    }
161
162    /// Every group: its lock and aggregate signature, earliest lock first.
163    fn groups(
164        &self,
165    ) -> impl Iterator<Item = (Option<LockView>, &<T::SignatureKey as SignatureKey>::QcType)> {
166        self.earlier
167            .iter()
168            .map(|group| (group.lock, &group.signatures))
169            .chain([(self.lock(), &self.latest.signatures)])
170    }
171
172    /// Check that the certificate's lock is no later than its view and its
173    /// epoch, as the lock of every honest signer is.
174    ///
175    /// Needs no committee, so a certificate can be checked before the lock's
176    /// epoch is known.
177    pub fn check_lock(&self) -> Result<()> {
178        let Some(lock) = self.lock() else {
179            return Ok(());
180        };
181        ensure!(
182            lock.view <= self.view_number,
183            "timeout certificate lock {lock} is later than its view {}",
184            self.view_number
185        );
186        ensure!(
187            lock.epoch <= self.epoch,
188            "timeout certificate lock {lock} is later than its epoch {}",
189            self.epoch
190        );
191        Ok(())
192    }
193
194    /// Check everything but the lock certificate's own signatures.
195    ///
196    /// The earlier groups must be in lock order with no lock twice, all
197    /// earlier than the certificate's lock, which must pass
198    /// [`Self::check_lock`]. Every group must have a signer, and no signer may
199    /// be in two groups. Each group's signature must be valid over its own
200    /// data, and together the groups must reach `threshold`. That the lock
201    /// certificate is signed by a quorum of its own epoch is
202    /// [`Self::lock_epoch`]'s committee's to check, and is not checked here: a
203    /// certificate is valid only with both.
204    pub fn check_signatures(
205        &self,
206        stake_table: &[<T::SignatureKey as SignatureKey>::StakeTableEntry],
207        threshold: U256,
208        upgrade_lock: &UpgradeLock<T>,
209    ) -> Result<()> {
210        let locks: Vec<_> = self.groups().map(|(lock, _)| lock).collect();
211        ensure!(
212            locks.windows(2).all(|w| w[0] < w[1]),
213            "timeout certificate groups are not in strict lock order"
214        );
215        self.check_lock()?;
216
217        // The signers and their weight first, so that a certificate refused for
218        // them costs no signature check.
219        let mut seen = bitvec![0; stake_table.len()];
220        let mut weight = U256::ZERO;
221        for (_, signatures) in self.groups() {
222            let (_, signers) = T::SignatureKey::sig_proof(signatures);
223            ensure!(
224                signers.len() == stake_table.len(),
225                "signer bit vector does not match the stake table"
226            );
227            ensure!(signers.any(), "a timeout certificate group has no signer");
228            for (index, entry) in stake_table.iter().enumerate() {
229                if signers[index] {
230                    ensure!(
231                        !seen[index],
232                        "a timeout certificate signer is in two groups"
233                    );
234                    seen.set(index, true);
235                    weight += entry.stake();
236                }
237            }
238        }
239        ensure!(
240            weight >= threshold,
241            "timeout certificate weight {weight} is below threshold {threshold}"
242        );
243
244        let params = T::SignatureKey::public_parameter(stake_table, U256::ZERO);
245        for (lock, signatures) in self.groups() {
246            let commit =
247                VersionedVoteData::new(self.data(lock), self.view_number, upgrade_lock)?.commit();
248            T::SignatureKey::check(&params, commit.as_ref(), signatures)
249                .wrap()
250                .context(|e| warn!("timeout certificate signature check failed: {e}"))?;
251        }
252        Ok(())
253    }
254
255    /// The epoch whose committee signed the lock certificate.
256    pub fn lock_epoch(&self) -> Option<EpochNumber> {
257        self.lock().map(|lock| lock.epoch)
258    }
259}
260
261impl<T: NodeType> HasViewNumber for TimeoutCertificate3<T> {
262    fn view_number(&self) -> ViewNumber {
263        self.view_number
264    }
265}
266
267impl<T: NodeType> HasEpoch for TimeoutCertificate3<T> {
268    fn epoch(&self) -> Option<EpochNumber> {
269        Some(self.epoch)
270    }
271}
272
273/// Covers the lock certificate as sent. For a lock that is not checked, two
274/// certificates that differ only in the unverified parts of it both verify and
275/// commit differently, so the commitment does not identify the certificate's
276/// signed content. Nothing keys on it: consensus keys timeout certificates by
277/// view, and a proposal's leaf commitment covers the evidence its leader
278/// signed.
279impl<T: NodeType> Committable for TimeoutCertificate3<T> {
280    fn commit(&self) -> Commitment<Self> {
281        let mut builder = committable::RawCommitmentBuilder::new("Timeout certificate v3")
282            .u64_field("view number", *self.view_number)
283            .u64_field("epoch number", *self.epoch)
284            .u64_field("earlier groups", self.earlier.len() as u64);
285        for (lock, signatures) in self.groups() {
286            builder = builder
287                .field("data", self.data(lock).commit())
288                .var_size_field("signatures", &serialize_signature2::<T>(signatures));
289        }
290        builder
291            .optional("lock certificate", &self.latest.lock_cert)
292            .finalize()
293    }
294}
hotshot_types/simple_certificate/timeout3.rs

hotshot_types/simple_certificate/
timeout3.rs
