pki: Add trusted subtrees to CertificateTrust

Makes the trusted_subtrees_ field of MTCAnchor store it as a
std::shared_ptr, which is then copied into the CertificateTrust
representing the MTCAnchor. Along the way, remove constexpr from
CertificateTrust, and make a new type, TrustedSubtreeSet, holding a
std::vector<LogTrustedSubtrees> to handle validation and lookup of
trusted subtrees.

After this change, logic for handling trusted subtrees no longer lives
in MTCAnchor.

Changes the TrustAnchor::CertTrust() getter to return a reference since
CertificateTrust copies are no longer free.

This is a step towards making trust anchors uniformly representable as a
(ParsedCertificate, CertificateTrust) pair, pivoting away from the
earlier plan of migrating the representation of all trust anchors to
the TrustAnchor type.

Bug: 575507260
Change-Id: I45aea0a3f0a1f1e75093d8b8408ec3086a6a6964
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/104988
Presubmit-BoringSSL-Verified: boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com <boringssl-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Matt Mueller <mattm@google.com>
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: Lily Chen <chlily@google.com>
diff --git a/pki/trust_store.cc b/pki/trust_store.cc
index 291c30a..fd31acb 100644
--- a/pki/trust_store.cc
+++ b/pki/trust_store.cc
@@ -53,6 +53,92 @@
 
 }  // namespace
 
+TrustedSubtreeSet::TrustedSubtreeSet(
+    TrustedSubtreeSet::Token, std::vector<LogTrustedSubtrees> trusted_subtrees)
+    : trusted_subtrees_(std::move(trusted_subtrees)) {}
+
+// static
+std::shared_ptr<const TrustedSubtreeSet> TrustedSubtreeSet::Create(
+    std::vector<LogTrustedSubtrees> trusted_subtrees) {
+  if (!IsValid(trusted_subtrees)) {
+    return nullptr;
+  }
+  return std::make_shared<TrustedSubtreeSet>(Token(),
+                                             std::move(trusted_subtrees));
+}
+
+std::optional<TreeHashConstSpan> TrustedSubtreeSet::LookupSubtreeHash(
+    uint16_t log_number, Subtree target_range) const {
+  // The `trusted_subtrees_` is generally expected to have one, or rarely two,
+  // elements, so just using a simple find rather than a binary search.
+  auto subtrees_it =
+      std::find_if(trusted_subtrees_.begin(), trusted_subtrees_.end(),
+                   [log_number](const LogTrustedSubtrees &logsubtree) -> bool {
+                     return logsubtree.log_number == log_number;
+                   });
+  if (subtrees_it == trusted_subtrees_.end()) {
+    return std::nullopt;
+  }
+
+  const auto &subtrees = subtrees_it->trusted_subtrees;
+  auto it = std::lower_bound(
+      subtrees.begin(), subtrees.end(), target_range,
+      [](const TrustedSubtree &subtree, Subtree range) -> bool {
+        return subtree.range < range;
+      });
+  if (it == subtrees.end() || it->range != target_range) {
+    return std::nullopt;
+  }
+  return it->hash;
+}
+
+std::string TrustedSubtreeSet::DebugString() const {
+  if (trusted_subtrees_.empty()) {
+    return "none";
+  }
+  std::string result;
+
+  for (const auto &[log_number, subtrees] : trusted_subtrees_) {
+    if (!result.empty()) {
+      result += ", ";
+    }
+    result += "log " + std::to_string(log_number) + ":";
+    if (subtrees.empty()) {
+      result += "empty";
+    } else {
+      // Just showing the start of first range to end of last range is an
+      // oversimplification, but showing every single range is probably too
+      // verbose.
+      result += std::to_string(subtrees.size()) + " subtrees(" +
+                std::to_string(subtrees.front().range.start) + ".." +
+                std::to_string(subtrees.back().range.end) + ")";
+    }
+  }
+  return result;
+}
+
+// static
+bool TrustedSubtreeSet::IsValid(
+    const std::vector<LogTrustedSubtrees> &trusted_subtrees) {
+  uint16_t min_log_number = 0;
+  for (const auto &[log_number, subtrees] : trusted_subtrees) {
+    if (log_number <= min_log_number) {
+      // Log numbers must be greater than zero, and `trusted_subtrees` must be
+      // in sorted order without repeated log numbers.
+      return false;
+    }
+    min_log_number = log_number;
+    Subtree min_subtree;
+    for (const auto &subtree : subtrees) {
+      if (!subtree.range.IsValid() || subtree.range < min_subtree) {
+        return false;
+      }
+      min_subtree = subtree.range;
+    }
+  }
+  return true;
+}
+
 bool CertificateTrust::IsTrustAnchor() const {
   switch (type) {
     case CertificateTrustType::DISTRUSTED:
@@ -148,6 +234,11 @@
     result += '+';
     result += kRequireLeafSelfsigned;
   }
+  if (trusted_subtrees != nullptr) {
+    result += "+trusted_subtrees(";
+    result += trusted_subtrees->DebugString();
+    result += ')';
+  }
   return result;
 }
 
