sequoia_wot/

lib.rs

//! A web of trust engine.
//!
//! # Introduction
//!
//! The [web of trust] is a decentralized trust model popularized by
//! PGP.  It is [a superset] of [X.509], which is a hierarchical trust
//! model, and is the most popular trust model on the public internet
//! today.  As used on the public internet, however, X.509 relies on a
//! handful of global [certification authorities] (CAs) who often
//! [undermine its security].
//!
//!   [web of trust]: https://en.wikipedia.org/wiki/Web_of_trust
//!   [a superset]: https://www.oreilly.com/library/view/beautiful-security/9780596801786/ch07.html
//!   [X.509]: https://de.wikipedia.org/wiki/X.509
//!   [certification authorities]: https://en.wikipedia.org/wiki/Certificate_authority
//!   [undermine its security]: https://sslmate.com/resources/certificate_authority_failures
//!
//! The web of trust is more nuanced than X.509.  A user can partially
//! trust a CA thereby preventing a single bad actor from compromising
//! their security.  And those who have stronger security requirements
//! can use the web of trust in a completely decentralized manner.
//!
//! Today, the tooling around the web of trust is primitive at best.
//! Many people interpret this lack of good tooling as a sign that the
//! web of trust is intrinsically difficult to use.  We disagree and
//! think that efforts like our [OpenPGP CA] project provide evidence
//! that this is not the case.
//!
//!   [OpenPGP CA]: https://openpgp-ca.org/
//!
//! # Web of Trust
//!
//! A web of trust is a network where the nodes are certificates,
//! which are also called public keys, and the edges are
//! certifications.  In OpenPGP's web of trust, edges may include
//! non-local constraints.  For instance, the trust depth parameter
//! determines whether the edges of subsequent nodes should be
//! followed.  This means that many graph algorithms cannot be used
//! without modification.
//!
//! This crate implements a web of trust engine.  It is designed
//! around [OpenPGP]'s authentication concepts, but it does not
//! require OpenPGP data structures and, as such, can be used in other
//! contexts.
//!
//!   [OpenPGP]: https://datatracker.ietf.org/doc/html/rfc4880
//!
//! We model a web of trust using the [`Network`] data structure.  As
//! shown in the [examples below], a `Network` can be created either
//! directly from OpenPGP data structures ([`Network::from_certs`]) or
//! it can be created manually ([`Network::new`]).  The latter is
//! useful when the web of trust has been cached.  It can also be used
//! to build a web of trust from non-OpenPGP data.
//!
//! [examples below]: #examples
//!
//! To authenticate a binding, you instantiate a [`Network`] object.
//! You then call [`Network::authenticate`] to authenticate the
//! binding.  The method returns the degree to which a binding (a
//! fingerprint and a User ID) can be considered authentic.  Because
//! authentication is not binary in the web of trust, and because
//! multiple paths can be combined to increase confidence, this
//! function returns a set of paths using the [`Paths`] data
//! structure.
//!
//! By using a variant of [Dijkstra's algorithm] to authenticate a
//! binding, authentication is fast even for large, highly connected
//! web of trusts.  Specifically, its run time is `O((|V| + |E|) *
//! log(|V|))` where `V` are the vertices or certificates, and `E` are
//! the edges or certifications.
//!
//!   [Dijkstra's algorithm]: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
//!
//! OpenPGP defines several authentication mechanisms, but it does not
//! define how they should be used to authenticate a binding.
//! Although both PGP and GnuPG implement a web of trust, neither
//! documents their exact semantics.  This engine treats the network
//! as a [flow network], which is similar, but not identical, to how
//! PGP 7 and later work.
//!
//!  [flow network]: https://en.wikipedia.org/wiki/Flow_network
//!
//! ## OpenPGP's Authentication Mechanisms
//!
//! OpenPGP provides four simple, yet powerful and flexible mechanisms
//! to facilitate authentication.  These are [third-party
//! certifications], a [trust amount] parameter, a [trust depth]
//! parameter, and a [regular expression] parameter.
//!
//!   [third-party certifications]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.1
//!   [trust amount]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.3.13
//!   [trust depth]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.3.13
//!   [regular expression]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.3.14
//!
//! A third-party certification is a machine-readable artifact that
//! says that the issuer believes that a binding between a User ID and
//! a certificate is correct.  OpenPGP distinguishes four different
//! types of third-party certifications ([signature types] 0x10 through
//! 0x13).  This engine treats all of these different signature types
//! identically.  In common practice, a persona certification
//! (signature type 0x11) is often treated as an invalid certification.
//! This engine ignores this distinction.
//!
//!   [signature types]: https://datatracker.ietf.org/doc/html/rfc4880#section-5.2.1
//!
//! The [trust amount] parameter is the degree to which the issuer of
//! a certification is convinced that the binding is correct.  This
//! can vary from 0 to 255.  Values that are 120 or larger mean that
//! the issuer is fully convinced.  Traditionally, an issuer uses 60
//! to indicate that they are partially (aka marginally) convinced,
//! however, any value between 1 and 119 can be used.
//!
//! This web of trust implementation interprets the trust amount as an
//! amount of evidence.  It assumes that evidence is independent and
//! can be combined linearly.  That is, if we have two paths that
//! don't share any edges, say a trust root partially trusts two
//! [certification authorities] (CAs) and they both certify a binding,
//! then the two paths can be added together.
//!
//!   [certification authorities]: https://en.wikipedia.org/wiki/Certificate_authority
//!
//! The [trust depth] parameter is used to indicate that the target
//! should also be used as a CA.  When this type of delegation is done
//! in OpenPGP, the target is sometimes called a trusted introducer.
//!
//! The trust depth parameter ranges from 0 to 255.  A value of 0
//! means that the target is not a trusted introducer, and this is
//! just a normal certification of the binding.  If the issuer of a
//! certification uses a value of 1, it means that they consider the
//! target to also be a trusted introducer.  A value of 2 means that
//! not only is the issuer willing to rely on certifications made by
//! the target, but the target can designate other certificates as
//! trusted introducers.  A value of 3 means that the third party can
//! delegate the certification capability.  In general, a value of `n`
//! means that a certificate that is at most `n` steps away from the
//! issuer may be considered a trusted introducer, and certificates
//! that are at most `n+1` steps away from the issuer can be
//! authenticated.  Consider the following network where the number is
//! the certification's trust depth parameter:
//!
//! ```text
//! alice --2--> bob --2--> carol --2--> dave --2--> ed
//! ```
//!
//! alice certifies bob and uses a trust depth of 2.  This means that
//! she considers bob to be a trusted introducer and that he can
//! delegate that capability to someone else, which he does when he
//! certifies carol and uses a positive trust depth parameter.  Then,
//! because carol certifies dave, alice can authenticate dave.  That
//! is, `alice - bob - carol - dave` is a valid path.
//!
//! But, alice cannot authenticate ed even though dave considers ed to
//! be a trusted introducer.  This is because alice does not consider
//! dave to be a trusted introducer: he is too far away; alice would
//! have had to set the trust depth on her certification of bob to 3
//! for her to consider dave a trusted introducer.
//!
//! The trust amount and trust depth parameters interact.  If alice
//! certifies bob's certificate and sets a trust depth of 1 and a
//! trust amount of 60, then the trust amount of any certifications
//! that bob makes are limited to 60.  Consider:
//!
//! ```text
//! alice --60/1--> bob --120/0--> carol
//! ```
//!
//! In the above network, alice says that bob is a partially trusted
//! introducer (amount = 60).  Even though bob has certificated
//! carol's key with a trust amount of 120, alice only assigns the
//! path `alice - bob - carol` a trust amount of 60.  In general, a
//! path's trust amount is the minimum trust amount of any
//! certification in the path.
//!
//! The final parameter is a regular expression.  A certification can
//! include zero or more regular expressions.  If it includes at least
//! one regular expression, then at least one of them has to match the
//! target User ID for the path to be valid.
//!
//! Regular expressions are a mechanism for a user to make use of a CA
//! in a limited way.  For instance, ed might be willing to rely on
//! `ca@nsa.gov` to certify other `nsa.gov` User IDs, but doesn't want
//! to rely on `ca@nsa.gov` to make a statement about any other User
//! ID.
//!
//! This implementation only applies the regular expression parameter
//! to the target User ID; it does not apply it to any CAs along the
//! path.  Thus, `ca@nsa.gov` could consider `ca@fbi.gov` a CA and
//! `ca@fbi.gov` might certify `paul@nsa.gov`.  And, even though the
//! regular expression does not match the intermediate CA's User ID
//! (`ca@fbi.gov`), it does match the target so that path would be
//! valid.
//!
//! ## Multiple Paths and Maximum Flow
//!
//! OpenPGP does not only support binary authentication; it also
//! supports degrees of authentication.  If the path that this
//! implementation finds does not authenticate the binding to the
//! required degree, then the implementation will look for additional
//! paths.  If paths overlap, then the degree of authentication is the
//! [maximum flow] where the capacity of an edge is the
//! certification's trust amount.  Consider the following web of
//! trust:
//!
//!   [maximum flow]: https://en.wikipedia.org/wiki/Maximum_flow_problem
//!
//! ```text
//!         root
//!          |  90/2
//!          v
//!        alice
//! 40/1  /     \  60/1
//!      v       v
//!     bob    carol
//! 120   \     /   120
//!        v   v
//!        david
//! ```
//!
//! There are two paths from `root` to `david`: `root - alice - bob -
//! david` and `root - alice - carol - david`.  The degree of
//! authentication of each of the paths is the minimum trust amount of
//! any certification along the path, which, in this case, is 40 and
//! 60, respectively.  Combining these paths only results in a trust
//! amount of 90, however, since both paths use the `root - alice`
//! certification and its capacity is 90.
//!
//! ### Multiple User IDs
//!
//! It is possible to use a certificate to certify multiple User IDs
//! on another certificate using different parameters.  When this
//! happens, the path finding algorithm is run as usual and considers
//! all certifications to find the best path; no certifications are
//! trimmed a priori.
//!
//! The algorithm then creates a type of residual network where the
//! path is removed.  But instead of subtracting capacity from the
//! edges that occur in the path (i.e., the certifications), the
//! capacity is subtracted from the multi-edges.  That is the capacity
//! is removed from all of the certifications between two
//! certificates.
//!
//! Consider the following network where alice has certified both
//! `bob@some.org` and `bob@other.org` on bob's certificate:
//!
//! ```text
//!              alice
//!       40/2  /     \ 30/3
//!            v       v
//! bob@some.org - b - bob@other.org
//!         20/1 /   \ 120/2
//!             v     v
//!           carol  dave
//!             |     | 120/1
//!         120 |     v
//!             |     ed
//!              \   / 120
//!               v v
//!              frank
//! ```
//!
//! The algorithm first finds the path `a - b - c - f`, which has a
//! trust amount of 20.  When the algorithm is run on the residual
//! network, it finds `a - b - d - e - f`, which has a trust amount of
//! 10.  This is because the algorithm has to use the `bob@other.org`
//! certification (the `bob@some.org` certification's depth parameter
//! is too small) and all certifications between alice and bob are
//! suppressed by 20.
//!
//! Critically, the paths `a - bob@some.org - c - f` and `a -
//! bob@other.org - d - e - f` are not combined for an aggregate trust
//! amount of 70, even though they have no overlapped edges: they
//! share a multi-edge, which is partially suppressed.
//!
//! ## Examples
//!
//! Authenticating a binding is a two-step process.  First, you build
//! the network.  Then you query it.
//!
//! There are two ways to build the network.  You can provide OpenPGP
//! data structures and let the library build the network for you.
//! Or, you can describe the network.  The latter approach is useful
//! when you've saved a network, e.g., in a database, and don't want
//! reparse and revalidate the OpenPGP data structures, which can be
//! computationally expensive.  It is also useful when you don't
//! actually have OpenPGP data, but want to use the web of trust.
//!
//! The following two examples show each of these approaches using the
//! following network:
//!
//! ```text
//!           0xAA, alice@example.org
//!                    |  40/1/some.org
//!                    v
//!             0xCA, ca@some.org
//!     120/0  /                 \  120/0
//!           v                   v
//! 0xBB, bob@some.org     0xCC, carol@other.org
//! ```
//!
//! (The numbers next to the edges are the trust amount and trust
//! depth.  They are sometimes followed by a domain.  The domain
//! corresponds to a regular expression that matches email addresses
//! in that domain.)
//!
//! There are four certificates.  `alice@example.org` has certified
//! `ca@some.org` to be a partially trusted (amount = 40) trusted
//! introducer (depth = 1), scoped to `some.org`.  And, `ca@some.org`
//! has certified `bob@some.org` and `carol@other.org`.
//!
//! With `alice@example.org` as a root, we can partially authenticate
//! `bob@some.org`, but, due to the scoping rule, we can't
//! authenticate `carol@other.org` at all: the User ID doesn't match
//! the regular expression.
//!
//! ### Using OpenPGP Data Structures
//!
//! ```
//! use sequoia_openpgp as openpgp;
//! use openpgp::Cert;
//! use openpgp::cert::CertParser;
//! use openpgp::Fingerprint;
//! use openpgp::packet::UserID;
//! use openpgp::parse::Parse;
//! use openpgp::policy::StandardPolicy;
//!
//! use sequoia_wot::Network;
//! use sequoia_wot::FULLY_TRUSTED;
//! use sequoia_wot::PARTIALLY_TRUSTED;
//!
//! # fn main() -> anyhow::Result<()> {
//!
//! let keyring = "-----BEGIN PGP PUBLIC KEY BLOCK-----
//!
//!     xjMEYW/3iRYJKwYBBAHaRw8BAQdAnjTe1KqODINdZOIHuaG8s9aOoJxNJ+CunEI5
//! #   XM3nCGbCwAsEHxYKAH0FgmFv94kDCwkHCRAT3t2aD+UaV0cUAAAAAAAeACBzYWx0
//! #   QG5vdGF0aW9ucy5zZXF1b2lhLXBncC5vcmfX931STLM0Jms6P9W4v8WGhgmfuuaO
//! #   TT8Umsbx55vS8AMVCggCmwECHgEWIQQ3B3E3Sb1zXwy91VUT3t2aD+UaVwAAy+gA
//! #   /1lMXxNzxQLbjQsrioAKi+k0Wb2JxlJU1/9bWmGWUu78AP4gUXAYc7eWYa49iiuG
//! #   d2CIwnMu++/6gA2tCU9Oj3BbCc0NPGNhQHNvbWUub3JnPsLADgQTFgoAgAWCYW/3
//! #   iQMLCQcJEBPe3ZoP5RpXRxQAAAAAAB4AIHNhbHRAbm90YXRpb25zLnNlcXVvaWEt
//! #   cGdwLm9yZ6aTpERi74O/4kUhJybOIrhCgMjzqntoWNdLZCPnvl79AxUKCAKZAQKb
//! #   AQIeARYhBDcHcTdJvXNfDL3VVRPe3ZoP5RpXAAArdAD9EeFG8OylF5aykO7c6uxE
//! #   of3DafAzDzIpbZ5rNC1jrDgBAOUjPP4z9Y040MsPVZaUnAY/1Cz3EnNSmwUyX8kw
//! #   5ocOwsAfBBAWCgCRBYJhcAVJBYMJZ5o7A4UBKBeGPFtePl0rW0AuXXNvbWVcLm9y
//! #   Zz4kAAkQ0WzsWOrfU01HFAAAAAAAHgAgc2FsdEBub3RhdGlvbnMuc2VxdW9pYS1w
//! #   Z3Aub3JnTJBFIWL2tBbfuUxHvEXeqG+eYezdu9/ZHLRGhPmaJSgWIQTOOYvmU4lU
//! #   jsIzT+jRbOxY6t9TTQAAqEIBAOFaZ5WNUYgzLQm0cONZ18NcETl5CLtXs5nAvkOy
//! #   RCALAP9I9XXLsTZ3yhrQ2DLxY0Ofc2AYnIZbSUoH/Mp4B61oDs4zBGFv94kWCSsG
//! #   AQQB2kcPAQEHQHCTaKwm4GF8Pq/4yELj2mDQeavJtS5tseDG7PNofRqtwsC/BBgW
//! #   CgExBYJhb/eJCRAT3t2aD+UaV0cUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1
//! #   b2lhLXBncC5vcme6uYEsVIk0S5cxjhSAoWzvT8JO6EVVD1V5cjVvKrNsBQKbAr6g
//! #   BBkWCgBvBYJhb/eJCRA3bmybINBvi0cUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5z
//! #   ZXF1b2lhLXBncC5vcmeQxtudFLbnDAdIkeDYGvY/SDGK/8WjZj6OIeaB9lN9XxYh
//! #   BEr0Vidlm4mGYZWHADdubJsg0G+LAABWowD+PWlZo6HD/E1msiCzbsQE3kymenO2
//! #   0zi9wO9K6tpWSjEBAPfJwl3P75DfuZFk7oFfs1dEu13Y6sqFNXtWAdv9pSAOFiEE
//! #   NwdxN0m9c18MvdVVE97dmg/lGlcAAFbUAQC+q7zIXXpAsYPtgkZFLwE7P6FT6Mwc
//! #   fNQsWJThSs3l2wEAu3w17et6Um462YyA7/e8oYoof0jmE6zm8J+rpiJ9vAzGMwRh
//! #   b/eJFgkrBgEEAdpHDwEBB0Dy4HQX3KNylOVGxcr1fCsPLrKRMXU4NBEuN4tKA9Bf
//! #   NMLACwQfFgoAfQWCYW/3iQMLCQcJENFs7Fjq31NNRxQAAAAAAB4AIHNhbHRAbm90
//! #   YXRpb25zLnNlcXVvaWEtcGdwLm9yZ3H4ZFguXTuDstdPt/4OEHz7pzPAeDfnrqVN
//! #   31tK7REeAxUKCAKbAQIeARYhBM45i+ZTiVSOwjNP6NFs7Fjq31NNAAAGMwEAq7HL
//! #   EhSsj6m3/d5w+brM5wPy5NfeRU//KDlypn+k/jkBAJgjigEl7PHou/S/7xCl3/yN
//! #   jrSmctNaPcWKaHvA8mYGzRM8YWxpY2VAZXhhbXBsZS5vcmc+wsAOBBMWCgCABYJh
//! #   b/eJAwsJBwkQ0WzsWOrfU01HFAAAAAAAHgAgc2FsdEBub3RhdGlvbnMuc2VxdW9p
//! #   YS1wZ3Aub3JnwiIwVUPZ4cWc6uxMET790yfw9FNMyNVSv5sprbnM7S4DFQoIApkB
//! #   ApsBAh4BFiEEzjmL5lOJVI7CM0/o0WzsWOrfU00AAJshAP98sZXu0EOhQhvuiVrk
//! #   Td/3nuOTDBEP7vbS9IQdz/1O0wD+IXMHZDL4kAoYaRzdBN67lTPNoF86CgF5o6Xj
//! #   ss+JOwHOMwRhb/eJFgkrBgEEAdpHDwEBB0BEpXxuCZPOh5bZHmIxM8t1pW1QVM4G
//! #   pgDIOKVfT7p+DMLAvwQYFgoBMQWCYW/3iQkQ0WzsWOrfU01HFAAAAAAAHgAgc2Fs
//! #   dEBub3RhdGlvbnMuc2VxdW9pYS1wZ3Aub3Jn7sWL0sTBq10p7d2GN7ZgsZkUxVY+
//! #   JUnn9R4WhFaH06YCmwK+oAQZFgoAbwWCYW/3iQkQY8VPvdEOAONHFAAAAAAAHgAg
//! #   c2FsdEBub3RhdGlvbnMuc2VxdW9pYS1wZ3Aub3Jn+DEKCHP+xYMcV5LLB5K5dH2I
//! #   w9BmJxSJckTsAkIX/OQWIQRvo9S/vEXV8ksghTZjxU+90Q4A4wAAorAA/2eO42HY
//! #   FVH3wJj3SvhqT8EQ7qe/hpMPAb7uznxhL6CfAP9nlen3sa+Hb1FvEQIjCXjYv0G/
//! #   vMJMdEujNIydIhgMCxYhBM45i+ZTiVSOwjNP6NFs7Fjq31NNAABvHwEA0LH6AxAs
//! #   5hGYltx9cevRYBOBp6IZgcHjFe8ul+BluRkBAKoOtddLcHVWqkQvwhJfZeFsWh4Z
//! #   xmCcSRIPhKIQKd8FxjMEYW/3iRYJKwYBBAHaRw8BAQdAaTuo6QJUO97wvBRzLjrr
//! #   3TtHWNDmsqfNW822cxziIXfCwAsEHxYKAH0FgmFv94kDCwkHCRDHSeVh6tRJFEcU
//! #   AAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1b2lhLXBncC5vcmeOVXbQyo69KDqD
//! #   DwF3tHvUQ+TcAo36x0OVEvO/5Tiz/wMVCggCmwECHgEWIQSU4urbpMNHKjgy1aHH
//! #   SeVh6tRJFAAA1TEBAN9JsM3mR/mfsc8MDv4jAPHfme1Fb1kzfeSAGErxcoXCAP9Y
//! #   SVUUITnu5an8pEq+VvfrmI3+GlUHcwHqRweNZzuyCc0OPGJvYkBzb21lLm9yZz7C
//! #   wA4EExYKAIAFgmFv94kDCwkHCRDHSeVh6tRJFEcUAAAAAAAeACBzYWx0QG5vdGF0
//! #   aW9ucy5zZXF1b2lhLXBncC5vcmcQLXTmQuGBBrqvrQcp9bAJRReeM6iGoKGZwyaA
//! #   uFvJiwMVCggCmQECmwECHgEWIQSU4urbpMNHKjgy1aHHSeVh6tRJFAAAKxkBALVZ
//! #   0bfvmTiZGdRdwmmN11o8jW7Y4Dl03qBxM4mnlImpAPkB8aHacdJqayTGXAHEpCYs
//! #   in4Rub0MrpL8sHXLVGHPCMLAAwQQFgoAdQWCYXAFSQWDCWeaOwkQE97dmg/lGldH
//! #   FAAAAAAAHgAgc2FsdEBub3RhdGlvbnMuc2VxdW9pYS1wZ3Aub3JnQXhNpXB+3MHz
//! #   Ga1xoefNExdGLVxZYUjz7aFcAhoaKRYWIQQ3B3E3Sb1zXwy91VUT3t2aD+UaVwAA
//! #   tvoBANTItWBApjgY/JhR6iODkuzs0NgUa8FB7dciX0NKcCvuAPsFEsZ8MvZNpDWr
//! #   wygyZqBXrfGeVF9XX5gea+YjPszJD84zBGFv94kWCSsGAQQB2kcPAQEHQCw202vX
//! #   S2AO45UCegla3BdT5Ni04rU0UmmPb9VdEiEYwsC/BBgWCgExBYJhb/eJCRDHSeVh
//! #   6tRJFEcUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1b2lhLXBncC5vcmeNRh9E
//! #   KpZbEAC5BGlRwmdRJ+ezFjLbFRTBODMnakTtdAKbAr6gBBkWCgBvBYJhb/eJCRDr
//! #   Orxt/dguCUcUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1b2lhLXBncC5vcmfO
//! #   n5KJiwXj8/+4OcbCxpa2WAtmlN48ryqBuNgu0pzVuRYhBAz8pIL7wcszRr42iOs6
//! #   vG392C4JAAARegEA7RV9eqlrzRep7Oh0LRDD6zXoambuyOtttJQRKE/OKlABAMyI
//! #   Ha/5V3O4lfspfI0ghuTMxTPc81rRcREhwYuqXNwDFiEElOLq26TDRyo4MtWhx0nl
//! #   YerUSRQAAEB0AQDgyVqdYxHb1XmGbKqmzAK7hClGXDkqGjngOh6r3l8oQAD+I330
//! #   E8ZHE0PBWJ6Rb6YXmtPEsvcsEgfm/pN0augU7A/GMwRhb/eKFgkrBgEEAdpHDwEB
//! #   B0DR6YaeeCOax42CffJndlZvv/r09cCVjt0ORB90j9lEP8LACwQfFgoAfQWCYW/3
//! #   igMLCQcJEFJtELjzPANJRxQAAAAAAB4AIHNhbHRAbm90YXRpb25zLnNlcXVvaWEt
//! #   cGdwLm9yZyvJ6GlUekEcAqYsIeiFEyhdlqAW/OvPq1fDs/yMXdUJAxUKCAKbAQIe
//! #   ARYhBLIOjtMetcD960cJ6lJtELjzPANJAAB0EQEA/OuyDfAHgqfTd2bRzYzT7I2o
//! #   PiB/ihV0WUuUc88j/NkBAIe0op34YsVQKLU9Ix+JbZTfRkdYnTgOriY2lzHR5+oE
//! #   zRE8Y2Fyb2xAb3RoZXIub3JnPsLADgQTFgoAgAWCYW/3igMLCQcJEFJtELjzPANJ
//! #   RxQAAAAAAB4AIHNhbHRAbm90YXRpb25zLnNlcXVvaWEtcGdwLm9yZ0pWZ7F81PpB
//! #   rbYdp6JBWdbl0VqHn1AWIlR1Ry+uUvm9AxUKCAKZAQKbAQIeARYhBLIOjtMetcD9
//! #   60cJ6lJtELjzPANJAAAXFAEA4jXm0znj0C/Ye6JYHOneGpoFgfCWy7kx+qR0zKJh
//! #   ocoA/22vYYb0g+L6Kdo+gTITaibHoWYkztcisqJcirONz8YJwsADBBAWCgB1BYJh
//! #   cAVJBYMJZ5o7CRAT3t2aD+UaV0cUAAAAAAAeACBzYWx0QG5vdGF0aW9ucy5zZXF1
//! #   b2lhLXBncC5vcmc6zt9LwAW1nYyI2k0zINUYzXj9pWLfh2Uij020D+014RYhBDcH
//! #   cTdJvXNfDL3VVRPe3ZoP5RpXAADe/wD/eKl+iefK1jhuGecOD2MBFOGuWKdmTjL6
//! #   x8lx08W1iFYA/i2kkP6uUIX8rn4HlWcY+tdWxzEfT3ExrW8UGtFov+wEzjMEYW/3
//! #   ihYJKwYBBAHaRw8BAQdAvHEeR20eC+45UsCaUdfxkG/CkEYzzyyCZk/gc4RRDVTC
//! #   wL8EGBYKATEFgmFv94oJEFJtELjzPANJRxQAAAAAAB4AIHNhbHRAbm90YXRpb25z
//! #   LnNlcXVvaWEtcGdwLm9yZyyvZrTVCn1hbMFSGPoXmek6QbeFvJIxDH8IiTgx2LXa
//! #   ApsCvqAEGRYKAG8FgmFv94oJEFVL1AWo5KwsRxQAAAAAAB4AIHNhbHRAbm90YXRp
//! #   b25zLnNlcXVvaWEtcGdwLm9yZ5vdUn08uTdpCKTyvFDQiOYJbemhOguSoBlGbunb
//! #   vYXWFiEEZsOhvCD6arW5g7qnVUvUBajkrCwAAGuvAQCb2J/W/pV0q7AOLDFJ3PmH
//! #   p6LXdEFyMM8MOsF9HXF0ewD/cqW1f0GnZpUqppVNWJ5UaxzwH4LJN2Syuy5dZgv5
//! #   PAAWIQSyDo7THrXA/etHCepSbRC48zwDSQAAsIcBAL9fexChDBcBlscpSSmtzUbh
//! #   eqZRftsm4rzrUlzU3bknAP413jTBeSQItsUjpvwBLM3jFohGLRTI8gu96jWvTXKZ
//! #   BA==
//! #   =QO4G
//! #   -----END PGP PUBLIC KEY BLOCK-----" /* docstring trickery ahead:
//!     // ...
//!     -----END PGP PUBLIC KEY BLOCK-----";
//! # */;
//!
//! let certs: Vec<Cert> = CertParser::from_bytes(keyring)?
//!     // Silently discard invalid certifications.
//!     .filter_map(|r| r.ok())
//!     .collect();
//! assert_eq!(certs.len(), 4);
//!
//! let alice_fpr: Fingerprint =
//!     "CE398BE65389548EC2334FE8D16CEC58EADF534D"
//!    .parse().expect("valid fingerprint");
//! let alice_uid
//!     = UserID::from("<alice@example.org>");
//!
//! let ca_fpr: Fingerprint =
//!     "3707713749BD735F0CBDD55513DEDD9A0FE51A57"
//!    .parse().expect("valid fingerprint");
//! let ca_uid
//!     = UserID::from("<ca@some.org>");
//!
//! let bob_fpr: Fingerprint =
//!     "94E2EADBA4C3472A3832D5A1C749E561EAD44914"
//!    .parse().expect("valid fingerprint");
//! let bob_uid
//!     = UserID::from("<bob@some.org>");
//!
//! let carol_fpr: Fingerprint =
//!     "B20E8ED31EB5C0FDEB4709EA526D10B8F33C0349"
//!    .parse().expect("valid fingerprint");
//! let carol_uid
//!     = UserID::from("<carol@other.org>");
//!
//! let p = &StandardPolicy::new();
//! let n = Network::from_cert_refs(certs.iter(), p, None,
//!                                 &[ alice_fpr.clone() ])?;
//!
//! let paths = n.authenticate(bob_uid, bob_fpr.clone(), FULLY_TRUSTED);
//! assert_eq!(paths.len(), 1);
//! assert_eq!(paths[0].0.amount(), PARTIALLY_TRUSTED);
//! assert_eq!(paths[0].0.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>(),
//!            vec![ alice_fpr, ca_fpr, bob_fpr ]);
//!
//! let paths = n.authenticate(carol_uid, carol_fpr.clone(), FULLY_TRUSTED);
//! eprintln!("{:?}", paths);
//! assert_eq!(paths.len(), 0);
//! # Ok(())
//! # }
//! ```
//!
//! ### Building a Network By Hand
//!
//! ```
//! use std::time::SystemTime;
//! use std::iter::once;
//!
//! use sequoia_openpgp as openpgp;
//! use openpgp::Fingerprint;
//! use openpgp::regex::RegexSet;
//!
//! use sequoia_wot::CertSynopsis;
//! use sequoia_wot::UserIDSynopsis;
//! use sequoia_wot::Certification;
//! use sequoia_wot::Network;
//! use sequoia_wot::RevocationStatus;
//! use sequoia_wot::FULLY_TRUSTED;
//! use sequoia_wot::PARTIALLY_TRUSTED;
//!
//! # fn main() -> anyhow::Result<()> {
//! let reference_time = SystemTime::now();
//!
//! let alice_fpr: Fingerprint =
//!     "CE398BE65389548EC2334FE8D16CEC58EADF534D"
//!    .parse().expect("valid fingerprint");
//! let alice_uid
//!     = UserIDSynopsis::from("<alice@example.org>");
//!
//! let ca_fpr: Fingerprint =
//!     "3707713749BD735F0CBDD55513DEDD9A0FE51A57"
//!    .parse().expect("valid fingerprint");
//! let ca_uid
//!     = UserIDSynopsis::from("<ca@some.org>");
//!
//! let bob_fpr: Fingerprint =
//!     "94E2EADBA4C3472A3832D5A1C749E561EAD44914"
//!    .parse().expect("valid fingerprint");
//! let bob_uid
//!     = UserIDSynopsis::from("<bob@some.org>");
//!
//! let carol_fpr: Fingerprint =
//!     "B20E8ED31EB5C0FDEB4709EA526D10B8F33C0349"
//!    .parse().expect("valid fingerprint");
//! let carol_uid
//!     = UserIDSynopsis::from("<carol@other.org>");
//!
//! let alice = CertSynopsis::new(
//!     alice_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
//!     once(alice_uid.clone()));
//! let ca = CertSynopsis::new(
//!     ca_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
//!     once(ca_uid.clone()));
//! let bob = CertSynopsis::new(
//!     bob_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
//!     once(bob_uid.clone()));
//! let carol = CertSynopsis::new(
//!     carol_fpr.clone(), None, RevocationStatus::NotAsFarAsWeKnow,
//!     once(carol_uid.clone()));
//!
//! let alice_certifies_ca = Certification::new(
//!     alice.clone(), Some(ca_uid.userid().clone()), ca.clone(),
//!     reference_time)
//!     .set_amount(PARTIALLY_TRUSTED)
//!     .set_depth(1)
//!     .set_regular_expressions(
//!         [ &b"<[^>]+[@.]some.org>$"[..] ].into_iter());
//!
//! let ca_certifies_bob = Certification::new(
//!     ca.clone(), Some(bob_uid.userid().clone()), bob.clone(),
//!     reference_time);
//!
//! let certs = &[ alice, ca, bob, carol ][..];
//! let certifications = &[ alice_certifies_ca, ca_certifies_bob ];
//! let n = Network::from_synopses(
//!     certs, certifications,
//!     reference_time,
//!     &[ alice_fpr.clone() ])?;
//!
//! let paths = n.authenticate(bob_uid.userid().clone(), bob_fpr.clone(),
//!                            FULLY_TRUSTED);
//! assert_eq!(paths.len(), 1);
//! assert_eq!(paths[0].0.amount(), PARTIALLY_TRUSTED);
//! assert_eq!(paths[0].0.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>(),
//!            vec![ alice_fpr, ca_fpr, bob_fpr ]);
//! # Ok(())
//! # }
//! ```

