pki/merkle_tree_unittest.cc

// Copyright 2025 The BoringSSL Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "merkle_tree.h"

#include <cassert>
#include <cstdint>
#include <limits>
#include <sstream>
#include <string>

#include <gmock/gmock.h>
#include <gtest/gtest.h>
#include <openssl/digest.h>
#include <openssl/sha2.h>

#include "../crypto/test/file_test.h"
#include "../crypto/test/test_util.h"

BSSL_NAMESPACE_BEGIN

namespace {

// Returns a subtree consistency proof for `subtree` in the first `n` elements
// of `tree`. This is currently implemented recursively, matching the
// specification. If we ever need to expose it, we can implement it more
// efficiently.
std::vector<uint8_t> SubtreeConsistencyProof(const MerkleTree &mt,
                                             Subtree subtree,
                                             const Subtree &tree,
                                             bool known_hash = true) {
  BSSL_CHECK(subtree.IsValid());
  BSSL_CHECK(tree.IsValid());
  BSSL_CHECK(tree.Contains(subtree));

  if (subtree.Size() == 0) {
    return {};
  }
  if (subtree == tree) {
    if (known_hash) {
      return {};
    }
    TreeHash h = mt.SubtreeHash(subtree);
    return std::vector(h.begin(), h.end());
  }

  uint64_t k = tree.Split();
  Subtree subproof_tree, mth_tree;
  if (subtree.end <= k) {
    subproof_tree = tree.Left();
    mth_tree = tree.Right();
  } else if (subtree.start >= k) {
    mth_tree = tree.Left();
    subproof_tree = tree.Right();
  } else {
    subtree.start = k;
    mth_tree = tree.Left();
    subproof_tree = tree.Right();
    known_hash = false;
  }
  std::vector<uint8_t> subproof =
      SubtreeConsistencyProof(mt, subtree, subproof_tree, known_hash);
  TreeHash mth = mt.SubtreeHash(mth_tree);
  subproof.insert(subproof.end(), mth.begin(), mth.end());
  return subproof;
}

std::vector<std::vector<uint8_t>> MakeTestEntries(std::string_view label,
                                                  size_t n) {
  std::vector<std::vector<uint8_t>> entries;
  entries.reserve(n);
  for (size_t i = 0; i < n; i++) {
    std::vector<uint8_t> entry(label.begin(), label.end());
    for (size_t j = 0; j < 8; j++) {
      entry.push_back(static_cast<uint8_t>(i >> (j * 8)));
    }
    entries.push_back(std::move(entry));
  }
  return entries;
}

// Generates test entries compatible with the "accumulated" tests described
// in appendix C of draft-ietf-plants-merkle-tree-certs.
// This works for `n` up to 255.
std::vector<std::vector<uint8_t>> MakeAccumulatedTestEntries(size_t n) {
  std::vector<std::vector<uint8_t>> entries;
  entries.reserve(n);
  for (size_t i = 0; i < n; i++) {
    entries.push_back({static_cast<uint8_t>(i)});
  }
  return entries;
}

std::vector<uint8_t> ConcatProof(const std::vector<TreeHash> &proof) {
  std::vector<uint8_t> out;
  for (const auto &p : proof) {
    out.insert(out.end(), p.begin(), p.end());
  }
  return out;
}

TEST(MerkleTreeTest, SubtreeIsValid) {
  // An empty subtree is valid.
  EXPECT_TRUE((Subtree{0, 0}.IsValid()));
  // But if the end is before start, it's invalid.
  EXPECT_FALSE((Subtree{1, 0}.IsValid()));
  // A subtree of the maximum expressible size is valid.
  EXPECT_TRUE((Subtree{0, std::numeric_limits<uint64_t>::max()}.IsValid()));

  // Subtrees don't have to start at 0.
  EXPECT_TRUE((Subtree{4, 8}.IsValid()));
  // But if they don't start at 0, there's a limit to how big they can be.
  EXPECT_FALSE((Subtree{4, 9}.IsValid()));
  // Subtrees can have a ragged right edge.
  EXPECT_TRUE((Subtree{4, 6}.IsValid()));
  EXPECT_TRUE((Subtree{0, 6}.IsValid()));
}

TEST(MerkleTreeTest, SubtreeSplit) {
  // Empty subtree.
  EXPECT_EQ((Subtree{24601, 24601}).Split(), 24601ul);
  // Single-item subtree.
  EXPECT_EQ((Subtree{1336, 1337}).Split(), 1337ul);
  // Two items in subtree.
  EXPECT_EQ((Subtree{42, 44}).Split(), 43ul);
  // Subtree size is 1 less than a power of 2.
  EXPECT_EQ((Subtree{0, 31}).Split(), 16ul);
  // Subtree size is a power of 2.
  EXPECT_EQ((Subtree{64, 128}).Split(), 96ul);
  /// Subtree size is 1 more than a power of 2.
  EXPECT_EQ((Subtree{0, 257}).Split(), 256ul);

  static const uint64_t u64_max = std::numeric_limits<uint64_t>::max();
  // Maximum size tree.
  EXPECT_EQ((Subtree{0, u64_max}).Split(), 1ull << 63);
  // Small tree, with end at maximum value.
  EXPECT_EQ((Subtree{u64_max - 3, u64_max}).Split(), u64_max - 1);
}

// This executes the "accumulated" Subtree Hashes test from appendix C.1 of
// draft-ietf-plants-merkle-tree-certs.
TEST(MerkleTreeTest, AccumulatedSubtreeHashes) {
  auto entries = MakeAccumulatedTestEntries(256);
  MerkleTreeInMemory tree(entries);

  ScopedEVP_MD_CTX ctx;
  EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr);

