Gecko (and therefore Firefox) relies on NSS to implement various cryptographic functions. NSS consists of a collection of loosely-coupled libraries. libssl, for example, is the TLS implementation. NSS is a Mozilla project, but its development differs significantly from the rest of the tree. In fact, it has its own tree that is periodically imported wholesale into mozilla-central. The component that uses the NSS libraries in Firefox is a layer called PSM ("Personal Security Manager" or "Privacy and Security Module").
To enable secure TLS connections to the best of our ability, PSM implements a certificate verification callback. It performs a number of checks, but ultimately it must determine if it trusts a certificate presented by a peer. The approach PSM takes is to repeatedly build a potential path to a trust anchor, validate the potential path, and either return that path if it validates correctly or find another potential path. mozilla::pkix is a C++ library that provides a framework to implement this approach.
mozilla::pkix was originally implemented as part of mozilla-central (i.e. gecko) but has since been moved into NSS. However, it is not part of NSS' stable C API. As a library, mozilla::pkix uses the notion of a "trust domain" provided by the application to build a trusted chain from an end-entity certificate to a root. The trust domain is responsible for saying what trust level a certificate has, finding potential issuers of a certificate, and checking the revocation for a certificate. A certificate can be a trust anchor, it can inherit its trust, or it can be actively distrusted. Given an end-entity certificate and a trust domain, the library will perform issuer-independent checks on that certificate (e.g. expiration, appropriate key usages), get a list of potential issuers, and perform a depth-first traversal. If it encounters a distrusted certificate, it abandons searching that path. If it finds a trust anchor, it queries the trust domain again to see if that path is acceptable (this is where gecko implements checks that are specific to the platform and not the abstract problem of building a trusted certificate chain). If so, the end-entity certificate has successfully been verified.
Unlike the other NSS libraries, mozilla::pkix is written in C++ and can take advantage of more modern language features.
The platform looks for trust anchors in a few locations. First, Mozilla ships a list of trust anchors with the platform corresponding to the root Certificate Authorities (CAs) in the Mozilla Root CA Program. Additionally, the user may import their own trust anchors. These are stored in the profile's cert9.db file. The user may also import third-party PKCS#11 modules that provide trust anchors. The enterprise roots feature, if enabled, may collect trust anchors provided by the operating system.
Similarly, the platform gathers intermediate certificates from a few locations. The TLS specification mandates that the peer include in the handshake any necessary intermediate certificates to verify the end-entity. In practice this may not be the case, but the platform uses these if they are available. The user may manually add intermediate certificates. Again these are stored in the profile's cert9.db file. The enterprise roots feature also looks for intermediates provided by the operating system.
When the platform successfully verifies an end-entity certificate, it caches the intermediates from that verified chain in the profile (cert9.db) in case they will be useful in the future (for example, when connecting to a different peer that uses a certificate issued by the same CA but neglects to include intermediate certificates in the handshake).
As part of Mozilla's Root CA Program, there is a list of root certificates that are trusted to issue Extended Validation (EV) certificates. This list is available in code form at https://hg.mozilla.org/mozilla-central/annotate/tip/security/certverifier/ExtendedValidation.cpp.
Other Verification Routines in NSS
NSS exposes other certificate verification functions that are not yet implemented using mozilla::pkix. The following is informational and has little bearing on the behavior of Firefox.
The so-called "classic" certificate verification algorithm performs issuer-independent checks on the given certificate, finds a potential issuer, verifies that the signature matches, and recurses. If multiple issuers are found, it attempts to use the "best" one. However, this is a heuristic, and as it does not perform backtracking, it can fail to verify a valid certificate. This is spectacularly apparent in the case of key-pinning if the algorithm chooses to not traverse a certificate path that contains a necessary key.
The code is here: https://hg.mozilla.org/projects/nss/file/tip/lib/certhigh
libpkix was auto-translated from Java to C. It attempts to implement Java's exception semantics in C. It makes liberal use of unclear macros (e.g. https://hg.mozilla.org/projects/nss/annotate/5d9f8b809e6f7020529ba1345b64e36f61994c8d/lib/libpkix/pkix/util/pkix_tools.h#l67 ). A source-line-counting tool clocks it in at 45,000 lines of code (the code is here: https://hg.mozilla.org/projects/nss/file/tip/lib/libpkix ). There are known bugs in the implementation. No one who works on it wants to continue working on it.