|
|
Created:
4 years, 5 months ago by Rob Percival Modified:
4 years, 1 month ago CC:
chromium-reviews, rsleevi+watch_chromium.org, certificate-transparency-chrome_googlegroups.com, cbentzel+watch_chromium.org, Eran Messeri Base URL:
https://chromium.googlesource.com/chromium/src.git@master Target Ref:
refs/pending/heads/master Project:
chromium Visibility:
Public. |
DescriptionAdds a VerifyAuditProof method to CTLogVerifier
This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly.
BUG=631087
Committed: https://crrev.com/89f010d82559c73e7d23cbf067137ceb1df698df
Cr-Commit-Position: refs/heads/master@{#430264}
Patch Set 1 #
Total comments: 1
Patch Set 2 : Rebase #
Total comments: 5
Patch Set 3 : Switch from flag to bool constant #
Total comments: 2
Patch Set 4 : Removes hash cache #
Total comments: 20
Patch Set 5 : Rebase #Patch Set 6 : Addresses some of Ryan Sleevi's comments #
Total comments: 16
Patch Set 7 : Rebase #Patch Set 8 : Addresses some minor comments #Patch Set 9 : More extensive refactoring #
Total comments: 4
Patch Set 10 : Update RFC6962-bis link #
Total comments: 15
Patch Set 11 : Addresses David's comments #
Total comments: 4
Patch Set 12 : Better documentation for MerkleAuditProof #Patch Set 13 : Rebase #
Messages
Total messages: 62 (36 generated)
Patchset #1 (id:1) has been deleted
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
robpercival@chromium.org changed reviewers: + eranm@chromium.org
PTAL https://codereview.chromium.org/2182533002/diff/20001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/20001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:213: // Test vectors use a 1-based leaf index, but our code uses a 0-based index. I can more heavily modify the tests (which were adapted from https://github.com/google/certificate-transparency/blob/master/cpp/merkletree...) so that they use 0-based leaf indexes, which would be less confusing for readers and probably eliminate a few fairly pointless test cases.
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
rsleevi@chromium.org changed reviewers: + rsleevi@chromium.org
Please don't combine the caching CL with this, or at least, it doesn't seem related to your description. Please significantly expand your CL description. Please significantly expand your code documentation. https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:36: const char* kNoHashCacheFlag = "no-hash-cache"; This is not a good design for unittests to have arbitrary flags like this. Note, unlike Google3, we strongly discourage flags from being spread out (that is, gflags-patterns are anti-patterns) https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:596: if (hash.empty()) { DESIGN: Do error handling first if (!hash.empty()) return hash; ... Although really, this should be coupled with the above, if it even remains, which would be if (is_cache_enabled) { ... if (iter != cache.end()) hash = iter->second; if (!hash.empty()) return hash } if (!input.size) { ... }
https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier.cc:261: uint64_t sn = proof.tree_size - 1; DESIGN: From this CL, it's unclear whether or not MerkleAuditProof is trusted or untrusted input. If it's untrusted input, then you run the risk of tree_size = 0, right? If so, what impact does this have. If you're guaranteed that tree_size > 0, where/how?
https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:36: const char* kNoHashCacheFlag = "no-hash-cache"; On 2016/07/25 19:41:41, Ryan Sleevi (extremely slow) wrote: > This is not a good design for unittests to have arbitrary flags like this. > > Note, unlike Google3, we strongly discourage flags from being spread out (that > is, gflags-patterns are anti-patterns) Ok, I'll drop the flag. It really only exists for the benefit of myself and reviewers to assess the cost of caching the hashes. Would you like a way of toggling the cache (e.g. just a bool declared here), or shall I remove the "feature toggle" entirely? https://codereview.chromium.org/2182533002/diff/40001/net/cert/ct_log_verifie... net/cert/ct_log_verifier_unittest.cc:596: if (hash.empty()) { On 2016/07/25 19:41:41, Ryan Sleevi (extremely slow) wrote: > DESIGN: Do error handling first > > if (!hash.empty()) > return hash; > > ... > > Although really, this should be coupled with the above, if it even remains, > which would be > > if (is_cache_enabled) { > ... > if (iter != cache.end()) > hash = iter->second; > if (!hash.empty()) > return hash > } > > if (!input.size) { > ... > } That isn't error handling - it's checking whether anything was retrieved from the cache. I've refactored it a bit to return early as suggested though.
overall looks good, I'll wait until https://codereview.chromium.org/2178153003/ is reviewed and submitted before thoroughly reviewing the test code. https://codereview.chromium.org/2182533002/diff/60001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/60001/net/cert/ct_log_verifie... net/cert/ct_log_verifier.cc:252: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-16#section-10.4.1. Nit: Please link to the latest draft, draft 17.
Patchset #4 (id:80001) has been deleted
Description was changed from ========== Adds a VerifyAuditProof method to CTLogVerifier BUG=631087 ========== to ========== Adds a VerifyAuditProof method to CTLogVerifier This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly. BUG=631087 ==========
https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:11: #include <vector> Unnecessary https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:13: #include "base/macros.h" ? for what? https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:127: int snapshot; Why are these stored as int, and then force-coerced to uint64? (for line 199). Why aren't they stored as uint64_t? https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:128: int path_length; path_length should be size_t https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:205: // Test vectors use a 1-based leaf index, but our code uses a 0-based index. 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. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:226: // no other combination of leaves, snapshots and proof nodes verifies. 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. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:701: VerifyAuditProof(log_, 2, 1, path, std::string(), std::string())); All should be grouped into a new test; this seems entirely unrelated to 'empty path' tests.
https://codereview.chromium.org/2182533002/diff/60001/net/cert/ct_log_verifie... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/60001/net/cert/ct_log_verifie... net/cert/ct_log_verifier.cc:252: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-16#section-10.4.1. On 2016/07/26 15:52:40, Eran Messeri wrote: > Nit: Please link to the latest draft, draft 17. Done. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:11: #include <vector> On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > Unnecessary Why? Vector is already used in this file, the #include was just missing. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:13: #include "base/macros.h" On 2016/07/26 19:33:44, Ryan Sleevi (extremely slow) wrote: > ? for what? 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). https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:127: int snapshot; On 2016/07/26 19:33:44, Ryan Sleevi (extremely slow) wrote: > Why are these stored as int, and then force-coerced to uint64? (for line 199). > Why aren't they stored as uint64_t? 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. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:205: // Test vectors use a 1-based leaf index, but our code uses a 0-based index. On 2016/07/26 19:33:45, Ryan Sleevi (slow) wrote: > 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. I'll improve this, though I'd like to get rid of this leaf index base mismatch entirely rather than merely document it. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:226: // no other combination of leaves, snapshots and proof nodes verifies. On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > 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. 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?
https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:11: #include <vector> On 2016/07/28 05:18:47, Rob Percival wrote: > On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > > Unnecessary > > Why? Vector is already used in this file, the #include was just missing. The use is from proof.nodes on line 188, which means it should be coming from line 20. For example, line 188 could have said "auto" and you still would have had the dependency on line 20. This is the sort of change that bears commenting, at least, when publishing for reviewers - when it's a cleanup unrelated at all to the substance of the CL, but you happened to notice on the CL. Otherwise, it becomes a test for reviewers, and that's not ideal. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:13: #include "base/macros.h" On 2016/07/28 05:18:47, Rob Percival wrote: > On 2016/07/26 19:33:44, Ryan Sleevi (extremely slow) wrote: > > ? for what? > > 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). 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* :)
https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:252: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-17#section-10.4.1. Omit the period at the end, it's getting interpreted as part of the URL :) https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:226: // no other combination of leaves, snapshots and proof nodes verifies. On 2016/07/28 05:18:47, Rob Percival wrote: > On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > > 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. > > 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? 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?
Is this ready for re-review?
https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:252: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-17#section-10.4.1. On 2016/07/28 16:40:46, Ryan Sleevi (slow) wrote: > Omit the period at the end, it's getting interpreted as part of the URL :) Done. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:128: int path_length; On 2016/07/26 19:33:45, Ryan Sleevi (slow) wrote: > path_length should be size_t Done. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:226: // no other combination of leaves, snapshots and proof nodes verifies. On 2016/07/28 16:40:47, Ryan Sleevi (slow) wrote: > On 2016/07/28 05:18:47, Rob Percival wrote: > > On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > > > 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. > > > > 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? > > 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? 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. https://codereview.chromium.org/2182533002/diff/100001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:701: VerifyAuditProof(log_, 2, 1, path, std::string(), std::string())); On 2016/07/26 19:33:44, Ryan Sleevi (slow) wrote: > All should be grouped into a new test; this seems entirely unrelated to 'empty > path' tests. 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.
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: Try jobs failed on following builders: android_compile_dbg on master.tryserver.chromium.android (JOB_FAILED, https://build.chromium.org/p/tryserver.chromium.android/builders/android_comp...)
Since performance came up in the other CL, should we be removing HexToBytes and switching to const char* entirely? I'm not sure the HexToBytes simplicity of hex strings is worth the performance overhead being incurred from all the string copies in these permutation tests. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:177: bool VerifyAuditProof(scoped_refptr<const CTLogVerifier> log, STYLE: https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md... bool VerifyAuditProof(const CTLogVerifier* log, https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:251: wrong_path.push_back(root); 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. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:503: public ::testing::WithParamInterface<size_t> {}; <size_t /* tree_size */> ? https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:564: // leaf with index |leaf| (1-based). The tree is designated by |inputs|. 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?) https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:565: std::vector<std::string> ReferenceMerklePath(std::string* inputs, DESIGN: Do you need to pass as std::string? Or would const char* suffice? (See previous comments about performance0 https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:567: uint64_t leaf) { STYLE: These should be size_t, not uint64_t - https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md... https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:587: } 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. https://codereview.chromium.org/2182533002/diff/140001/net/cert/merkle_audit_... File net/cert/merkle_audit_proof.h (right): https://codereview.chromium.org/2182533002/diff/140001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:27: MerkleAuditProof(); FUTURE CL: Should we still have this ctor? Would it make more sense to remove it, given that we want to ensure all parameters are sanely initialized?
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
PTAL. I've renamed some things, reworded some of the documentation and gotten rid of the 1-based leaf indices, amongst other small improvements. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:177: bool VerifyAuditProof(scoped_refptr<const CTLogVerifier> log, On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > STYLE: > https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md... > > bool VerifyAuditProof(const CTLogVerifier* log, Done. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:251: wrong_path.push_back(root); On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > 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. Done. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:503: public ::testing::WithParamInterface<size_t> {}; On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > <size_t /* tree_size */> ? Done. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:564: // leaf with index |leaf| (1-based). The tree is designated by |inputs|. On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > 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?) 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. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:565: std::vector<std::string> ReferenceMerklePath(std::string* inputs, On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > DESIGN: Do you need to pass as std::string? Or would const char* suffice? (See > previous comments about performance0 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. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:567: uint64_t leaf) { On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > STYLE: These should be size_t, not uint64_t - > https://chromium.googlesource.com/chromium/src/+/master/styleguide/c++/c++.md... Done. https://codereview.chromium.org/2182533002/diff/140001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:587: } On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > 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. Done. https://codereview.chromium.org/2182533002/diff/140001/net/cert/merkle_audit_... File net/cert/merkle_audit_proof.h (right): https://codereview.chromium.org/2182533002/diff/140001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:27: MerkleAuditProof(); On 2016/08/25 18:56:24, Ryan Sleevi (slow) wrote: > FUTURE CL: Should we still have this ctor? Would it make more sense to remove > it, given that we want to ensure all parameters are sanely initialized? LogDnsClient currently makes use of it, as it populates the proof incrementally. It wouldn't be unreasonable to use the other constructor for that case though, and just pass in zeros and an empty vector.
Patchset #9 (id:200001) has been deleted
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
robpercival@chromium.org changed reviewers: + davidben@chromium.org
Hi David, mind reviewing this? I'm drowning Ryan in reviews right now and Eran says you've reviewed CT verification code in the past. Thanks!
drive-by review, overall looks good. https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:253: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-17#section-10.4.1 nit: Update the link to point to the latest draft. https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:279: } else { // Otherwise: nit: The comment here does not add much.
Patchset #10 (id:240001) has been deleted
https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:253: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-17#section-10.4.1 On 2016/10/05 13:17:54, Eran Messeri wrote: > nit: Update the link to point to the latest draft. Done. https://codereview.chromium.org/2182533002/diff/220001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:279: } else { // Otherwise: On 2016/10/05 13:17:54, Eran Messeri wrote: > nit: The comment here does not add much. All of these comments are taken from the RFC. I think it's worth keeping them all just so it's blatantly obvious how the pseudo-code maps to this implementation.
Seems I'm not much more timely than Ryan is. :-( Sorry about that! This looks good. Just one comment here that I think the algorithm is missing a check. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:253: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-19#section-10.4.1 Nit: Kind of similar to VerifyConsistencyProof, I might add a second paragraph here like: // // It maintains a hash |r|, initialized to |leaf_hash|, and hashes nodes from |proof| into it. The proof is then valid if |r| is |root_hash|, proving that |root_hash| includes |leaf_hash|. The gist here is that, if you're trying to just confirm this function will never erroneously say YES, you don't care about the exact mess around |fn| and |sn|, which is a bit harder to verify. You only care that |r| starts at |leaf_hash|, gets junk hashed into it, and ends at |root_hash|. (Erroneously saying YES is a security bug, erroneously saying NO is merely an availability bug.) https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:267: for (const std::string& p : proof.nodes) { Shouldn't this check if sn == 0 here? That means you have more proof nodes than you're supposed to have. It's similar to how the other algorithm was missing checks. Specifically, I believe if you have a valid proof for leaf_index = 7, tree_size = 8, it will also work for leaf_index = 3, tree_size = 4; leaf_index = 1, tree_size = 2; and leaf_index = 0, tree_size = 1. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:287: } [Convinced myself this algorithm is correct, the note above aside.[ https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:164: // Constructs a consistency/audit proof from a test vector. This confused me at first. Perhaps add "This is templated so T may be ConsistencyProofTestVector or AuditProofTestVector." https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:244: << "proof passed verification with wrong root hash"; If you add leaf / 2 and tree_size / 2, I think that'll catch the missing check. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:322: << "proof passed verification with old tree size ^ 2"; This lost a number of comments from the old VerifyConsistencyCheck method. Was this intentional? https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:473: // tree_sizes that are always consistent, because they are either Nit: tree_sizes => Tree sizes? https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:694: ::testing::Range(size_t(0), arraysize(kAuditProofs))); Nit: Should this be before the rfc6962 stuff?
No worries, thanks for looking it over. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier.cc (right): https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:253: // https://tools.ietf.org/html/draft-ietf-trans-rfc6962-bis-19#section-10.4.1 On 2016/10/18 22:18:57, davidben wrote: > Nit: Kind of similar to VerifyConsistencyProof, I might add a second paragraph > here like: > > // > // It maintains a hash |r|, initialized to |leaf_hash|, and hashes nodes from > |proof| into it. The proof is then valid if |r| is |root_hash|, proving that > |root_hash| includes |leaf_hash|. > > The gist here is that, if you're trying to just confirm this function will never > erroneously say YES, you don't care about the exact mess around |fn| and |sn|, > which is a bit harder to verify. You only care that |r| starts at |leaf_hash|, > gets junk hashed into it, and ends at |root_hash|. (Erroneously saying YES is a > security bug, erroneously saying NO is merely an availability bug.) Done. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier.cc:267: for (const std::string& p : proof.nodes) { On 2016/10/18 22:18:57, davidben wrote: > Shouldn't this check if sn == 0 here? That means you have more proof nodes than > you're supposed to have. It's similar to how the other algorithm was missing > checks. > > Specifically, I believe if you have a valid proof for leaf_index = 7, tree_size > = 8, it will also work for leaf_index = 3, tree_size = 4; leaf_index = 1, > tree_size = 2; and leaf_index = 0, tree_size = 1. Done. Also reported this as a bug in RFC6962-bis (https://trac.tools.ietf.org/wg/trans/trac/ticket/159). https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... File net/cert/ct_log_verifier_unittest.cc (right): https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:164: // Constructs a consistency/audit proof from a test vector. On 2016/10/18 22:18:57, davidben wrote: > This confused me at first. Perhaps add "This is templated so T may be > ConsistencyProofTestVector or AuditProofTestVector." Done. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:244: << "proof passed verification with wrong root hash"; On 2016/10/18 22:18:57, davidben wrote: > If you add leaf / 2 and tree_size / 2, I think that'll catch the missing check. Done. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:322: << "proof passed verification with old tree size ^ 2"; On 2016/10/18 22:18:57, davidben wrote: > This lost a number of comments from the old VerifyConsistencyCheck method. Was > this intentional? Yes, I think I captured all of the substance of the removed comments in the new failure messages, which have the advantage of making it clearer which case failed. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:473: // tree_sizes that are always consistent, because they are either On 2016/10/18 22:18:57, davidben wrote: > Nit: tree_sizes => Tree sizes? Done. https://codereview.chromium.org/2182533002/diff/260001/net/cert/ct_log_verifi... net/cert/ct_log_verifier_unittest.cc:694: ::testing::Range(size_t(0), arraysize(kAuditProofs))); On 2016/10/18 22:18:57, davidben wrote: > Nit: Should this be before the rfc6962 stuff? Done.
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
lgtm
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
lgtm % two minor comments. https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... File net/cert/merkle_audit_proof.h (right): https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:36: // Number of leaves in the log's tree. nit: Be more explicit and relate that to the proof, so it's clear the size here must match the size of the tree specified when the proof nodes were fetched. https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:37: uint64_t tree_size = 0; Nit: Make tree_size const.
https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... File net/cert/merkle_audit_proof.h (right): https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:36: // Number of leaves in the log's tree. On 2016/10/23 16:18:06, Eran Messeri wrote: > nit: Be more explicit and relate that to the proof, so it's clear the size here > must match the size of the tree specified when the proof nodes were fetched. Done. https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... net/cert/merkle_audit_proof.h:37: uint64_t tree_size = 0; On 2016/10/23 16:18:06, Eran Messeri wrote: > Nit: Make tree_size const. Why?
The CQ bit was checked by robpercival@chromium.org to run a CQ dry run
Dry run: CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
The CQ bit was unchecked by commit-bot@chromium.org
Dry run: This issue passed the CQ dry run.
On 2016/11/07 09:39:49, Rob Percival wrote: > https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... > File net/cert/merkle_audit_proof.h (right): > > https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... > net/cert/merkle_audit_proof.h:36: // Number of leaves in the log's tree. > On 2016/10/23 16:18:06, Eran Messeri wrote: > > nit: Be more explicit and relate that to the proof, so it's clear the size > here > > must match the size of the tree specified when the proof nodes were fetched. > > Done. > > https://codereview.chromium.org/2182533002/diff/280001/net/cert/merkle_audit_... > net/cert/merkle_audit_proof.h:37: uint64_t tree_size = 0; > On 2016/10/23 16:18:06, Eran Messeri wrote: > > Nit: Make tree_size const. > > Why? Eran has requested that this be committed now so that he can use it immediately. Since it's been 2 months since Ryan's last comments, I'm going to go ahead and commit it with 2 out of 3 LGTMs. Ryan, if you have any further comments, feel free to make them here and I'll address them in a follow-up CL.
The CQ bit was checked by robpercival@chromium.org
The patchset sent to the CQ was uploaded after l-g-t-m from eranm@chromium.org, davidben@chromium.org Link to the patchset: https://codereview.chromium.org/2182533002/#ps320001 (title: "Rebase")
CQ is trying da patch. Follow status at https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...
Message was sent while issue was closed.
Description was changed from ========== Adds a VerifyAuditProof method to CTLogVerifier This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly. BUG=631087 ========== to ========== Adds a VerifyAuditProof method to CTLogVerifier This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly. BUG=631087 ==========
Message was sent while issue was closed.
Committed patchset #13 (id:320001)
Message was sent while issue was closed.
Description was changed from ========== Adds a VerifyAuditProof method to CTLogVerifier This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly. BUG=631087 ========== to ========== Adds a VerifyAuditProof method to CTLogVerifier This allows audit (aka. inclusion) proofs to be verified, which helps check that CT logs are behaving correctly. BUG=631087 Committed: https://crrev.com/89f010d82559c73e7d23cbf067137ceb1df698df Cr-Commit-Position: refs/heads/master@{#430264} ==========
Message was sent while issue was closed.
Patchset 13 (id:??) landed as https://crrev.com/89f010d82559c73e7d23cbf067137ceb1df698df Cr-Commit-Position: refs/heads/master@{#430264}
Message was sent while issue was closed.
> Eran has requested that this be committed now so that he can use it immediately. > Since it's been 2 months since Ryan's last comments, I'm going to go ahead and > commit it with 2 out of 3 LGTMs. Ryan, if you have any further comments, feel > free to make them here and I'll address them in a follow-up CL. I think Ryan probably meant for me to review in his stead anyway. :-P |