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 fb342f4b1116d50ac03676e160101249f0b78cf1..5be67a237ed7823256335ebb7fbb269a878bf6eb 100644
--- a/net/cert/ct_log_verifier_unittest.cc
+++ b/net/cert/ct_log_verifier_unittest.cc
@@ -10,11 +10,13 @@
 #include <string>
 #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"
@@ -53,6 +55,17 @@ struct ProofTestVector {
 const char* const kSHA256EmptyTreeHash =
     "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855";
 
+// Hashes of the leaf data for the sample tree (8 leaves).
+const char* const kSHA256LeafHashes[8] = {
+    "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
+    "96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
+    "0298d122906dcfc10892cb53a73992fc5b9f493ea4c9badb27b791b4127a7fe7",
+    "07506a85fd9dd2f120eb694f86011e5bb4662e5c415a62917033d4a9624487e7",
+    "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
+    "4271a26be0d8a84f0bd54c8c302e7cb3a3b5d1fa6780a40bcce2873477dab658",
+    "b08693ec2e721597130641e8211e7eedccb4c26413963eee6c1e2ed16ffb1a5f",
+    "46f6ffadd3d06a09ff3c5860d2755c8b9819db7df44251788c7d8e3180de8eb1"};
+
 // Root hashes 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 char* const kSHA256Roots[8] = {
@@ -94,6 +107,45 @@ const ProofTestVector kSHA256Proofs[4] = {
      {"5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
       "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b", ""}}};
 
+// 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 {
+  uint64_t leaf;
+  uint64_t snapshot;
+  size_t path_length;
+  const char* const 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, {"", "", ""}},
+    {1, 1, 0, {"", "", ""}},
+    {1,
+     8,
+     3,
+     {"96a296d224f285c67bee93c30f8a309157f0daa35dc5b87e410b78630a09cfc7",
+      "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
+      "6b47aaf29ee3c2af9af889bc1fb9254dabd31177f16232dd6aab035ca39bf6e4"}},
+    {6,
+     8,
+     3,
+     {"bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b",
+      "ca854ea128ed050b41b35ffc1b87b8eb2bde461e9e3b5596ece6b9d5975a0ae0",
+      "d37ee418976dd95753c1c73862b9398fa2a2cf9b4ff0fdfe8b30cd95209614b7"}},
+    {3,
+     3,
+     1,
+     {"fac54203e7cc696cf0dfcb42c92a1d9dbaf70ad9e621f4bd8d98662f00e3c125", "",
+      ""}},
+    {2,
+     5,
+     3,
+     {"6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d",
+      "5f083f0a1a33ca076a95279832580db3e0ef4584bdff1f54c8a360f50de3031e",
+      "bc1a0643b12e4d2d7c77918f44e0f4f79a838b6cf9ec5b5c283e1f4d88599e6b"}}};
+
 // Decodes a hexadecimal string into the binary data it represents.
 std::string HexToBytes(const std::string& hex_data) {
   std::vector<uint8_t> output;
@@ -122,6 +174,21 @@ bool VerifyConsistencyProof(scoped_refptr<const CTLogVerifier> log,
       old_tree_root, new_tree_root);
 }
 
+bool VerifyAuditProof(scoped_refptr<const CTLogVerifier> log,

[Ryan Sleevi, 2016/08/25 18:56:24]

STYLE:
https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md...

bool VerifyAuditProof(const CTLogVerifier* log, 

[Rob Percival, 2016/10/03 17:39:26]

Done.

+                      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 CTLogVerifier uses a 0-based
+  // index. We need to map |leaf| to a 0-based index but there is no mapping for
+  // 0, so reject it. Subtract 1 from any other value.
+  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() {}
@@ -135,6 +202,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,
+                                  GetEmptyTreeHash(), 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);

[Ryan Sleevi, 2016/08/25 18:56:24]

PERFORMANCE: Since you were concerned about perf in other CLs, why not just
wrong_path.back() = root;

That at least avoids the potential of the resize.

[Rob Percival, 2016/10/03 17:39:25]

Done.

+    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,
@@ -361,27 +498,28 @@ TEST_F(CTLogVerifierTest,
                                       empty_tree_hash, proof));
 }
 