  for (uint64_t end = 0; end < 131; ++end) {
    for (uint64_t start = 0; start < end + 1; ++start) {
      Subtree subtree{start, end};
      if (!subtree.IsValid()) {
        continue;
      }
      std::stringstream ss;
      ss << "[" << std::to_string(start) << ", " << std::to_string(end) << ") "
         << EncodeHex(tree.SubtreeHash(subtree)) << "\n";
      std::string str = ss.str();
      EVP_DigestUpdate(ctx.get(), str.data(), str.size());
    }
  }
  std::vector<uint8_t> final(EVP_MAX_MD_SIZE);
  unsigned final_size;
  EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size);
  final.resize(final_size);

  const uint8_t kExpected[] = {
      0xb8, 0x28, 0x06, 0xad, 0x42, 0x65, 0xbb, 0x15, 0x1c, 0x11, 0x19,
      0xc0, 0xf4, 0xdb, 0x43, 0x7b, 0xb4, 0xd1, 0xa1, 0xf8, 0x87, 0xb3,
      0xa7, 0xfb, 0xa1, 0xcd, 0x4e, 0xbf, 0x55, 0x2e, 0x3e, 0x81,
  };
  EXPECT_EQ(Bytes(final), Bytes(kExpected));
}

// This executes the "accumulated" Subtree Inclusion Proofs test from appendix
// C.2 of draft-ietf-plants-merkle-tree-certs.
TEST(MerkleTreeTest, AccumulatedSubtreeInclusionProofs) {
  auto entries = MakeAccumulatedTestEntries(256);
  MerkleTreeInMemory tree(entries);

  ScopedEVP_MD_CTX ctx;
  EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr);

  for (uint64_t end = 0; end < 131; ++end) {
    for (uint64_t start = 0; start < end + 1; ++start) {
      Subtree subtree{start, end};
      if (!subtree.IsValid()) {
        continue;
      }
      for (uint64_t index = start; index < end; ++index) {
        std::stringstream ss;
        ss << std::to_string(index) << " [" << std::to_string(start) << ", "
           << std::to_string(end) << ")";
        auto proof = tree.SubtreeInclusionProof(index, subtree);
        for (size_t i = 0; i < proof.size(); i += SHA256_DIGEST_LENGTH) {
          ss << " " << EncodeHex(Span(proof).subspan(i, SHA256_DIGEST_LENGTH));
        }
        ss << "\n";
        std::string str = ss.str();
        EVP_DigestUpdate(ctx.get(), str.data(), str.size());
      }
    }
  }
  std::vector<uint8_t> final(EVP_MAX_MD_SIZE);
  unsigned final_size;
  EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size);
  final.resize(final_size);

  const uint8_t kExpected[] = {
      0xac, 0x2a, 0x8f, 0x98, 0x9e, 0x44, 0xd9, 0x9e, 0x39, 0x9d, 0xb4,
      0x48, 0x05, 0x0f, 0xf5, 0xf1, 0x97, 0x57, 0xdf, 0x53, 0xcf, 0xb7,
      0x16, 0xaa, 0x81, 0x01, 0x5d, 0x39, 0x55, 0xd8, 0x16, 0x3f,
  };
  EXPECT_EQ(Bytes(final), Bytes(kExpected));
}