@@ -223,31 +314,13 @@
       ca_id_(ca_id.begin(), ca_id.end()),
       ca_signature_algorithm_(ca_signature_algorithm),
       ca_key_(std::move(ca_key)),
-      trusted_subtrees_(std::move(log_trusted_subtrees)) {
+      trusted_subtrees_(
+          TrustedSubtreeSet::Create(std::move(log_trusted_subtrees))) {
   CreateSyntheticCert(ca_id);
 }
 
 bool MTCAnchor::IsValid() const {
-  if (!synthetic_cert_) {
-    return false;
-  }
-  uint16_t min_log_number = 0;
-  for (const auto &[log_number, subtrees] : trusted_subtrees_) {
-    if (log_number <= min_log_number) {
-      // Log numbers must be greater than zero, and `trusted_subtrees_` must be
-      // in sorted order without repeated log numbers.
-      return false;
-    }
-    min_log_number = log_number;
-    Subtree min_subtree;
-    for (const auto &subtree : subtrees) {
-      if (!subtree.range.IsValid() || subtree.range < min_subtree) {
-        return false;
-      }
-      min_subtree = subtree.range;
-    }
-  }
-  return true;
+  return synthetic_cert_ != nullptr && trusted_subtrees_ != nullptr;
 }
 
 der::Input MTCAnchor::NormalizedSubject() const {
@@ -257,6 +330,7 @@
 CertificateTrust MTCAnchor::CertTrust() const {
   CertificateTrust trust;
   trust.type = CertificateTrustType::TRUSTED_ANCHOR;
+  trust.trusted_subtrees = trusted_subtrees_;
   return trust;
 }
 
@@ -265,54 +339,18 @@
 }
 
 std::optional<TreeHashConstSpan> MTCAnchor::SubtreeHash(
-    uint16_t log_number,
-    Subtree target_range) const {
-  // The `trusted_subtrees_` is generally expected to have one, or rarely two,
-  // elements, so just using a simple find rather than a binary search.
-  auto subtrees_it = std::find_if(
-      trusted_subtrees_.begin(), trusted_subtrees_.end(),
-      [log_number](const LogTrustedSubtrees &logsubtree) -> bool {
-        return logsubtree.log_number == log_number;
-      });
-  if (subtrees_it == trusted_subtrees_.end()) {
+    uint16_t log_number, Subtree target_range) const {
+  if (trusted_subtrees_ == nullptr) {
     return std::nullopt;
   }
-
-  const auto& subtrees = subtrees_it->trusted_subtrees;
-  auto it = std::lower_bound(
-      subtrees.begin(), subtrees.end(), target_range,
-      [](const TrustedSubtree &subtree, Subtree range) -> bool {
-        return subtree.range < range;
-      });
-  if (it == subtrees.end() || it->range != target_range) {
-    return std::nullopt;
-  }
-  return it->hash;
+  return trusted_subtrees_->LookupSubtreeHash(log_number, target_range);
 }
 
 std::string MTCAnchor::TrustedSubtreesDebugString() const {
-  if (trusted_subtrees_.empty()) {
-    return "none";
+  if (trusted_subtrees_ == nullptr) {
+    return "Invalid";
   }
-  std::string result;
-
-  for (const auto &[log_number, subtrees] : trusted_subtrees_) {
-    if (!result.empty()) {
-      result += ", ";
-    }
-    result += "log " + std::to_string(log_number) + ":";
-    if (subtrees.empty()) {
-      result += "empty";
-    } else {
-      // Just showing the start of first range to end of last range is an
-      // oversimplification, but showing every single range is probably too
-      // verbose.
-      result += std::to_string(subtrees.size()) + " subtrees(" +
-                std::to_string(subtrees.front().range.start) + ".." +
-                std::to_string(subtrees.back().range.end) + ")";
-    }
-  }
-  return result;
+  return trusted_subtrees_->DebugString();
 }
 
 void MTCAnchor::CreateSyntheticCert(bssl::Span<const uint8_t> ca_id) {
@@ -411,7 +449,7 @@
   trust_ = new_trust;
 }
 
-CertificateTrust TrustAnchor::CertTrust() const { return trust_; }
+const CertificateTrust &TrustAnchor::CertTrust() const { return trust_; }
 
 std::shared_ptr<const MTCAnchor> TrustAnchor::MTCAnchor() const {
   return mtc_anchor_;
diff --git a/pki/trust_store.h b/pki/trust_store.h
index 9a1dcf1..42c37fb 100644
--- a/pki/trust_store.h
+++ b/pki/trust_store.h
@@ -61,59 +61,100 @@
   std::vector<TrustedSubtree> trusted_subtrees;
 };
 
+// Represents an ordered list of trusted subtrees for an MTC CA.
+class OPENSSL_EXPORT TrustedSubtreeSet {
+ public:
+  class Token {
+   private:
+    explicit Token() = default;
+    friend TrustedSubtreeSet;
+  };
+
+  // Wraps `trusted_subtrees` in a TrustedSubtreeSet instance if valid,
+  // otherwise returns nullptr. Returned TrustedSubtreeSet is guaranteed to be
+  // valid.
+  static std::shared_ptr<const TrustedSubtreeSet> Create(
+      std::vector<LogTrustedSubtrees> trusted_subtrees);
+
+  // This constructor is conceptually private, but needs to be public for
+  // make_shared to work. Uses the "passkey idiom" to prevent callers outside
+  // of the class from calling it. Outside callers should use Create().
+  TrustedSubtreeSet(Token, std::vector<LogTrustedSubtrees> trusted_subtrees);
+
+  TrustedSubtreeSet(const TrustedSubtreeSet &) = delete;
+  TrustedSubtreeSet &operator=(const TrustedSubtreeSet &) = delete;
+
+  ~TrustedSubtreeSet() = default;
+
+  // Looks up a `target_range`'s subtree hash within the trusted subtrees for
+  // `log_number`. Returns std::nullopt if not found.
+  std::optional<TreeHashConstSpan> LookupSubtreeHash(
+      uint16_t log_number, Subtree target_range) const;
+
+  std::string DebugString() const;
+
+ private:
+  // Returns whether log numbers are greater than zero, and are in sorted order
+  // without repeated log numbers, and within each log number the subtrees are
+  // valid and listed in order. (An empty list for a log number is valid, and
+  // equivalent to that log number being absent.)
+  static bool IsValid(const std::vector<LogTrustedSubtrees> &trusted_subtrees);
+
+  // Entries in the vector must be sorted by log number, and each
+  // `TrustedSubtree` within must be sorted by their subtree ranges.
+  std::vector<LogTrustedSubtrees> trusted_subtrees_;
+};
+
 // Describes the level of trust in a certificate.
 struct OPENSSL_EXPORT CertificateTrust {
-  static constexpr CertificateTrust ForTrustAnchor() {
+  static CertificateTrust ForTrustAnchor() {
     CertificateTrust result;
     result.type = CertificateTrustType::TRUSTED_ANCHOR;
     return result;
   }
 
-  static constexpr CertificateTrust ForTrustAnchorOrLeaf() {
+  static CertificateTrust ForTrustAnchorOrLeaf() {
     CertificateTrust result;
     result.type = CertificateTrustType::TRUSTED_ANCHOR_OR_LEAF;
     return result;
   }
 
-  static constexpr CertificateTrust ForTrustedLeaf() {
+  static CertificateTrust ForTrustedLeaf() {
     CertificateTrust result;
     result.type = CertificateTrustType::TRUSTED_LEAF;
     return result;
   }
 
-  static constexpr CertificateTrust ForUnspecified() {
+  static CertificateTrust ForUnspecified() {
     CertificateTrust result;
     return result;
   }
 
-  static constexpr CertificateTrust ForDistrusted() {
+  static CertificateTrust ForDistrusted() {
     CertificateTrust result;
     result.type = CertificateTrustType::DISTRUSTED;
     return result;
   }
 
-  constexpr CertificateTrust WithEnforceAnchorExpiry(bool value = true) const {
+  CertificateTrust WithEnforceAnchorExpiry(bool value = true) const {
     CertificateTrust result = *this;
     result.enforce_anchor_expiry = value;
     return result;
   }
 
-  constexpr CertificateTrust WithEnforceAnchorConstraints(
-      bool value = true) const {
+  CertificateTrust WithEnforceAnchorConstraints(bool value = true) const {
     CertificateTrust result = *this;
     result.enforce_anchor_constraints = value;
     return result;
   }
 
-  constexpr CertificateTrust WithRequireAnchorBasicConstraints(
-      bool value = true) const {
+  CertificateTrust WithRequireAnchorBasicConstraints(bool value = true) const {
     CertificateTrust result = *this;
     result.require_anchor_basic_constraints = value;
     return result;
   }
 
-  constexpr CertificateTrust WithRequireLeafSelfSigned(
-      bool value = true) const {
+  CertificateTrust WithRequireLeafSelfSigned(bool value = true) const {
     CertificateTrust result = *this;
     result.require_leaf_selfsigned = value;
     return result;
@@ -126,6 +167,8 @@
 
   std::string ToDebugString() const;
 
+  // FromDebugString does not parse trusted subtrees from the debug string. If
+  // there are any trusted_subtrees, they will not round-trip.
   static std::optional<CertificateTrust> FromDebugString(
       const std::string &trust_string);
 
@@ -146,6 +189,14 @@
 
   // Optionally, require trusted leafs to be self-signed to be trusted.
   bool require_leaf_selfsigned = false;
+
+  // For an MTC CA, a list of trusted subtrees
+  // (draft-ietf-plants-merkle-tree-certs, Section 7.4) that are known to be
+  // consistent with the relying party's cosigner requirements. A null pointer
+  // is equivalent to an empty set (no landmark-relative MTCs from this MTC CA
+  // are recognized). Ignored (and should be null) unless this is the trust for
+  // an MTC CA.
+  std::shared_ptr<const TrustedSubtreeSet> trusted_subtrees;
 };
 
 class OPENSSL_EXPORT MTCAnchor {
@@ -208,11 +259,10 @@
     return ca_signature_algorithm_;
   }
   const CRYPTO_BUFFER *ca_key() const { return ca_key_.get(); }
-  // TODO(nharper): Move this function to TrustAnchor.
   der::Input NormalizedSubject() const;
-  // TODO(nharper): Remove this function in favor of TrustAnchor's version.
   CertificateTrust CertTrust() const;
-  // TODO(nharper): Move this function to TrustAnchor.
+  // TODO(crbug.com/575507260): Replace synthesized certificate with a real MTC
+  // CA certificate.
   std::shared_ptr<const ParsedCertificate> AsCert() const;
 
   std::optional<TreeHashConstSpan> SubtreeHash(uint16_t log_number,
@@ -227,33 +277,26 @@
   SignatureAlgorithm ca_signature_algorithm_;
   UniquePtr<CRYPTO_BUFFER> ca_key_;
   std::shared_ptr<const ParsedCertificate> synthetic_cert_;
-  std::vector<LogTrustedSubtrees> trusted_subtrees_;
+  // If `trusted_subtrees_` is null, `Create*()` failed and `IsValid()` is
+  // false.
+  std::shared_ptr<const TrustedSubtreeSet> trusted_subtrees_;
 };
 
 // A TrustAnchor contains information about how a trust anchor is trusted and
-// what is trusted. It should be used in place of a (ParsedCertificate,
-// CertificateTrust) tuple as some trust information, e.g. MTC anchors, is not
+// what is trusted.
+//
+// TODO(crbug.com/575507260): This class was formerly the first step of a large
+// refactor to use TrustAnchor in place of a (ParsedCertificate,
+// CertificateTrust) tuple as some trust information, e.g. MTC anchors, was not
 // representable by such a tuple.
-//
-// TODO(nharper): This class is the first step of a large refactor to stop
-// representing TrustAnchors as ParsedCertificates. Prior to the introduction of
-// Merkle Tree Certs, the information about a trust anchor was split between
-// a ParsedCertificate (containing the anchor's Subject name and public key) and
-// a CertificateTrust struct (informing when/how the trust anchor is trusted, as
-// well as whether any additional constraints should be applied). With the
-// introduction of Merkle Tree Certs, some of this information about how to use
-// an MTC trust anchor fits in neither place. The eventual goal is that the
-// TrustAnchor class is the single place that contains all information about a
-// trust anchor, rather than that information being split across multiple
-// objects. This will allow a further goal of removing the dependency of
-// requiring that a trust anchor be representable as a ParsedCertificate: MTC
-// trust anchors only have a ParsedCertificate accessor for compatibility
-// reasons, and while draft-ietf-lamps-x509-alg-none improves the efficiency of
-// storing trust anchors in X.509 certs, this refactor will allow further
-// improvements for classical (non-MTC) roots.
-//
-// See also internal design doc:
+// Original internal TrustAnchor design doc:
 // https://docs.google.com/document/d/1wqHAmZqtF8oJzNObFBm41lzDt2JWRhjM32A3z6ampJE/edit
+//
+// The current plan is to align with the X.509 certificate representation of MTC
+// CAs in draft-ietf-plants-merkle-tree-certs-05 and up, and make the
+// (ParsedCertificate, CertificateTrust) representation work for all trust
+// anchors. After migrating to the X.509 representation, TrustAnchor will be
+// removed.
 class OPENSSL_EXPORT TrustAnchor {
  public:
   // Creates a default TrustAnchor with an unspecified CertificateTrust.
@@ -261,6 +304,8 @@
 
   // Creates a TrustAnchor with no associated MTCAnchor.
   explicit TrustAnchor(CertificateTrust trust) : TrustAnchor(trust, nullptr) {}
+
+  // Creates a TrustAnchor with an associated MTCAnchor.
   TrustAnchor(CertificateTrust trust,
               std::shared_ptr<const MTCAnchor> mtc_anchor)
       : trust_(trust), mtc_anchor_(std::move(mtc_anchor)) {}
@@ -278,7 +323,7 @@
   // TODO(nharper): Remove this function as part of the larger TrustAnchor
   // refactor.
   void OverrideCertTrust(CertificateTrust new_trust);
-  CertificateTrust CertTrust() const;
+  const CertificateTrust &CertTrust() const;
   std::shared_ptr<const bssl::MTCAnchor> MTCAnchor() const;
 
  private:
diff --git a/pki/trust_store_in_memory_unittest.cc b/pki/trust_store_in_memory_unittest.cc
index 87b6228..1ac1b40 100644
--- a/pki/trust_store_in_memory_unittest.cc
+++ b/pki/trust_store_in_memory_unittest.cc
@@ -15,6 +15,8 @@
 #include "trust_store_in_memory.h"
 
 #include <memory>
+#include <optional>
+#include <string>
 #include <vector>
 
 #include <gtest/gtest.h>
@@ -280,5 +282,232 @@
   EXPECT_FALSE(in_memory2.ContainsMTCAnchor(anchor1.get()));
 }
 
+class TrustedSubtreeSetTest : public testing::Test {
+ protected:
+  // Returns a TrustedSubtree for [start, end) whose hash is filled with
+  // `hash_byte`, so that lookup results can be told apart.
+  static TrustedSubtree MakeSubtree(uint64_t start, uint64_t end,
+                                    uint8_t hash_byte) {
+    TrustedSubtree subtree;
+    subtree.range = Subtree{start, end};
+    subtree.hash.fill(hash_byte);
+    return subtree;
+  }
+
+  // Returns the expected hash for a subtree made with MakeSubtree(...,
+  // `hash_byte`).
+  static std::vector<uint8_t> ExpectedHash(uint8_t hash_byte) {
+    return std::vector<uint8_t>(SHA256_DIGEST_LENGTH, hash_byte);
+  }
+
+  static std::optional<std::vector<uint8_t>> Lookup(
+      const TrustedSubtreeSet &set, uint16_t log_number, Subtree range) {
+    std::optional<TreeHashConstSpan> hash =
+        set.LookupSubtreeHash(log_number, range);
+    if (!hash) {
+      return std::nullopt;
+    }
+    return std::vector<uint8_t>(hash->begin(), hash->end());
+  }
+
+  static std::shared_ptr<const MTCAnchor> MakeMTCAnchor(
+      std::vector<LogTrustedSubtrees> subtrees) {
+    static const uint8_t kCaId[] = {42};  // relative OID of 42
+    // The ca_key doesn't need to be valid for these tests.
+    UniquePtr<CRYPTO_BUFFER> ca_spki(CRYPTO_BUFFER_new({}, 0, nullptr));
+    return std::make_shared<MTCAnchor>(kCaId, SignatureAlgorithm::kMldsa44,
+                                       std::move(ca_spki), std::move(subtrees));
+  }
+};
+
+TEST_F(TrustedSubtreeSetTest, CreateValid) {
+  const TrustedSubtree a = MakeSubtree(0, 4, 1);
+  const TrustedSubtree b = MakeSubtree(0, 6, 2);
+  const TrustedSubtree c = MakeSubtree(8, 9, 3);
+
+  const struct {
+    const char *name;
+    std::vector<LogTrustedSubtrees> subtrees;
+  } kTests[] = {
+      {"Empty", {}},
+      {"OneLogNoSubtrees", {{1, {}}}},
+      {"OneLogOneSubtree", {{1, {a}}}},
+      {"OneLogSortedSubtrees", {{1, {a, b, c}}}},
+      {"MultipleSortedLogs", {{1, {a, c}}, {2, {b}}, {7, {a}}}},
+      {"MaxLogNumber", {{1, {a}}, {UINT16_MAX, {b}}}},
+  };
+  for (const auto &t : kTests) {
+    SCOPED_TRACE(t.name);
+    EXPECT_TRUE(TrustedSubtreeSet::Create(t.subtrees));
+  }
+}
+
+TEST_F(TrustedSubtreeSetTest, CreateInvalid) {
+  const TrustedSubtree a = MakeSubtree(0, 4, 1);
+  const TrustedSubtree b = MakeSubtree(0, 6, 2);
+  const TrustedSubtree c = MakeSubtree(8, 9, 3);
+  // Ragged left edge: 4 is only divisible by 4, but the subtree has 5 elements.
+  const TrustedSubtree ragged = MakeSubtree(4, 9, 4);
+  const TrustedSubtree backwards = MakeSubtree(9, 8, 5);
+
+  const struct {
+    const char *name;
+    std::vector<LogTrustedSubtrees> subtrees;
+  } kTests[] = {
+      {"LogNumberZero", {{0, {a}}}},
+      {"LogNumberZeroBeforeValid", {{0, {a}}, {1, {b}}}},
+      {"LogsOutOfOrder", {{2, {a}}, {1, {b}}}},
+      {"DuplicateLogNumber", {{1, {a}}, {1, {b}}}},
+      {"RaggedSubtree", {{1, {ragged}}}},
+      {"BackwardsSubtree", {{1, {backwards}}}},
+      {"InvalidSubtreeInSecondLog", {{1, {a}}, {2, {ragged}}}},
+      {"SubtreesOutOfOrder", {{1, {b, a, c}}}},
+      {"SubtreesOutOfOrderInSecondLog", {{1, {a}}, {2, {c, a}}}},
+  };
+  for (const auto &t : kTests) {
+    SCOPED_TRACE(t.name);
+    EXPECT_FALSE(TrustedSubtreeSet::Create(t.subtrees));
+  }
+}
+
+// Duplicate subtree ranges within a log are accepted as valid, because
+// validation only rejects ranges that sort strictly before their predecessor.
+TEST_F(TrustedSubtreeSetTest, CreateDuplicateRanges) {
+  std::vector<LogTrustedSubtrees> subtrees = {
+      {1, {MakeSubtree(0, 4, 1), MakeSubtree(0, 4, 2)}}};
+  EXPECT_TRUE(TrustedSubtreeSet::Create(subtrees));
+}
+
+TEST_F(TrustedSubtreeSetTest, LookupSubtreeHash) {
+  std::shared_ptr<const TrustedSubtreeSet> set = TrustedSubtreeSet::Create({
+      {1, {MakeSubtree(0, 4, 1), MakeSubtree(0, 8, 2), MakeSubtree(8, 12, 3)}},
+      {3, {MakeSubtree(0, 4, 4), MakeSubtree(16, 32, 5)}},
+  });
+  ASSERT_TRUE(set);
+
+  // First, middle and last subtree in the first log.
+  EXPECT_EQ(Lookup(*set, 1, Subtree{0, 4}), ExpectedHash(1));
+  EXPECT_EQ(Lookup(*set, 1, Subtree{0, 8}), ExpectedHash(2));
+  EXPECT_EQ(Lookup(*set, 1, Subtree{8, 12}), ExpectedHash(3));
+
+  // The same range in a different log has a different hash.
+  EXPECT_EQ(Lookup(*set, 3, Subtree{0, 4}), ExpectedHash(4));
+  EXPECT_EQ(Lookup(*set, 3, Subtree{16, 32}), ExpectedHash(5));
+
+  // Unknown log numbers, including one between two known logs.
+  EXPECT_FALSE(Lookup(*set, 0, Subtree{0, 4}));
+  EXPECT_FALSE(Lookup(*set, 2, Subtree{0, 4}));
+  EXPECT_FALSE(Lookup(*set, 4, Subtree{0, 4}));
+
+  // Ranges not in the log: before the first, between two existing ranges,
+  // sharing only a start or end with an existing range, after the last, and a
+  // range present only in the other log.
+  EXPECT_FALSE(Lookup(*set, 3, Subtree{0, 2}));
+  EXPECT_FALSE(Lookup(*set, 1, Subtree{0, 6}));
+  EXPECT_FALSE(Lookup(*set, 1, Subtree{4, 8}));
+  EXPECT_FALSE(Lookup(*set, 1, Subtree{8, 10}));
+  EXPECT_FALSE(Lookup(*set, 1, Subtree{12, 16}));
+  EXPECT_FALSE(Lookup(*set, 1, Subtree{16, 32}));
+}
+
+TEST_F(TrustedSubtreeSetTest, LookupSubtreeHashEmpty) {
+  std::shared_ptr<const TrustedSubtreeSet> empty =
+      TrustedSubtreeSet::Create({});
+  ASSERT_TRUE(empty);
+  EXPECT_FALSE(Lookup(*empty, 1, Subtree{0, 4}));
+
+  std::shared_ptr<const TrustedSubtreeSet> empty_log =
+      TrustedSubtreeSet::Create({{1, {}}});
+  ASSERT_TRUE(empty_log);
+  EXPECT_FALSE(Lookup(*empty_log, 1, Subtree{0, 4}));
+}
+
+TEST_F(TrustedSubtreeSetTest, DebugString) {
+  std::shared_ptr<const TrustedSubtreeSet> set = TrustedSubtreeSet::Create({});
+  ASSERT_TRUE(set);
+  EXPECT_EQ(set->DebugString(), "none");
+
+  set = TrustedSubtreeSet::Create({{1, {}}});
+  ASSERT_TRUE(set);
+  EXPECT_EQ(set->DebugString(), "log 1:empty");
+
+  set = TrustedSubtreeSet::Create({
+      {1, {MakeSubtree(0, 4, 1), MakeSubtree(8, 12, 2)}},
+      {2, {}},
+      {3, {MakeSubtree(16, 32, 3)}},
+  });
+  ASSERT_TRUE(set);
+  EXPECT_EQ(set->DebugString(),
+            "log 1:2 subtrees(0..12), log 2:empty, log 3:1 subtrees(16..32)");
+}
+
+TEST_F(TrustedSubtreeSetTest, MTCAnchorCertTrust) {
+  std::shared_ptr<const MTCAnchor> anchor =
+      MakeMTCAnchor({{1, {MakeSubtree(0, 4, 1), MakeSubtree(8, 12, 2)}}});
+  ASSERT_TRUE(anchor->IsValid());
+
+  CertificateTrust trust = anchor->CertTrust();
+  EXPECT_TRUE(trust.IsTrustAnchor());
+  ASSERT_TRUE(trust.trusted_subtrees);
+  // CertTrust() shares the MTCAnchor's TrustedSubtreeSet rather than copying.
+  EXPECT_EQ(trust.trusted_subtrees.get(),
+            anchor->CertTrust().trusted_subtrees.get());
+
+  // The CertificateTrust's subtrees agree with the MTCAnchor.
+  for (Subtree range : {Subtree{0, 4}, Subtree{8, 12}, Subtree{4, 8}}) {
+    SCOPED_TRACE(std::to_string(range.start) + ".." +
+                 std::to_string(range.end));
+    std::optional<std::vector<uint8_t>> from_trust =
+        Lookup(*trust.trusted_subtrees, 1, range);
+    std::optional<TreeHashConstSpan> from_anchor =
+        anchor->SubtreeHash(1, range);
+    ASSERT_EQ(from_trust.has_value(), from_anchor.has_value());
+    if (from_trust) {
+      EXPECT_EQ(*from_trust,
+                std::vector<uint8_t>(from_anchor->begin(), from_anchor->end()));
+    }
+  }
+
+  EXPECT_EQ(trust.ToDebugString(),
+            "TRUSTED_ANCHOR+trusted_subtrees(log 1:2 subtrees(0..12))");
+}
+
+TEST_F(TrustedSubtreeSetTest, MTCAnchorCertTrustNoSubtrees) {
+  std::shared_ptr<const MTCAnchor> anchor = MakeMTCAnchor({});
+  ASSERT_TRUE(anchor->IsValid());
+
+  CertificateTrust trust = anchor->CertTrust();
+  ASSERT_TRUE(trust.trusted_subtrees);
+  EXPECT_EQ(trust.ToDebugString(), "TRUSTED_ANCHOR+trusted_subtrees(none)");
+}
+
+TEST_F(TrustedSubtreeSetTest, NonMTCCertTrust) {
+  for (const CertificateTrust &trust :
+       {CertificateTrust::ForTrustAnchor(),
+        CertificateTrust::ForTrustAnchorOrLeaf(),
+        CertificateTrust::ForTrustedLeaf(), CertificateTrust::ForUnspecified(),
+        CertificateTrust::ForDistrusted()}) {
+    SCOPED_TRACE(trust.ToDebugString());
+    EXPECT_FALSE(trust.trusted_subtrees);
+    EXPECT_EQ(trust.ToDebugString().find("trusted_subtrees"),
+              std::string::npos);
+  }
+}
+
+// An MTCAnchor constructed directly with invalid subtrees reports itself as
+// invalid, and lookups through it fail rather than crashing.
+TEST_F(TrustedSubtreeSetTest, MTCAnchorInvalidSubtrees) {
+  std::shared_ptr<const MTCAnchor> anchor =
+      MakeMTCAnchor({{1, {MakeSubtree(8, 12, 1), MakeSubtree(0, 4, 2)}}});
+  EXPECT_FALSE(anchor->IsValid());
+  EXPECT_FALSE(anchor->SubtreeHash(1, Subtree{0, 4}));
+  EXPECT_FALSE(anchor->SubtreeHash(1, Subtree{8, 12}));
+  EXPECT_EQ(anchor->TrustedSubtreesDebugString(), "Invalid");
+
+  CertificateTrust trust = anchor->CertTrust();
+  EXPECT_FALSE(trust.trusted_subtrees);
+  EXPECT_EQ(trust.ToDebugString(), "TRUSTED_ANCHOR");
+}
+
 }  // namespace
 BSSL_NAMESPACE_END