openpgp: Lazily verify self-signatures in certs.

  - In the original implementation of `Cert::canonicalize`, all
    self-signatures were verified.  This has turned out to be very
    expensive.  Instead, we should only verify the signatures we are
    actually interested in.

  - To preserve the semantics, every self signature we hand out from
    the `Cert` API must have been verified first.  However, we can do
    that lazily.  And, when we reason over the cert (i.e. we are
    looking for the right self-signature), we can search the
    signatures without triggering the verification, and only verify
    the one we are really interested in.

7 files changed, 662 insertions, 74 deletions

diff --git a/openpgp/src/cert.rs b/openpgp/src/cert.rs
index 0dbdd896..aeff17c0 100644
--- a/openpgp/src/cert.rs
+++ b/openpgp/src/cert.rs
@@ -189,6 +189,7 @@ use bundle::{
     SubkeyBundles,
     UnknownBundles,
 };
+mod lazysigs;
 mod parser;
 pub mod raw;
 mod revoke;
@@ -1174,7 +1175,12 @@ impl Cert {
     /// ```
     pub fn bad_signatures(&self)
                           -> impl Iterator<Item = &Signature> + Send + Sync {
-        self.bad.iter()
+        self.primary.bad_signatures()
+            .chain(self.userids.iter().flat_map(|u| u.bad_signatures()))
+            .chain(self.user_attributes.iter().flat_map(|u| u.bad_signatures()))
+            .chain(self.subkeys.iter().flat_map(|u| u.bad_signatures()))
+            .chain(self.unknowns.iter().flat_map(|u| u.bad_signatures()))
+            .chain(self.bad.iter())
     }
 
     /// Returns a list of any designated revokers for this certificate.
@@ -1518,33 +1524,57 @@ impl Cert {
         // desc: a description of the component
         // binding: the binding to check
         // sigs: a vector of sigs in $binding to check
-        // verify_method: the method to call on a signature to verify it
-        // verify_args: additional arguments to pass to verify_method
         macro_rules! check {
             ($desc:expr, $binding:expr, $sigs:ident,
-             $verify_method:ident, $($verify_args:expr),*) => ({
+             $hash_method:ident,    // method to hash the signature
+             $sig_type_pat:pat,     // pattern to test signature types against
+             $($hash_args:expr),* // additional arguments to pass to hash_method
+            ) => ({
                 t!("check!({}, {}, {:?}, {}, ...)",
                    $desc, stringify!($binding), $binding.$sigs,
-                   stringify!($verify_method));
-                for sig in mem::take(&mut $binding.$sigs).into_iter() {
-                     match sig.$verify_method(self.primary.key(),
-                                              self.primary.key(),
-                                              $($verify_args),*) {
-                         Ok(()) => $binding.$sigs.push(sig),
-                         Err(err) => {
-                             t!("Sig {:02X}{:02X}, type = {} \
-                                 doesn't belong to {}: {:?}",
-                                sig.digest_prefix()[0], sig.digest_prefix()[1],
-                                sig.typ(), $desc, err);
-
-                             self.bad.push(sig);
-                         }
+                   stringify!($hash_method));
+                for sig in $binding.$sigs.take().into_iter() {
+                    // Use hash prefix as heuristic.
+                    let key = self.primary.key();
+                    match sig.hash_algo().context().and_then(|mut ctx| {
+                        if matches!(sig.typ(), $sig_type_pat) {
+                            sig.$hash_method(&mut ctx, key, $($hash_args),*);
+                            ctx.into_digest()
+                        } else {
+                            Err(Error::UnsupportedSignatureType(sig.typ()).into())
+                        }
+                    }) {
+                      Ok(hash) => {
+                        if &sig.digest_prefix()[..] == &hash[..2] {
+                            sig.set_computed_digest(Some(hash));
+                            $binding.$sigs.push(sig);
+                        } else {
+                            t!("Sig {:02X}{:02X}, type = {} \
+                                doesn't belong to {} (computed hash's prefix: {:02X}{:02X})",
+                               sig.digest_prefix()[0], sig.digest_prefix()[1],
+                               sig.typ(), $desc,
+                               hash[0], hash[1]);
+
+                            self.bad.push(sig);
+                        }
+                      },
+                      Err(e) => {
+                        // Hashing failed, we likely don't support the
+                        // hash algorithm, or the signature type was
+                        // bad.
+                        t!("Sig {:02X}{:02X}, type = {}: \
+                            Hashing failed: {}",
+                           sig.digest_prefix()[0], sig.digest_prefix()[1],
+                           sig.typ(), e);
+
+                        self.bad.push(sig);
+                      },
                     }
                 }
             });
             ($desc:expr, $binding:expr, $sigs:ident,
-             $verify_method:ident) => ({
-                check!($desc, $binding, $sigs, $verify_method,)
+             $hash_method:ident, $sig_type_pat:pat) => ({
+                check!($desc, $binding, $sigs, $hash_method, $sig_type_pat, )
             });
         }
 
@@ -1610,8 +1640,9 @@ impl Cert {
                         }
                       },
                       Err(e) => {
-                        // Hashing failed, we likely don't support
-                        // the hash algorithm.
+                        // Hashing failed, we likely don't support the
+                        // hash algorithm, or the signature type was
+                        // bad.
                         t!("Sig {:02X}{:02X}, type = {}: \
                             Hashing failed: {}",
                            sig.digest_prefix()[0], sig.digest_prefix()[1],
@@ -1636,9 +1667,9 @@ impl Cert {
         }
 
         check!("primary key",
-               self.primary, self_signatures, verify_direct_key);
+               self.primary, self_signatures, hash_direct_key, DirectKey);
         check!("primary key",
-               self.primary, self_revocations, verify_primary_key_revocation);
+               self.primary, self_revocations, hash_direct_key, KeyRevocation);
         check_3rd_party!("primary key",
                          self.primary, certifications, lookup_fn,
                          verify_direct_key, hash_direct_key, DirectKey);
@@ -1650,15 +1681,19 @@ impl Cert {
         for ua in self.userids.iter_mut() {
             check!(format!("userid \"{}\"",
                            String::from_utf8_lossy(ua.userid().value())),
-                   ua, self_signatures, verify_userid_binding,
+                   ua, self_signatures, hash_userid_binding,
+                   GenericCertification | PersonaCertification
+                   | CasualCertification | PositiveCertification,
                    ua.userid());
             check!(format!("userid \"{}\"",
                            String::from_utf8_lossy(ua.userid().value())),
-                   ua, self_revocations, verify_userid_revocation,
+                   ua, self_revocations, hash_userid_binding,
+                   CertificationRevocation,
                    ua.userid());
             check!(format!("userid \"{}\"",
                            String::from_utf8_lossy(ua.userid().value())),
-                   ua, attestations, verify_userid_attestation,
+                   ua, attestations, hash_userid_binding,
+                   AttestationKey,
                    ua.userid());
             check_3rd_party!(
                 format!("userid \"{}\"",
@@ -1679,13 +1714,17 @@ impl Cert {
 
         for binding in self.user_attributes.iter_mut() {
             check!("user attribute",
-                   binding, self_signatures, verify_user_attribute_binding,
+                   binding, self_signatures, hash_user_attribute_binding,
+                   GenericCertification | PersonaCertification
+                   | CasualCertification | PositiveCertification,
                    binding.user_attribute());
             check!("user attribute",
-                   binding, self_revocations, verify_user_attribute_revocation,
+                   binding, self_revocations, hash_user_attribute_binding,
+                   CertificationRevocation,
                    binding.user_attribute());
             check!("user attribute",
-                   binding, attestations, verify_user_attribute_attestation,
+                   binding, attestations, hash_user_attribute_binding,
+                   AttestationKey,
                    binding.user_attribute());
             check_3rd_party!(
                 "user attribute",
@@ -1704,10 +1743,12 @@ impl Cert {
 
         for binding in self.subkeys.iter_mut() {
             check!(format!("subkey {}", binding.key().keyid()),
-                   binding, self_signatures, verify_subkey_binding,
+                   binding, self_signatures, hash_subkey_binding,
+                   SubkeyBinding,
                    binding.key());
             check!(format!("subkey {}", binding.key().keyid()),
-                   binding, self_revocations, verify_subkey_revocation,
+                   binding, self_revocations, hash_subkey_binding,
+                   SubkeyRevocation,
                    binding.key());
             check_3rd_party!(
                 format!("subkey {}", binding.key().keyid()),
@@ -1737,13 +1778,13 @@ impl Cert {
         // remember where we took them from.
         for (i, c) in self.unknowns.iter_mut().enumerate() {
             for sig in
-                std::mem::take(&mut c.self_signatures).into_iter()
+                c.self_signatures.take().into_iter()
                 .chain(
                     std::mem::take(&mut c.certifications).into_iter())
                 .chain(
-                    std::mem::take(&mut c.attestations).into_iter())
+                    c.attestations.take().into_iter())
                 .chain(
-                    std::mem::take(&mut c.self_revocations).into_iter())
+                    c.self_revocations.take().into_iter())
                 .chain(
                     std::mem::take(&mut c.other_revocations).into_iter())
             {
@@ -7035,16 +7076,6 @@ Pu1xwz57O4zo1VYf6TqHJzVC3OMvMUM2hhdecMUe5x6GorNaj6g=
         let cert = Cert::try_from(pp)?;
         assert_eq!(cert.clone().merge_public_and_secret(cert.clone())?, cert);
 
-        // Specifically, the issuer information should have been added
-        // back by the canonicalization.
-        assert_eq!(
-            cert.userids().next().unwrap().self_signatures().next().unwrap()
-                .unhashed_area().subpackets(SubpacketTag::Issuer).count(),
-            1);
-        assert_eq!(
-            cert.keys().subkeys().next().unwrap().self_signatures().next().unwrap()
-                .unhashed_area().subpackets(SubpacketTag::Issuer).count(),
-            1);
         Ok(())
     }
 
diff --git a/openpgp/src/cert/bundle.rs b/openpgp/src/cert/bundle.rs
index 580e60a6..cf843d9f 100644
--- a/openpgp/src/cert/bundle.rs
+++ b/openpgp/src/cert/bundle.rs
@@ -81,8 +81,10 @@
 use std::time;
 use std::cmp::{self, Ordering};
 use std::ops::{Deref, DerefMut};
+use std::sync::Arc;
 
 use crate::{
+    cert::lazysigs::LazySignatures,
     Error,
     packet::Signature,
     packet::Key,
@@ -116,17 +118,21 @@ pub struct ComponentBundle<C> {
     pub(super) hash_algo_security: HashAlgoSecurity,
 
     // Self signatures.
-    pub(super) self_signatures: Vec<Signature>,
+    pub(super) self_signatures: LazySignatures,
+
+    /// If set, is equal to `component`, and provides context to
+    /// verify primary key binding signatures.
+    backsig_signer: Option<Key<key::PublicParts, key::SubordinateRole>>,
 
     // Third-party certifications.  (In general, this will only be by
     // designated revokers.)
     pub(super) certifications: Vec<Signature>,
 
     // Attestation key signatures.
-    pub(super) attestations: Vec<Signature>,
+    pub(super) attestations: LazySignatures,
 
     // Self revocations.
-    pub(super) self_revocations: Vec<Signature>,
+    pub(super) self_revocations: LazySignatures,
 
     // Third-party revocations (e.g., designated revokers).
     pub(super) other_revocations: Vec<Signature>,
@@ -185,17 +191,19 @@ impl<C> ComponentBundle<C> {
     /// use `pub(in ...)` because the cert parser isn't an ancestor of
     /// this module.
     pub(crate) fn new(component: C,
-           hash_algo_security: HashAlgoSecurity,
-           sigs: Vec<Signature>)
+                      hash_algo_security: HashAlgoSecurity,
+                      sigs: Vec<Signature>,
+                      primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>)
            -> ComponentBundle<C>
     {
         ComponentBundle {
             component,
             hash_algo_security,
-            self_signatures: vec![],
+            self_signatures: LazySignatures::new(primary_key.clone()),
+            backsig_signer: None,
             certifications: sigs,
-            attestations: vec![],
-            self_revocations: vec![],
+            attestations: LazySignatures::new(primary_key.clone()),
+            self_revocations: LazySignatures::new(primary_key),
             other_revocations: vec![],
         }
     }
@@ -278,6 +286,9 @@ impl<C> ComponentBundle<C> {
         // We want the newest signature that is older than `t`, or
         // that has been created at `t`.  So, search for `t`.
 
+          // XXX: this should be done over all signatures, independent
+          // of their state:
+
         let i =
             // Usually, the first signature is what we are looking for.
             // Short circuit the binary search.
@@ -348,6 +359,10 @@ impl<C> ComponentBundle<C> {
                 continue;
             }
 
+
+            // XXX: and here we lazily verify the signature, skipping bad ones.
+
+
             // The signature is good, but we may still need to verify the
             // back sig.
             if s.typ() == crate::types::SignatureType::SubkeyBinding &&
@@ -411,8 +426,10 @@ impl<C> ComponentBundle<C> {
         }
       }
 
-        find_binding_signature(policy, &self.self_signatures,
-                               self.hash_algo_security, t)
+        find_binding_signature(
+            policy,
+            self.self_signatures.slice_verified(self.backsig_signer.as_ref()),
+            self.hash_algo_security, t)
     }
 
     /// Returns the component's self-signatures.
@@ -443,13 +460,13 @@ impl<C> ComponentBundle<C> {
     // XXXv2: Rename this function.
     pub fn self_signatures2(&self)
                             -> impl Iterator<Item=&Signature> + Send + Sync {
-        self.self_signatures.iter()
+        self.self_signatures.iter_verified(self.backsig_signer.as_ref())
     }
 
     /// Returns the component's self-signatures.
     #[deprecated(note = "Use self_signatures2 instead.")]
     pub fn self_signatures(&self) -> &[Signature] {
-        &self.self_signatures
+        &self.self_signatures.slice_verified(self.backsig_signer.as_ref())
     }
 
     /// Returns the component's third-party certifications.
@@ -518,14 +535,14 @@ impl<C> ComponentBundle<C> {
     // XXXv2: Rename this function.
     pub fn self_revocations2(&self)
                              -> impl Iterator<Item=&Signature> + Send + Sync {
-        self.self_revocations.iter()
+        self.self_revocations.iter_verified(self.backsig_signer.as_ref())
     }
 
     /// Returns the component's revocations that were issued by the
     /// certificate holder.
     #[deprecated(note = "Use self_revocations2 instead.")]
     pub fn self_revocations(&self) -> &[Signature] {
-        &self.self_revocations
+        &self.self_revocations.slice_verified(self.backsig_signer.as_ref())
     }
 
     /// Returns the component's revocations that were issued by other
@@ -603,7 +620,7 @@ impl<C> ComponentBundle<C> {
     pub fn attestations(&self)
                       -> impl Iterator<Item = &Signature> + Send + Sync
     {
-        self.attestations.iter()
+        self.attestations.iter_verified(None)
     }
 
     /// Returns all of the component's signatures.
@@ -742,7 +759,8 @@ impl<C> ComponentBundle<C> {
         };
 
         if let Some(revs)
-            = check(&self.self_revocations, self.hash_algo_security)
+            = check(self.self_revocations.slice_verified(self.backsig_signer.as_ref()),
+                    self.hash_algo_security) // XXX must use iterator for lazy verification
         {
             t!("-> RevocationStatus::Revoked({})", revs.len());
             RevocationStatus::Revoked(revs)
@@ -780,9 +798,9 @@ impl<C> ComponentBundle<C> {
     {
         let p : Packet = self.component.into();
         std::iter::once(p)
-            .chain(self.self_revocations.into_iter().map(|s| s.into()))
-            .chain(self.self_signatures.into_iter().map(|s| s.into()))
-            .chain(self.attestations.into_iter().map(|s| s.into()))
+            .chain(self.self_revocations.into_unverified().map(|s| s.into()))
+            .chain(self.self_signatures.into_unverified().map(|s| s.into()))
+            .chain(self.attestations.into_unverified().map(|s| s.into()))
             .chain(self.certifications.into_iter().map(|s| s.into()))
             .chain(self.other_revocations.into_iter().map(|s| s.into()))
     }
@@ -829,12 +847,12 @@ impl<C> ComponentBundle<C> {
         // Order self signatures so that the most recent one comes
         // first.
         self.self_signatures.sort_by(sig_cmp);
-        self.self_signatures.iter_mut().for_each(sig_fixup);
+        self.self_signatures.iter_mut_unverified().for_each(sig_fixup);
 
         self.attestations.sort_by(Signature::normalized_cmp);
         self.attestations.dedup_by(sig_merge);
         self.attestations.sort_by(sig_cmp);
-        self.attestations.iter_mut().for_each(sig_fixup);
+        self.attestations.iter_mut_unverified().for_each(sig_fixup);
 
         self.certifications.sort_by(Signature::normalized_cmp);
         self.certifications.dedup_by(sig_merge);
@@ -849,7 +867,7 @@ impl<C> ComponentBundle<C> {
         self.self_revocations.sort_by(Signature::normalized_cmp);
         self.self_revocations.dedup_by(sig_merge);
         self.self_revocations.sort_by(sig_cmp);
-        self.self_revocations.iter_mut().for_each(sig_fixup);
+        self.self_revocations.iter_mut_unverified().for_each(sig_fixup);
 
         self.other_revocations.sort_by(Signature::normalized_cmp);
         self.other_revocations.dedup_by(sig_merge);
@@ -892,7 +910,42 @@ impl<P: key::KeyParts, R: key::KeyRole> ComponentBundle<Key<P, R>> {
     }
 }
 
+impl<P: key::KeyParts> ComponentBundle<Key<P, key::PrimaryRole>> {
+    /// Returns all of the bundles's bad signatures.
+    pub(crate) fn bad_signatures(&self)
+        -> impl Iterator<Item = &Signature> + Send + Sync
+    {
+        self.self_signatures.iter_bad(self.backsig_signer.as_ref())
+            .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref()))
+    }
+}
+
 impl<P: key::KeyParts> ComponentBundle<Key<P, key::SubordinateRole>> {
+    /// Creates a new subkey component.
+    ///
+    /// Should only be used from the cert parser.  However, we cannot
+    /// use `pub(in ...)` because the cert parser isn't an ancestor of
+    /// this module.
+    pub(crate) fn new_subkey(component: Key<P, key::SubordinateRole>,
+                             hash_algo_security: HashAlgoSecurity,
+                             sigs: Vec<Signature>,
+                             primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>)
+           -> Self
+    {
+        let backsig_signer = component.pk_algo().for_signing()
+            .then(|| component.parts_as_public().clone());
+        ComponentBundle {
+            component,
+            hash_algo_security,
+            self_signatures: LazySignatures::new(primary_key.clone()),
+            backsig_signer,
+            certifications: sigs,
+            attestations: LazySignatures::new(primary_key.clone()),
+            self_revocations: LazySignatures::new(primary_key),
+            other_revocations: vec![],
+        }
+    }
+
     /// Returns the subkey's revocation status at time `t`.
     ///
     /// A subkey is revoked at time `t` if:
@@ -937,6 +990,14 @@ impl<P: key::KeyParts> ComponentBundle<Key<P, key::SubordinateRole>> {
         self._revocation_status(policy, t, true,
                                 self.binding_signature(policy, t).ok())
     }
+
+    /// Returns all of the bundles's bad signatures.
+    pub(crate) fn bad_signatures(&self)
+        -> impl Iterator<Item = &Signature> + Send + Sync
+    {
+        self.self_signatures.iter_bad(self.backsig_signer.as_ref())
+            .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref()))
+    }
 }
 
 impl ComponentBundle<UserID> {
@@ -1012,6 +1073,14 @@ impl ComponentBundle<UserID> {
         let t = t.into();
         self._revocation_status(policy, t, false, self.binding_signature(policy, t).ok())
     }
+
+    /// Returns all of the bundles's bad signatures.
+    pub(crate) fn bad_signatures(&self)
+        -> impl Iterator<Item = &Signature> + Send + Sync
+    {
+        self.self_signatures.iter_bad(self.backsig_signer.as_ref())
+            .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref()))
+    }
 }
 
 impl ComponentBundle<UserAttribute> {
@@ -1083,6 +1152,14 @@ impl ComponentBundle<UserAttribute> {
         self._revocation_status(policy, t, false,
                                 self.binding_signature(policy, t).ok())
     }
+
+    /// Returns all of the bundles's bad signatures.
+    pub(crate) fn bad_signatures(&self)
+        -> impl Iterator<Item = &Signature> + Send + Sync
+    {
+        self.self_signatures.iter_bad(self.backsig_signer.as_ref())
+            .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref()))
+    }
 }
 
 impl ComponentBundle<Unknown> {
@@ -1112,6 +1189,14 @@ impl ComponentBundle<Unknown> {
     pub fn unknown(&self) -> &Unknown {
         self.component()
     }
+
+    /// Returns all of the bundles's bad signatures.
+    pub(crate) fn bad_signatures(&self)
+        -> impl Iterator<Item = &Signature> + Send + Sync
+    {
+        self.self_signatures.iter_bad(self.backsig_signer.as_ref())
+            .chain(self.self_revocations.iter_bad(self.backsig_signer.as_ref()))
+    }
 }
 
 /// A collection of `ComponentBundles`.
diff --git a/openpgp/src/cert/lazysigs.rs b/openpgp/src/cert/lazysigs.rs
new file mode 100644
index 00000000..d54ca551
--- /dev/null
+++ b/openpgp/src/cert/lazysigs.rs
@@ -0,0 +1,356 @@
+//! Lazily verified signatures.
+//!
+//! In the original implementation of `Cert::canonicalize`, all
+//! self-signatures were verified.  This has turned out to be very
+//! expensive.  Instead, we should only verify the signatures we are
+//! actually interested in.
+//!
+//! To preserve the semantics, every self signature we hand out from
+//! the `Cert` API must have been verified first.  However, we can do
+//! that lazily.  And, when we reason over the cert (i.e. we are
+//! looking for the right self-signature), we can search the
+//! signatures without triggering the verification, and only verify
+//! the one we are really interested in.
+
+use std::{
+    cmp::Ordering,
+    mem,
+    sync::{Arc, Mutex, OnceLock},
+};
+
+use crate::{
+    Error,
+    Result,
+    packet::{
+        Key,
+        Signature,
+        key,
+        signature::subpacket::{SubpacketTag, SubpacketValue},
+    },
+};
+
+/// Lazily verified signatures, similar to a `Vec<Signature>`.
+///
+/// We use two distinct vectors to store the signatures and their
+/// state.  The reason for that is that we need to modify the
+/// signature states while the signatures are borrowed.
+///
+/// We provide a subset of `Vec<Signature>`'s interface to make it
+/// (mostly) a drop-in replacement.
+///
+/// # Invariant
+///
+/// - There are as many signatures as signature states.
+///
+/// - If the field `verified_sigs` is used, then there must have been
+///   a bad signature (i.e. len(verified_sigs) < len(sigs)).
+#[derive(Debug)]
+pub struct LazySignatures {
+    /// The primary key to verify the signatures with.
+    primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>,
+
+    /// The signatures.
+    sigs: Vec<Signature>,
+
+    /// The signature states.
+    states: Mutex<Vec<SigState>>,
+
+    /// Verified signatures.
+    ///
+    /// Because of https://gitlab.com/sequoia-pgp/sequoia/-/issues/638
+    /// we have to hand out contiguous slices of verified signatures.
+    /// If all signatures are good, we can serve that request from
+    /// `sigs`.  Otherwise, we have to clone the verified signatures.
+    ///
+    /// XXXv2: Remove this field.
+    verified_sigs: OnceLock<Vec<Signature>>,
+}
+
+impl PartialEq for LazySignatures {
+    fn eq(&self, other: &Self) -> bool {
+        self.assert_invariant();
+        other.assert_invariant();
+        self.primary_key == other.primary_key
+            && self.sigs == other.sigs
+    }
+}
+
+impl Clone for LazySignatures {
+    fn clone(&self) -> Self {
+        self.assert_invariant();
+        LazySignatures {
+            primary_key: self.primary_key.clone(),
+            sigs: self.sigs.clone(),
+            // Avoid blocking.  If we fail to get the lock, reset the
+            // signature states to unverified in the clone.
+            states: if let Ok(states) = self.states.try_lock() {
+                states.clone()
+            } else {
+                vec![SigState::Unverified; self.sigs.len()]
+            }.into(),
+            verified_sigs: Default::default(),
+        }
+    }
+}
+
+/// Verification state of a signature.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub enum SigState {
+    /// Not yet verified.
+    Unverified,
+
+    /// Verification was successful.
+    Good,
+
+    /// Verification failed.
+    Bad,
+}
+
+impl LazySignatures {
+    /// Asserts the invariant.
+    fn assert_invariant(&self) {
+        debug_assert_eq!(self.sigs.len(), self.states.lock().unwrap().len());
+        debug_assert!(
+            self.verified_sigs.get().map(|v| v.len() < self.sigs.len())
+                .unwrap_or(true));
+    }
+
+    /// Creates a vector of lazily verified signatures.
+    ///
+    /// The provided `primary_key` is used to verify the signatures.
+    /// It should be shared across the certificate.
+    pub fn new(primary_key: Arc<Key<key::PublicParts, key::PrimaryRole>>)
+               -> Self
+    {
+        LazySignatures {
+            primary_key,
+            sigs: Default::default(),
+            states: Default::default(),
+            verified_sigs: Default::default(),
+        }
+    }
+
+    /// Like [`Vec::is_empty`].
+    pub fn is_empty(&self) -> bool {
+        self.assert_invariant();
+        self.sigs.is_empty()
+    }
+
+    /// Like [`std::mem::take`].
+    pub fn take(&mut self) -> Vec<Sig