// This executes the "accumulated" Subtree Consistency Proofs test from appendix
// C.3 of draft-ietf-plants-merkle-tree-certs.
TEST(MerkleTreeTest, AccumulatedSubtreeConsistencyProofs) {
  auto entries = MakeAccumulatedTestEntries(256);
  MerkleTreeInMemory tree(entries);

  ScopedEVP_MD_CTX ctx;
  EVP_DigestInit_ex(ctx.get(), EVP_sha256(), nullptr);

  for (size_t n = 0; n < 131; ++n) {
    Subtree final_tree{0, n};
    for (uint64_t end = 0; end < n + 1; ++end) {
      for (uint64_t start = 0; start < end + 1; ++start) {
        Subtree subtree{start, end};
        if (!subtree.IsValid()) {
          continue;
        }
        std::stringstream ss;
        ss << "[" << std::to_string(start) << ", " << std::to_string(end)
           << ") " << std::to_string(n);
        auto proof = SubtreeConsistencyProof(tree, subtree, final_tree);
        for (size_t i = 0; i < proof.size(); i += SHA256_DIGEST_LENGTH) {
          ss << " " << EncodeHex(Span(proof).subspan(i, SHA256_DIGEST_LENGTH));
        }
        ss << "\n";
        std::string str = ss.str();
        EVP_DigestUpdate(ctx.get(), str.data(), str.size());
      }
    }
  }
  std::vector<uint8_t> final(EVP_MAX_MD_SIZE);
  unsigned final_size;
  EVP_DigestFinal_ex(ctx.get(), final.data(), &final_size);
  final.resize(final_size);

  const uint8_t kExpected[] = {
      0x10, 0xfa, 0x99, 0xb3, 0x7b, 0xf9, 0xbf, 0x9f, 0xfa, 0x26, 0xb4,
      0x12, 0xfb, 0xd9, 0x8b, 0xd7, 0x53, 0x63, 0x25, 0x6d, 0x0b, 0x75,
      0xd6, 0x1b, 0xc4, 0x53, 0x8b, 0x9c, 0x9c, 0x5a, 0x0a, 0x74,
  };
  EXPECT_EQ(Bytes(final), Bytes(kExpected));
}