// Public re-exports.
pub use sequoia_cert_store;

type Result<T, E=anyhow::Error> = std::result::Result<T, E>;

#[macro_use] mod log;

pub mod store;
mod userid;
pub use userid::UserIDSynopsis;
mod cert;
pub use cert::CertSynopsis;
mod certification;
pub use certification::Depth;
pub use certification::Certification;
mod revocation;
pub use revocation::RevocationStatus;
pub use certification::CertificationSet;
pub use certification::CertificationError;
mod network;
pub use network::{
    CertLints,
    CertificationLints,
    Network,
    NetworkBuilder,
    PathError,
    PathLints,
    Root,
    Roots,
};
// mod forward_propagation;
mod backward_propagation;
mod path;
pub use path::{Path, Paths};
mod priority_queue;
use priority_queue::PriorityQueue;

#[cfg(test)]
mod testdata;

const TRACE: bool = false;

/// The amount of trust needed for a binding to be fully trusted.
pub const FULLY_TRUSTED: usize = 120;
/// The usual amount of trust assigned to a partially trusted
/// trusted introducer.
///
/// Normally, three partially trusted introducers are needed to
/// authenticate a binding.  Thus, this is a third of `FULLY_TRUSTED`.
pub const PARTIALLY_TRUSTED: usize = 40;

