private List<X509Certificate> checkTrustedRecursive(X509Certificate[] certs, byte[] ocspData,
            byte[] tlsSctData, String host, boolean clientAuth,
            List<X509Certificate> untrustedChain, List<TrustAnchor> trustAnchorChain,
            Set<X509Certificate> used) throws CertificateException {
        CertificateException lastException = null;
        X509Certificate current;
        if (trustAnchorChain.isEmpty()) {
            current = untrustedChain.get(untrustedChain.size() - 1);
        } else {
            current = trustAnchorChain.get(trustAnchorChain.size() - 1).getTrustedCert();
        }

        // Check that the certificate isn't blocklisted.
        checkBlocklist(current);

        // 1. If the current certificate in the chain is self-signed verify the chain as is.
        if (current.getIssuerDN().equals(current.getSubjectDN())) {
            return verifyChain(untrustedChain, trustAnchorChain, host, clientAuth, ocspData,
                    tlsSctData);
        }

        // 2. Try building a chain via any trust anchors that issued the current certificate.
        // Note that we do not stop at the first trust anchor since it is possible that the trust
        // anchor is not self-signed and its issuer may be needed for additional validation such as
        // certificate pinning. In the common case the first trust anchor will be self-signed or
        // its issuer's certificate will be missing.
        Set<TrustAnchor> anchors = findAllTrustAnchorsByIssuerAndSignature(current);
        boolean seenIssuer = false;
        for (TrustAnchor anchor : sortPotentialAnchors(anchors)) {
            X509Certificate anchorCert = anchor.getTrustedCert();
            // Avoid using certificates that have already been used.
            if (used.contains(anchorCert)) {
                continue;
            }
            seenIssuer = true;
            used.add(anchorCert);
            trustAnchorChain.add(anchor);
            try {
                return checkTrustedRecursive(certs, ocspData, tlsSctData, host, clientAuth,
                        untrustedChain, trustAnchorChain, used);
            } catch (CertificateException ex) {
                lastException = ex;
            }
            // Could not form a valid chain via this certificate, remove it from this chain.
            trustAnchorChain.remove(trustAnchorChain.size() - 1);
            used.remove(anchorCert);
        }

        // 3. If we were unable to find additional trusted issuers, verify the current chain.
        // This may happen if the root of trust is not self-signed and the issuer is not
        // present in the trusted set.
        if (!trustAnchorChain.isEmpty()) {
            if (!seenIssuer) {
                return verifyChain(untrustedChain, trustAnchorChain, host, clientAuth, ocspData,
                        tlsSctData);
            }

            // Otherwise all chains based on the current trust anchor were rejected, fail.
            throw lastException;
        }

        // 4. Use the certificates provided by the peer to grow the chain.
        // Ignore the first certificate, as that is the leaf certificate.
        for (int i = 1; i < certs.length; i++) {
            X509Certificate candidateIssuer = certs[i];
            // Avoid using certificates that have already been used.
            if (used.contains(candidateIssuer)) {
                continue;
            }
            if (current.getIssuerDN().equals(candidateIssuer.getSubjectDN())) {
                // Check the strength and validity of the certificate to prune bad certificates
                // early.
                try {
                    candidateIssuer.checkValidity();
                    ChainStrengthAnalyzer.checkCert(candidateIssuer);
                } catch (CertificateException ex) {
                    lastException = new CertificateException("Unacceptable certificate: "
                            + candidateIssuer.getSubjectX500Principal(), ex);
                    continue;
                }
                used.add(candidateIssuer);
                untrustedChain.add(candidateIssuer);
                try {
                    return checkTrustedRecursive(certs, ocspData, tlsSctData, host, clientAuth,
                            untrustedChain, trustAnchorChain, used);
                } catch (CertificateException ex) {
                    lastException = ex;
                }
                // Could not form a valid chain via this certificate, remove it from this chain.
                used.remove(candidateIssuer);
                untrustedChain.remove(untrustedChain.size() - 1);
            }
        }

        // 5. Finally try the cached intermediates to handle server that failed to send them.
        Set<TrustAnchor> intermediateAnchors =
                intermediateIndex.findAllByIssuerAndSignature(current);
        for (TrustAnchor intermediate : sortPotentialAnchors(intermediateAnchors)) {
            X509Certificate intermediateCert = intermediate.getTrustedCert();
            // Avoid using certificates that have already been used.
            if (used.contains(intermediateCert)) {
                continue;
            }
            used.add(intermediateCert);
            untrustedChain.add(intermediateCert);
            try {
                return checkTrustedRecursive(certs, ocspData, tlsSctData, host, clientAuth,
                        untrustedChain, trustAnchorChain, used);
            } catch (CertificateException ex) {
                lastException = ex;
            }
            // Could not form a valid chain via this certificate, remove it from this chain.
            untrustedChain.remove(untrustedChain.size() - 1);
            used.remove(intermediateCert);
        }

        // 6. We were unable to build a valid chain, throw the last error encountered.
        if (lastException != null) {
            throw lastException;
        }

        // 7. If no errors were encountered above then verifyChain was never called because it was
        // not possible to build a valid chain to a trusted certificate.
        CertPath certPath = factory.generateCertPath(untrustedChain);
        throw new CertificateException(new CertPathValidatorException(
                "Trust anchor for certification path not found.", null, certPath, -1));
    }
Recursively build certificate chains until a valid chain is found or all possible paths are
exhausted.
<p>
The chain is built in two sections, the complete trusted path is the the combination of
{@code untrustedChain} and {@code trustAnchorChain}. The chain begins at the leaf
certificate and ends in the final trusted root certificate.

@param certs the bag of certs provided by the peer. No order is assumed.
@param host the host being connected to.
@param clientAuth if a client is being authorized instead of a server.
@param untrustedChain the untrusted section of the chain built so far. Must be mutable.
@param trustAnchorChain the trusted section of the chain built so far. Must be mutable.
@param used the set certificates used so far in path building. Must be mutable.

@return The entire valid chain starting with the leaf certificate. This is the
concatenation of untrustedChain and trustAnchorChain.

@throws CertificateException If no valid chain could be constructed. Note that there may be
multiple reasons why no valid chain exists and there is no guarantee that the most severe is
reported in this exception. As such applications MUST NOT use the specifics of this error
for trust decisions (e.g. showing the user a click through page based on the specific error).
common/src/main/java/org/conscrypt/TrustManagerImpl.java