TEST(MerkleTreeTest, VerifySubtreeInclusionProof) {
  auto entries = MakeTestEntries("label", 847);
  MerkleTreeInMemory tree(entries);

  uint64_t index = 0;
  auto node_hash = tree.SubtreeHash({index, index + 1});
  Subtree subtree{0, 16};
  auto proof = tree.SubtreeInclusionProof(index, subtree);
  EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(
      subtree.end, {index, index + 1}, proof, node_hash,
      tree.SubtreeHash(subtree)));
  // Check again with EvaluateMerkleSubtreeInclusionProof
  auto root_hash =
      EvaluateMerkleSubtreeInclusionProof(proof, index, node_hash, subtree);
  ASSERT_TRUE(root_hash.has_value());
  EXPECT_EQ(root_hash, tree.SubtreeHash(subtree));

  // Build and verify a proof from a subtree with start != 0
  index = 845;
  node_hash = tree.SubtreeHash({index, index + 1});
  subtree = {840, 847};
  proof = tree.SubtreeInclusionProof(index, subtree);
  EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(
      subtree.Size(), {index - subtree.start, index - subtree.start + 1}, proof,
      node_hash, tree.SubtreeHash(subtree)));
  // Check again with EvaluateMerkleSubtreeInclusionProof
  root_hash =
      EvaluateMerkleSubtreeInclusionProof(proof, index, node_hash, subtree);
  ASSERT_TRUE(root_hash.has_value());
  EXPECT_EQ(root_hash, tree.SubtreeHash(subtree));
}

TEST(MerkleTreeTest, SubtreeInclusionProofInvalidArgs) {
  auto entries = MakeTestEntries("label", 847);
  MerkleTreeInMemory tree(entries);

  uint64_t index = 845;
  auto node_hash = tree.SubtreeHash({index, index + 1});
  Subtree subtree = {840, 847};
  auto proof = tree.SubtreeInclusionProof(index, subtree);

  // If the wrong node hash is passed in, the function will still compute a
  // root hash, but it won't match the expected value.
  auto wrong_node_hash = tree.SubtreeHash({index + 1, index + 2});
  auto root_hash = EvaluateMerkleSubtreeInclusionProof(
      proof, index, wrong_node_hash, subtree);
  ASSERT_TRUE(root_hash.has_value());
  EXPECT_NE(root_hash, tree.SubtreeHash(subtree));

  // If the subtree isn't valid, the function will fail.
  ASSERT_FALSE(
      EvaluateMerkleSubtreeInclusionProof(proof, index, node_hash, {840, 849}));

  // If the index isn't contained within the subtree, the function will fail.
  ASSERT_FALSE(
      EvaluateMerkleSubtreeInclusionProof(proof, 848, node_hash, {840, 847}));
}

