Background for https://codereview.chromium.org/2269383003 :

I'm in the process of implementing auditing of CT logs by checking inclusion of log entries for which SCTs were issued.
This is done by requesting inclusion proofs from a Google-operated mirrors of the logs, over a DNS-based protocol.
DNS front-ends are required for all logs that are added to the list of logs
(net/cert/ct_known_logs_static-inc.h) - all logs must be auditable, as there
is no good criteria to differentiate between logs.
Even logs which have been shut down should still be audited to ensure
they are not backdating Signed Certificate Timestamps (SCTs).

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/efc343f3e590013c880525c0d934f1322dc5438d

commit efc343f3e590013c880525c0d934f1322dc5438d
Author: eranm <eranm@chromium.org>
Date: Thu Aug 25 11:04:34 2016

Certificate Transparency: Make DNS front-end required.

From an out-of-band discussion with rsleevi came the conclusion that
all CT logs, including ones that ceased operation, must be auditable
(since some of their SCTs are accepted).

This change ensures that if logs are added to the known logs list
without a DNS front-end address, it will be detected on start-up.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2269383003
Cr-Commit-Position: refs/heads/master@{#414389}

[modify] https://crrev.com/efc343f3e590013c880525c0d934f1322dc5438d/components/certificate_transparency/single_tree_tracker_unittest.cc
[modify] https://crrev.com/efc343f3e590013c880525c0d934f1322dc5438d/net/cert/ct_log_verifier.cc
[modify] https://crrev.com/efc343f3e590013c880525c0d934f1322dc5438d/net/cert/ct_objects_extractor_unittest.cc
[modify] https://crrev.com/efc343f3e590013c880525c0d934f1322dc5438d/net/cert/multi_log_ct_verifier_unittest.cc
[modify] https://crrev.com/efc343f3e590013c880525c0d934f1322dc5438d/net/quic/chromium/crypto/proof_verifier_chromium_test.cc

Write-up of the need to support throttling in the LogDnsClient:
* We'd like to limit the rate of DNS queries performed by the client to minimize the impact CT log auditing has on clients (and in particular to prevent starvation of other DNS requests).
* An efficient way to do this, given the current design of TreeStateTracker / SingleTreeTracker, is to have SingleTreeTracker instances all share the same LogDnsClient.
* Then, a "global" (per TreeStateTracker) limit on the rate of DNS queries can be set in the LogDnsClient. The LogDnsClient will notify the caller that a request is being throttled, synchronously or asynchronously.
* With the current design, each SingleTreeTracker has its own queue of pending requests (this ensures, among other things, consistent auditing of all logs). Throttled requests to the LogDnsClient will simply remain in the queue (if it's full, new requests will be dropped).

The two open issues:
* Asynchronous vs synchronous throttling: With asynchronous throttling, the LogDnsClient client does not know when to stop sending requests to the LogDnsClient, since it will find out that the requests are throttled after the fact. The naive client behaviour in this case is to submit *all* queued requests and keep the ones that get throttled in the queue. This could mean a lot of churn if, for example, the client has a queue of 100 entries but the LogDnsClient only handles one at a time.

* Un-throttling / finding out the LogDnsClient is idle: The LogDnsClient has no way of notifying clients that it is free to take on more requests. Naively, a client would submit queued requests to the LogDnsClient the LogDnsClient invokes the callback informing of completion of a previous request.
The problem with this approach is that, since several SingleTreeTrackers share the same LogDnsClient, it could conceivably happen that *all* requests from a particular SingleTreeTracker got throttled, so that SingleTreeTracker will never have a completion callback invoked - so it will never learn that the LogDnsClient is idle.
The work-around I have for this is attempting to submit pending requests whenever the SingleTreeTracker observes a new SCT/STH. Given SCTs are observed often enough, that is a poor-man's periodic re-try mechanism.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9

commit 9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9
Author: robpercival <robpercival@chromium.org>
Date: Wed Oct 05 13:29:44 2016

LogDnsClient now rejects responses unless they contain exactly one TXT RDATA string

Previously, multiple TXT RDATA strings would be concatenated if present,
allowing a larger number of audit proof nodes to be delivered. However,
the CT-over-DNS draft RFC
(https://github.com/google/certificate-transparency-rfcs/blob/master/dns/draft-ct-over-dns.md)
explicitly states that the response should contain only one string, and trying
to handle other cases only causes confusion.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2375693002
Cr-Commit-Position: refs/heads/master@{#423140}

[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/mock_log_dns_traffic.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/2a9f5c09189a26b2f6140c02946bbd44ca9876f7

commit 2a9f5c09189a26b2f6140c02946bbd44ca9876f7
Author: robpercival <robpercival@chromium.org>
Date: Tue Oct 11 20:56:40 2016

Allow LogDnsClient queries to be rate-limited

A maximum number of concurrent queries can be specified. By default,
there is no limit.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2331923003
Cr-Commit-Position: refs/heads/master@{#424541}

[modify] https://crrev.com/2a9f5c09189a26b2f6140c02946bbd44ca9876f7/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/2a9f5c09189a26b2f6140c02946bbd44ca9876f7/components/certificate_transparency/log_dns_client.h
[modify] https://crrev.com/2a9f5c09189a26b2f6140c02946bbd44ca9876f7/components/certificate_transparency/log_dns_client_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/8da709c5cf63b5535f8c30ae6cc9e786bc8eaae8

commit 8da709c5cf63b5535f8c30ae6cc9e786bc8eaae8
Author: robpercival <robpercival@chromium.org>
Date: Wed Oct 12 16:23:48 2016

Merge LogDnsClient's QueryLeafIndex and QueryAuditProof methods

QueryAuditProof now takes a leaf hash, rather than a leaf index.
It will look up the leaf index, then the audit proof.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2367523002
Cr-Commit-Position: refs/heads/master@{#424758}

[modify] https://crrev.com/8da709c5cf63b5535f8c30ae6cc9e786bc8eaae8/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/8da709c5cf63b5535f8c30ae6cc9e786bc8eaae8/components/certificate_transparency/log_dns_client.h
[modify] https://crrev.com/8da709c5cf63b5535f8c30ae6cc9e786bc8eaae8/components/certificate_transparency/log_dns_client_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/f02172072e3fd83e2296e984f1e5bd86ba40093c

commit f02172072e3fd83e2296e984f1e5bd86ba40093c
Author: robpercival <robpercival@chromium.org>
Date: Thu Oct 13 08:34:03 2016

Improves documentation and formatting.

Replaces some test ASSERT/EXPECT calls with DCHECK, as they would only be the result of incorrect test setup.

Small refactorings to improve encapsulation.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2348393002
Cr-Commit-Position: refs/heads/master@{#424984}

[modify] https://crrev.com/f02172072e3fd83e2296e984f1e5bd86ba40093c/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/f02172072e3fd83e2296e984f1e5bd86ba40093c/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/f02172072e3fd83e2296e984f1e5bd86ba40093c/components/certificate_transparency/mock_log_dns_traffic.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/edce9665b9672f51ac2709224798354c434c88e7

commit edce9665b9672f51ac2709224798354c434c88e7
Author: msramek <msramek@chromium.org>
Date: Thu Oct 13 09:42:23 2016

Revert of Minor improvements to MockLogDnsTraffic (patchset #9 id:160001 of https://codereview.chromium.org/2348393002/ )

Reason for revert:
This broke a lot of LogDnsClientTest tests on all platforms:

https://build.chromium.org/p/chromium.mac/builders/Mac10.9%20Tests/builds/29988
https://build.chromium.org/p/chromium.linux/builders/Linux%20Tests/builds/47542
https://build.chromium.org/p/chromium.win/builders/Win7%20Tests%20%281%29/builds/58536

Original issue's description:
> Improves documentation and formatting.
>
> Replaces some test ASSERT/EXPECT calls with DCHECK, as they would only be the result of incorrect test setup.
>
> Small refactorings to improve encapsulation.
>
> BUG= 624894 
>
> Committed: https://crrev.com/f02172072e3fd83e2296e984f1e5bd86ba40093c
> Cr-Commit-Position: refs/heads/master@{#424984}

TBR=eranm@chromium.org,rsleevi@chromium.org,robpercival@chromium.org
# Skipping CQ checks because original CL landed less than 1 days ago.
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true
BUG= 624894 

Review-Url: https://codereview.chromium.org/2415063002
Cr-Commit-Position: refs/heads/master@{#424990}

[modify] https://crrev.com/edce9665b9672f51ac2709224798354c434c88e7/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/edce9665b9672f51ac2709224798354c434c88e7/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/edce9665b9672f51ac2709224798354c434c88e7/components/certificate_transparency/mock_log_dns_traffic.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/3106d3fe1758a68145023d2047ebaf70e1b7cbcd

commit 3106d3fe1758a68145023d2047ebaf70e1b7cbcd
Author: robpercival <robpercival@chromium.org>
Date: Tue Oct 18 08:40:32 2016

Improves documentation and formatting.

Replaces some test ASSERT/EXPECT calls with CHECK, as they would only be the result of incorrect test setup.

Small refactorings to improve encapsulation.

BUG= 624894 

Committed: https://crrev.com/f02172072e3fd83e2296e984f1e5bd86ba40093c
Review-Url: https://codereview.chromium.org/2348393002
Cr-Original-Commit-Position: refs/heads/master@{#424984}
Cr-Commit-Position: refs/heads/master@{#425924}

[modify] https://crrev.com/3106d3fe1758a68145023d2047ebaf70e1b7cbcd/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/3106d3fe1758a68145023d2047ebaf70e1b7cbcd/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/3106d3fe1758a68145023d2047ebaf70e1b7cbcd/components/certificate_transparency/mock_log_dns_traffic.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/cfe43126e0716d7626175dd0c4cac9a12863a50b

commit cfe43126e0716d7626175dd0c4cac9a12863a50b
Author: robpercival <robpercival@chromium.org>
Date: Thu Oct 20 11:39:10 2016

LogDnsClient now returns some errors synchronously

This allows users to handle issues, such as throttling, immediately.
Uses a sync-async DoLoop pattern internally now.

BUG= 624894 

Review-Url: https://chromiumcodereview.appspot.com/2369373002
Cr-Commit-Position: refs/heads/master@{#426451}

[modify] https://crrev.com/cfe43126e0716d7626175dd0c4cac9a12863a50b/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/cfe43126e0716d7626175dd0c4cac9a12863a50b/components/certificate_transparency/log_dns_client.h
[modify] https://crrev.com/cfe43126e0716d7626175dd0c4cac9a12863a50b/components/certificate_transparency/log_dns_client_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/0cb5c9c3ad3a29b0cfd9235cae02c051515fa8c5

commit 0cb5c9c3ad3a29b0cfd9235cae02c051515fa8c5
Author: robpercival <robpercival@chromium.org>
Date: Thu Oct 20 14:27:44 2016

Adds LogDnsClient::NotifyWhenNotThrottled

Allows a callback to be registered that will be invoked once the
LogDnsClient has stopped throttling queries.

BUG= 624894 

Review-Url: https://chromiumcodereview.appspot.com/2380293002
Cr-Commit-Position: refs/heads/master@{#426472}

[modify] https://crrev.com/0cb5c9c3ad3a29b0cfd9235cae02c051515fa8c5/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/0cb5c9c3ad3a29b0cfd9235cae02c051515fa8c5/components/certificate_transparency/log_dns_client.h
[modify] https://crrev.com/0cb5c9c3ad3a29b0cfd9235cae02c051515fa8c5/components/certificate_transparency/log_dns_client_unittest.cc

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/7038ecd8f58dc8fbd3201ad84b3875a6edc3ce3c

commit 7038ecd8f58dc8fbd3201ad84b3875a6edc3ce3c
Author: robpercival <robpercival@chromium.org>
Date: Thu Oct 20 17:05:49 2016

As suggested by Ryan Sleevi (https://codereview.chromium.org/2348393002/diff/80001/components/certificate_transparency/mock_log_dns_traffic.cc#newcode47), MockLogDnsTraffic will no longer CHECK-fail when given invalid test expectations. Instead, it will return false and the tests using it can ASSERT_TRUE.

BUG= 624894 

Review-Url: https://chromiumcodereview.appspot.com/2389993003
Cr-Commit-Position: refs/heads/master@{#426510}

[modify] https://crrev.com/7038ecd8f58dc8fbd3201ad84b3875a6edc3ce3c/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/7038ecd8f58dc8fbd3201ad84b3875a6edc3ce3c/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/7038ecd8f58dc8fbd3201ad84b3875a6edc3ce3c/components/certificate_transparency/mock_log_dns_traffic.h

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9

commit 9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9
Author: robpercival <robpercival@chromium.org>
Date: Wed Oct 05 13:29:44 2016

LogDnsClient now rejects responses unless they contain exactly one TXT RDATA string

Previously, multiple TXT RDATA strings would be concatenated if present,
allowing a larger number of audit proof nodes to be delivered. However,
the CT-over-DNS draft RFC
(https://github.com/google/certificate-transparency-rfcs/blob/master/dns/draft-ct-over-dns.md)
explicitly states that the response should contain only one string, and trying
to handle other cases only causes confusion.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2375693002
Cr-Commit-Position: refs/heads/master@{#423140}

[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/log_dns_client_unittest.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/mock_log_dns_traffic.cc
[modify] https://crrev.com/9dc75a8c1abe75bf6dd4674090f7b7591d1ea0f9/components/certificate_transparency/mock_log_dns_traffic.h

[Automated comment] removing mislabelled merge-merged-2840

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/5bfec4f1be40d333d92c0ebe200135be4928701c

commit 5bfec4f1be40d333d92c0ebe200135be4928701c
Author: robpercival <robpercival@chromium.org>
Date: Tue Nov 08 14:17:03 2016

Cleanup and minor refactoring of LogDnsClient

Given that a MerkleAuditProof only proves an inclusion path for a tree of a specific size, a tree_size parameter was added to it in  https://crrev.com/89f010d82559c73e7d23cbf067137ceb1df698df to keep track of which tree the proof was for. Because of this, it's no longer necessary to store the tree size separately in LogDnsClient::AuditProofQuery. Instead, it can just use the tree_size member of the MerkleAuditProof.

The QueryAuditProof method still takes the tree_size as a separate parameter, so as to not make the proof parameter a mixed in/out parameter, which could be confusing.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2485653002
Cr-Commit-Position: refs/heads/master@{#430604}

[modify] https://crrev.com/5bfec4f1be40d333d92c0ebe200135be4928701c/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/5bfec4f1be40d333d92c0ebe200135be4928701c/components/certificate_transparency/log_dns_client.h
[modify] https://crrev.com/5bfec4f1be40d333d92c0ebe200135be4928701c/components/certificate_transparency/log_dns_client_unittest.cc

http://crrev.com/2017563002 enables fetching of inclusion proofs.

The following revision refers to this bug:
  https://chromium.googlesource.com/chromium/src.git/+/70544e886eb9d0751fc233b54c724d792bf53da1

commit 70544e886eb9d0751fc233b54c724d792bf53da1
Author: robpercival <robpercival@chromium.org>
Date: Wed Mar 01 10:32:59 2017

UMA metrics for LogDnsClient

Records the time spent and status of retrieving an inclusion proof for a signed certificate timestamp (SCT) over DNS. This will show the effectiveness of retrieving proofs using Chromium's built-in DNS client.

BUG= 624894 

Review-Url: https://codereview.chromium.org/2491363002
Cr-Commit-Position: refs/heads/master@{#453898}

[modify] https://crrev.com/70544e886eb9d0751fc233b54c724d792bf53da1/components/certificate_transparency/log_dns_client.cc
[modify] https://crrev.com/70544e886eb9d0751fc233b54c724d792bf53da1/tools/metrics/histograms/histograms.xml