-TEST_F(CTLogVerifierTest, VerifiesValidConsistencyProofs) {
+class CTLogVerifierConsistencyProofTest
+    : public CTLogVerifierTest,
+      public ::testing::WithParamInterface<size_t> {};

[Ryan Sleevi, 2016/08/25 18:56:24]

<size_t /* tree_size */> ?

[Rob Percival, 2016/10/03 17:39:25]

Done.

+
+TEST_P(CTLogVerifierConsistencyProofTest, VerifiesValidConsistencyProof) {
+  const size_t i = GetParam();
   std::vector<std::string> proof;
-  std::string root1, root2;
-
-  // 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 char* const v = kSHA256Proofs[i].proof[j];
-      proof.push_back(HexToBytes(v));
-    }
-    const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
-    const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
-    const char* const old_root = kSHA256Roots[snapshot1 - 1];
-    const char* const new_root = kSHA256Roots[snapshot2 - 1];
-    VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root),
-                             HexToBytes(new_root), proof);
+  for (size_t j = 0; j < kSHA256Proofs[i].proof_length; ++j) {
+    proof.push_back(HexToBytes(kSHA256Proofs[i].proof[j]));
   }
+  const uint64_t snapshot1 = kSHA256Proofs[i].snapshot1;
+  const uint64_t snapshot2 = kSHA256Proofs[i].snapshot2;
+  const char* const old_root = kSHA256Roots[snapshot1 - 1];
+  const char* const new_root = kSHA256Roots[snapshot2 - 1];
+  VerifierConsistencyCheck(snapshot1, snapshot2, HexToBytes(old_root),
+                           HexToBytes(new_root), proof);
 }
 
+INSTANTIATE_TEST_CASE_P(KnownGoodProofs,
+                        CTLogVerifierConsistencyProofTest,
+                        ::testing::Range(0ul, arraysize(kSHA256Proofs)));
+
 const char kLeafPrefix[] = {'\x00'};
 
 // Reference implementation of RFC6962.
@@ -421,6 +559,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|.

[Ryan Sleevi, 2016/08/25 18:56:24]

I'm completely struggling to understand what this code does, and while I suspect
with a lot of time to dig in, it could be understood, it's a bad sign when the
code isn't clear itself.

Concrete issues with the comment (not trying to pile on, just trying to explain
my confusion)
1) "Reference implementation of Merkle paths" is ambiguous. Is it trying to stay
this function is a reference implementation? I'm further confused because the
third sentence says "Returns an audit proof" - which suggests that should be the
thing most important here.
2) "Path from leaf to root, excluding the leaf and root themselves" - leaf and
root aren't mentioned in the parameters here, and so there's no context to
understand what they are. It also doesn't feel like a complete sentence - is
this describing what's being returned? If so, isn't this something that modifies
the third sentence, and should come after it, rather than before?
3) "The tree is designated by inputs" - this doesn't really help understand how
the inputs should be structured.

Putting this back together leads me to something like this, which I would not
suggest copying verbatim simply because it's me trying to make sure I understand
first.

// Returns an audit proof for the Merkle tree designated by |inputs|, which is
[somehow structured], for the node
// at index |leaf| (which is probably the wrong name) in the tree. The audit
proof is computed using the
// reference implementation (as opposed to what? What does "Reference
implementation" mean here as related to... what?)

[Rob Percival, 2016/10/03 17:39:26]

Don't worry about "piling on", I didn't even write most of this (see
https://github.com/google/certificate-transparency/blob/master/cpp/merkletree...,
the origin of most of this code) and agree that it's pretty impenetrable. I'll
take a shot at rewriting and documenting it as necessary to make it clearer.

+std::vector<std::string> ReferenceMerklePath(std::string* inputs,

[Ryan Sleevi, 2016/08/25 18:56:24]

DESIGN: Do you need to pass as std::string? Or would const char* suffice? (See
previous comments about performance0

[Rob Percival, 2016/10/03 17:39:26]

Each element of |inputs| can be an arbitrary string, so we'd also need the
length of each element (i.e. a StringPiece at least). Using StringPiece would
make some of the tests (those that generate |inputs|) more complicated, and
they'd end up being converted to std::strings anyway as that's what the
CTLogVerifier methods take.

+                                             uint64_t input_size,
+                                             uint64_t leaf) {

[Ryan Sleevi, 2016/08/25 18:56:24]

STYLE: These should be size_t, not uint64_t -
https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md...

[Rob Percival, 2016/10/03 17:39:25]

Done.

+  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));
+  }

[Ryan Sleevi, 2016/08/25 18:56:24]

You should add more documentation here as to explain why this split and such
exists. It's unclear what this algorithm is doing without significantly diving
into it.