// Test that the computed consistency proofs match the examples given in RFC
// 9162 section 2.1.5.
TEST(MerkleTreeTest, SubtreeConsistencyProofRFC9162) {
  auto entries = MakeTestEntries("label", 7);
  MerkleTreeInMemory tree(entries);

  // The example from section 2.1.5 has a final tree with 7 leaves.
  Subtree final_tree{0, 7};

  // The examples refer to letters representing the hashes of various subtrees
  // within that tree. a and e aren't used in any of the examples.
  auto b = tree.SubtreeHash({1, 2});
  auto c = tree.SubtreeHash({2, 3});
  auto d = tree.SubtreeHash({3, 4});
  auto f = tree.SubtreeHash({5, 6});
  auto g = tree.SubtreeHash({0, 2});
  auto h = tree.SubtreeHash({2, 4});
  auto i = tree.SubtreeHash({4, 6});
  auto j = tree.SubtreeHash({6, 7});
  auto k = tree.SubtreeHash({0, 4});
  auto l = tree.SubtreeHash({4, 7});

  // Inclusion proofs:

  // Section 2.1.5: "The inclusion proof for `d0` is `[b, h, l]`."
  auto d0_proof = tree.SubtreeInclusionProof(0, final_tree);
  EXPECT_EQ(d0_proof, ConcatProof({b, h, l}));

  // Section 2.1.5: "The inclusion proof for `d3` is `[c, g, l]`."
  auto d3_proof = tree.SubtreeInclusionProof(3, final_tree);
  EXPECT_EQ(d3_proof, ConcatProof({c, g, l}));

  // Section 2.1.5: "The inclusion proof for `d4` is `[f, j, k]`."
  auto d4_proof = tree.SubtreeInclusionProof(4, final_tree);
  EXPECT_EQ(d4_proof, ConcatProof({f, j, k}));

  // Section 2.1.5: "The inclusion proof for `d6` is `[i, k]`."
  auto d6_proof = tree.SubtreeInclusionProof(6, final_tree);
  EXPECT_EQ(d6_proof, ConcatProof({i, k}));

  // Consistency proofs:

  // The consistency proofs refer to the lettered hashes above, as well as some
  // hashes of the tree as it was incrementally built.
  Subtree hash0_subtree = {0, 3};
  Subtree hash1_subtree = {0, 4};
  auto hash1 = tree.SubtreeHash(hash1_subtree);
  ASSERT_EQ(hash1, k);
  Subtree hash2_subtree = {0, 6};

  // "The consistency proof between hash0 and hash is [c, d, g, l]."
  auto hash0_proof = SubtreeConsistencyProof(tree, hash0_subtree, final_tree);
  EXPECT_EQ(hash0_proof, ConcatProof({c, d, g, l}));

  // "The consistency proof between hash1 and hash is [l]."
  auto hash1_proof = SubtreeConsistencyProof(tree, hash1_subtree, final_tree);
  EXPECT_EQ(hash1_proof, ConcatProof({l}));

  // "The consistency proof between hash2 and hash is [i, j, k]."
  auto hash2_proof = SubtreeConsistencyProof(tree, hash2_subtree, final_tree);
  EXPECT_EQ(hash2_proof, ConcatProof({i, j, k}));
}

TEST(MerkleTreeTest, ValidProofsTest) {
  uint64_t n = 4, start = 0, end = 3;
  Subtree full_tree{0, n};
  auto entries = MakeTestEntries("label", n);
  MerkleTreeInMemory tree(entries);

  auto tree_hash = tree.SubtreeHash(full_tree);
  Subtree subtree{start, end};
  ASSERT_TRUE(subtree.IsValid());
  auto subtree_hash = tree.SubtreeHash(subtree);

  auto proof = SubtreeConsistencyProof(tree, subtree, full_tree);
  EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(n, subtree, proof,
                                                  subtree_hash, tree_hash));
}

TEST(MerkleTreeTest, ValidProofs) {
  // As of the time of writing this test, a run was performed with limit=257 and
  // the test passed. This value is set to 129 to balance how much of the space
  // to explore with test execution time. In particular, in an unoptimized
  // build, limit=257 takes about 4 seconds.
  for (bool incremental : {false, true}) {
    SCOPED_TRACE(incremental);

    uint64_t limit = 129;
    auto entries = MakeTestEntries("label", limit);
    MerkleTreeInMemory tree;
    if (incremental) {
      for (const auto &entry : entries) {
        tree.Append(entry);
      }
    } else {
      tree = MerkleTreeInMemory(entries);
    }

    // Exhaustively test subtree consistency proofs.
    for (uint64_t n = 0; n < limit; n++) {
      Subtree full_tree{0, n};
      auto tree_hash = tree.SubtreeHash(full_tree);
      for (uint64_t end = 0; end <= n; end++) {
        for (uint64_t start = 0; start < end; start++) {
          Subtree subtree{start, end};
          if (!subtree.IsValid()) {
            continue;
          }
          SCOPED_TRACE(testing::Message() << "Tree n=" << n << ", start: "
                                          << start << ", end: " << end);
          auto subtree_hash = tree.SubtreeHash(subtree);
          auto proof = SubtreeConsistencyProof(tree, subtree, full_tree);
          EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(
              n, subtree, proof, subtree_hash, tree_hash));
        }
      }
    }

    // Exhaustively test subtree inclusion proofs.
    for (uint64_t end = 0; end <= limit; end++) {
      for (uint64_t start = 0; start < end; start++) {
        Subtree subtree{start, end};
        if (!subtree.IsValid()) {
          continue;
        }
        for (uint64_t index = start; index < end; index++) {
          SCOPED_TRACE(testing::Message() << "index: " << index << ", start: "
                                          << start << ", end: " << end);
          auto subtree_hash = tree.SubtreeHash(subtree);
          auto entry_hash = tree.SubtreeHash({index, index + 1});
          auto proof = tree.SubtreeInclusionProof(index, subtree);
          auto computed_hash = EvaluateMerkleSubtreeInclusionProof(
              proof, index, entry_hash, subtree);
          EXPECT_EQ(computed_hash, subtree_hash);

          // A subtree inclusion proof is a special case of a consistency proof.
          auto proof2 =
              SubtreeConsistencyProof(tree, {index, index + 1}, subtree);
          EXPECT_EQ(proof, proof2);
        }
      }
    }
  }
}

