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 ff911d6a14b729f9bd4f0a356fed465b9d86645b..d71ae2f1a2794f5f9ab0e342c90e5ff80f332d6e 100644
--- a/net/cert/ct_log_verifier_unittest.cc
+++ b/net/cert/ct_log_verifier_unittest.cc
@@ -8,12 +8,15 @@
 
 #include <memory>
 #include <string>
+#include <vector>
 
+#include "base/macros.h"

[Ryan Sleevi, 2016/07/26 19:33:44]

? for what?

[Rob Percival, 2016/07/28 05:18:47]

arraysize is used in this code. I added the #include when I momentarily chose to
use arraysize in some of the new code, but later removed it. I didn't remove the
#include though, because it should have been there in the first place. I can
leave it out if you'd prefer, given that it's unrelated to the change I'm
actually making (and invites questions like this one).

[Ryan Sleevi, 2016/07/28 14:54:49]

There's a threshold to use judgement, but whenever doing something surprising,
err on the side of documentation. Some reviewers (hi!) look through all the
changed code and try to see if every header addition is necessary - so when code
like this is added, it invites comments.

I'm fine leaving it in, now that it's explained *why* :)

 #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"
@@ -61,6 +64,18 @@ struct ProofTestVector {
 const TestVector kSHA256EmptyTreeHash = {
     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855", 32};
 
+// 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] = {
@@ -104,6 +119,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;

[Ryan Sleevi, 2016/07/26 19:33:44]

Why are these stored as int, and then force-coerced to uint64? (for line 199).
Why aren't they stored as uint64_t?

[Rob Percival, 2016/07/28 05:18:47]

The answer to most of your following comments is that I made the minimum number
of changes when porting from
https://github.com/google/certificate-transparency/blob/master/cpp/merkletree...,
and so almost everything is as it was there. I did leave an initial comment
pointing out one of the oddities that resulted from this (1-based leaf indices
in the tests) and the gains to be had from more heavily overhauling the test
code. However, I wanted to give Eran a chance to review it first, while it was
still easily comparable with the original test code.

+  int path_length;

[Ryan Sleevi, 2016/07/26 19:33:45]

path_length should be size_t

[Rob Percival, 2016/08/25 17:44:59]

Done.

+  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;
@@ -138,6 +196,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.

[Ryan Sleevi, 2016/07/26 19:33:45]

https://groups.google.com/a/chromium.org/d/msg/chromium-dev/NH-S6KCkr2M/yv0z3...

// The code uses a 0-based index, but the test vectors use a 1-based leaf index.

Both the above suggestion and the original comment leave a considerable point of
ambiguity - which code is "our code" / "the code" that uses the 0-based index?
Is it log->VerifyAuditProof? Is it this code? Is it some other function?

The comment could be improved here, but I'm not sure how because I'm not sure
what's being stated.

[Rob Percival, 2016/07/28 05:18:47]

I'll improve this, though I'd like to get rid of this leaf index base mismatch
entirely rather than merely document it.

+  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() {}
@@ -151,6 +222,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.

[Ryan Sleevi, 2016/07/26 19:33:44]

Every one of these checks should be separate tests that each cover the 'logical'
part of functionality - the original path, wrong leaf indices, wrong tree
heights, wrong roots, wrong paths, modified element, trailing garbage, leading
garbage, missing node.

That is, they should *not* be all one test.

[Rob Percival, 2016/07/28 05:18:47]

Again, inherited from the original tests. If I find the time, I'll backport any
improvements made here to the original tests as well. I should point out that
this is called from the VerifiesValidAuditProofsFromReferenceGenerator so, if I
both split this up and turn that into a value-parameterized test as requested,
we'll end up with 74304 test cases in place of that single test case (if my
calculations are correct). I expect that will increase the test duration
significantly, and I'm not sure whether that will adversely affect anything else
(e.g. as a result of much larger GTest result files). Can you see a way of
avoiding this, or do you think it'll not be a problem?

[Ryan Sleevi, 2016/07/28 16:40:47]

Well, whether or not we split it out to parameterized queries, it does mean
you're doing 74304 tests, right? Is that the right thing?

That it, as I understand it, you're saying for every leaf in the possible path,
you're verifying that it fails on the wrong tree height, wrong root, and wrong
path. That seems... overkill? Shouldn't it be sufficient simply to exercise that
all unique conditions in the code under test are covered, rather than all
possible permutations?

[Rob Percival, 2016/08/25 17:44:59]

That should be sufficient, but Eran is quite passionate about keeping these
exhaustive tests. These are also the same tests that are used in various other
codebases to test consistency and audit proof verification, so there's an
argument for keeping them consistent. I certainly see where you're coming from
though, and I doubt I'd have written the tests this way if I was starting from
scratch.

+  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,
@@ -439,6 +580,36 @@ std::string ReferenceMerkleTreeHash(std::string* inputs, uint64_t input_size) {
       ReferenceMerkleTreeHash(&inputs[split], input_size - split));
 }
 
+// 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 path;
+
+  const uint64_t split = CalculateNearestPowerOfTwo(input_size);
+
+  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
 // consistency proof between two snapshots of the tree designated
 // by |inputs|.
@@ -504,9 +675,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);
@@ -515,6 +688,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()));

[Ryan Sleevi, 2016/07/26 19:33:44]

All should be grouped into a new test; this seems entirely unrelated to 'empty
path' tests.

[Rob Percival, 2016/08/25 17:44:59]

Done. The cases with a leaf index of 0 were pointless, as they can't be mapped
to a 0-based leaf index by VerifyAuditProof and so get rejected immediately.
I've deleted those and the rest of the test cases appear to fit together under
the banner of "invalid leaf index", given that it's larger than the tree size in
all cases. I'm not entirely sure what these cases were really supposed to be
testing though.. which is an argument for deleting them entirely.

+
+  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