[Rob Percival, 2016/10/03 17:39:25]

Done.

+
+  return path;
+}
+
 // Reference implementation of snapshot consistency. Returns a
 // consistency proof between two snapshots of the tree designated
 // by |inputs|.
@@ -468,20 +636,50 @@ std::vector<std::string> ReferenceSnapshotConsistency(std::string* inputs,
   return proof;
 }
 
+TEST_F(CTLogVerifierTest, VerifiesAuditProofEdgeCases_InvalidLeafIndex) {
+  std::vector<std::string> path;
+  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_, 1, 0, path, empty_hash, std::string()));
+  EXPECT_FALSE(VerifyAuditProof(log_, 2, 1, path, empty_hash, std::string()));
+}
+
+class CTLogVerifierAuditProofTest
+    : public CTLogVerifierTest,
+      public ::testing::WithParamInterface<size_t> {};
+
+TEST_P(CTLogVerifierAuditProofTest, VerifiesValidAuditProofs) {
+  size_t i = GetParam();
+  // Construct the path.
+  std::vector<std::string> path;
+  for (size_t j = 0; j < kSHA256Paths[i].path_length; ++j)
+    path.push_back(HexToBytes(kSHA256Paths[i].path[j]));
+  const char* const root_hash = kSHA256Roots[kSHA256Paths[i].snapshot - 1];
+  VerifierCheck(kSHA256Paths[i].leaf, kSHA256Paths[i].snapshot, path,
+                HexToBytes(root_hash),
+                HexToBytes(kSHA256LeafHashes[kSHA256Paths[i].leaf - 1]));
+}
+
+// kSHA256Paths[0] is an invalid path, so only use elements 1-5.
+INSTANTIATE_TEST_CASE_P(KnownGoodPaths,
+                        CTLogVerifierAuditProofTest,
+                        ::testing::Range(1ul, arraysize(kSHA256Paths)));
+
 class CTLogVerifierTestUsingReferenceGenerator
     : public CTLogVerifierTest,
       public ::testing::WithParamInterface<uint64_t> {};
 
 const uint64_t kReferenceTreeSize = 256;
 
-// Tests that every possible valid consistency proof for a tree of a given size
-// verifies correctly. Also checks that invalid variations of each proof fail to
-// verify (see VerifierConsistencyCheck).
 TEST_P(CTLogVerifierTestUsingReferenceGenerator,
        VerifiesValidConsistencyProof) {
   std::vector<std::string> data;
   for (uint64_t i = 0; i < kReferenceTreeSize; ++i)
-    data.push_back(std::string(1, static_cast<char>(i)));
+    data.emplace_back(1, static_cast<char>(i));
 
   const uint64_t tree_size = GetParam();
   const std::string tree_root = ReferenceMerkleTreeHash(data.data(), tree_size);
@@ -497,8 +695,27 @@ TEST_P(CTLogVerifierTestUsingReferenceGenerator,
   }
 }
 
-// Test verification of consistency proofs between all tree sizes from 1 to 128.
-INSTANTIATE_TEST_CASE_P(RangeOfTreeSizesAndSnapshots,
+TEST_P(CTLogVerifierTestUsingReferenceGenerator, VerifiesValidAuditProofs) {
+  std::vector<std::string> data;
+  for (uint64_t i = 0; i < kReferenceTreeSize; ++i)
+    data.emplace_back(1, static_cast<char>(i));
+
+  // More tests with reference path generator.
+  const uint64_t tree_size = GetParam();
+  const std::string root = ReferenceMerkleTreeHash(data.data(), tree_size);
+  // Repeat for each leaf in range.
+  for (uint64_t leaf = 1; leaf <= tree_size; ++leaf) {
+    SCOPED_TRACE(leaf);
+    std::vector<std::string> path =
+        ReferenceMerklePath(data.data(), tree_size, leaf);
+    VerifierCheck(leaf, tree_size, path, root,
+                  TreeHasher::HashLeaf(data[leaf - 1]));
+  }
+}
+
+// Test verification of consistency proofs and audit proofs for all tree sizes
+// from 1 to |kReferenceTreeSize / 2|.
+INSTANTIATE_TEST_CASE_P(RangeOfTreeSizes,
                         CTLogVerifierTestUsingReferenceGenerator,
                         testing::Range(UINT64_C(1),
                                        (kReferenceTreeSize / 2) + 1));