class MerkleTreeLarge : public MerkleTree {
 public:
  // Constructs a Merkle Tree over 2^64 - 1 copies of `entry`.
  explicit MerkleTreeLarge(Span<const uint8_t> entry) {
    HashLeaf(entry, levels_[0]);
    for (size_t i = 1; i < levels_.size(); i++) {
      HashNode(levels_[i - 1], levels_[i - 1], levels_[i]);
    }
  }

  uint64_t Size() const override {
    return std::numeric_limits<uint64_t>::max();
  }

  TreeHash GetNode(size_t level, uint64_t index) const override {
    BSSL_CHECK(level < 64);
    return levels_[level];
  }

 private:
  std::array<TreeHash, 64> levels_;
};

TEST(MerkleTreeTest, VeryLargeProofs) {
  MerkleTreeLarge tree(StringAsBytes("entry"));

  Subtree fullest_tree = {0, std::numeric_limits<uint64_t>::max()};
  auto root_hash = tree.SubtreeHash(fullest_tree);

  Subtree test_subtrees[] = {
      fullest_tree,
      {0, 1},
      {0, 1ull << 63},
      {1ull << 63, std::numeric_limits<uint64_t>::max()},
      {std::numeric_limits<uint64_t>::max() - 1,
       std::numeric_limits<uint64_t>::max()},
  };
  for (auto subtree : test_subtrees) {
    SCOPED_TRACE(testing::Message() << "Subtree start: " << subtree.start
                                    << ", end: " << subtree.end);

    auto proof = SubtreeConsistencyProof(tree, subtree, fullest_tree);
    EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(
        fullest_tree.end, subtree, proof, tree.SubtreeHash(subtree),
        root_hash));
  }
}

void InclusionProofFileTest(FileTest *t) {
  uint64_t index, start, end;
  ASSERT_TRUE(t->GetUint64(&index, "Index"));
  ASSERT_TRUE(t->GetUint64(&start, "Start"));
  ASSERT_TRUE(t->GetUint64(&end, "End"));
  std::vector<uint8_t> entry_hash, subtree_hash, proof;
  ASSERT_TRUE(t->GetBase64(&entry_hash, "EntryHash"));
  ASSERT_TRUE(t->GetBase64(&subtree_hash, "SubtreeHash"));
  ASSERT_TRUE(t->GetBase64(&proof, "Proof"));

  const Subtree subtree{start, end};
  TreeHashConstSpan entry_hash_span(entry_hash);
  TreeHashConstSpan subtree_hash_span(subtree_hash);

  auto computed_hash = EvaluateMerkleSubtreeInclusionProof(
      proof, index, entry_hash_span, subtree);
  EXPECT_TRUE(computed_hash.has_value());
  EXPECT_EQ(*computed_hash, subtree_hash_span);

  // Truncated inclusion proofs don't work.
  const size_t original_proof_size = proof.size();
  EXPECT_FALSE(EvaluateMerkleSubtreeInclusionProof(
      Span(proof).subspan(original_proof_size - 1), index, entry_hash_span,
      subtree));
  EXPECT_FALSE(EvaluateMerkleSubtreeInclusionProof(
      Span(proof).subspan(original_proof_size - EVP_MD_size(EVP_sha256())),
      index, entry_hash_span, subtree));

  // Extended inclusion proofs don't work.
  proof.resize(original_proof_size + EVP_MD_size(EVP_sha256()));
  EXPECT_FALSE(EvaluateMerkleSubtreeInclusionProof(
      Span(proof).subspan(original_proof_size + 1), index, entry_hash_span,
      subtree));
  EXPECT_FALSE(EvaluateMerkleSubtreeInclusionProof(proof, index,
                                                   entry_hash_span, subtree));

  // Bitflipped inclusion proof should produce a wrong subtree hash.
  proof.resize(original_proof_size);
  proof[0] ^= 1;
  computed_hash = EvaluateMerkleSubtreeInclusionProof(proof, index,
                                                      entry_hash_span, subtree);
  EXPECT_TRUE(computed_hash.has_value());
  EXPECT_NE(*computed_hash, subtree_hash_span);
}

