Adds a VerifyAuditProof method to CTLogVerifier

net/cert/ct_log_verifier_unittest.cc

Index: net/cert/ct_log_verifier_unittest.cc
diff --git a/net/cert/ct_log_verifier_unittest.cc b/net/cert/ct_log_verifier_unittest.cc
index 754d3e39073c50f89c3c83b1d3d623a7ef782659..6bac844bfc721d1f4baa663ce7c48c5613b985b9 100644
--- a/net/cert/ct_log_verifier_unittest.cc
+++ b/net/cert/ct_log_verifier_unittest.cc
@@ -6,14 +6,19 @@
 
 #include <stdint.h>
 
+#include <map>
 #include <memory>
 #include <string>
+#include <utility>
+#include <vector>
 
+#include "base/macros.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/time/time.h"
 #include "crypto/secure_hash.h"
 #include "net/base/hash_value.h"
 #include "net/cert/ct_log_verifier_util.h"
+#include "net/cert/merkle_audit_proof.h"
 #include "net/cert/merkle_consistency_proof.h"
 #include "net/cert/signed_certificate_timestamp.h"
 #include "net/cert/signed_tree_head.h"
@@ -24,6 +29,11 @@ namespace net {
 
 namespace {
 
+// Enables the node hash cache used to accelerate some of the tests.
+// The cache reduces the duration of some tests by at least 50%, in exchange for
+// significantly higher memory usage.
+const bool kIsHashCacheEnabled = true;
+
 // Calculate the power of two nearest to, but less than, |n|.
 // |n| must be at least 2.
 uint64_t CalculateNearestPowerOfTwo(uint64_t n) {
@@ -41,8 +51,8 @@ uint64_t CalculateNearestPowerOfTwo(uint64_t n) {
 
 // A single hash node.
 struct TestVector {
-  const char* const str;
-  size_t length_bytes;
+  const char* const str;  // hex string
+  size_t length_bytes;    // number of bytes represented by |str|
 };
 
 // A single consistency proof. Contains the old and new tree sizes
@@ -61,8 +71,20 @@ struct ProofTestVector {
 const TestVector kSHA256EmptyTreeHash = {
     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32};
 
-// Node hashes for a sample tree of size 8 (each element in this array is
-// a node hash, not leaf data; order represents order of the nodes in the tree).
+// Hashes of the leaf data for the sample tree (8 leaves).
+const TestVector kSHA256LeafHashes[8] = {
+    {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
+    {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
+    {"0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7", 32},
+    {"07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7", 32},
+    {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
+    {"4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658", 32},
+    {"b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f", 32},
+    {"46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1", 32},
+};
+
+// Incremental roots from building the sample tree of size 8 leaf-by-leaf.
+// The first entry is the root at size 0, the last is the root at size 8.
 const TestVector kSHA256Roots[8] = {
     {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
     {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
@@ -73,8 +95,7 @@ const TestVector kSHA256Roots[8] = {
     {"ddb89be403809e325750d3d263cd78929c2942b7942a34b77e122c9594a74c8c", 32},
     {"5dc9da79a70659a9ad559cb701ded9a2ab9d823aad2f4960cfe370eff4604328", 32}};
 
-// A collection of consistency proofs between various sub-trees of the tree
-// defined by |kSHA256Roots|.
+// A collection of consistency proofs between various nodes of the sample tree.
 const ProofTestVector kSHA256Proofs[4] = {
     // Empty consistency proof between trees of the same size (1).
     {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
@@ -105,6 +126,49 @@ const ProofTestVector kSHA256Proofs[4] = {
       {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
       {"", 0}}}};
 
+// A single audit proof. Contains the leaf index (leaf), tree size (snapshot),
+// the length of the proof (proof_length) and at most 3 proof nodes (all test
+// proofs will be for a tree of size 8).
+struct PathTestVector {
+  int leaf;
+  int snapshot;
+  int path_length;
+  TestVector path[3];
+};
+
+// A collection of audit proofs for various leaves and sub-trees of the tree
+// defined by |kSHA256Roots|.
+const PathTestVector kSHA256Paths[6] = {
+    {0, 0, 0, {{"", 0}, {"", 0}, {"", 0}}},
+    {1, 1, 0, {{"", 0}, {"", 0}, {"", 0}}},
+    {1,
+     8,
+     3,
+     {{"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7", 32},
+      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
+      {"6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4",
+       32}}},
+    {6,
+     8,
+     3,
+     {{"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", 32},
+      {"ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0", 32},
+      {"d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7",
+       32}}},
+    {3,
+     3,
+     1,
+     {{"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", 32},
+      {"", 0},
+      {"", 0}}},
+    {2,
+     5,
+     3,
+     {{"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d", 32},
+      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e", 32},
+      {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
+       32}}}};
+
 // Decodes a hexadecimal string into the binary data it represents.
 std::string HexToBytes(const char* hex_data, size_t hex_data_length) {
   std::vector<uint8_t> output;
@@ -115,9 +179,14 @@ std::string HexToBytes(const char* hex_data, size_t hex_data_length) {
   return result;
 }
 
+std::string HexToBytes(const TestVector& x) {
+  std::string bytes = HexToBytes(x.str, x.length_bytes * 2);
+  CHECK_EQ(x.length_bytes, bytes.size());
+  return bytes;
+}
+
 std::string GetEmptyTreeHash() {
-  return HexToBytes(kSHA256EmptyTreeHash.str,
-                    kSHA256EmptyTreeHash.length_bytes);
+  return HexToBytes(kSHA256EmptyTreeHash);
 }
 
 // Creates a ct::MerkleConsistencyProof and returns the result of
@@ -134,6 +203,19 @@ bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
       old_tree_root, new_tree_root);
 }
 
+bool VerifyAuditProof(scoped_refptr<const CTLogVerifier> log,
+                      uint64_t leaf,
+                      uint64_t tree_size,
+                      const std::vector<std::string>& proof,
+                      const std::string& tree_root,
+                      const std::string& leaf_hash) {
+  // Test vectors use a 1-based leaf index, but our code uses a 0-based index.
+  if (leaf == 0)
+    return false;
+  return log->VerifyAuditProof(ct::MerkleAuditProof(leaf - 1, tree_size, proof),
+                               tree_root, leaf_hash);
+}
+
 class CTLogVerifierTest : public ::testing::Test {
  public:
   CTLogVerifierTest() {}
@@ -147,6 +229,76 @@ class CTLogVerifierTest : public ::testing::Test {
     ASSERT_EQ("ct.example.com", log_->dns_domain());
   }
 
+  // Given an audit proof for a leaf in the tree, asserts that it verifies and
+  // no other combination of leaves, snapshots and proof nodes verifies.
+  void VerifierCheck(int leaf,
+                     int tree_size,
+                     const std::vector<std::string>& path,
+                     const std::string& root,
+                     const std::string& leaf_hash) {
+    // Verify the original path.
+    EXPECT_TRUE(VerifyAuditProof(log_, leaf, tree_size, path, root, leaf_hash));
+
+    // Wrong leaf index.
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf - 1, tree_size, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf + 1, tree_size, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf ^ 2, tree_size, path, root, leaf_hash));
+
+    // Wrong tree height.
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size * 2, path, root, leaf_hash));
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size / 2, path, root, leaf_hash));
+
+    // Wrong root.
+    EXPECT_FALSE(VerifyAuditProof(log_, leaf, tree_size, path,
+                                  HexToBytes(kSHA256EmptyTreeHash), leaf_hash));
+
+    // Wrong paths.
+    std::vector<std::string> wrong_path;
+
+    // Modify a single element on the path.
+    for (size_t j = 0; j < path.size(); ++j) {
+      wrong_path = path;
+      wrong_path[j] = HexToBytes(kSHA256EmptyTreeHash);
+      EXPECT_FALSE(
+          VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    }
+
+    // Add garbage at the end of the path.
+    wrong_path = path;
+    wrong_path.push_back(std::string());
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    wrong_path.pop_back();
+
+    wrong_path.push_back(root);
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    wrong_path.pop_back();
+
+    // Remove a node from the end.
+    if (!wrong_path.empty()) {
+      wrong_path.pop_back();
+      EXPECT_FALSE(
+          VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+    }
+
+    // Add garbage in the beginning of the path.
+    wrong_path.clear();
+    wrong_path.push_back(std::string());
+    wrong_path.insert(wrong_path.end(), path.begin(), path.end());
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+
+    wrong_path[0] = root;
+    EXPECT_FALSE(
+        VerifyAuditProof(log_, leaf, tree_size, wrong_path, root, leaf_hash));
+  }
+
   // Given a consistency proof between two snapshots of the tree, asserts that
   // it verifies and no other combination of snapshots and proof nodes verifies.
   void VerifierConsistencyCheck(int snapshot1,
@@ -379,18 +531,18 @@ TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) {
 
   // Known good proofs.
   for (size_t i = 0; i < arraysize(kSHA256Proofs); ++i) {
+    SCOPED_TRACE(i);
     proof.clear();
     for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
       const TestVector& v = kSHA256Proofs[i].proof[j];
-      proof.push_back(HexToBytes(v.str, v.length_bytes));
+      proof.push_back(HexToBytes(v));
     }
     const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
     const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
     const TestVector& old_root = kSHA256Roots[snapshot1 - 1];
     const TestVector& new_root = kSHA256Roots[snapshot2 - 1];
-    VerifierConsistencyCheck(
-        snapshot1, snapshot2, HexToBytes(old_root.str, old_root.length_bytes),
-        HexToBytes(new_root.str, new_root.length_bytes), proof);
+    VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root),
+                             HexToBytes(new_root), proof);
   }
 }
 
@@ -402,10 +554,7 @@ const char kLeafPrefix[] = {'\x00'};
 // code.
 class TreeHasher {
  public:
-  static std::string HashEmpty() {
-    return HexToBytes(kSHA256EmptyTreeHash.str,
-                      kSHA256EmptyTreeHash.length_bytes);
-  }
+  static std::string HashEmpty() { return HexToBytes(kSHA256EmptyTreeHash); }
 
   static std::string HashLeaf(const std::string& leaf) {
     SHA256HashValue sha256;
@@ -426,16 +575,64 @@ class TreeHasher {
 // Recursively calculates the hash of the root given the leaf data
 // specified in |inputs|.
 std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
-  if (!input_size)
-    return TreeHasher::HashEmpty();
+  // Memoize function - this requires 34 bytes of memory per unique pair of
+  // |inputs| and |input_size|, plus std::map and std::string overhead.
+  // This results in a ~50% reduction in time required to run the
+  // *FromReferenceGenerator tests.
+  static std::map<std::pair<std::string*, uint64_t>, std::string> cache;
+  if (kIsHashCacheEnabled) {
+    auto iter = cache.find(std::make_pair(inputs, input_size));
+    if (iter != cache.end())
+      return iter->second;
+  }
+
+  std::string hash;
+  if (!input_size) {
+    hash = TreeHasher::HashEmpty();
+  } else if (input_size == 1) {
+    hash = TreeHasher::HashLeaf(inputs[0]);
+  } else {
+    const uint64_t split = CalculateNearestPowerOfTwo(input_size);
+
+    hash = ct::internal::HashNodes(
+        ReferenceMerkleTreeHash(&inputs[0], split),
+        ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  }
+
+  if (kIsHashCacheEnabled)
+    cache[std::make_pair(inputs, input_size)] = hash;
+
+  return hash;
+}
+
+// Reference implementation of Merkle paths. Path from leaf to root,
+// excluding the leaf and root themselves. Returns an audit proof for the tree
+// leaf with index |leaf| (1-based). The tree is designated by |inputs|.
+std::vector<std::string> ReferenceMerklePath(std::string* inputs,
+                                             uint64_t input_size,
+                                             uint64_t leaf) {
+  std::vector<std::string> path;
+  if (leaf > input_size || leaf == 0)
+    return path;
+
   if (input_size == 1)
-    return TreeHasher::HashLeaf(inputs[0]);
+    return path;
 
   const uint64_t split = CalculateNearestPowerOfTwo(input_size);
 
-  return ct::internal::HashNodes(
-      ReferenceMerkleTreeHash(&inputs[0], split),
-      ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  std::vector<std::string> subpath;
+  if (leaf <= split) {
+    subpath = ReferenceMerklePath(&inputs[0], split, leaf);
+    path.insert(path.end(), subpath.begin(), subpath.end());
+    path.push_back(ReferenceMerkleTreeHash(&inputs[split], input_size - split));
+  } else {
+    subpath =
+        ReferenceMerklePath(&inputs[split], input_size - split, leaf - split);
+    path.insert(path.end(), subpath.begin(), subpath.end());
+    path.push_back(ReferenceMerkleTreeHash(&inputs[0], split));
+  }
+
+  return path;
 }
 
 // Reference implementation of snapshot consistency. Returns a
@@ -503,9 +700,11 @@ TEST_F(CTLogVerifierTest,
   std::string root1, root2;
   // More tests with reference proof generator.
   for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
+    SCOPED_TRACE(tree_size);
     root2 = ReferenceMerkleTreeHash(data.data(), tree_size);
     // Repeat for each snapshot in range.
     for (size_t snapshot = 1; snapshot <= tree_size; ++snapshot) {
+      SCOPED_TRACE(snapshot);
       proof =
           ReferenceSnapshotConsistency(data.data(), tree_size, snapshot, true);
       root1 = ReferenceMerkleTreeHash(data.data(), snapshot);
@@ -514,6 +713,63 @@ TEST_F(CTLogVerifierTest,
   }
 }
 
+TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_EmptyProof) {
+  std::vector<std::string> path;
+  // Various invalid paths.
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 0, 0, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 0, 1, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 1, 0, path, std::string(), std::string()));
+  EXPECT_FALSE(
+      VerifyAuditProof(log_, 2, 1, path, std::string(), std::string()));
+
+  const std::string empty_hash = HexToBytes(kSHA256EmptyTreeHash);
+  EXPECT_FALSE(VerifyAuditProof(log_, 0, 0, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 0, 1, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 1, 0, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 2, 1, path, empty_hash, std::string()));
+}
+
+TEST_F(CTLogVerifierTest, VerifiesValidAuditProofs) {
+  std::vector<std::string> path;
+  // Known good paths.
+  // i = 0 is an invalid path.
+  for (int i = 1; i < 6; ++i) {
+    SCOPED_TRACE(i);
+    // Construct the path.
+    path.clear();
+    for (int j = 0; j < kSHA256Paths[i].path_length; ++j)
+      path.push_back(HexToBytes(kSHA256Paths[i].path[j]));
+    const TestVector& root_hash = kSHA256Roots[kSHA256Paths[i].snapshot - 1];
+    VerifierCheck(kSHA256Paths[i].leaf, kSHA256Paths[i].snapshot, path,
+                  HexToBytes(root_hash),
+                  HexToBytes(kSHA256LeafHashes[kSHA256Paths[i].leaf - 1]));
+  }
+}
+
+TEST_F(CTLogVerifierTest, VerifiesValidAuditProofsFromReferenceGenerator) {
+  std::vector<std::string> data;
+  for (size_t i = 0; i < 256; ++i)
+    data.emplace_back(1, i);
+
+  // More tests with reference path generator.
+  std::string root;
+  std::vector<std::string> path;
+  for (size_t tree_size = 1; tree_size <= data.size() / 2; ++tree_size) {
+    SCOPED_TRACE(tree_size);
+    // Repeat for each leaf in range.
+    for (size_t leaf = 1; leaf <= tree_size; ++leaf) {
+      SCOPED_TRACE(leaf);
+      path = ReferenceMerklePath(data.data(), tree_size, leaf);
+      root = ReferenceMerkleTreeHash(data.data(), tree_size);
+      VerifierCheck(leaf, tree_size, path, root,
+                    TreeHasher::HashLeaf(data[leaf - 1]));
+    }
+  }
+}
+
 }  // namespace
 
 }  // namespace net