/// Errors used in this crate.
///
/// Note: This enum cannot be exhaustively matched to allow future
/// extensions.
#[non_exhaustive]
#[derive(thiserror::Error, Debug, Clone, PartialEq, Eq)]
pub enum Error {
    /// Not a revocation revocation certificate.
    #[error("Not a revocation revocation certificate")]
    NotARevocationCertificate,
}

/// Formats the given time.
pub(crate) fn format_time(t: &std::time::SystemTime) -> String {
    chrono::DateTime::<chrono::Utc>::from(t.clone())
        .format("%Y-%m-%d %H:%M.%S")
        .to_string()
}

/// Like std::time::SystemTime::now, but works on WASM.
fn now() -> std::time::SystemTime {
    #[cfg(all(target_arch = "wasm32", target_os = "unknown"))] {
        chrono::Utc::now().into()
    }
    #[cfg(not(all(target_arch = "wasm32", target_os = "unknown")))] {
        std::time::SystemTime::now()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    use std::slice;
    use std::time;

    use sequoia_openpgp as openpgp;

    use openpgp::Cert;
    use openpgp::cert::CertParser;
    use openpgp::Fingerprint;
    use openpgp::KeyHandle;
    use openpgp::KeyID;
    use openpgp::parse::Parse;
    use openpgp::packet::UserID;
    use openpgp::policy::StandardPolicy;
    use openpgp::Result;

    use crate::store::Backend;
    use crate::store::CertStore;
    use crate::store::Store;

    // Authenticates the target.
    fn check<'a, S>(q: &Network<S>,
                    target_fpr: &Fingerprint, target_userid: &UserID,
                    expected: &[ (usize, &[ &Fingerprint ]) ],
                    min_trust_amount: Option<usize>,
                    gossip: bool)
    where S: Store + Backend<'a>
    {
        eprintln!("\nauthenticating: {}, {}",
                  target_fpr,
                  String::from_utf8_lossy(target_userid.value()));
        let got = if gossip {
            assert!(min_trust_amount.is_none());
            q.gossip(target_fpr.clone(),
                     target_userid.clone())
        } else {
            q.authenticate(target_userid.clone(),
                           target_fpr.clone(),
                           min_trust_amount.unwrap_or(120))
        };
        match (got.iter().count() > 0, expected.len() > 0) {
            (false, false) => {
                eprintln!("Can't authenticate == can't authenticate (good)");
            }
            (false, true) => {
                panic!("Couldn't authenticate.  Expected: paths:\n{}",
                       expected.iter()
                           .enumerate()
                           .flat_map(|(i, (_, p))| {
                               p.iter().enumerate().map(move |(j, f)| {
                                   format!("  {}.{}. {}", i, j, f.to_hex())
                               })
                           })
                           .collect::<Vec<_>>()
                           .join("\n  "));
            }
            (true, false) => {
                panic!("Unexpectedly authenticated binding.  Got:\n{}",
                       got.iter().enumerate().map(|(i, p)| {
                           format!("PATH #{}\n{:?}", i, p)
                       })
                       .collect::<Vec<_>>()
                       .join("\n"));
            }
            (true, true) => {
                eprintln!("Paths: {:?}", got);

                assert_eq!(got.iter().count(), expected.len(),
                           "Expected {:?} paths, got {:?}",
                           expected, got);
                for (i, ((got_amount, got_path), (expected_amount, expected_path)))
                    in got.iter().map(|(p, a)| {
                        (a,
                         p.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>())
                    })
                    .zip(expected.iter().map(|(a, fprs)| {
                        (a, fprs.iter().map(|&fpr| {
                            fpr.clone()
                        }).collect::<Vec<Fingerprint>>())
                    }))
                    .enumerate()
                {
                    assert_eq!(got_path, expected_path,
                               "got vs. expected path (#{})",
                               i);
                    assert_eq!(got_amount, expected_amount,
                               "got vs. expected trust amount (#{})",
                               i);
                }
                assert_eq!(got.amount(),
                           expected.iter().map(|(a, _)| a).sum::<usize>());
            }
        }

        // Make sure Network::path agrees that the paths are good.
        for &(amount, path) in expected.iter() {
            if let Err(err) = q.path(
                &path
                    .iter()
                    .map(|&fpr| KeyHandle::from(fpr))
                    .collect::<Vec<_>>()[..],
                target_userid,
                amount,
                // XXX
                &StandardPolicy::new())
            {
                panic!("Unexpectedly failed to validate {} {:?}: {}.",
                       path.iter()
                           .map(|&fpr| KeyID::from(fpr).to_hex())
                           .collect::<Vec<_>>()
                           .join(" "),
                       target_userid,
                       err);
            }
        }
    }

    fn sp<'a, S>(q: &Network<S>,
                 target_fpr: &Fingerprint, target_userid: &UserID,
                 expected: &[ (usize, &[ &Fingerprint ]) ],
                 min_trust_amount: Option<usize>)
    where S: Store + Backend<'a>
    {
        check(q, target_fpr, target_userid, expected, min_trust_amount, false);
    }

    fn gp<'a, S>(q: &Network<S>,
                 target_fpr: &Fingerprint, target_userid: &UserID,
                 expected: &[ (usize, &[ &Fingerprint ]) ])
    where S: Store + Backend<'a>
    {
        check(q, target_fpr, target_userid, expected, None, true);
    }

    #[test]
    #[allow(unused)]
    fn simple() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "39A479816C934B9E0464F1F4BC1DCFDEADA4EE90"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D

        let carol_fpr: Fingerprint =
            "43530F91B450EDB269AA58821A1CF4DC7F500F04"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 39A479816C934B9E0464F1F4BC1DCFDEADA4EE90

        let dave_fpr: Fingerprint =
            "329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 43530F91B450EDB269AA58821A1CF4DC7F500F04

        let ellen_fpr: Fingerprint =
            "A7319A9B166AB530A5FBAC8AB43CA77F7C176AF4"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: 329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281

        let frank_fpr: Fingerprint =
            "2693237D2CED0BB68F118D78DC86A97CD2C819D9"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("simple.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rooted(
            &store, slice::from_ref(&alice_fpr)).build();

        eprintln!("{:?}", n);

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (100, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (100, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (100, &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[][..],
           None);

        // No one authenticated Bob's User ID on Carol's key.
        sp(&n, &carol_fpr, &bob_uid.clone(),
           &[][..],
           None);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (120, &[ &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (100, &[ &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (100, &[ &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[][..],
           None);

        // No one authenticated Bob's User ID on Carol's key.
        sp(&n, &carol_fpr, &bob_uid.clone(),
           &[][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn simple_gossip() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "39A479816C934B9E0464F1F4BC1DCFDEADA4EE90"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D

        let carol_fpr: Fingerprint =
            "43530F91B450EDB269AA58821A1CF4DC7F500F04"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 39A479816C934B9E0464F1F4BC1DCFDEADA4EE90

        let dave_fpr: Fingerprint =
            "329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 43530F91B450EDB269AA58821A1CF4DC7F500F04

        let ellen_fpr: Fingerprint =
            "A7319A9B166AB530A5FBAC8AB43CA77F7C176AF4"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: 329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281

        let frank_fpr: Fingerprint =
            "2693237D2CED0BB68F118D78DC86A97CD2C819D9"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("simple.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rooted(
            &store, slice::from_ref(&alice_fpr)).build();

        eprintln!("{:?}", n);

        gp(&n, &alice_fpr, &alice_uid.clone(),
           &[
               (120, &[ &alice_fpr ][..])
           ][..]);

        gp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (100, &[ &alice_fpr, &bob_fpr ][..]),
               (0, &[ &bob_fpr ][..]),
           ][..]);

        gp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (100, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
               (0, &[ &carol_fpr ][..]),
           ][..]);

        gp(&n, &dave_fpr, &dave_uid.clone(),
           &[
               (100, &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]),
               (0, &[ &dave_fpr ][..]),
           ][..]);

        gp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[
               (0, &[ &carol_fpr, &dave_fpr, &ellen_fpr ][..]),
               (0, &[ &ellen_fpr ][..]),
           ][..]);

        gp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (0, &[ &frank_fpr ][..]),
           ][..]);

        // No one authenticated Bob's User ID on Carol's key.
        gp(&n, &carol_fpr, &bob_uid.clone(),
           &[][..]);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();

        gp(&n, &alice_fpr, &alice_uid.clone(),
           &[
               (0, &[ &alice_fpr ][..]),
           ][..]);

        gp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (120, &[ &bob_fpr ][..]),
           ][..]);

        gp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (100, &[ &bob_fpr, &carol_fpr ][..]),
               (0, &[ &carol_fpr ][..]),
           ][..]);

        gp(&n, &dave_fpr, &dave_uid.clone(),
           &[
               (100, &[ &bob_fpr, &carol_fpr, &dave_fpr ][..]),
               (0, &[ &dave_fpr ][..]),
           ][..]);

        gp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[
               (0, &[ &carol_fpr, &dave_fpr, &ellen_fpr ][..]),
               (0, &[ &ellen_fpr ][..]),
           ][..]);

        gp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (0, &[ &frank_fpr ][..]),
           ][..]);

        // No one authenticated Bob's User ID on Carol's key.
        gp(&n, &carol_fpr, &bob_uid.clone(),
           &[][..]);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cycle() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "BFC5CA10FB55A4B790E2A1DBA5CFAB9A9E34E183"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "A637747DCF876A7F6C9149F74D47846E24A20C0B"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 4458062DC7388909CF760E6823150D8E4408638A
        // Certified by: BFC5CA10FB55A4B790E2A1DBA5CFAB9A9E34E183

        let carol_fpr: Fingerprint =
            "394B04774FDAB0CDBF4D6FFD7930EA0FB549E303"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: A637747DCF876A7F6C9149F74D47846E24A20C0B

        let dave_fpr: Fingerprint =
            "4458062DC7388909CF760E6823150D8E4408638A"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 394B04774FDAB0CDBF4D6FFD7930EA0FB549E303

        let ed_fpr: Fingerprint =
            "78C3814EFD16E68F4F1AB4B874E30AE11FFCFB1B"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 4458062DC7388909CF760E6823150D8E4408638A

        let frank_fpr: Fingerprint =
            "A6219FF753AEAE2DE8A74E8487977DD568A08237"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: 78C3814EFD16E68F4F1AB4B874E30AE11FFCFB1B


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cycle.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(
            &store, slice::from_ref(&alice_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (120,
                &[ &alice_fpr, &bob_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (90,
                &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &ed_fpr, &ed_uid.clone(),
           &[
               (30,
                &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr, &ed_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[][..],
           None);

        let n = NetworkBuilder::rooted(
            &store, &[ alice_fpr.clone(), dave_fpr.clone()  ]).build();


        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        // The following paths are identical and the sorting depends
        // on the fingerprint.  Thus regenerating the keys could
        // create a failure.
        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (120, &[ &alice_fpr, &bob_fpr ][..]),
               (120, &[ &dave_fpr, &bob_fpr ][..]),
           ][..],
           Some(300));

        // The following paths are identical and the sorting depends
        // on the fingerprint.  Thus regenerating the keys could
        // create a failure.
        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
           ][..],
           None);

        sp(&n, &ed_fpr, &ed_uid.clone(),
           &[
               (30,
                &[ &dave_fpr, &ed_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (30,
                &[ &dave_fpr, &ed_fpr, &frank_fpr ][..]
               )
           ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cliques() -> Result<()> {
        use std::time::Duration;

        let p = &StandardPolicy::new();

        let root_fpr: Fingerprint =
            "D2B0 C383 5C01 B0C1 20BC  540D A4AA 8F88 0BA5 12B5"
           .parse().expect("valid fingerprint");
        let root_uid
            = UserID::from("<root@example.org>");

        let a_0_fpr: Fingerprint =
            "3630 82E9 EEB2 2E50 AD30  3D8B 1BFE 9BA3 F4AB D40E"
           .parse().expect("valid fingerprint");
        let a_0_uid
            = UserID::from("<a-0@example.org>");

        let a_1_fpr: Fingerprint =
            "7974 C04E 8D5B 540D 23CD  4E62 DDFA 779D 91C6 9894"
           .parse().expect("valid fingerprint");
        let a_1_uid
            = UserID::from("<a-1@example.org>");

        let b_0_fpr: Fingerprint =
            "25D8 EAAB 8947 05BB 64D4  A6A8 9649 EF81 AEFE 5162"
           .parse().expect("valid fingerprint");
        let b_0_uid
            = UserID::from("<b-0@example.org>");

        let b_1_fpr: Fingerprint =
            "46D2 F5CE D9BD 3D63 A11D  DFEE 1BA0 1950 6BE6 7FBB"
           .parse().expect("valid fingerprint");
        let b_1_uid
            = UserID::from("<b-1@example.org>");

        let c_0_fpr: Fingerprint =
            "A0CD 8758 2C21 743C 0E30  637F 7FAD B1C3 FEFB FE59"
           .parse().expect("valid fingerprint");
        let c_0_uid
            = UserID::from("<c-0@example.org>");

        let c_1_fpr: Fingerprint =
            "5277 C14F 9D37 A0F4 D615  DD9C CDCC 1AC8 464C 8FE5"
           .parse().expect("valid fingerprint");
        let c_1_uid
            = UserID::from("<c-1@example.org>");

        let d_0_fpr: Fingerprint =
            "C24C C091 02D2 2E38 E839  3C55 1669 8256 1E14 0C03"
           .parse().expect("valid fingerprint");
        let d_0_uid
            = UserID::from("<d-0@example.org>");

        let d_1_fpr: Fingerprint =
            "7A80 DB53 30B7 D900 D5BD  1F82 EAD7 2FF7 9140 78B2"
           .parse().expect("valid fingerprint");
        let d_1_uid
            = UserID::from("<d-1@example.org>");

        let e_0_fpr: Fingerprint =
            "D1E9 F85C EF62 7169 9FBD  E5AB 26EF E0E0 35AC 522E"
           .parse().expect("valid fingerprint");
        let e_0_uid
            = UserID::from("<e-0@example.org>");

        let f_0_fpr: Fingerprint =
            "C0FF AEDE F092 8B18 1265  775A 222B 480E B43E 0AFF"
           .parse().expect("valid fingerprint");
        let f_0_uid
            = UserID::from("<f-0@example.org>");

        let target_fpr: Fingerprint =
            "CE22 ECD2 82F2 19AA 9959  8BA3 B58A 7DA6 1CA9 7F55"
           .parse().expect("valid fingerprint");
        let target_uid
            = UserID::from("<target@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        // Take the reference time from the root certificate, plus 1 year.
        let ref_cert = certs.iter()
            .find(|c| c.fingerprint() == root_fpr)
            .unwrap();
        let ref_time = ref_cert
            .primary_key()
            .key()
            .creation_time()
            .checked_add(Duration::from_secs(60 * 60 * 24 * 365))
            .unwrap();
        eprintln!("RefTime: {:?} taken from {}", ref_time, ref_cert.fingerprint());

        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, ref_time)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(
            &store, slice::from_ref(&root_fpr)).build();

        // root -> a-0 -> a-1 -> b-0 -> ... -> f-0 -> target
        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (120, &[
                   &root_fpr,
                   &a_0_fpr,
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ],
           None);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&a_1_fpr)).build();

        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (120, &[
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ][..],
           None);

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques-local-optima.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, ref_time)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&root_fpr)).build();

        // root -> b-0 -> ... -> f-0 -> target
        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (30, &[
                   &root_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..]),
               (30, &[
                   &root_fpr,
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..]),
               (60, &[
                   &root_fpr,
                   &a_0_fpr,
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ],
           None);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&a_1_fpr)).build();

        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (120, &[
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ][..],
           None);


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cliques-local-optima-2.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, ref_time)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&root_fpr)).build();

        // root -> b-0 -> ... -> f-0 -> target
        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (30, &[
                   &root_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..]),
               (30, &[
                   &root_fpr,
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..]),
               (60, &[
                   &root_fpr,
                   &a_0_fpr,
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ],
           None);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&a_1_fpr)).build();

        sp(&n, &target_fpr, &target_uid.clone(),
           &[
               (30, &[
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..]),
               (90, &[
                   &a_1_fpr,
                   &b_0_fpr,
                   &b_1_fpr,
                   &c_0_fpr,
                   &c_1_fpr,
                   &d_0_fpr,
                   &d_1_fpr,
                   &e_0_fpr,
                   &f_0_fpr,
                   &target_fpr
               ][..])
           ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn roundabout() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "41E9B069C96EB6D47525294B10BBBD00912BEA02"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "2E90AEE966DF28CB916439B20397E086E705AC1A"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 3267D46247D26101B3E5014CDF4F9BA5831D91DA
        // Certified by: 41E9B069C96EB6D47525294B10BBBD00912BEA02

        let carol_fpr: Fingerprint =
            "92DDE8747C8E6ED09D41A4E1330D1190E858754C"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 41E9B069C96EB6D47525294B10BBBD00912BEA02

        let dave_fpr: Fingerprint =
            "D4515E6619084ED8142DF8589059E3846A025611"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 92DDE8747C8E6ED09D41A4E1330D1190E858754C

        let elmar_fpr: Fingerprint =
            "E553C11DCFA777F3205E5090F5EE59C2795CDBA2"
           .parse().expect("valid fingerprint");
        let elmar_uid
            = UserID::from("<elmar@example.org>");
        // Certified by: AE40578962411356F9609CAA9C2447E61FFDBB15
        // Certified by: D4515E6619084ED8142DF8589059E3846A025611

        let frank_fpr: Fingerprint =
            "3267D46247D26101B3E5014CDF4F9BA5831D91DA"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: E553C11DCFA777F3205E5090F5EE59C2795CDBA2

        let george_fpr: Fingerprint =
            "CCD5DB27BD7C4F8E2010083605EF17E8A93EB652"
           .parse().expect("valid fingerprint");
        let george_uid
            = UserID::from("<george@example.org>");
        // Certified by: AE40578962411356F9609CAA9C2447E61FFDBB15
        // Certified by: 2E90AEE966DF28CB916439B20397E086E705AC1A

        let henry_fpr: Fingerprint =
            "7F62EF97091AE1FCB4E1C67EC8D9E94C4731529B"
           .parse().expect("valid fingerprint");
        let henry_uid
            = UserID::from("<henry@example.org>");
        // Certified by: CCD5DB27BD7C4F8E2010083605EF17E8A93EB652

        let isaac_fpr: Fingerprint =
            "32FD4D68B3227334CD0583E9FA0721F49D2F395D"
           .parse().expect("valid fingerprint");
        let isaac_uid
            = UserID::from("<isaac@example.org>");
        // Certified by: 7F62EF97091AE1FCB4E1C67EC8D9E94C4731529B

        let jenny_fpr: Fingerprint =
            "AE40578962411356F9609CAA9C2447E61FFDBB15"
           .parse().expect("valid fingerprint");
        let jenny_uid
            = UserID::from("<jenny@example.org>");

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("roundabout.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr ][..]
               ),
               (120,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr, &bob_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (120, &[ &alice_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (120, &[ &alice_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &elmar_fpr, &elmar_uid.clone(),
           &[ (120, &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr ][..]) ][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (120,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &george_fpr, &george_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &george_fpr ][..]
               ),
               (60,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr, &bob_fpr, &george_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &henry_fpr, &henry_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &george_fpr, &henry_fpr ][..]
               ),
               (60,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr, &bob_fpr, &george_fpr, &henry_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &isaac_fpr, &isaac_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &george_fpr, &henry_fpr, &isaac_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &jenny_fpr, &jenny_uid.clone(),
           &[ ][..],
           None);



        let n = NetworkBuilder::rooted(&store, slice::from_ref(&jenny_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr, &bob_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[][..],
           None);

        sp(&n, &elmar_fpr, &elmar_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &elmar_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &george_fpr, &george_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &george_fpr ][..]
               ),
               (100,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr, &bob_fpr, &george_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &henry_fpr, &henry_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &george_fpr, &henry_fpr ][..]
               ),
               (20,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr, &bob_fpr, &george_fpr, &henry_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &isaac_fpr, &isaac_uid.clone(),
           &[][..],
           None);

        sp(&n, &jenny_fpr, &jenny_uid.clone(),
           &[ (120, &[ &jenny_fpr ][..]) ][..],
           None);



        let n = NetworkBuilder::rooted(&store, &[ alice_fpr.clone(), jenny_fpr.clone() ]).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        // In the first iteration of backwards_propagate, we find two paths:
        //
        //   A -> B (60)
        //   J -> E -> F -> B (100)
        //
        // It doesn't find:
        //
        //   A -> C -> D -> E -> F -> B (120)
        //
        // Network::authenticate chooses the path rooted at J,
        // because it has more trust.  Then we call
        // backwards_propagate again and find:
        //
        //   A -> B (60)
        //
        // Finally, we call backwards a third time and find:
        //
        //   A -> C -> D -> E -> F -> B (120 -> 20)
        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr, &bob_fpr ][..]
                ),
               (60,
                &[ &alice_fpr, &bob_fpr ][..]
                ),
               (20,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr, &bob_fpr ][..]
                ),
           ][..],
           Some(240));

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (120, &[ &alice_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (120, &[ &alice_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &elmar_fpr, &elmar_uid.clone(),
           &[
               (120,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr ][..]
               ),
           ],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (120,
                &[ &alice_fpr, &carol_fpr, &dave_fpr, &elmar_fpr,
                    &frank_fpr ][..]
               ),
           ][..],
           Some(240));

        sp(&n, &george_fpr, &george_uid.clone(),
           &[
               (100,
                &[ &jenny_fpr, &george_fpr ][..]
               ),
               (100,
                &[ &jenny_fpr, &elmar_fpr, &frank_fpr, &bob_fpr, &george_fpr ][..]
               ),
               (20,
                &[ &alice_fpr, &bob_fpr, &george_fpr ][..]
               ),
           ][..],
           Some(240));

        sp(&n, &henry_fpr, &henry_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &george_fpr, &henry_fpr ][..]
               ),
               (60,
                &[ &jenny_fpr, &george_fpr, &henry_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &isaac_fpr, &isaac_uid.clone(),
           &[
               (60,
                &[ &alice_fpr, &bob_fpr, &george_fpr, &henry_fpr, &isaac_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &jenny_fpr, &jenny_uid.clone(),
           &[ (120, &[ &jenny_fpr ][..]) ][..],
           None);


        Ok(())
    }


    #[test]
    #[allow(unused)]
    fn local_optima() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8
        // Certified by: EAAE12F98D39F38BF0D1B4C5C46A428ADEFBB2F8

        let carol_fpr: Fingerprint =
            "E9DF94E389F529F8EF6AA223F6CC1F8544C0874D"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let dave_fpr: Fingerprint =
            "C2F822F17B68E946853A2DCFF55541D89F27F88B"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: E9DF94E389F529F8EF6AA223F6CC1F8544C0874D
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let ellen_fpr: Fingerprint =
            "70507A9058A57FEAE18CC3CE6A398AC9051D9CA8"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: C2F822F17B68E946853A2DCFF55541D89F27F88B
        // Certified by: C2F822F17B68E946853A2DCFF55541D89F27F88B
        // Certified by: E9DF94E389F529F8EF6AA223F6CC1F8544C0874D

        let francis_fpr: Fingerprint =
            "D8DDA78A2297CA3C35B9377577E8B54B9350C082"
           .parse().expect("valid fingerprint");
        let francis_uid
            = UserID::from("<francis@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8
        // Certified by: 89C7A9FB7236A77ABBE4F29CB8180FBF6382F90F

        let georgina_fpr: Fingerprint =
            "C5D1B22FEC75911A04E1A5DC75B66B994E70ADE2"
           .parse().expect("valid fingerprint");
        let georgina_uid
            = UserID::from("<georgina@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8

        let henry_fpr: Fingerprint =
            "F260739E3F755389EFC2FEE67F58AACB661D5120"
           .parse().expect("valid fingerprint");
        let henry_uid
            = UserID::from("<henry@example.org>");
        // Certified by: 70507A9058A57FEAE18CC3CE6A398AC9051D9CA8


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("local-optima.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (120,
                &[ &alice_fpr, &bob_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (100,
                &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[
               (50,
                &[ &alice_fpr, &bob_fpr, &dave_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[
               (100,
                &[ &alice_fpr, &bob_fpr, &carol_fpr, &ellen_fpr ][..]
               ),
               (20,
                &[ &alice_fpr, &bob_fpr, &dave_fpr, &ellen_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &francis_fpr, &francis_uid.clone(),
           &[
               (75,
                &[ &alice_fpr, &bob_fpr, &francis_fpr ][..]
               ),
               (45,
                &[ &alice_fpr, &bob_fpr, &carol_fpr, &ellen_fpr, &francis_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &georgina_fpr, &georgina_uid.clone(),
           &[
               (30,
                &[ &alice_fpr, &bob_fpr, &dave_fpr, &ellen_fpr, &georgina_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &henry_fpr, &henry_uid.clone(),
           &[
               (100,
                &[ &alice_fpr, &bob_fpr, &carol_fpr, &ellen_fpr, &henry_fpr ][..]
               ),
               (20,
                &[ &alice_fpr, &bob_fpr, &dave_fpr, &ellen_fpr, &henry_fpr ][..]
               ),
           ][..],
           None);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (120, &[ &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (100,
                &[ &bob_fpr, &carol_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[
               (50,
                &[ &bob_fpr, &dave_fpr ][..]
               )
           ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[
               (100,
                &[ &bob_fpr, &carol_fpr, &ellen_fpr ][..]
               ),
               (50,
                &[ &bob_fpr, &dave_fpr, &ellen_fpr ][..]
               ),
           ][..],
           None);

        sp(&n, &francis_fpr, &francis_uid.clone(),
           &[
               (75,
                &[ &bob_fpr, &francis_fpr ][..]
               ),
               (100,
                &[ &bob_fpr, &carol_fpr, &ellen_fpr, &francis_fpr ][..]
                ),
               (20,
                &[ &bob_fpr, &dave_fpr, &ellen_fpr, &francis_fpr ][..]
               ),
           ][..],
           Some(240));

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn multiple_userids_3() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "DA3CFC60BD4B8835702A66782C7A431946C12DF7"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "28C108707090FCDFF630D1E141FB02F0E397D55E"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@other.org>");
        // Certified by: DA3CFC60BD4B8835702A66782C7A431946C12DF7
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");
        // Certified by: DA3CFC60BD4B8835702A66782C7A431946C12DF7
        let bob_third_org_uid
            = UserID::from("<bob@third.org>");

        let carol_fpr: Fingerprint =
            "9FB1D2F41AB5C478378E728C8DD5A5A434EEAAB8"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 28C108707090FCDFF630D1E141FB02F0E397D55E

        let dave_fpr: Fingerprint =
            "0C131F8959F45D08B6136FDAAD2E16A26F73D48E"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 28C108707090FCDFF630D1E141FB02F0E397D55E

        let ed_fpr: Fingerprint =
            "296935FAE420CCCF3AEDCEC9232BFF0AE9A7E5DB"
           .parse().expect("valid fingerprint");
        let ed_uid
            = UserID::from("<ed@example.org>");
        // Certified by: 0C131F8959F45D08B6136FDAAD2E16A26F73D48E

        let frank_fpr: Fingerprint =
            "A72AA1B7D9D8CB04D988F1520A404E37A7766608"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");
        // Certified by: 9FB1D2F41AB5C478378E728C8DD5A5A434EEAAB8
        // Certified by: 296935FAE420CCCF3AEDCEC9232BFF0AE9A7E5DB

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("multiple-userids-3.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

        /// Tests.

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[
               (20, &[ &alice_fpr, &bob_fpr, &carol_fpr, &frank_fpr ][..]),
               (10, &[ &alice_fpr, &bob_fpr, &dave_fpr, &ed_fpr, &frank_fpr ][..]),
           ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn certification_liveness() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "77C077250C26357E5E64A58A41426350B1D7F738"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "840891562819D3A108C4DA1BB31438DE34F8CF69"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 77C077250C26357E5E64A58A41426350B1D7F738
        // Certified by: 77C077250C26357E5E64A58A41426350B1D7F738

        let carol_fpr: Fingerprint =
            "E8BB154D000C17AC87291D7271553C836973FE01"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 840891562819D3A108C4DA1BB31438DE34F8CF69
        // Certified by: 840891562819D3A108C4DA1BB31438DE34F8CF69

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("certification-liveness.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            sp(&n, &carol_fpr, &carol_uid.clone(),
               &[
                   (match i + 1 {
                       1 => 60,
                       2 => 120,
                       3 => 60,
                       _ => unreachable!(),
                   },
                   &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
               ][..],
               None);
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cert_revoked_soft() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "66037F98B444BBAFDFE98E871738DFAB86878262"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "4CD8737F76C2B897C4F058DBF28C47540FA2C3B3"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 66037F98B444BBAFDFE98E871738DFAB86878262

        let carol_fpr: Fingerprint =
            "AB4E3F8EE8BBD3459754D75ACE570F9B8C7DC75D"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 66037F98B444BBAFDFE98E871738DFAB86878262

        let dave_fpr: Fingerprint =
            "DF6A440ED9DE723B0EBC7F50E24FBB1B9FADC999"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 4CD8737F76C2B897C4F058DBF28C47540FA2C3B3
        // Certified by: AB4E3F8EE8BBD3459754D75ACE570F9B8C7DC75D
        // Certified by: 4CD8737F76C2B897C4F058DBF28C47540FA2C3B3

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cert-revoked-soft.pgp"))?
            .map(|c| c.expect("no errors"))
            .collect();

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        // At t1, soft revocations are in the future so certifications
        // are still valid.
        //
        // At t2, B is soft revoked so existing certifications are
        // still valid, but we can no longer authenticate B.
        //
        // At t3, A recertifies B and B recertifies D.  These
        // certifications should be ignored as they are made after B
        // was revoked.
        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            // Consider just the code path where B is the issuer.
            //
            // Covers scenarios #1 at t1, #3 at t2 and t3
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();
            sp(&n, &dave_fpr, &dave_uid.clone(),
               &[
                   (60, &[ &bob_fpr, &dave_fpr ][..]),
               ][..],
               None);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            // Consider just the code path where B is the target.
            //
            // Covers scenarios #2 at t1, #4 at t2 and t3.
            if i + 1 == 1 {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[
                       (90, &[ &alice_fpr, &bob_fpr ][..]),
                   ][..],
                   None);
            } else {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[][..],
                   None);
            }

            // Consider the code path where B is both an issuer and a
            // target.
            //
            // Covers scenarios #1 & #2 at t1, #3 & #4 at t2 and t3.
            sp(&n, &dave_fpr, &dave_uid.clone(),
               &[
                   (60, &[ &alice_fpr, &bob_fpr, &dave_fpr ][..]),
                   (30, &[ &alice_fpr, &carol_fpr, &dave_fpr ][..]),
               ][..],
               None);
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cert_revoked_hard() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "219AAB661C8AAF4526DBC31AA751A7A0532863BA"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "90E02BFB03FAA04714D1D3D87543157EF3B12BE9"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 219AAB661C8AAF4526DBC31AA751A7A0532863BA
        // Certified by: 219AAB661C8AAF4526DBC31AA751A7A0532863BA

        let carol_fpr: Fingerprint =
            "BF680710128E6BCCB2268154569F5F6BFB95C544"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 219AAB661C8AAF4526DBC31AA751A7A0532863BA

        let dave_fpr: Fingerprint =
            "46945292F8F643F0573AF71183F9C1A4759A16D6"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 90E02BFB03FAA04714D1D3D87543157EF3B12BE9
        // Certified by: BF680710128E6BCCB2268154569F5F6BFB95C544
        // Certified by: 90E02BFB03FAA04714D1D3D87543157EF3B12BE9


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cert-revoked-hard.pgp"))?
            .map(|c| c.expect("no errors"))
            .collect();

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        // At t1, B is hard revoked in the future so all
        // certifications are invalid.
        //
        // At t2, B is hard revoked so all certifications are invalid.
        //
        // At t3, A recertifies B and B recertifies D.  These
        // certifications should also be ignored.
        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            // Consider just the code path where B is the issuer.
            //
            // Covers scenarios #5 at t1, #7 at t2 and t3
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();
            sp(&n, &dave_fpr, &dave_uid.clone(),
               &[][..],
               None);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            // Consider just the code path where B is the target.
            //
            // Covers scenarios #6 at t1, #8 at t2 and t3.
            sp(&n, &bob_fpr, &bob_uid.clone(),
               &[][..],
               None);

            // Consider the code path where B is both an issuer and a
            // target.
            //
            // Covers scenarios #5 & #6 at t1, #7 & #8 at t2 and t3.
            sp(&n, &dave_fpr, &dave_uid.clone(),
               &[
                   (30, &[ &alice_fpr, &carol_fpr, &dave_fpr ][..]),
               ][..],
               None);
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn cert_expired() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "1FA62523FB7C06E71EEFB82BB5159F3FC3EB3AC9"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "B166B31AE5F95600B3F7184FE74C6CE62821686F"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 1FA62523FB7C06E71EEFB82BB5159F3FC3EB3AC9

        let carol_fpr: Fingerprint =
            "81CD118AC5BD9156DC113772626222D76ACDFFCF"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: B166B31AE5F95600B3F7184FE74C6CE62821686F

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("cert-expired.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            // Bob as target.  (Once Bob has expired it can be used as
            // a trusted introducer for prior certifications, but
            // bindings cannot be authenticated.)
            if i + 1 == 1 {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[ (60, &[ &alice_fpr, &bob_fpr ][..]) ][..],
                   None);
            } else {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[][..],
                   None);
            }

            // Bob in the middle.
            sp(&n, &carol_fpr, &carol_uid.clone(),
               & [ (60, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
               None);

            // Bob as root.
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();
            sp(&n, &carol_fpr, &carol_uid.clone(),
               & [ (60, &[ &bob_fpr, &carol_fpr ][..]) ][..],
               None);

            // Bob's self signature.
            if i + 1 == 1 {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   & [ (120, &[ &bob_fpr ][..]) ][..],
                   None);
            } else {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[][..],
                   None);
            }
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn userid_revoked() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "01672BB67E4B4047E5A4EC0A731CEA092C465FC8"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "EA479A77CD074458EAFE56B4861BF42FF490C581"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 01672BB67E4B4047E5A4EC0A731CEA092C465FC8
        // Certified by: 01672BB67E4B4047E5A4EC0A731CEA092C465FC8

        let carol_fpr: Fingerprint =
            "212873BB9C4CC49F8E5A6FEA78BC5397470BA7F0"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: EA479A77CD074458EAFE56B4861BF42FF490C581
        // Certified by: EA479A77CD074458EAFE56B4861BF42FF490C581

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("userid-revoked.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        // At t2, B is soft revoked so all future certifications are
        // invalid.
        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            // Revoked User ID on the root.
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();
            if i + 1 == 1 {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[ (120, &[ &bob_fpr ][..]), ][..],
                   None);
            } else {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[][..],
                   None);
            }

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            if i + 1 == 1 {
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[ (60, &[ &alice_fpr, &bob_fpr ][..]), ][..],
                   None);
            } else {
                // Can't authenticate binding with a revoked User ID.
                sp(&n, &bob_fpr, &bob_uid.clone(),
                   &[][..],
                   None);
            }

            // Can use a delegation even if the certification that it
            // is a part of has had its User ID revoked.
            if i + 1 < 3 {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[
                       (60, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
                   ][..],
                   None);
            } else {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[
                       (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
                   ][..],
                   None);
            }
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn certifications_revoked() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "817C2BE18D9FF48FFE58FF39B699FC21AD92EFDC"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "4258ACF6C3C8FCE130D6EBAB0CC5158AEA25F24A"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 817C2BE18D9FF48FFE58FF39B699FC21AD92EFDC
        // Certified by: 817C2BE18D9FF48FFE58FF39B699FC21AD92EFDC

        let carol_fpr: Fingerprint =
            "36766215FFD2FA000B0804BFF54577580DDC1741"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 4258ACF6C3C8FCE130D6EBAB0CC5158AEA25F24A

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("certification-revoked.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        /// Tests.

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);
        // $ date '+%s' -d 20200402
        // 1585778400
        let t3 = time::UNIX_EPOCH + time::Duration::new(1585778400, 0);

        for (i, t) in [t1, t2, t3].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            sp(&n, &alice_fpr, &alice_uid.clone(),
               &[ (120, &[&alice_fpr][..]), ][..],
               None);

            match i + 1 {
                1 => {
                    sp(&n, &bob_fpr, &bob_uid.clone(),
                       &[ (60, &[&alice_fpr, &bob_fpr][..]), ][..],
                       None);
                    sp(&n, &carol_fpr, &carol_uid.clone(),
                       &[ (60, &[&alice_fpr, &bob_fpr, &carol_fpr][..]), ][..],
                       None);
                }
                2 => {
                    sp(&n, &bob_fpr, &bob_uid.clone(),
                       &[][..],
                       None);
                    sp(&n, &carol_fpr, &carol_uid.clone(),
                       &[][..],
                       None);
                }
                3 => {
                    sp(&n, &bob_fpr, &bob_uid.clone(),
                       &[ (120, &[&alice_fpr, &bob_fpr][..]), ][..],
                       None);
                    sp(&n, &carol_fpr, &carol_uid.clone(),
                       &[ (120, &[&alice_fpr, &bob_fpr, &carol_fpr][..]), ][..],
                       None);
                }
                _ => unreachable!(),
            }

            // Alice, not Bob, revokes Bob's user id.  So when Bob is
            // the root, the self signature should still be good.
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();
            sp(&n, &bob_fpr, &bob_uid.clone(),
               &[ (120, &[&bob_fpr][..]), ][..],
               None);
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn infinity_and_beyond() -> Result<()> {
        let p = &StandardPolicy::new();

        let u1_fpr: Fingerprint =
            "B557862780A97676CC32F4BB1491A9C2BDE6F1DC"
           .parse().expect("valid fingerprint");
        let u1_uid
            = UserID::from("<u1@example.org>");

        let u260_fpr: Fingerprint =
            "B69A678AA242FA4F0BBF12205C0608799B0E3C51"
           .parse().expect("valid fingerprint");
        let u260_uid
            = UserID::from("<u260@example.org>");

        let u254_fpr: Fingerprint =
            "AF097DA4DB5C0E2116EF583B25A6B381B621C082"
           .parse().expect("valid fingerprint");
        let u254_uid
            = UserID::from("<u254@example.org>");

        let fprs: [&Fingerprint; 260] = [
            &"B557862780A97676CC32F4BB1491A9C2BDE6F1DC".parse().unwrap(),
            &"0618F850B6D0C48DBF406BBFAB3DAED809A35F78".parse().unwrap(),
            &"70B0C5FEFFE6B55F2CEE85455621246D16D6785E".parse().unwrap(),
            &"EC4475DE5BD76EA7DD4798777E9C990C249738B1".parse().unwrap(),
            &"FB00C7044A9DD164243CEC460B48AA8ADD29A129".parse().unwrap(),
            &"7DCB823AB1B33C6D22FC84AC3026DA74AEEB4A6E".parse().unwrap(),
            &"0058DCF7A7C6C4360DE9095DB6F33843D961E818".parse().unwrap(),
            &"D0BF1856B95A62763DE49088CE6FF96D17E0EAF0".parse().unwrap(),
            &"7F945244A20A74E1BA50BE73E917BC24D2D53F79".parse().unwrap(),
            &"12C92685CA2A867B93FD79762B2D56CF0B94304E".parse().unwrap(),
            &"02B1DB86B6869BCF92C0F74312D1A5F22E128F18".parse().unwrap(),
            &"9C8245F2DD06E4A2FE21FB1643A9663DDF7DF168".parse().unwrap(),
            &"CB7C6D3FCBB8DA0B3D7F6EC0DD193A96517579DC".parse().unwrap(),
            &"66D0F95325D4A02A36C14265FD247584CCA3C8BA".parse().unwrap(),
            &"291ABB75D735BC5B625E221B021152DF0CA1F86A".parse().unwrap(),
            &"27DF659AEE573E30D3A65B6E43474D9A4CA64DE3".parse().unwrap(),
            &"591492CAF51C06516278723EAFB9AF2643B89A3A".parse().unwrap(),
            &"20B481FFB7B72F6781BA49806C8E35B5C79A3E41".parse().unwrap(),
            &"270E3D9E87CA0999D422CD22F905BF87E8F60A36".parse().unwrap(),
            &"192124BD42BA6BF54A8820FB94B6B70D818241E3".parse().unwrap(),
            &"07C1D93539328F97517C59D27ABC3071DB73A790".parse().unwrap(),
            &"A915D1BA3F066E989B965ADFA27CC8D161C0F48A".parse().unwrap(),
            &"D968AFB7EAF13E04BB71D96100CC514119C8303E".parse().unwrap(),
            &"A62F988F2896A0286F92F8B8201E7737D11D7039".parse().unwrap(),
            &"9BF8933FCA5306F567F5F5750CE3375AFA9398A1".parse().unwrap(),
            &"5EC7400A739E579B704E618809345EF1045B304A".parse().unwrap(),
            &"2C7B74D1388CE0F2C4002CE41EAD11DBB281472A".parse().unwrap(),
            &"C18D79710A68696E972B0F321E6DE596CD08B4FD".parse().unwrap(),
            &"C1B1150980254353538D9CC5A91187FE2DBD51FF".parse().unwrap(),
            &"4FD94C288F39C4633FBBD120BF1A1C6B6789F983".parse().unwrap(),
            &"DE70A745F098EBCC45B4A3B25D0195EC3C6E0D65".parse().unwrap(),
            &"44350591F20A4069F131156283AABF91FE4AE5EF".parse().unwrap(),
            &"76E9D213C5F67F2DBE410F57DF3F9BB9622AAFC7".parse().unwrap(),
            &"A48F536C34D4A493CD233870C05B675B873B139D".parse().unwrap(),
            &"7C3FEDFAB082D236A9181B8E2B6483A582756C6E".parse().unwrap(),
            &"0FDFAF64606B6C72BF1C940D24F80C95D5B8310E".parse().unwrap(),
            &"6B5A25C2DD40AE58272FB17D15C33EF13B9D7FE8".parse().unwrap(),
            &"3814E465DDDCDB7F352E513D9C34D38E08A4360A".parse().unwrap(),
            &"2BF243991E5B6444861FC662E93888456D33F149".parse().unwrap(),
            &"124760101EF948B0E9EC24D9326FFEBD505BE4D3".parse().unwrap(),
            &"074E083627D1ED618486FB18865EA7123912BE53".parse().unwrap(),
            &"955B6A60E5EA85BADD68B1E08AF3E45D3AB93DE9".parse().unwrap(),
            &"857B9C8DCF9EBD72556237A40E652DDF8101E2D0".parse().unwrap(),
            &"FA11A49DA2E22F686471A4343E6A36C53F7C2155".parse().unwrap(),
            &"90DF0E04097EBFD295E05B9F40BE700A2E8D0995".parse().unwrap(),
            &"90BA919C17ED4252F8F0ED327192D79A112A0CE6".parse().unwrap(),
            &"3762EB478F47FEA848ADA9E1611C433D28D84071".parse().unwrap(),
            &"E960CD893E6CF7F41E752BEF15ED83ECDF49463C".parse().unwrap(),
            &"B1256D987F2789601FC5D8FAF268AB5F6AB44782".parse().unwrap(),
            &"5EE4B68A4828F5C15DD87114DC4A8509993DCFAB".parse().unwrap(),
            &"5C472E1C68A9A587C2AF9F00BC59B13A9918BBC1".parse().unwrap(),
            &"5320428600FCDB9A3AA32DA3E14D0128D7C372EC".parse().unwrap(),
            &"41958AAE8E1EED80B680F4DCD5ABFA33A1DB1C23".parse().unwrap(),
            &"7F4DFF6FC276995C94C2BF92146B7BED38209DB9".parse().unwrap(),
            &"6DE33C3735906B7E69AE593A0CD724AF410A89CE".parse().unwrap(),
            &"70F56B5B0EA57CB9ACDEB08B5333D900488A16B1".parse().unwrap(),
            &"02C9977BFF7BA0295AF671AA31894E2CD88A0F0D".parse().unwrap(),
            &"81FF106638ACE77B0C1039D5E69BCC93690A6B8D".parse().unwrap(),
            &"136368A84C7E56A86515ACC6DCD0744ABE10225D".parse().unwrap(),
            &"2B5E1D94813CED1CD63A3F28FEF343EA790E2333".parse().unwrap(),
            &"680ADF1182D00512D298417C6DBFC9084BFDB79D".parse().unwrap(),
            &"17DFBFB2149AB4A82B1DE5E5AE63FBDCE6874162".parse().unwrap(),
            &"2FD6D0F680B55F9AF128DBCBA4C71E44F433B728".parse().unwrap(),
            &"26551C85DBFDDEA97B7E7A0068DBDE9E792A7A49".parse().unwrap(),
            &"341BB68A3695B3D9EE307D7794317B145CEFCB60".parse().unwrap(),
            &"2E65A5B2F70D16D5D4D0664D360AE9BD58C555C1".parse().unwrap(),
            &"DEE7D3162919AC8AC9592051BFACF193B344DEF1".parse().unwrap(),
            &"2A8CE469DD783B95C92A6F3294A5A609AA679F71".parse().unwrap(),
            &"8A9FE07B40482C5559A6770B57B79188B52BD346".parse().unwrap(),
            &"6993EE3E5C4653A03EACBEC25604E4A55B4F75AB".parse().unwrap(),
            &"66DF2690FEAC606C285AA4D986376ACD1964BE48".parse().unwrap(),
            &"29FD7B1C6B29663CFA64306670E67F3E7F6FBCD4".parse().unwrap(),
            &"2C6E7C99DE5F5922E05D11D235C2E562CC528E76".parse().unwrap(),
            &"88E99AC4D5CB6ACF3CD396D5D6AA9961B4F938AB".parse().unwrap(),
            &"4471A85059215D231D47B1D4A109C3F0B6BDB258".parse().unwrap(),
            &"2C755244C6B83CAA7E48BD234C7FDB8645611B3B".parse().unwrap(),
            &"9C015FEBD3D19A81716E7700052058B47F889611".parse().unwrap(),
            &"9014E514D677C2ED19D93329C1485FE55F1C72D6".parse().unwrap(),
            &"343F2C6F9DB8F9EE4E59F5C0886BAE56FA55CE26".parse().unwrap(),
            &"13C37CE8ED0ACC92CF61808755241D6DA1633FA4".parse().unwrap(),
            &"ED5C07A820DCB2AA6DAFDE9C8562765D88A4BB36".parse().unwrap(),
            &"21655669D7B36A2EB5007B31442FCE197ADCC8D8".parse().unwrap(),
            &"CD220E58B30D2D1CBBC5B921555C92A70B303860".parse().unwrap(),
            &"5FF5C8CBD8D670565B300519887E3ED2F9E0DDA9".parse().unwrap(),
            &"B47FF2EF9DEB08C7FC55532C746F0F2DB723C462".parse().unwrap(),
            &"F8F8F30931EEB93C2FDE9363F9EE328402F33860".parse().unwrap(),
            &"3714D9CB0A8A0B4EE695B21AB052CAE69A2A7689".parse().unwrap(),
            &"FF093E66CCFB8804193115058643E0CB52C5A793".parse().unwrap(),
            &"0A5553209858B36F3EA0EFA463FD6758FF116167".parse().unwrap(),
            &"D9C06C9D100813BEBD35427DF65F7634EB2EAD6A".parse().unwrap(),
            &"05CA2D388297E826B9C3B431A8B15D93895257F9".parse().unwrap(),
            &"BF79DD51D462180014D2AD71D2462BE4CF36F625".parse().unwrap(),
            &"FC0DE4AD683BE64F47E8642F7472D7BB781E5C76".parse().unwrap(),
            &"F1FE09936F39A4E7A907D909CDFA4993BE4124AF".parse().unwrap(),
            &"465CD9AD11B5003A48BB28118DB2CEBD29D4F603".parse().unwrap(),
            &"9DF99BDB7078BE13CE3F66D97F212BF669F995C6".parse().unwrap(),
            &"57071A60EFBBFFA6DDCE7796F14A1B2C681A8A83".parse().unwrap(),
            &"8AB11E4F18DC57F2BA400B8D7B5FD8990C1CCAC5".parse().unwrap(),
            &"286EC5D4E5D1D136E54C996FE2D9E350B7CF3D8A".parse().unwrap(),
            &"AF87AF1183FB3E9370D509CE4E255380D5F3A8D5".parse().unwrap(),
            &"036F0956E3436BB10D030C89241EB37A3E931678".parse().unwrap(),
            &"33C2757572312304682BDD62C46C67D099B92680".parse().unwrap(),
            &"47A458ECE5784E7AF11C2286AA75FA9B8401E257".parse().unwrap(),
            &"43950C8B0B46693E9E48676637A98A31CF4B62AD".parse().unwrap(),
            &"A881411005DCCA6AF01331438783D3432031442F".parse().unwrap(),
            &"AA96AB4A6A98A839676621E66E756674E8DE55F3".parse().unwrap(),
            &"6844B0D8AB1D74A5766311157F652BC182F0875D".parse().unwrap(),
            &"B6F83FFF8B788418D48C11FA084D0F3AC9A2AECD".parse().unwrap(),
            &"99B269CFF458C780108B370C7A3F523A4DD62521".parse().unwrap(),
            &"48ADBA117B6D38703248D7AE72FB58B9E9798B7E".parse().unwrap(),
            &"FBC503FCBE4143C984E88358E700E23D4F573CCF".parse().unwrap(),
            &"E249A634759A417A040615736E200525AAF6F629".parse().unwrap(),
            &"BC782C4357D9E72075AF3DBF2C2FCAB09C09C252".parse().unwrap(),
            &"7B47E68EFB03A0C8346BD80E4A2FA75B6488D6D3".parse().unwrap(),
            &"DC2807A9E1CCD83B797A1EB2829D1F4641E0DB9B".parse().unwrap(),
            &"33C7585C640E74974790F349F64B2668DF09DE8E".parse().unwrap(),
            &"C766141BA6C7998C7EE40DE116FB427F2C57657F".parse().unwrap(),
            &"D0DF7D293426D9451E9EE0FD03A4D8196D10976D".parse().unwrap(),
            &"D56E5DB01CFAAD99697B33163B81D229170F58B4".parse().unwrap(),
            &"97D592FDE6199E3A4F6B437F40B34142AA67397B".parse().unwrap(),
            &"8C19F12A8386D0EF3FC0AFD28D7FE8D90F070EFB".parse().unwrap(),
            &"5B87566BAA2C8EC78C7D44594F21D5ABA36767F2".parse().unwrap(),
            &"53AB6BCCE1111DCD151E66625F52509FC67F4076".parse().unwrap(),
            &"318DA1A8A8E92698EAAC0AB468406FF3D0B6733A".parse().unwrap(),
            &"350068CCCD295D7EB80C6A97060FCBD15175ADB2".parse().unwrap(),
            &"3A7DF039CCCA3B3C9286B01619D8EA302427C910".parse().unwrap(),
            &"3C964F3E9C57330753EE5923B49FC01974400307".parse().unwrap(),
            &"4E9E5E2E1A868706DAADFD5A362C66828E5E4621".parse().unwrap(),
            &"36328DA9EAC85DB46843FA168A4AA6C4B47ADE22".parse().unwrap(),
            &"0AB20633A6D636B80337EFE3403702D89A3CD852".parse().unwrap(),
            &"8CDF07D3CEA5ED1B72ECD8869CA0A447943C1F3B".parse().unwrap(),
            &"E052363BDCA7BB374570774F9EE1EA2E8BF88026".parse().unwrap(),
            &"6603EA823BC641A465D8E5C45EDAD32360EDFC6A".parse().unwrap(),
            &"7D2E0E09E14B5BAB084A268786B0C6357215757B".parse().unwrap(),
            &"44F5446DBE64118D55D007453C6EF4840B47CD82".parse().unwrap(),
            &"419FA3D74A917B54F53AF2157B81A4A67CBA27F0".parse().unwrap(),
            &"36EB37E159817A86D0D4F506A3DDF317DFEDF32F".parse().unwrap(),
            &"9F5918BE6A7898670283859B05280E0DDA09EC95".parse().unwrap(),
            &"24EFDB2253318E11B73B617C6A7C5DC8792A2A55".parse().unwrap(),
            &"4AF832B3208DB3DD126C21E3CAF4AA3126156F8B".parse().unwrap(),
            &"E00EE6E5D079CA81E37F964EAD799F4D59738D54".parse().unwrap(),
            &"5A962B09EF649F4267DFDAE046B2F28E5134573F".parse().unwrap(),
            &"BAB9FB2EC409E68165AEF78D58BB96EB511C41B2".parse().unwrap(),
            &"ADD6E345227F27489E1E8AA7E0CD788437CC47BF".parse().unwrap(),
            &"BCD1FB9A7524E6B2D1ADB920653E81204C30A119".parse().unwrap(),
            &"17DE4392A165DC82CF50E879B5CB17B550CC0DE2".parse().unwrap(),
            &"5E9C128259B95B3C90C651E3E106A3276D83FFD1".parse().unwrap(),
            &"837B524C48C821FB23C4331A764076A4958D02E6".parse().unwrap(),
            &"1DBFA683F2744FCCFCF46D35989519FEB16FB4B1".parse().unwrap(),
            &"16561C850378BDB387F6E620B261465512DF841D".parse().unwrap(),
            &"40903D9038604F9F0325F4F595735AB9651D3899".parse().unwrap(),
            &"542CE462E1A66CEECDE4A15E3B614535DCA71EEF".parse().unwrap(),
            &"91FE56BE25CCB3CF5439DFAAC42E3BADAAFA919A".parse().unwrap(),
            &"0EBD96F41958B13F8F69B5FFD95B370820AE2176".parse().unwrap(),
            &"FE6500EC3768698238FA02AE836FE5675367B4F9".parse().unwrap(),
            &"34E96CA46093CDFC25ACE6A3A2FE701D926F093A".parse().unwrap(),
            &"45046E989B2E1B90A1DAEB5ADB7580D1B78D3BC6".parse().unwrap(),
            &"64A9859344F5073B183BD5C8AA60941E63199D9D".parse().unwrap(),
            &"729EDA4A2A634E776780E1847CA24E9550F7D0A7".parse().unwrap(),
            &"8844DCA493E8F20107CB447191FEA3BD4C01890B".parse().unwrap(),
            &"F965044BE1E7300C7B6716E293C396B4FA94CD92".parse().unwrap(),
            &"BC007EC19B0BC8DDE59847B09EA70EB3222D9E51".parse().unwrap(),
            &"B333A058F7209C46F2D027BB03738EAAC50701ED".parse().unwrap(),
            &"A9A1A3B0F12233D6120809D6F8F0C11D96152693".parse().unwrap(),
            &"2BFE10D7FEE9E5DF5833B6F61B584BAB2FD86575".parse().unwrap(),
            &"E5F3B17D545521F9B5395B10E92020FDB3E8109E".parse().unwrap(),
            &"58035C57B66B0EBFB069F9B7F3C623A5C52A3B92".parse().unwrap(),
            &"003E9C5A9DAB8626FD1694AAC2C43642A20E1496".parse().unwrap(),
            &"E7947E382B12FE628BDA130201EFC9D900B5540C".parse().unwrap(),
            &"17B55B1078D282C73FA2E76287FAB537AEAFE66C".parse().unwrap(),
            &"27CE83D68C669FE4F1B8C938D4A919E6F59E4D0B".parse().unwrap(),
            &"86B1E98692F4CA34122012C1524B4079CF57E850".parse().unwrap(),
            &"5B8A8AC5213064AE84C97DE41ED4BF239D9C10F2".parse().unwrap(),
            &"3FEAB08FC63829C080412CBFC6D3836C6E817789".parse().unwrap(),
            &"231605AEE34762F3BBC8ECF73808EFA9258837F8".parse().unwrap(),
            &"AE2759F4EC850FA6CE98FA4729FD82649411B973".parse().unwrap(),
            &"E7529E3567F59BBCADAAD1246613DBC86DAD45F8".parse().unwrap(),
            &"CF320590351A8C41C9EA0C1F4C6F00F7AEA73AD5".parse().unwrap(),
            &"475A44091578C02A0C5C2D62F106918D87E15476".parse().unwrap(),
            &"5B88BF2E7163D0594CE0E302C2AD0FE43D473EFE".parse().unwrap(),
            &"E4ADA4F5D702AD510C2F7A19316950AD7429C1FA".parse().unwrap(),
            &"6D6B846B8661F1013E7BC8D64C7280F7DF9DA6E6".parse().unwrap(),
            &"49883F6CA68B9F452F2A5F2F04687A6078E00FBF".parse().unwrap(),
            &"3046B5075B9DAF5645F51717D01AB61342900011".parse().unwrap(),
            &"16213F8B540AC28FE0CB3548D84F0D748AC23379".parse().unwrap(),
            &"9C68E98198FF9964FA2366ADCBAD3A465C76396B".parse().unwrap(),
            &"6EC3A10AA0B6B70DC5408CAE74B0BE836FD382D6".parse().unwrap(),
            &"E25E062BE69B48D3B99A96086991D15CA7370F0C".parse().unwrap(),
            &"A01A30A1AB191AF9C148C3704F4582E27D8D7527".parse().unwrap(),
            &"5D33551903E14FAABF75E9ECFB7AE6C2AC9959FB".parse().unwrap(),
            &"B37AE84FB0B4226FB935A3090F7C543F95A21EEF".parse().unwrap(),
            &"65B2CD9E6A6F6A36496B54A285F9BA4B68AA5174".parse().unwrap(),
            &"C0AA5CFC45580335A785DC2B3F9EE769EAAFE70D".parse().unwrap(),
            &"09973DF6334673259B774B840B1496371FDC2BE6".parse().unwrap(),
            &"29AAA5AF7CF941F4307DE966BD9E690D59FE5383".parse().unwrap(),
            &"9BDA50D8A6C78525051AAE07CC26594022C7D4AE".parse().unwrap(),
            &"2B0B6FDB04B9E8FF3A31EBE16A6B0A72A6571C45".parse().unwrap(),
            &"5C2650D8DA9842951614026288805244633C686B".parse().unwrap(),
            &"EEA6502B34AB08FA2F3BDA1E355AC29B6D8B67FA".parse().unwrap(),
            &"61B00DCDC02069F46F20D7F91075929DC6DA674C".parse().unwrap(),
            &"A1F5307F398FA45ECFC68CA92A5FC888D2DD2728".parse().unwrap(),
            &"AB0ADD3BF024EB6C75D9A366ABE69FC6E9F60DA0".parse().unwrap(),
            &"20DFEEF42F418CCEB02DB3E896E40B0413F1B4C5".parse().unwrap(),
            &"59C4E41C31D1E16F11BCF51304E7B81D67AD1FA0".parse().unwrap(),
            &"C0A3A190F8BFB6115A87CF7CBEC9211A2E210C86".parse().unwrap(),
            &"8932D417D3C0C4E3694E90480B92349F276E4EE0".parse().unwrap(),
            &"5BE288B0F7DCD89200D112D009E73AB06030B4EB".parse().unwrap(),
            &"CF472156042D6F2032BC025B68544E0A5844F3A7".parse().unwrap(),
            &"D54401DBBDE32805DAF08C4E1177C10E27F7D235".parse().unwrap(),
            &"56100D18E943687F7CFBC3CB20479A11B7DD5E1D".parse().unwrap(),
            &"9349703A779BD3725C5C822E21DA8172102EC4CD".parse().unwrap(),
            &"5DCAAB77198D13785C340D7B375DD44D815A0481".parse().unwrap(),
            &"5959CAC7EB9C1C7D9ECF10B8C023ED12A0F7F556".parse().unwrap(),
            &"7D4EA25C4F364AF1B61B64164816D289775352A8".parse().unwrap(),
            &"84291C882E059C5100C5C1AD1746298F01E7D682".parse().unwrap(),
            &"F3A95472FDB65D965EC2C4E3D22BD567B60BE41E".parse().unwrap(),
            &"0B9B18FB07F29E89D33AA0A86ED47AC9E7B86518".parse().unwrap(),
            &"2A11B65832E97E65DAA69D690C304130A843F532".parse().unwrap(),
            &"BB1B2F93AE4C4D41B4385AB653A4193345AA17C7".parse().unwrap(),
            &"4B526E27DAA41961F9D89404ED2F25E650D82444".parse().unwrap(),
            &"8DC51F77AEFAE450554792A0C704999EF5D32A6B".parse().unwrap(),
            &"ACD80C31E49FEAF9AA07DBD9FA96E7E857A694DE".parse().unwrap(),
            &"F2A4AE3ABC6DE0475E22B836DB0B8264BE496577".parse().unwrap(),
            &"14AA7B5B7D9088CBBD5FF8CB95F34513BA887EC0".parse().unwrap(),
            &"185A81E45751F6322490BE7987DDCD2A02E38D38".parse().unwrap(),
            &"BFCC758F6B567FF489801B539ED707902064CF71".parse().unwrap(),
            &"6F80DC80D1F4C14810750CAF51FAB910F100F6AB".parse().unwrap(),
            &"D220EB0F833DB97983F221D902D45679E35E555A".parse().unwrap(),
            &"6F757C636ED4E157D6F6570DBC03D6A8FCC6CD68".parse().unwrap(),
            &"C0C4B2D29A88A8F042FB13422605B3290364FF74".parse().unwrap(),
            &"23EBA00A8576434AE4B077F9819A1B623B2E138C".parse().unwrap(),
            &"88C18A2D51339461068DDF72693871FAF6FFC6FF".parse().unwrap(),
            &"CDA5DE7236C247F0D116CC0A1A25910D0CD909C0".parse().unwrap(),
            &"E405060228D49BA43C6ED9A3E25ADFDCC0012F48".parse().unwrap(),
            &"575DB527D78D5A063AB4197891DB2946F8EE3A8C".parse().unwrap(),
            &"D4BBE60FCA2FC7850FF7309102DEF04D111BA114".parse().unwrap(),
            &"97794BE1FD5729470D049D86BE16BB8E38D6D8EB".parse().unwrap(),
            &"4C011F0F9E4C58022DBD2E1FAA549F086FB77001".parse().unwrap(),
            &"950D06C53390F94AF59A15609900DA7A91A638CF".parse().unwrap(),
            &"013B231F139A46312550BBCBC52451FDB72285FC".parse().unwrap(),
            &"A814BA237B27B4605C71A907B8A8D55FC49CB5E6".parse().unwrap(),
            &"A3AE147DBC887FA325852A4DC3FFE143772A8587".parse().unwrap(),
            &"4D88E9B314F4ECAF99E02611C985FD350408C791".parse().unwrap(),
            &"CE9A27BE12483A5F094F85330E51D13DC2830B24".parse().unwrap(),
            &"B6565ADDD563FDD720D05411CD3449BD50892312".parse().unwrap(),
            &"F1EBB0F94C08A777867F403E9FAFBE3A10228952".parse().unwrap(),
            &"94D627E627E15F9B9144457816A736F442FD6A6F".parse().unwrap(),
            &"B3B1CDB5875CD8725B5FC915B1ED7C0FCE7721EE".parse().unwrap(),
            &"9E80CD683AA01265FE25DF265DADCE433039185C".parse().unwrap(),
            &"AFDE99A008E9BC761DFA6367C984AF52546308CF".parse().unwrap(),
            &"364854C36A1EFFDCAC7B80296A8F683B48BC5F33".parse().unwrap(),
            &"77C3730DB611591E71EE4528A15EE7D5EF32333F".parse().unwrap(),
            &"138CC2085B1A06F02DE1946D5FB391D63C886EE6".parse().unwrap(),
            &"AF097DA4DB5C0E2116EF583B25A6B381B621C082".parse().unwrap(),
            &"02DF6CB2758D7695940B6937804CAD30CDAC243C".parse().unwrap(),
            &"7F7C33899D1A34BE0D2B3C1C3B8F983DFABA03B4".parse().unwrap(),
            &"041549DBA90F2C4EB9E22505B4515224EB745A2C".parse().unwrap(),
            &"B73206C4F70E0735E9288128BAC3400233738122".parse().unwrap(),
            &"FCDF4C1D67ACFA8B42F6A77C408A9CB7367171C2".parse().unwrap(),
            &"B69A678AA242FA4F0BBF12205C0608799B0E3C51".parse().unwrap(),
        ];

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("infinity-and-beyond.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, slice::from_ref(&u1_fpr)).build();

        /// Tests.

        // This should always work.
        sp(&n, &u254_fpr, &u254_uid.clone(),
           &[ (120, &fprs[0..254]), ][..],
           None);

        // This tests that depth=255 really means infinity.
        sp(&n, &u260_fpr, &u260_uid.clone(),
           &[ (120, &fprs[..]), ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn zero_trust() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "931E51F99B89649783A1DFF265266E28246040C2"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "A1042B157AFA71F005208D645915549D8D21A97B"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 931E51F99B89649783A1DFF265266E28246040C2
        // Certified by: 931E51F99B89649783A1DFF265266E28246040C2

        let carol_fpr: Fingerprint =
            "E06DB0539D99759681D7EC8508A267AE8FA838F4"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: A1042B157AFA71F005208D645915549D8D21A97B

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("zero-trust.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        /// Tests.

        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);
        // $ date '+%s' -d 20200302
        // 1583103600
        let t2 = time::UNIX_EPOCH + time::Duration::new(1583103600, 0);

        // At t2, B is certified with a trust amount of 0.  This
        // should eliminate the path.
        for (i, t) in [t1, t2].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr)).build();

            if i + 1 == 1 {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[ (60, &[&alice_fpr, &bob_fpr, &carol_fpr][..]), ][..],
                   None);
            } else {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[][..],
                   None);
            }

            // Start with bob and make sure that a certification by a
            // root with a 0 trust amount is also respected.
            let n = NetworkBuilder::rooted(&store, slice::from_ref(&bob_fpr)).build();

            if i + 1 == 1 {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[ (60, &[&bob_fpr, &carol_fpr][..]), ][..],
                   None);
            } else {
                sp(&n, &carol_fpr, &carol_uid.clone(),
                   &[][..],
                   None);
            }
        }

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn partially_trusted_roots() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "39A479816C934B9E0464F1F4BC1DCFDEADA4EE90"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D

        let carol_fpr: Fingerprint =
            "43530F91B450EDB269AA58821A1CF4DC7F500F04"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 39A479816C934B9E0464F1F4BC1DCFDEADA4EE90

        let dave_fpr: Fingerprint =
            "329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 43530F91B450EDB269AA58821A1CF4DC7F500F04

        let ellen_fpr: Fingerprint =
            "A7319A9B166AB530A5FBAC8AB43CA77F7C176AF4"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: 329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281

        let frank_fpr: Fingerprint =
            "2693237D2CED0BB68F118D78DC86A97CD2C819D9"
           .parse().expect("valid fingerprint");
        let frank_uid
            = UserID::from("<frank@example.org>");


        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("simple.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        let n = NetworkBuilder::rooted(&store, &[ (alice_fpr.clone(), 90) ])
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        sp(&n, &frank_fpr, &frank_uid.clone(),
           &[][..],
           None);

        // No one authenticated Bob's User ID on Carol's key.
        sp(&n, &carol_fpr, &bob_uid.clone(),
           &[][..],
           None);

        // Multiple partially trusted roots.  Check that together they
        // can fully certify a self signature.
        let n = NetworkBuilder::rooted(
            &store,
            &[
                (alice_fpr.clone(), 90),
                (bob_fpr.clone(), 90)
            ])
            .build();


        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (90, &[ &bob_fpr ][..]),
               (90, &[ &alice_fpr, &bob_fpr ][..]),
           ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn self_signed() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "838454E0D61D046300B408A908A4FDB4F368ECB9"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "7A7B5DE6C8F464CAB78BEFB9CE14BEE51D4DEC01"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 838454E0D61D046300B408A908A4FDB4F368ECB9

        let carol_fpr: Fingerprint =
            "830230061426EE99A0455E6ADA869CF879A5630D"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 7A7B5DE6C8F464CAB78BEFB9CE14BEE51D4DEC01
        let carol_other_org_uid
            = UserID::from("<carol@other.org>");

        let dave_fpr: Fingerprint =
            "51A5E15F87AC6ECAFBEA930FA5F30AF6EB6EF14A"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 830230061426EE99A0455E6ADA869CF879A5630D

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("self-signed.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        /// Tests.

        let n = NetworkBuilder::rooted(
            &store,
            &[
                (alice_fpr.clone(), 120),
            ])
            .build();

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (100, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_other_org_uid.clone(),
           &[][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[][..],
           None);

        let n = NetworkBuilder::rooted(
            &store,
            &[
                (bob_fpr.clone(), 120),
            ])
            .build();

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (120, &[ &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_other_org_uid.clone(),
           &[ (90, &[ &bob_fpr, &carol_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (90, &[ &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        Ok(())
    }

    #[test]
    #[allow(unused)]
    fn isolated_root() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "DCF3020AAB76ECC7F0E5AC0D375DCE1BEE264B87"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");
        let alice_other_org_uid
            = UserID::from("<alice@other.org>");

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("isolated-root.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();

        /// Tests.
        // $ date '+%s' -d 20200102
        // 1577919600
        let t0 = time::UNIX_EPOCH + time::Duration::new(1577919600, 0);
        // $ date '+%s' -d 20200202
        // 1580598000
        let t1 = time::UNIX_EPOCH + time::Duration::new(1580598000, 0);

        for (i, t) in [t0, t1].iter().enumerate() {
            eprintln!("\n\nTrying at t{}", i + 1);

            let store = CertStore::from_cert_refs(
                certs.iter().map(|c| c.into()), p, *t)?;
            let n = NetworkBuilder::rootless(&store).build();

            eprintln!("{:?}", n);

            let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr))
                .build();

            if i == 0 {
                sp(&n, &alice_fpr, &alice_uid.clone(),
                   &[ (120, &[&alice_fpr][..]), ][..],
                   None);
            } else {
                sp(&n, &alice_fpr, &alice_uid.clone(),
                   &[][..],
                   None);
            }

            sp(&n, &alice_fpr, &alice_other_org_uid.clone(),
               &[ (120, &[&alice_fpr][..]), ][..],
               None);
        }

        Ok(())
    }

    #[test]
    fn limit_depth() -> Result<()> {
        let p = &StandardPolicy::new();

        let alice_fpr: Fingerprint =
            "85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "39A479816C934B9E0464F1F4BC1DCFDEADA4EE90"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Certified by: 85DAB65713B2D0ABFC5A4F28BC10C9CE4A699D8D

        let carol_fpr: Fingerprint =
            "43530F91B450EDB269AA58821A1CF4DC7F500F04"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@example.org>");
        // Certified by: 39A479816C934B9E0464F1F4BC1DCFDEADA4EE90

        let dave_fpr: Fingerprint =
            "329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@example.org>");
        // Certified by: 43530F91B450EDB269AA58821A1CF4DC7F500F04

        let ellen_fpr: Fingerprint =
            "A7319A9B166AB530A5FBAC8AB43CA77F7C176AF4"
           .parse().expect("valid fingerprint");
        let ellen_uid
            = UserID::from("<ellen@example.org>");
        // Certified by: 329D5AAF73DC70B4E3DD2D11677CB70FFBFE1281

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("simple.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();


        eprintln!("{:?}", n);

        eprintln!("Unconstrained query.");
        let n = NetworkBuilder::rooted(&store, &[ (alice_fpr.clone(), 90) ])
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        // Network constrained to a depth of 2.  This doesn't change
        // anything, as Alice's tsig on Bob also has depth 2.
        eprintln!("Network constrained to a depth of 2:");
        let n = NetworkBuilder::rooted(&store, &[ (alice_fpr.clone(), 90) ])
            .maximum_depth(2)
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr, &dave_fpr ][..]) ][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        // Network constrained to a depth of 1.
        eprintln!("Network constrained to a depth of 1:");
        let n = NetworkBuilder::rooted(&store, &[ (alice_fpr.clone(), 90) ])
            .maximum_depth(1)
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]) ][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        // Network constrained to a depth of 0.
        eprintln!("Network constrained to a depth of 0:");
        let n = NetworkBuilder::rooted(&store, &[ (alice_fpr.clone(), 90) ])
            .maximum_depth(0)
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (90, &[ &alice_fpr ][..]) ][..],
           None);

        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[ (90, &[ &alice_fpr, &bob_fpr ][..]) ][..],
           None);

        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[][..],
           None);

        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[][..],
           None);

        sp(&n, &ellen_fpr, &ellen_uid.clone(),
           &[][..],
           None);

        Ok(())
    }

    #[test]
    fn regex4() -> Result<()> {
        // Consider:
        //
        // <alice@example.org>
        // |
        // | Authorization (depth: 1, amount: 120),
        // | Regular expression: some.org
        // v
        // <bob@example.org>
        //
        // Alice designates Bob as an introducer for some.org.  At the
        // same time, she vouches that '<bob@example.org>' controls a
        // particular certificate.  What's interesting about this is
        // that the user ID has a different domain from the scope!
        // This test checks that we can correctly authenticate Bob's
        // self-signed user ID '<bob@some.org>' via
        // '<bob@example.org>', but can't authenticate his other
        // self-signed user ID '<bob@other.org>' via
        // '<bob@example.org>' as it doesn't match the scope.

        let alice_fpr: Fingerprint =
            "43ED15FAF18395C08AEDEDC0FC9EB4BFABE67F70"
           .parse().expect("valid fingerprint");
        let alice_uid
            = UserID::from("<alice@example.org>");

        let bob_fpr: Fingerprint =
            "3A9E44015431B8655CD3FECFBFB6DEC7D711138F"
           .parse().expect("valid fingerprint");
        let bob_uid
            = UserID::from("<bob@example.org>");
        // Regular expression: <[^>]+[@.]some\.org>$
        // Certified by: 43ED15FAF18395C08AEDEDC0FC9EB4BFABE67F70 <alice@example.org> (UNAUTHENTICATED)
        let bob_other_org_uid
            = UserID::from("<bob@other.org>");
        let bob_some_org_uid
            = UserID::from("<bob@some.org>");

        let carol_fpr: Fingerprint =
            "03357E46D9E0C47A9D92CA58F71DE1B5B9CD2D10"
           .parse().expect("valid fingerprint");
        let carol_uid
            = UserID::from("<carol@some.org>");
        // Certified by: 3A9E44015431B8655CD3FECFBFB6DEC7D711138F <bob@example.org> (UNAUTHENTICATED)

        let dave_fpr: Fingerprint =
            "B7FE472208AE5188971466F1FF7C4B36B578B709"
           .parse().expect("valid fingerprint");
        let dave_uid
            = UserID::from("<dave@other.org>");
        // Certified by: 3A9E44015431B8655CD3FECFBFB6DEC7D711138F <bob@example.org> (UNAUTHENTICATED)

        let p = &StandardPolicy::new();

        let certs: Vec<Cert> = CertParser::from_bytes(
            &crate::testdata::data("regex-4.pgp"))?
            .map(|c| c.expect("Valid certificate"))
            .collect();
        let store = CertStore::from_cert_refs(
            certs.iter().map(|c| c.into()), p, None)?;
        let n = NetworkBuilder::rootless(&store).build();

        eprintln!("{:?}", n);

        eprintln!("Unconstrained query.");
        let n = NetworkBuilder::rooted(&store, slice::from_ref(&alice_fpr))
            .build();

        sp(&n, &alice_fpr, &alice_uid.clone(),
           &[ (120, &[ &alice_fpr ][..]) ][..],
           None);
        // Alice certified bob@example.org.
        sp(&n, &bob_fpr, &bob_uid.clone(),
           &[
               (120, &[ &alice_fpr, &bob_fpr ][..]),
           ][..],
           None);
        // Alice made Bob via a certification on bob@example.org a
        // trusted introducer for some.org so he can introducer this
        // self-signed user ID.
        sp(&n, &bob_fpr, &bob_some_org_uid.clone(),
           &[
               (120, &[ &alice_fpr, &bob_fpr, &bob_fpr ][..]),
           ][..],
           None);
        // Alice made Bob a trusted introducer for some.org, but not
        // other.org.
        sp(&n, &bob_fpr, &bob_other_org_uid.clone(),
           &[][..],
           None);
        sp(&n, &carol_fpr, &carol_uid.clone(),
           &[
               (120, &[ &alice_fpr, &bob_fpr, &carol_fpr ][..]),
           ][..],
           None);
        sp(&n, &dave_fpr, &dave_uid.clone(),
           &[][..],
           None);

        Ok(())
    }

    /// This is like the regex_4 test, but instead of Alice making Bob
    /// a CA via a user ID, she does a delegation (i.e., a direct key
    /// signature).
    ///
    /// ```
    /// alice
    ///   |
    ///   | Delegation (uid=None, depth=unconstrained, amount=120)
    ///   | Regex: <[^>]+[@.]some\.org>$
    ///   v
    /// bob
    ///   └── self-signed UID: <bob@other.org>
    /// ```
    #[test]
    fn regex4_2() {
        // We build the network manually, because sq doesn't currently
        // support creating delegations.
        use std::time::Duration;
        use std::time::UNIX_EPOCH;

        use openpgp::Fingerprint;
        use openpgp::packet::UserID;

        use crate::CertSynopsis;
        use crate::Certification;
        use crate::UserIDSynopsis;

        fn make_fpr(id: u8) -> Fingerprint {
            let mut bytes = [0u8; 20];
            bytes[0] = id;
            bytes[19] = id.wrapping_add(1);
            Fingerprint::from_bytes(4, &bytes).expect("valid v4 fingerprint")
        }

        let ref_time = UNIX_EPOCH + Duration::from_secs(1_700_000_000);
        let alice_fpr = make_fpr(1);
        let bob_fpr = make_fpr(2);

        // Alice's certificate.
        let alice_cert = CertSynopsis::new(
            alice_fpr.clone(), None,
            crate::RevocationStatus::NotAsFarAsWeKnow,
            vec![UserIDSynopsis::from(
                ("<alice@example.org>", ref_time - Duration::from_secs(86400)),
            )].into_iter(),
        );

        // Bob's certificate with a user ID that matches the regex and
        // another one that does not.
        let bob_cert = CertSynopsis::new(
            bob_fpr.clone(),
            None,
            crate::RevocationStatus::NotAsFarAsWeKnow,
            vec![
                UserIDSynopsis::from(
                    ("<bob@other.org>", ref_time - Duration::from_secs(86400))),
                UserIDSynopsis::from(
                    ("<bob@some.org>", ref_time - Duration::from_secs(86400))),
            ].into_iter());
        let bob_other_org_uid = UserID::from("<bob@other.org>");
        let bob_some_org_uid = UserID::from("<bob@some.org>");


        // Alice makes Bob a trusted introducer for the "some.org"
        // domain.  This is a delegation (uid=None), NOT a user ID
        // certification.
        let delegation = Certification::new(
            alice_cert.clone(),
            None::<UserID>, // None => delegation.
            bob_cert.clone(),
            ref_time - Duration::from_secs(3600))
                .set_amount(120)
                .set_depth(Depth::unconstrained())
                .set_regular_expressions(
                    [&b"<[^>]+[@.]some\\.org>$"[..]].into_iter(),
                );

        let certs = [alice_cert, bob_cert];
        let certifications = [delegation];

        let n = Network::from_synopses(
            &certs, &certifications, ref_time, &[alice_fpr.clone()])
            .expect("valid network");

        // We should be able to authenticate bob@some.org via the
        // delegation.
        let paths = n.authenticate(
            bob_some_org_uid.clone(), bob_fpr.clone(), 1);

        assert_eq!(paths.len(), 1);
        let (path, amount) = paths.iter().next().unwrap();
        assert_eq!(*amount, 120);
        assert_eq!(path.certificates().map(|c| c.fingerprint()).collect::<Vec<_>>(),
                   vec![ alice_fpr, bob_fpr.clone(), bob_fpr.clone() ]);

        // We shouldn't be able to authenticate bob@other.org via the
        // delegation.
        let paths = n.authenticate(
            bob_other_org_uid.clone(), bob_fpr.clone(), 1);

        assert_eq!(paths.len(), 0);
    }
}