TEST(MerkleTreeTest, LargeInclusionProofs) {
  FileTestGTest(
      "crypto/x509/test/mtc/large_merkle_tree_inclusion_proof_tests.txt",
      InclusionProofFileTest);
}

void ConsistencyProofFileTest(FileTest *t) {
  uint64_t start, end, tree_size;
  ASSERT_TRUE(t->GetUint64(&start, "Start"));
  ASSERT_TRUE(t->GetUint64(&end, "End"));
  ASSERT_TRUE(t->GetUint64(&tree_size, "TreeSize"));
  std::vector<uint8_t> subtree_hash, tree_hash, proof;
  ASSERT_TRUE(t->GetBase64(&subtree_hash, "SubtreeHash"));
  ASSERT_TRUE(t->GetBase64(&tree_hash, "TreeHash"));
  if (!t->HasAttribute("ProofEmpty")) {
    ASSERT_TRUE(t->GetBase64(&proof, "Proof"));
  }

  const Subtree subtree{start, end};
  TreeHashConstSpan subtree_hash_span(subtree_hash);
  TreeHashConstSpan tree_hash_span(tree_hash);

  EXPECT_TRUE(VerifyMerkleSubtreeConsistencyProof(
      tree_size, subtree, proof, subtree_hash_span, tree_hash_span));

  // Truncated consistency proofs don't work.
  const size_t original_proof_size = proof.size();
  if (original_proof_size > 0) {
    EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof(
        tree_size, subtree, Span(proof).subspan(original_proof_size - 1),
        subtree_hash_span, tree_hash_span));
    EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof(
        tree_size, subtree,
        Span(proof).subspan(original_proof_size - EVP_MD_size(EVP_sha256())),
        subtree_hash_span, tree_hash_span));
  }

  // Extended consistency proofs don't work.
  proof.resize(original_proof_size + EVP_MD_size(EVP_sha256()));
  EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof(
      tree_size, subtree, Span(proof).subspan(original_proof_size + 1),
      subtree_hash_span, tree_hash_span));
  EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof(
      tree_size, subtree, proof, subtree_hash_span, tree_hash_span));

  // Bitflipped input subtree hash should either fail verification.
  proof.resize(original_proof_size);
  subtree_hash[0] ^= 1;
  EXPECT_FALSE(VerifyMerkleSubtreeConsistencyProof(
      tree_size, subtree, proof, subtree_hash_span, tree_hash_span));
}

TEST(MerkleTreeTest, LargeConsistencyProofs) {
  FileTestGTest(
      "crypto/x509/test/mtc/large_merkle_tree_consistency_proof_tests.txt",
      ConsistencyProofFileTest);
}

}  // namespace

BSSL_NAMESPACE_END