Add function to evaluate MT inclusion proof
Change-Id: I26d1b532c52b33165a6ebf64a49c9bfd2119d7fd
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/83647
Reviewed-by: David Benjamin <davidben@google.com>
Commit-Queue: Nick Harper <nharper@chromium.org>
diff --git a/pki/merkle_tree.cc b/pki/merkle_tree.cc
index 8247ce3..08ba35a 100644
--- a/pki/merkle_tree.cc
+++ b/pki/merkle_tree.cc
@@ -203,4 +203,16 @@
return computed_root_hash;
}
+std::optional<TreeHash> EvaluateMerkleSubtreeInclusionProof(
+ Span<const uint8_t> inclusion_proof, uint64_t index,
+ TreeHashConstSpan entry_hash, const Subtree &subtree) {
+ if (!subtree.IsValid() || !subtree.Contains(index)) {
+ return std::nullopt;
+ }
+ // Re-root |index| inside of |subtree|.
+ index -= subtree.start;
+ return EvaluateMerkleSubtreeConsistencyProof(
+ subtree.Size(), {index, index + 1}, inclusion_proof, entry_hash);
+}
+
BSSL_NAMESPACE_END
diff --git a/pki/merkle_tree.h b/pki/merkle_tree.h
index 4523579..f61f092 100644
--- a/pki/merkle_tree.h
+++ b/pki/merkle_tree.h
@@ -144,6 +144,17 @@
uint64_t n, const Subtree &subtree, Span<const uint8_t> proof,
TreeHashConstSpan node_hash);
+// Performs the procedure defined in section 4.3.2 of
+// draft-davidben-tls-merkle-tree-certs-08, Evaluating a Subtree Inclusion
+// Proof:
+//
+// Given a subtree inclusion proof, inclusion_proof, for entry index, with
+// hash entry_hash, of a subtree [start, end), the subtree inclusion proof can
+// be evaluated to compute the expected subtree hash
+OPENSSL_EXPORT std::optional<TreeHash> EvaluateMerkleSubtreeInclusionProof(
+ Span<const uint8_t> inclusion_proof, uint64_t index,
+ TreeHashConstSpan entry_hash, const Subtree &subtree);
+
// Helper function to compute the hash value of an interior node in a Merkle
// tree, i.e. HASH(0x01 || left || right). 32 bytes of output are written to
// |out|. This function is intended for internal use only and only exists here
diff --git a/pki/merkle_tree_unittest.cc b/pki/merkle_tree_unittest.cc
index 2447598..8d4a562 100644
--- a/pki/merkle_tree_unittest.cc
+++ b/pki/merkle_tree_unittest.cc
@@ -264,7 +264,7 @@
return out;
}
-TEST(MerkleTreeTest, VerifySubtreeConsistencyProof) {
+TEST(MerkleTreeTest, VerifySubtreeInclusionProof) {
ConcatData tree_data(StringAsBytes("label"));
MerkleTree tree(&tree_data);
@@ -272,11 +272,63 @@
auto node_hash = tree.MTH({index, index + 1});
Subtree subtree{0, 16};
auto proof = tree.InclusionProof(index, subtree);
+ auto concat_proof = ConcatProof(*proof);
ASSERT_TRUE(proof.has_value());
auto root_hash = EvaluateMerkleSubtreeConsistencyProof(
- subtree.end, {index, index + 1}, ConcatProof(*proof), *node_hash);
+ subtree.end, {index, index + 1}, concat_proof, *node_hash);
ASSERT_TRUE(root_hash.has_value());
EXPECT_EQ(root_hash, tree.MTH(subtree));
+ // Check again with EvaluateMerkleSubtreeInclusionProof
+ root_hash = EvaluateMerkleSubtreeInclusionProof(concat_proof, index,
+ *node_hash, subtree);
+ ASSERT_TRUE(root_hash.has_value());
+ EXPECT_EQ(root_hash, tree.MTH(subtree));
+
+ // Build and verify a proof from a subtree with start != 0
+ index = 845;
+ node_hash = tree.MTH({index, index + 1});
+ subtree = {840, 847};
+ proof = tree.InclusionProof(index, subtree);
+ concat_proof = ConcatProof(*proof);
+ ASSERT_TRUE(proof.has_value());
+ root_hash = EvaluateMerkleSubtreeConsistencyProof(
+ subtree.Size(), {index - subtree.start, index - subtree.start + 1},
+ concat_proof, *node_hash);
+ ASSERT_TRUE(root_hash.has_value());
+ EXPECT_EQ(root_hash, tree.MTH(subtree));
+ // Check again with EvaluateMerkleSubtreeInclusionProof
+ root_hash = EvaluateMerkleSubtreeInclusionProof(concat_proof, index,
+ *node_hash, subtree);
+ ASSERT_TRUE(root_hash.has_value());
+ EXPECT_EQ(root_hash, tree.MTH(subtree));
+}
+
+TEST(MerkleTreeTest, SubtreeInclusionProofInvalidArgs) {
+ ConcatData tree_data(StringAsBytes("label"));
+ MerkleTree tree(&tree_data);
+
+ uint64_t index = 845;
+ auto node_hash = tree.MTH({index, index + 1});
+ Subtree subtree = {840, 847};
+ auto proof = tree.InclusionProof(index, subtree);
+ auto concat_proof = ConcatProof(*proof);
+ ASSERT_TRUE(proof.has_value());
+
+ // 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.MTH({index + 1, index + 2});
+ auto root_hash = EvaluateMerkleSubtreeInclusionProof(
+ concat_proof, index, *wrong_node_hash, subtree);
+ ASSERT_TRUE(root_hash.has_value());
+ EXPECT_NE(root_hash, tree.MTH(subtree));
+
+ // If the subtree isn't valid, the function will fail.
+ ASSERT_FALSE(EvaluateMerkleSubtreeInclusionProof(concat_proof, index,
+ *node_hash, {840, 849}));
+
+ // If the index isn't contained within the subtree, the function will fail.
+ ASSERT_FALSE(EvaluateMerkleSubtreeInclusionProof(concat_proof, 848,
+ *node_hash, {840, 847}));
}
// Test that the computed consistency proofs match the examples given in RFC
