TRANS                                                        L. Nordberg
Internet-Draft                                                  NORDUnet
Intended status: Experimental                                 D. Gillmor
Expires: September 22, 2016 January 9, 2017                                            ACLU
                                                               T. Ritter

                                                          March 21,

                                                           July 08, 2016

                            Gossiping in CT
                       draft-ietf-trans-gossip-02
                       draft-ietf-trans-gossip-03

Abstract

   The logs in Certificate Transparency are untrusted in the sense that
   the users of the system don't have to trust that they behave
   correctly since the behaviour behavior of a log can be verified to be correct.

   This document tries to solve the problem with logs presenting a
   "split view" of their operations.  It describes three gossiping
   mechanisms for Certificate Transparency: SCT Feedback, STH
   Pollination and Trusted Auditor Relationship.

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on September 22, 2016. January 9, 2017.

Copyright Notice

   Copyright (c) 2016 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   3
   2.  Defining the problem  . . . . . . . . . . . . . . . . . . . .   4
   3.  Overview  . . . . . . . . . . . . . . . . . . . . . . . . . .   4
   4.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .   5
     4.1.  Pre-Loaded vs Locally Added Anchors . . . . . . . . . . .   5
   5.  Who gossips with whom . . . . . . . . . . . . . . . . . . . .   5
   6.  What to gossip about and how  . . . . . . . . . . . . . . . .   6
   7.  Data flow . . . . . . . . . . . . . . . . . . . . . . . . . .   6
   8.  Gossip Mechanisms . . . . . . . . . . . . . . . . . . . . . .   7
     8.1.  SCT Feedback  . . . . . . . . . . . . . . . . . . . . . .   7
       8.1.1.  SCT Feedback data format  . . . . . . . . . . . . . .   8
       8.1.2.  HTTPS client to server  . . . . . . . . . . . . . . .   8
       8.1.3.  HTTPS server operation  . . . . . . . . . . . . . . .  11
       8.1.4.  HTTPS server to auditors  . . . . . . . . . . . . . .  13
     8.2.  STH pollination . . . . . . . . . . . . . . . . . . . . .  14
       8.2.1.  HTTPS Clients and Proof Fetching  . . . . . . . . . .  15
       8.2.2.  STH Pollination without Proof Fetching  . . . . . . .  17
       8.2.3.  Auditor Action  . . . . . . . . . . . . . . . . . . .  17
       8.2.4.  STH Pollination data format . . . . . . . . . . . . .  17
     8.3.  Trusted Auditor Stream  . . . . . . . . . . . . . . . . .  17
       8.3.1.  Trusted Auditor data format . . . . . . . . . . . . .  18
   9.  3-Method Ecosystem  . . . . . . . . . . . . . . . . . . . . .  19
     9.1.  SCT Feedback  . . . . . . . . . . . . . . . . . . . . . .  19
     9.2.  STH Pollination . . . . . . . . . . . . . . . . . . . . .  20
     9.3.  Trusted Auditor Relationship  . . . . . . . . . . . . . .  21
     9.4.  Interaction . . . . . . . . . . . . . . . . . . . . . . .  22
   10. Security considerations . . . . . . . . . . . . . . . . . . .  22
     10.1.  Attacks by actively malicious logs . . . . . . . . . . .  22
     10.2.  Dual-CA Compromise . . . . . . . . . . . . . . . . . . .  23
     10.3.  Censorship/Blocking considerations . . . . . . . . . . .  23  24
     10.4.  Privacy considerations  Flushing Attacks . . . . . . . . . . . . . . . . . . . .  25
       10.4.1.  STHs . . . . . . . . . . . . . . . . . . . . . . . .  25
       10.4.2.  SCTs & Certificate Chains on HTTPS Servers . . . . .  26
       10.4.3.  SCTs & Certificate Chains on HTTPS Clients . . . . .  26
     10.5.  Privacy considerations . . . . . . . . . . . . . . . . .  27
       10.5.1.  Privacy and SCTs . . . . . . . . . . . . . . . . . .  25
       10.4.2.  27
       10.5.2.  Privacy in SCT Feedback  . . . . . . . . . . . . . .  25
       10.4.3.  27
       10.5.3.  Privacy for HTTPS clients performing STH Proof
                Fetching . . . . . . . . . . . . . . . . . . . . . .  26
       10.4.4.  28

       10.5.4.  Privacy in STH Pollination . . . . . . . . . . . . .  26
       10.4.5.  28
       10.5.5.  Privacy in STH Interaction . . . . . . . . . . . . .  27
       10.4.6.  29
       10.5.6.  Trusted Auditors for HTTPS Clients . . . . . . . . .  28
       10.4.7.  29
       10.5.7.  HTTPS Clients as Auditors  . . . . . . . . . . . . .  28  30
   11. Policy Recommendations  . . . . . . . . . . . . . . . . . . .  29  30
     11.1.  Blocking Recommendations . . . . . . . . . . . . . . . .  29  31
       11.1.1.  Frustrating blocking . . . . . . . . . . . . . . . .  29  31
       11.1.2.  Responding to possible blocking  . . . . . . . . . .  29  31
     11.2.  Proof Fetching Recommendations . . . . . . . . . . . . .  31  32
     11.3.  Record Distribution Recommendations  . . . . . . . . . .  31  33
       11.3.1.  Mixing Algorithm . . . . . . . . . . . . . . . . . .  32  34
       11.3.2.  Flushing Attacks  The Deletion Algorithm . . . . . . . . . . . . . . .  35
     11.4.  Concrete Recommendations . . . . .  33
       11.3.3.  The Deletion Algorithm . . . . . . . . . . .  36
       11.4.1.  STH Pollination  . . . .  34 . . . . . . . . . . . . . .  36
       11.4.2.  SCT Feedback . . . . . . . . . . . . . . . . . . . .  39
   12. IANA considerations . . . . . . . . . . . . . . . . . . . . .  45  53
   13. Contributors  . . . . . . . . . . . . . . . . . . . . . . . .  45  53
   14. ChangeLog . . . . . . . . . . . . . . . . . . . . . . . . . .  45  53
     14.1.  Changes between ietf-02 and ietf-03  . . . . . . . . . .  53
     14.2.  Changes between ietf-01 and ietf-02  . . . . . . . . . .  45
     14.2.  54
     14.3.  Changes between ietf-00 and ietf-01  . . . . . . . . . .  46
     14.3.  54
     14.4.  Changes between -01 and -02  . . . . . . . . . . . . . .  46
     14.4.  54
     14.5.  Changes between -00 and -01  . . . . . . . . . . . . . .  46  55
   15. References  . . . . . . . . . . . . . . . . . . . . . . . . .  47  55
     15.1.  Normative References . . . . . . . . . . . . . . . . . .  47  55
     15.2.  Informative References . . . . . . . . . . . . . . . . .  47  55
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  47  56

1.  Introduction

   The purpose of the protocols in this document, collectively referred
   to as CT Gossip, is to detect certain misbehavior by CT logs.  In
   particular, CT Gossip aims to detect logs that are providing
   inconsistent views to different log clients, and logs failing to
   include submitted certificates within the time period stipulated by
   MMD.

   [ TODO: enumerate the interfaces used for detecting misbehaviour? ]

   One of the major challenges of any gossip protocol is limiting damage
   to user privacy.  The goal of CT gossip is to publish and distribute
   information about the logs and their operations, but not to expose
   any additional information about the operation of any of the other
   participants.  Privacy of consumers of log information (in
   particular, of web browsers and other TLS clients) should not be
   undermined by gossip.

   This document presents three different, complementary mechanisms for
   non-log elements of the CT ecosystem to exchange information about
   logs in a manner that preserves the privacy of HTTPS clients.  They
   should provide protective benefits for the system as a whole even if
   their adoption is not universal.

2.  Defining the problem

   When a log provides different views of the log to different clients
   this is described as a partitioning attack.  Each client would be
   able to verify the append-only nature of the log but, in the extreme
   case, each client might see a unique view of the log.

   The CT logs are public, append-only and untrusted and thus have to be
   audited for consistency, i.e., they should never rewrite history.
   Additionally, auditors and other log clients need to exchange
   information about logs in order to be able to detect a partitioning
   attack (as described above).

   Gossiping about log behaviour behavior helps address the problem of detecting
   malicious or compromised logs with respect to a partitioning attack.
   We want some side of the partitioned tree, and ideally both sides, to
   see the other side.

   Disseminating information about a log poses a potential threat to the
   privacy of end users.  Some data of interest (e.g.  SCTs) is linkable
   to specific log entries and thereby to specific websites, which makes
   sharing them with others a privacy concern.  Gossiping about this
   data has to take privacy considerations into account in order not to
   expose associations between users of the log (e.g., web browsers) and
   certificate holders (e.g., web sites).  Even sharing STHs (which do
   not link to specific log entries) can be problematic - user tracking
   by fingerprinting through rare STHs is one potential attack (see
   Section 8.2).

3.  Overview

   This document presents three gossiping mechanisms: SCT Feedback, STH
   Pollination, and a Trusted Auditor Relationship.

   SCT Feedback enables HTTPS clients to share Signed Certificate
   Timestamps (SCTs) (Section 3.3 of [RFC-6962-BIS-09]) with CT auditors
   in a privacy-preserving manner by sending SCTs to originating HTTPS
   servers, who in turn share them with CT auditors.

   In STH Pollination, HTTPS clients use HTTPS servers as pools to share
   Signed Tree Heads (STHs) (Section 3.6 of [RFC-6962-BIS-09]) with
   other connecting clients in the hope that STHs will find their way to
   CT auditors.

   HTTPS clients in a Trusted Auditor Relationship share SCTs and STHs
   with trusted CT auditors directly, with expectations of privacy
   sensitive data being handled according to whatever privacy policy is
   agreed on between client and trusted party.

   Despite the privacy risks with sharing SCTs there is no loss in
   privacy if a client sends SCTs for a given site to the site
   corresponding to the SCT.  This is because the site's logs would
   already indicate that the client is accessing that site.  In this way
   a site can accumulate records of SCTs that have been issued by
   various logs for that site, providing a consolidated repository of
   SCTs that could be shared with auditors.  Auditors can use this
   information to detect logs a misbehaving log that misbehave by not including
   certificates fails to include a
   certificate within the time period stipulated by the its MMD metadata.

   Sharing an STH is considered reasonably safe from a privacy
   perspective as long as the same STH is shared by a large number of
   other log clients.  This safety in numbers can be achieved by only
   allowing gossiping of STHs issued in a certain window of time, while
   also refusing to gossip about STHs from logs with too high an STH
   issuance frequency (see Section 8.2).

4.  Terminology

   This document relies on terminology and data structures defined in
   [RFC-6962-BIS-09], including MMD, STH, SCT, Version, LogID, SCT
   timestamp, CtExtensions, SCT signature, Merkle Tree Hash.

   This document relies on terminology defined in
   [draft-ietf-trans-threat-analysis-03], including Auditing.

4.1.  Pre-Loaded vs Locally Added Anchors

   Through the document, we refer to both Trust Anchors (Certificate
   Authorities) and Logs.  Both Logs and Trust Anchors may be locally
   added by an administrator.  Unless otherwise clarified, in both cases
   we refer to the set of Trust Anchors and Logs that come pre-loaded
   and pre-trusted in a piece of client software.

5.  Who gossips with whom

   o  HTTPS clients and servers (SCT Feedback and STH Pollination)

   o  HTTPS servers and CT auditors (SCT Feedback and STH Pollination)

   o  CT auditors (Trusted Auditor Relationship)
   Additionally, some HTTPS clients may engage with an auditor who they
   trust with their privacy:

   o  HTTPS clients and CT auditors (Trusted Auditor Relationship)

6.  What to gossip about and how

   There are three separate gossip streams:

   o  SCT Feedback - transporting SCTs and certificate chains from HTTPS
      clients to CT auditors via HTTPS servers.

   o  STH Pollination - HTTPS clients and CT auditors using HTTPS
      servers as STH pools for exchanging STHs.

   o  Trusted Auditor Stream - HTTPS clients communicating directly with
      trusted CT auditors sharing SCTs, certificate chains and STHs.

   It is worthwhile to note that when an HTTPS Client client or CT auditor
   interact
   interacts with a log, they may equivalently interact with a log
   mirror or cache that replicates the log.

7.  Data flow

   The following picture shows how certificates, SCTs and STHs flow
   through a CT system with SCT Feedback and STH Pollination.  It does
   not show what goes in the Trusted Auditor Relationship stream.

      +- Cert ---- +----------+
      |            |    CA    | ----------+
      |   + SCT -> +----------+           |
      v   |                           Cert [& SCT]
   +----------+                           |
   |   Log    | ---------- SCT -----------+
   +----------+                           v
     |  ^                          +----------+
     |  |          SCT         SCTs & Certs --- | Website  |
     |  |[1]           |           +----------+
     |  |[2]          STH         STHs            ^     |
     |  |[3]           v             |     |
     |  |          +----------+      |     |
     |  +--------> | Auditor  |      |  HTTPS traffic
     |             +----------+      |     |
    STH                              |  SCT & Cert
     |                         SCT                        SCTs & Certs |
   Log entries                       |     |
     |                              STH   STH                             STHs   STHs
     v                               |     |
   +----------+                      |     v
   | Monitor  |                    +----------+
   +----------+                    | Browser  |
                                   +----------+

   #   Auditor                        Log
   [1] |--- get-sth ------------------->|
       |<-- STH ------------------------|
   [2] |--- leaf hash + tree size ----->|
       |<-- index + inclusion proof --->|
   [3] |--- tree size 1 + tree size 2 ->|
       |<-- consistency proof ----------|

8.  Gossip Mechanisms

8.1.  SCT Feedback

   The goal of SCT Feedback is for clients to share SCTs and certificate
   chains with CT auditors while still preserving the privacy of the end
   user.  The sharing of SCTs contribute to the overall goal of
   detecting misbehaving logs by providing auditors with SCTs from many
   vantage points, making it more likely to catch a violation of a log's
   MMD or a log presenting inconsistent views.  The sharing of
   certificate chains is beneficial to HTTPS server operators interested
   in direct feedback from clients for detecting bogus certificates
   issued in their name and therefore incentivises incentivizes server operators to
   take part in SCT Feedback.

   SCT Feedback is the most privacy-preserving gossip mechanism, as it
   does not directly expose any links between an end user and the sites
   they've visisted visited to any third party.

   HTTPS clients store SCTs and certificate chains they see, and later
   send them to the originating HTTPS server by posting them to a well-
   known URL (associated with that server), as described in
   Section 8.1.2.  Note that clients will send the same SCTs and chains
   to a server multiple times with the assumption that any man-in-the-
   middle attack eventually will cease, and an honest server will
   eventually receive collected malicious SCTs and certificate chains.

   HTTPS servers store SCTs and certificate chains received from
   clients, as described in Section 8.1.3.  They later share them with
   CT auditors by either posting them to auditors or making them
   available via a well-known URL.  This is described in Section 8.1.4.

8.1.1.  SCT Feedback data format

   The data shared between HTTPS clients and servers, as well as between
   HTTPS servers and CT auditors, is a JSON array [RFC7159].  Each item
   in the array is a JSON object with the following content:

   o  x509_chain: An array of base64-encoded PEM-encoded X.509 certificates.  The first
      element is the end-entity certificate, the second certifies the
      first and so on.

   o  sct_data: An array of objects consisting of the base64
      representation of the binary SCT data as defined in
      [RFC-6962-BIS-09] Section 3.3.

   We will refer to this object as 'sct_feedback'.

   The x509_chain element always contains at least one element.  It also
   always contains a full chain from a leaf
   certificate to a self-signed trust anchor.

   [ TBD: Be strict about

   See Section 8.1.2 for details on what the sct_data may contain or is this
   sufficiently implied by previous sections? ] element contains
   as well as more details about the x509_chain element.

8.1.2.  HTTPS client to server

   When an HTTPS client connects to an HTTPS server, the client receives
   a set of SCTs as part of the TLS handshake.  SCTs are included in the
   TLS handshake using one or more of the three mechanisms described in
   [RFC-6962-BIS-09] section 3.4 - in the server certificate, in a TLS
   extension, or in an OCSP extension.  The client MUST discard SCTs
   that are not signed by a log known to the client and SHOULD store the
   remaining SCTs together with a locally constructed certificate chain
   which is trusted (i.e. terminated in a pre-loaded or locally
   installed Trust Anchor) in an sct_feedback object or equivalent data
   structure for later use in SCT Feedback.

   The SCTs stored on the client MUST be keyed by the exact domain name
   the client contacted.  They MUST NOT be sent to any domain not
   matching the original domain (e.g. if the original domain is
   sub.example.com they must not be sent to sub.sub.example.com or to
   example.com.)  They MUST NOT be sent to any Subject Alternate Names
   specified in the certificate.  In the case of certificates that
   validate multiple domain names, the same SCT is expected to be stored
   multiple times.

   Not following these constraints would increase the risk for two types
   of privacy breaches.  First, the HTTPS server receiving the SCT would
   learn about other sites visited by the HTTPS client.  Second,
   auditors receiving SCTs from the HTTPS server would learn information
   about other HTTPS servers visited by its clients.

   If the client later again connects to the same HTTPS server, it again
   receives a set of SCTs and calculates a certificate chain, and again
   creates an sct_feedback or similar object.  If this object does not
   exactly match an existing object in the store, then the client MUST
   add this new object to the store, associated with the exact domain
   name contacted, as described above.  An exact comparison is needed to
   ensure that attacks involving alternate chains are detected.  An
   example of such an attack is described in [TODO double-CA-compromise
   attack].
   [dual-ca-compromise-attack].  However, at least one optimization is
   safe and MAY be performed: If the certificate chain exactly matches
   an existing certificate chain, the client may MAY store the union of the
   SCTs from the two objects in the first (existing) object.

   If the client does connect to the same HTTPS server a subsequent
   time, it MUST send to the server sct_feedback objects in the store
   that are associated with that domain name.  It  However, it is not
   necessary to send an sct_feedback object constructed from the current
   TLS session.

   The session, and if the client does so, it MUST NOT send the same set of SCTs to be marked as sent
   in any internal tracking done by the same server more
   often than TBD.

   [ TODO: expand on rate/resource limiting motivation ] client.

   Refer to Section 11.3 for recommendations about strategies. for implementation.

   Because SCTs can be used as a tracking mechanism (see
   Section 10.4.2), 10.5.2), they deserve special treatment when they are
   received from (and provided to) domains that are loaded as
   subresources from an origin domain.  Such domains are commonly called
   'third party domains'.  An HTTPS Client client SHOULD store SCT Feedback
   using a 'double-keying' approach, which isolates third party domains
   by the first party domain.  This is described in XXX. [double-keying].

   Gossip would be performed normally for third party domains only when
   the user revisits the first party domain.  In lieu of 'double-keying', 'double-
   keying', an HTTPS Client client MAY treat SCT Feedback in the same manner it
   treats other security mechanisms that can enable tracking (such as
   HSTS and HPKP.)

   [ XXX is currently https://www.torproject.org/projects/torbrowser/
   design/#identifier-linkability How should it be references?  Do we
   need to copy this out into another document?  An appendix? ]

   If the HTTPS client has configuration options for not sending cookies
   to third parties, SCTs of third parties MUST be treated as cookies
   with respect to this setting.  This prevents third party tracking
   through the use of SCTs/certificates, which would bypass the cookie
   policy.  For domains that are only loaded as third party domains, the
   client may never perform SCT Feedback; however the client may perform
   STH Pollination after fetching an inclusion proof, as specified in
   Section 8.2.

   SCTs and corresponding certificates are POSTed to the originating
   HTTPS server at the well-known URL:

   https://<domain>/.well-known/ct-gossip/v1/sct-feedback

   The data sent in the POST is defined in Section 8.1.1.  This data
   SHOULD be sent in an already established already-established TLS session.  This makes it
   hard for an attacker to disrupt SCT Feedback without also disturbing
   ordinary secure browsing (https://).  This is discussed more in
   Section 11.1.1.

   The HTTPS server SHOULD respond with an HTTP 200 response code and an
   empty body if it was able to process the request.  An HTTPS client
   who receives any other response SHOULD consider it an error.

   Some clients have trust anchors or logs that are locally added (e.g.
   by an administrator or by the user themselves).  These additions are
   potentially privacy-sensitive because they can carry information
   about the specific configuration, computer, or user.

   Certificates validated by locally added trust anchors will commonly
   have no SCTs associated with them, so in this case no action is
   needed with respect to CT Gossip.  SCTs issued by locally added logs
   MUST NOT be reported via SCT Feedback.

   If a certificate is validated by SCTs that are issued by publicly
   trusted logs, but chains to a local trust anchor, the client MAY
   perfom
   perform SCT Feedback for this SCT and certificate chain bundle.  If
   it does so, the client MUST include the full chain of certificates
   chaining to the local trust anchor in the x509_chain array.
   Perfoming
   Performing SCT Feedback in this scenario may be advantageous for the
   broader internet and CT ecosystem, but may also disclose information
   about the client.  If the client elects to omit SCT Feedback, it can
   still
   choose to perform STH Pollination after fetching an inclusion proof,
   as specified in Section 8.2.

   We require the client to send the full chain (or nothing at all) for
   two reasons.  Firstly, it simplifies the operation on the server if
   there are not two code paths.  Secondly, omitting the chain does not
   actually preserve user privacy.  The Issuer field in the certificate
   describes the signing certificate.  And if the certificate is being
   submitted at all, it means the certificate is logged, and has SCTs.
   This means that the Issuer can be queried and obtained from the log log,
   so omitting the parent signing certificate from the client's submission does
   not actually help user privacy.

8.1.3.  HTTPS server operation

   HTTPS servers can be configured (or omit configuration), resulting
   in, broadly, two modes of operation.  In the simpler mode, the server
   will only track leaf certificates and SCTs applicable to those leaf
   certificates.  In the more complex mode, the server will confirm the
   client's chain validation and store the certificate chain.  The
   latter mode requires more configuration, but is necessary to prevent
   denial of service (DoS) attacks on the server's storage space.

   In the simple mode of operation, upon recieving receiving a submission at the
   sct-feedback well-known URL, an HTTPS server will perform a set of
   operations, checking on each sct_feedback object before storing it:

   1.  the HTTPS server MAY modify the sct_feedback object, and discard
       all items in the x509_chain array except the first item (which is
       the end-entity certificate)

   2.  if a bit-wise compare of the sct_feedback object matches one
       already in the store, this sct_feedback object SHOULD be
       discarded

   3.  if the leaf cert is not for a domain for which the server is
       authoritative, the SCT MUST be discarded

   4.  if an SCT in the sct_data array can't be verified to be a valid
       SCT for the accompanying leaf cert, and issued by a known log,
       the individual SCT SHOULD be discarded

   The modification in step number 1 is necessary to prevent a malicious
   client from exhausting the server's storage space.  A client can
   generate their own issuing certificate authorities, and create an
   arbitrary number of chains that terminate in an end-entity
   certificate with an existing SCT.  By discarding all but the end-
   entity certificate, we prevent a simple HTTPS server from storing
   this data.  Note that operation in this mode will not prevent the
   attack described in Section 10.2. [dual-ca-compromise-attack].  Skipping this step
   requires additional configuration as described below.

   The check in step 2 is for detecting duplicates and minimizing
   processing and storage by the server.  As on the client, an exact
   comparison is needed to ensure that attacks involving alternate
   chains are detected.  Again, at least one optimization is safe and
   MAY be performed.  If the certificate chain exactly matches an
   existing certificate chain, the server may MAY store the union of the
   SCTs from the two objects in the first (existing) object.  It should
   do this after completing  If the
   validity check on any of the SCTs fails, the server SHOULD NOT store
   the union of the SCTs.

   The check in step 3 is to help malfunctioning clients from exposing
   which sites they visit.  It additionally helps prevent DoS attacks on
   the server.

   [ TBD: Note: Thinking about building this, how does the SCT Feedback app
   know which sites it's authoritative for?  It will need that amount of
   configuration at least. ]

   The check in step 4 is to prevent DoS attacks where an adversary
   fills up the store prior to attacking a client (thus preventing the
   client's feedback from being recorded), or an attack where an
   adversary simply attempts to fill up server's storage space.

   The above describes the simpler mode of operation.  In the more
   advanced server configuration mode, the server will detect the [TODO double-
   CA-compromise] attack. attack described in
   [dual-ca-compromise-attack].  In this configuration the server will
   not modify the sct_feedback object prior to performing checks 2, 3,
   and 4.

   To prevent a malicious client from filling the server's data store,
   the HTTPS Server server SHOULD perform an additional check:

   1. check in the more
   advanced mode:

   o  if the x509_chain consists of an invalid certificate chain, or the
      culminating trust anchor is not recognized by the server, the
      server SHOULD modify the sct_feedback object, discarding all items
      in the x509_chain array except the first item

   The HTTPS server may MAY choose to omit checks 4 or 5.  This will place
   the server at risk of having its data store filled up by invalid
   data, but can also allow a server to identify interesting certificate
   or certificate chains that omit valid SCTs, or do not chain to a
   trusted root.  This information may enable an HTTPS server operator
   to detect attacks or unusual behavior of Certificate Authorities even
   outside the Certificate Transparency ecosystem.

8.1.4.  HTTPS server to auditors

   HTTPS servers receiving SCTs from clients SHOULD share SCTs and
   certificate chains with CT auditors by either serving them on the
   well-known URL:

   https://<domain>/.well-known/ct-gossip/v1/collected-sct-feedback

   or by HTTPS POSTing them to a set of preconfigured auditors.  This
   allows an HTTPS server to choose between an active push model or a
   passive pull model.

   The data received in a GET of the well-known URL or sent in the POST
   is defined in Section 8.1.1. 8.1.1 with the following difference: The
   x509_chain element may contain only he end-entity certificate, as
   described below.

   HTTPS servers SHOULD share all sct_feedback objects they see that
   pass the checks in Section 8.1.3.  If this is an infeasible amount of
   data, the server may MAY choose to expire submissions according to an
   undefined policy.  Suggestions for such a policy can be found in
   Section 11.3.

   HTTPS servers MUST NOT share any other data that they may learn from
   the submission of SCT Feedback by HTTPS clients, like the HTTPS
   client IP address or the time of submission.

   As described above, HTTPS servers can be configured (or omit
   configuration), resulting in two modes of operation.  In one mode,
   the x509_chain array will contain a full certificate chain.  This
   chain may terminate in a trust anchor the auditor may recognize, or
   it may not.  (One scenario where this could occur is if the client
   submitted a chain terminiating terminating in a locally added trust anchor, and
   the server kept this chain.)  In the other mode, the x509_chain array
   will consist of only a single element, which is the end-entity
   certificate.

   Auditors SHOULD provide the following URL accepting HTTPS POSTing of
   SCT feedback data:

   https://<auditor>/ct-gossip/v1/sct-feedback

   [ TBD: Should that be .well-known?  Depends on whether auditors will
   operate in their own URL name space or not. ]

   Auditors SHOULD regularly poll HTTPS servers at the well-known
   collected-sct-feedback URL.  The frequency of the polling and how to
   determine which domains to poll is outside the scope of this
   document.  However, the selection MUST NOT be influenced by potential
   HTTPS clients connecting directly to the auditor.  For example, if a
   poll to example.com occurs directly after a client submits an SCT for
   example.com, an adversary observing the auditor can trivially
   conclude the activity of the client.

8.2.  STH pollination

   The goal of sharing Signed Tree Heads (STHs) through pollination is
   to share STHs between HTTPS clients and CT auditors while still
   preserving the privacy of the end user.  The sharing of STHs
   contribute to the overall goal of detecting misbehaving logs by
   providing CT auditors with STHs from many vantage points, making it
   possible to detect logs that are presenting inconsistent views.

   HTTPS servers supporting the protocol act as STH pools.  HTTPS
   clients and CT auditors in the possession of STHs can pollinate STH
   pools by sending STHs to them, and retrieving new STHs to send to
   other STH pools.  CT auditors can improve the value of their auditing
   by retrieving STHs from pools.

   HTPS

   HTTPS clients send STHs to HTTPS servers by POSTing them to the well-
   known URL:

   https://<domain>/.well-known/ct-gossip/v1/sth-pollination

   The data sent in the POST is defined in Section 8.2.4.  This data
   SHOULD be sent in an already established TLS session.  This makes it
   hard for an attacker to disrupt STH gossiping without also disturbing
   ordinary secure browsing (https://).  This is discussed more in
   Section 11.1.1.

   The response contains zero or more STHs in

   On a successful connection to an HTTPS server implementing STH
   Pollination, the same format, response code will be 200, and the response body is
   application/json, containing zero or more STHs in the same format, as
   described in Section 8.2.4.

   An HTTPS client may acquire STHs by several methods:

   o  in replies to pollination POSTs;

   o  asking logs that it recognises recognizes for the current STH, either
      directly (v2/get-sth) or indirectly (for example over DNS)

   o  resolving an SCT and certificate to an STH via an inclusion proof

   o  resolving one STH to another via a consistency proof
   HTTPS clients (that have STHs) and CT auditors SHOULD pollinate STH
   pools with STHs.  Which STHs to send and how often pollination should
   happen is regarded as undefined policy with the exception of privacy
   concerns explained below.  Suggestions for the policy may can be found in
   Section 11.3.

   An HTTPS client could be tracked by giving it a unique or rare STH.
   To address this concern, we place restrictions on different
   components of the system to ensure an STH will not be rare.

   o  HTTPS clients silently ignore STHs from logs with an STH issuance
      frequency of more than one STH per hour.  Logs use the STH
      Frequency Count metadata to express this ([RFC-6962-BIS-09]
      sections 3.6 and 5.1).

   o  HTTPS clients silently ignore STHs which are not fresh.

   An STH is considered fresh iff its timestamp is less than 14 days in
   the past.  Given a maximum STH issuance rate of one per hour, an
   attacker has 336 unique STHs per log for tracking.  Clients MUST
   ignore STHs older than 14 days.  We consider STHs within this
   validity window not to be personally identifiable data, and STHs
   outside this window to be personally identifiable.

   When multiplied by the number of logs from which a client accepts
   STHs, this number of unique STHs grow and the negative privacy
   implications grow with it.  It's important that this is taken into
   account when logs are chosen for default settings in HTTPS clients.
   This concern is discussed upon in Section 10.4.5. 10.5.5.

   A log may cease operation, in which case there will soon be no STH
   within the validity window.  Clients SHOULD perform all three methods
   of gossip about a log that has ceased operation since it is possible
   the log was still compromised and gossip can detect that.  STH
   Pollination is the one mechanism where a client must know about a log
   shutdown.  A client who does not know about a log shutdown MUST NOT
   attempt any heuristic to detect a shutdown.  Instead the client MUST
   be informed about the shutdown from a verifiable source (e.g. a
   software update).  The client SHOULD be provided the final STH issued
   by the log and SHOULD resolve SCTs and STHs to this final STH.  If an
   SCT or STH cannot be resolved to the final STH, clients should SHOULD follow
   the requirements and recommendations set forth in Section 11.1.2.

8.2.1.  HTTPS Clients and Proof Fetching

   There are two types of proofs a client may retrieve; inclusion proofs
   and consistency proofs.

   An HTTPS client will retrieve SCTs together with certificate chains
   from an HTTPS server, server.  Using the timestamp in the SCT together with
   the end-entity certificate and must the issuer key hash, it can obtain an
   inclusion proof to an STH in order to verify the promise made by the
   SCT.

   An HTTPS client will have STHs from performing STH Pollination, and
   may obtain a consistency proof to a more recent STH.

   An HTTPS client may also receive an SCT bundled with an inclusion
   proof to a historical STH via an unspecified future mechanism.
   Because this historical STH is considered personally identifiable
   information per above, the client must needs to obtain a consistency proof
   to a more recent STH.

   A client SHOULD perform proof fetching.  A client MUST NOT perform
   proof fetching for any SCTs or STHs issued by a locally added log.  A
   client MAY fetch an inclusion proof for an SCT (issued by a pre-
   loaded log) that validates a certificate chaining to a locally added
   trust anchor.

   [ TBD: Linus doesn't like this because we're mandating behavior that
   is not necessarily safe.  Is it unsafe?  Not sure.]

   If a client requested either proof directly from a log or auditor, it
   would reveal the client's browsing habits to a third party.  To
   mitigate this risk, an HTTPS client MUST retrieve the proof in a
   manner that disguises the client.

   Depending on the client's DNS provider, DNS may provide an
   appropriate intermediate layer that obfuscates the linkability
   between the user of the client and the request for inclusion (while
   at the same time providing a caching layer for oft-requested
   inclusion proofs.)

   [ TODO: Add a reference to Google's DNS mechanism more proper than
   http://www.certificate-transparency.org/august-2015-newsletter ] proofs).  See [draft-ct-over-dns] for an example of how
   this can be done.

   Anonymity networks such as Tor also present a mechanism for a client
   to anonymously retrieve a proof from an auditor or log.

   Even when using a privacy-preserving layer between the client and the
   log, certain observations may be made about an anonymous client or
   general user behavior depending on how proofs are fetched.  For
   example, if a client fetched all outstanding proofs at once, a log
   would know that SCTs or STHs recieved received around the same time are more
   likely to come from a particular client.  This could potentially go
   so far as correlation of activity at different times to a single
   client.  In aggregate the data could reveal what sites are commonly
   visited together.  HTTPS clients SHOULD use a strategy of proof
   fetching that attempts to obfuscate these patterns.  A suggestion of
   such a policy can be found in Section 11.2.

   Resolving either SCTs and STHs may result in errors.  These errors
   may be routine downtime or other transient errors, or they may be
   indicative of an attack.  Clients should SHOULD follow the requirements and
   recommendations set forth in Section 11.1.2 when handling these
   errors in order to give the CT ecosystem the greatest chance of
   detecting and responding to a compromise.

8.2.2.  STH Pollination without Proof Fetching

   An HTTPS client MAY participate in STH Pollination without fetching
   proofs.  In this situation, the client receives STHs from a server,
   applies the same validation logic to them (signed by a known log,
   within the validity window) and will later pass them to an another HTTPS
   server.

   When operating in this fashion, the HTTPS client is promoting gossip
   for Certificate Transparency, but derives no direct benefit itself.
   In comparison, a client who resolves SCTs or historical STHs to
   recent STHs and pollinates them is assured that if it was attacked,
   there is a probability that the ecosystem will detect and respond to
   the attack (by distrusting the log).

8.2.3.  Auditor Action

   CT auditors participate in STH pollination by retrieving STHs from
   HTTPS servers.  They verify that the STH is valid by checking the
   signature, and requesting a consistency proof from the STH to the
   most recent STH.

   After retrieving the consistency proof to the most recent STH, they
   SHOULD pollinate this new STH among participating HTTPS Servers. servers.  In
   this way, as STHs "age out" and are no longer fresh, their "lineage"
   continues to be tracked in the system.

8.2.4.  STH Pollination data format

   The data sent from HTTPS clients and CT auditors to HTTPS servers is
   a JSON object [RFC7159] with the following content:

   o  sths - an array of 0 or more fresh SignedTreeHead's SignedTreeHeads as defined in
      [RFC-6962-BIS-09] Section 3.6.1.

8.3.  Trusted Auditor Stream

   HTTPS clients MAY send SCTs and cert chains, as well as STHs,
   directly to auditors.  If sent, this data MAY include data that
   reflects locally added logs or trust anchors.  Note that there are
   privacy implications in doing so, these are outlined in
   Section 10.4.1 10.5.1 and Section 10.4.6. 10.5.6.

   The most natural trusted auditor arrangement arguably is a web
   browser that is "logged in to" a provider of various internet
   services.  Another equivalent arrangement is a trusted party like a
   corporation to which an employee is connected through a VPN or by
   other similar means.  A third might be individuals or smaller groups
   of people running their own services.  In such a setting, retrieving
   proofs from that third party could be considered reasonable from a
   privacy perspective.  The HTTPS client may also do its own auditing
   and might additionally share SCTs and STHs with the trusted party to
   contribute to herd immunity.  Here, the ordinary [RFC-6962-BIS-09]
   protocol is sufficient for the client to do the auditing while SCT
   Feedback and STH Pollination can be used in whole or in parts for the
   gossip part.

   Another well established trusted party arrangement on the internet
   today is the relation between internet users and their providers of
   DNS resolver services.  DNS resolvers are typically provided by the
   internet service provider (ISP) used, which by the nature of name
   resolving already know a great deal about which sites their users
   visit.  As mentioned in Section 8.2.1, in order for HTTPS clients to
   be able to retrieve proofs in a privacy preserving manner, logs could
   expose a DNS interface in addition to the ordinary HTTPS interface.
   An informal writeup
   A specification of such a protocol can be found at XXX. in
   [draft-ct-over-dns].

8.3.1.  Trusted Auditor data format

   Trusted Auditors expose a REST API at the fixed URI:

   https://<auditor>/ct-gossip/v1/trusted-auditor

   Submissions are made by sending an HTTPS POST request, with the body
   of the POST in a JSON object.  Upon successful receipt the Trusted
   Auditor returns 200 OK.

   The JSON object consists of two top-level keys: 'sct_feedback' and
   'sths'.  The 'sct_feedback' value is an array of JSON objects as
   defined in Section 8.1.1.  The 'sths' value is an array of STHs as
   defined in Section 8.2.4.

   Example:

   {
     'sct_feedback' :
       [
         {
           'x509_chain' :
             [
               '----BEGIN CERTIFICATE---\n
                AAA...',
               '----BEGIN CERTIFICATE---\n
                AAA...',
                ...
             ],
           'sct_data' :
             [
               'AAA...',
               'AAA...',
               ...
             ]
         }, ...
       ],
     'sths' :
       [
         'AAA...',
         'AAA...',
         ...
       ]
   }

9.  3-Method Ecosystem

   The use of three distinct methods for auditing logs may seem
   excessive, but each represents a needed component in the CT
   ecosystem.  To understand why, the drawbacks of each component must
   be outlined.  In this discussion we assume that an attacker knows
   which mechanisms an HTTPS client and HTTPS server implement.

9.1.  SCT Feedback

   SCT Feedback requires the cooperation of HTTPS clients and more
   importantly HTTPS servers.  Although SCT Feedback does require a
   significant amount of server-side logic to respond to the
   corresponding APIs, this functionality does not require
   customization, so it may be pre-provided and work out of the box.
   However, to take full advantage of the system, an HTTPS server would
   wish to perform some configuration to optimize its operation:

   o  Minimize its disk commitment by maintaining a list of known SCTs
      and certificate chains (or hashes thereof)

   o  Maximize its chance of detecting a misissued certificate by
      configuring a trust store of CAs

   o  Establish a "push" mechanism for POSTing SCTs to CT auditors

   These configuration needs, and the simple fact that it would require
   some deployment of software, means that some percentage of HTTPS
   servers will not deploy SCT Feedback.

   It is worthwhile to note that an attacker may be able to prevent
   detection of an attack on a webserver (in all cases) if SCT Feedback
   is not implemented.  This attack is detailed in Section 10.1).

   If SCT Feedback was the only mechanism in the ecosystem, any server
   that did not implement the feature would open itself and its users to
   attack without any possibility of detection.

   If SCT Feedback is not deployed by a webserver, malicious logs will
   be able to attack all users of the webserver (who do not have a
   Trusted Auditor relationship) with impunity.  Additionally, users who
   wish to have the strongest measure of privacy protection (by
   disabling STH Pollination Proof Fetching and forgoing a Trusted
   Auditor) could be attacked without risk of detection.

9.2.  STH Pollination

   STH Pollination requires the cooperation of HTTPS clients, HTTPS
   servers, and logs.

   For a client to fully participate in STH Pollination, and have this
   mechanism detect attacks against it, the client must have a way to
   safely perform Proof Fetching in a privacy preserving manner.  (The
   client may pollinate STHs it receives without performing Proof
   Fetching, but we do not consider this option in this section.)

   HTTPS Servers servers must deploy software (although, as in the case with SCT
   Feedback this logic can be pre-provided) and commit some configurable
   amount of disk space to the endeavor.

   Logs (or a third party) party mirroring the logs) must provide access to
   clients to query proofs in a privacy preserving manner, most likely
   through DNS.

   Unlike SCT Feedback, the STH Pollination mechanism is not hampered if
   only a minority of HTTPS servers deploy it.  However, it makes an
   assumption that an HTTPS client performs Proof Fetching (such as the
   DNS mechanism discussed).  Unfortunately, any manner that is
   anonymous for some (such as clients who use shared DNS services such
   as a large ISP), may not be anonymous for others.

   For instance, DNS requests expose a considerable amount of sensitive
   information (including what data is already present in the cache) in
   plaintext over the network.  For this reason, some percentage of
   HTTPS clients may choose to not enable the Proof Fetching component
   of STH Pollination.  (Although they can still request and send STHs
   among participating HTTPS servers, even when this affords them no
   direct benefit.)

   If STH Pollination was the only mechanism deployed, users that
   disable it would be able to be attacked without risk of detection.

   If STH Pollination was not deployed, HTTPS Clients clients visiting HTTPS
   Servers who did not deploy SCT Feedback could be attacked without
   risk of detection.

9.3.  Trusted Auditor Relationship

   The Trusted Auditor Relationship is expected to be the rarest gossip
   mechanism, as an HTTPS Client client is providing an unadulterated report of
   its browsing history to a third party.  While there are valid and
   common reasons for doing so, there is no appropriate way to enter
   into this relationship without retrieving informed consent from the
   user.

   However, the Trusted Auditor Relationship mechanism still provides
   value to a class of HTTPS Clients. clients.  For example, web crawlers have no
   concept of a "user" and no expectation of privacy.  Organizations
   already performing network auditing for anomalies or attacks can run
   their own Trusted Auditor for the same purpose with marginal increase
   in privacy concerns.

   The ability to change one's Trusted Auditor is a form of Trust
   Agility that allows a user to choose who to trust, and be able to
   revise that decision later without consequence.  A Trusted Auditor
   connection can be made more confidential than DNS (through the use of
   TLS), and can even be made (somewhat) anonymous through the use of
   anonymity services such as Tor. (Note that this does ignore the de-
   anonymization possibilities available from viewing a user's browsing
   history.)

   If the Trusted Auditor relationship was the only mechanism deployed,
   users who do not enable it (the majority) would be able to be
   attacked without risk of detection.

   If the Trusted Auditor relationship was not deployed, crawlers and
   organizations would build it themselves for their own needs.  By
   standardizing it, users who wish to opt-in (for instance those
   unwilling to participate fully in STH Pollination) can have an
   interoperable standard they can use to choose and change their
   trusted auditor.

9.4.  Interaction

   The interactions of the mechanisms is thus outlined:

   HTTPS Clients clients can be attacked without risk of detection if they do
   not participate in any of the three mechanisms.

   HTTPS Clients clients are afforded the greatest chance of detecting an attack
   when they either participate in both SCT Feedback and STH Pollination
   with Proof Fetching or if they have a Trusted Auditor relationship.
   (Participating in SCT Feedback is required to prevent a malicious log
   from refusing to ever resolve an SCT to an STH, as put forward in
   Section 10.1).  Additionally, participating in SCT Feedback enables
   an HTTPS Client client to assist in detecting the exact target of an attack.

   HTTPS Servers servers that omit SCT Feedback enable malicious logs to carry
   out attacks without risk of detection.  If these servers are targeted
   specifically, even if the attack is detected, without SCT Feedback
   they may never learn that they were specifically targeted.  HTTPS
   servers without SCT Feedback do gain some measure of herd immunity,
   but only because their clients participate in STH Pollination (with
   Proof Fetching) or have a Trusted Auditor Relationship.

   When HTTPS Servers servers omit SCT feedback, it allows their users to be
   attacked without detection by a malicious log; the vulnerable users
   are those who do not have a Trusted Auditor relationship.

10.  Security considerations

10.1.  Attacks by actively malicious logs

   One of the most powerful attacks possible in the CT ecosystem is a
   trusted log that has actively decided to be malicious.  It can carry
   out an attack in two ways:

   In the first attack, the log can present a split view of the log for
   all time.  The only way to detect this attack is to resolve each view
   of the log to the two most recent STHs and then force the log to
   present a consistency proof.  (Which it cannot.)  This attack can be
   detected by CT auditors participating in STH Pollination, as long as
   they are explicitly built to handle the situation of a log
   continuously presenting a split view.

   In the second attack, the log can sign an SCT, and refuse to ever
   include the certificate that the SCT refers to in the tree.
   (Alternately, it can include it in a branch of the tree and issue an
   STH, but then abandon that branch.)  Whenever someone requests an
   inclusion proof for that SCT (or a consistency proof from that STH),
   the log would respond with an error, and a client may simply regard
   the response as a transient error.  This attack can be detected using
   SCT Feedback, or an Auditor of Last Resort, as presented in
   Section 11.1.2.

10.2.  Dual-CA Compromise

   XXX

   [dual-ca-compromise-attack] describes an attack possible by an
   adversary who compromises two Certificate Authorites Authorities and a Log. This
   attack is difficult to defend against in the CT ecosystem, and XXX
   [dual-ca-compromise-attack] describes a few approaches to doing so.
   We note that Gossip is not intended to defend against this attack,
   but can in certain modes.

   Defending against the Dual-CA Compromise attack requires SCT
   Feedback, and explicitly requires the server to save full certificate
   chains (described in Section 8.1.3 as the 'complex' configuration.)
   After CT auditors receive the full certificate chains from servers,
   they must MAY compare the chain built by clients to the chain supplied by
   the log.  If the chains differ significantly, the auditor can SHOULD
   raise a concern.

   [ What does 'differ significantly' mean?  We should provide guidance.
   I _think_ the correct algorithm to raise a concern is:

   If  A method of determining if chains differ
   significantly is by asserting that one chain is not a subset of the
   other AND If and that the root
   certificates roots of the chains are different THEN It's suspicious.

   Justification: - different.

   [Note: Justification for this algorithm:

   Cross-Signatures could result in a different org being treated as the
   'root', but in this case, one chain would be a subset of the other.  -

   Intermediate swapping (e.g. different signature algorithms) could
   result in different chains, but the root would be the same.

   (Hitting both those cases at once would cause a false positive
   though.)

   What did I miss? ]
   though, but this would likely be rare.)

   Are there other cases that could occur?  (Left for the purposes of
   reading during pre-Last Call, to be removed by Editor)]

10.3.  Censorship/Blocking considerations

   We assume a network attacker who is able to fully control the
   client's internet connection for some period of time, including
   selectively blocking requests to certain hosts and truncating TLS
   connections based on information observed or guessed about client
   behavior.  In order to successfully detect log misbehavior, the
   gossip mechanisms must still work even in these conditions.

   There are several gossip connections that can be blocked:

   1.  Clients sending SCTs to servers in SCT Feedback

   2.  Servers sending SCTs to auditors in SCT Feedback (server push
       mechanism)

   3.  Servers making SCTs available to auditors (auditor pull
       mechanism)

   4.  Clients fetching proofs in STH Pollination

   5.  Clients sending STHs to servers in STH Pollination

   6.  Servers sending STHs to clients in STH Pollination

   7.  Clients sending SCTs to Trusted Auditors

   If a party cannot connect to another party, it can be assured that
   the connection did not succeed.  While it may not have been
   maliciously blocked, it knows the transaction did not succeed.
   Mechanisms which result in a positive affirmation from the recipient
   that the transaction succeeded allow confirmation that a connection
   was not blocked.  In this situation, the party can factor this into
   strategies suggested in Section 11.3 and in Section 11.1.2.

   The connections that allow positive affirmation are 1, 2, 4, 5, and
   7.

   More insidious is blocking the connections that do not allow positive
   confirmation: 3 and 6.  An attacker may truncate or drop a response
   from a server to a client, such that the server believes it has
   shared data with the recipient, when it has not.  However, in both
   scenatios
   scenarios (3 and 6), the server cannot distinguish the client as a
   cooperating member of the CT ecosystem or as an attacker performing a
   sybil
   Sybil attack, aiming to flush the server's data store.  Therefore the
   fact that these connections can be undetectably blocked does not
   actually alter the threat model of servers responding to these
   requests.  The choice of algorithm to release data is crucial to
   protect against these attacks; strategies are suggested in
   Section 11.3.

   Handling censorship and network blocking (which is indistinguishable
   from network error) is relegated to the implementation policy chosen
   by clients.  Suggestions for client behavior are specified in
   Section 11.1.

10.4.  Privacy considerations

   CT Gossip deals with HTTPS Clients which are trying to share
   indicators that correspond  Flushing Attacks

   A flushing attack is an attempt by an adversary to their browsing history.  The most
   sensitive relationships in flush a particular
   piece of data from a pool.  In the CT ecosystem are the relationships
   between HTTPS clients Gossip ecosystem, an attacker
   may have performed an attack and HTTPS servers.  Client-server relationships
   can be aggregated into a network graph with potentially serious
   implications for correlative de-anonymisation of clients and
   relationship-mapping or clustering left evidence of servers a compromised log
   on a client or of clients.

   There are, however, certain clients server.  They would be interested in flushing that do not require privacy
   protection.  Examples of these clients are web crawlers
   data, i.e.  tricking the target into gossiping or robots.
   But even in this case, pollinating the method by which these
   incriminating evidence with only attacker-controlled clients crawl or
   servers with the
   web hope they trick the target into deleting it.

   Flushing attacks may in fact be considered sensitive information.  In general, it
   is better to err defended against differently depending on the side of safety, and not assume a
   entity (HTTPS client is
   okay or HTTPS server) and record (STHs or SCTs with giving up its privacy.
   Certificate Chains).

10.4.1.  Privacy  STHs

   For both HTTPS clients and SCTs HTTPS servers, STHs within the validity
   window SHOULD NOT be deleted.  An SCT contains information that links attacker cannot flush an item from
   the cache if it to a particular web site.
   Because is never removed so flushing attacks are completely
   mitigated.

   The required disk space for all STHs within the client-server relationship validity window is sensitive, gossip between
   clients
   336 STHs per log that is trusted.  If 20 logs are trusted, and servers about unrelated SCTs each
   STH takes 1 Kilobytes, this is risky.  Therefore, a
   client with 6.56 Megabytes.

   Note that it is important that implementors do not calculate the
   exact size of cache expected - if an SCT for attack does occur, a given server should transmit that
   information small
   number of additional STHs will enter into the cache.  These STHs will
   be in only two channels: addition to the server associated with expected set, and will be evidence of the
   SCT itself;
   attack.

   If an HTTPS client or HTTPS server is operating in a constrained
   environment and cannot devote enough storage space to hold all STHs
   within the validity window it is recommended to use the below
   Deletion Algorithm Section 11.3.2 to make it more difficult for the
   attacker to perform a Trusted Auditor, if one exists. flushing attack.

10.4.2.  Privacy in SCT Feedback  SCTs introduce yet another mechanism for HTTPS servers to store state & Certificate Chains on an HTTPS client, and potentially track users. Servers

   An HTTPS clients which
   allow users to clear history or cookies associated with an origin
   MUST clear stored server will only accept SCTs and certificate chains associated with Certificate Chains for
   domains it is authoritative for.  Therefore the
   origin as well.

   Auditors should treat all SCTs as sensitive data.  SCTs received
   directly from an HTTPS client are especially sensitive, because storage space needed
   is bound by the
   auditor number of logs it accepts, multiplied by the number
   of domains it is a trusted authoritative for, multiplied by the client to not reveal their associations
   with servers.  Auditors MUST NOT share such SCTs in any way,
   including sending them to an external log, without first mixing them
   with multiple other SCTs learned through submissions from multiple
   other clients.  Suggestions number of
   certificates issued for mixing SCTs are presented in
   Section 11.3.

   There is a possible fingerprinting attack where a log issues those domains.

   Imagine a unique
   SCT server authoritative for targeted log client(s). 10,000 domains, and each domain
   has 3 certificate chains, and 10 SCTs.  A colluding log certificate chain is 5
   Kilobytes in size and HTTPS server
   operator could therefore be a threat to the privacy of an HTTPS
   client.  Given all SCT 1 Kilobyte.  This yields 732 Megabytes.

   This data can be large, but it is calculable.  Web properties with
   more certificates and domains are more likely to be able to handle
   the other opportunities for increased storage need, while small web properties will not seen
   an undue burden.  Therefore HTTPS servers to
   fingerprint clients - TLS session tickets, HPKP and HSTS headers,
   HTTP Cookies, etc. - this is considered acceptable.

   The fingerprinting attack described above would be mitigated by a
   requirement that logs MUST use a deterministic signature scheme when
   signing SHOULD NOT delete SCTs ([RFC-6962-BIS-09] Section 2.1.4).  A log signing using
   RSA or
   Certificate Chains.  This completely mitigates flushing attacks.

   Again, note that it is important that implementors do not required to use a deterministic signature scheme.

   Since logs are allowed to issue a new SCT for a certificate already
   present in calculate
   the log, mandating deterministic signatures does not stop
   this fingerprinting exact size of cache expected - if an attack altogether.  It does make occur, the attack
   harder new
   SCT(s) and Certificate Chain(s) will enter into the cache.  This data
   will be in addition to pull off without being detected though.

   There is another similar fingerprinting attack where the expected set, and will be evidence of the
   attack.

   If an HTTPS server
   tracks a client by using a unqiue certificate or is operating in a variation of cert
   chains.  The risk constrained environment and
   cannot devote enough storage space to hold all SCTs and Certificate
   Chains it is authoritative for this attack it is accepted on the same grounds as recommended to configure the unique SCT attack described above.  [XXX any mitigations possible
   here?]

10.4.3.  Privacy for HTTPS clients performing STH Proof Fetching

   An HTTPS client performing Proof Fetching should
   Feedback mechanism to allow only request proofs
   from a CT log certain certificates that it accepts are known
   to be valid.  These chains and SCTs from.  An HTTPS client MAY [TBD
   SHOULD?] regularly request an STH from all logs it can then be discarded without
   being stored or subsequently provided to any clients or auditors.  If
   the allowlist is willing not sufficient, the below Deletion Algorithm
   Section 11.3.2 is recommended to
   accept, even if make it has seen no SCTs from that log.

   [ TBD how regularly?  This has operational implications for log
   operators ]

   The actual mechanism by which Proof Fetching is done carries
   considerable privacy concerns.  Although out of scope more difficult for the
   document, DNS
   attacker to perform a flushing attack.

10.4.3.  SCTs & Certificate Chains on HTTPS Clients

   HTTPS clients will accumulate SCTs and Certificate Chains without
   bound.  It is expected they will choose a mechanism currently discussed.  DNS exposes data
   in plaintext over the network (including what sites particular cache size and
   delete entries when the user is
   visiting cache size meets its limit.  This does not
   mitigate flushing attacks, and what sites they have previously visited) such an may not be
   suitable for some.

10.4.4.  Privacy attack is documented in STH Pollination

   An STH linked
   [gossip-mixing].

   The below Deletion Algorithm Section 11.3.2 is recommended to an HTTPS client may indicate the following about
   that client:

   o  that the client gossips;

   o  that make it
   more difficult for the client has been using attacker to perform a flushing attack.

10.5.  Privacy considerations

   CT at least until the time that the
      timestamp and the tree size indicate;

   o Gossip deals with HTTPS clients which are trying to share
   indicators that the client is talking, possibly indirectly, correspond to their browsing history.  The most
   sensitive relationships in the log
      indicated by CT ecosystem are the tree hash;

   o  which software relationships
   between HTTPS clients and software version is being used.

   There is a possible fingerprinting attack where a log issues a unique
   STH for a targeted HTTPS client.  This is similar to the
   fingerprinting attack described in Section 10.4.2, but servers.  Client-server relationships
   can operate
   cross-origin.  If be aggregated into a log (or HTTPS Server cooperating network graph with a log)
   provides a unique STH to a client, the targeted client will be the
   only client pollinating potentially serious
   implications for correlative de-anonymization of clients and
   relationship-mapping or clustering of servers or of clients.

   There are, however, certain clients that STH cross-origin.

   It is mitigated partially because the log is limited do not require privacy
   protection.  Examples of these clients are web crawlers or robots.
   But even in this case, the number of
   STHs method by which these clients crawl the
   web may in fact be considered sensitive information.  In general, it can issue.  It must 'save' one of its STHs each MMD
   is better to
   perform err on the attack.

10.4.5.  Privacy in STH Interaction

   An HTTPS side of safety, and not assume a client may pollinate any STH within the last 14 days. is
   okay with giving up its privacy.

10.5.1.  Privacy and SCTs

   An
   HTTPS Client may also pollinate an STH for any log SCT contains information that links it knows
   about.  When a client pollinates STHs to a server, it will release
   more than one STH at a time.  It particular web site.
   Because the client-server relationship is unclear if a server may 'prime' sensitive, gossip between
   clients and servers about unrelated SCTs is risky.  Therefore, a
   client and be able to reliably detect the client at with an SCT for a later time.

   It's clear given server SHOULD NOT transmit that a single site can track a user
   information in any way they wish, but
   this attack works cross-origin and is therefore more concerning.  Two
   independent sites A and B want to collaborate to track a user cross-
   origin.  A feeds a client Carol some N specific STHs from other than the M logs
   Carol trusts, chosen following two channels: to be older and less common, but still in the
   validity window.  Carol visits B and chooses to release some of
   server associated with the
   STHs she has stored, according SCT itself; or to some policy.

   Modeling a representation for how common older STHs are Trusted Auditor, if
   one exists.

10.5.2.  Privacy in the pools
   of clients, and examining that with a given policy of how SCT Feedback

   SCTs introduce yet another mechanism for HTTPS servers to choose store state
   on an HTTPS client, and potentially track users.  HTTPS clients which of those STHs to send to B, it should be possible to calculate
   statistics about how unique Carol looks when talking
   allow users to B and how
   useful/accurate such a tracking mechanism is.

   Building such a model is likely impossible without some real world
   data, clear history or cookies associated with an origin
   MUST clear stored SCTs and requires a given implementation of a policy.  To combat
   this attack, suggestions are provided in Section 11.3 to attempt to
   minimize it, but follow-up testing certificate chains associated with real world deployment to
   improve the policy will be required.

10.4.6.  Trusted
   origin as well.

   Auditors for HTTPS Clients

   Some should treat all SCTs as sensitive data.  SCTs received
   directly from an HTTPS clients may choose to use client are especially sensitive, because the
   auditor is a trusted auditor.  This trust
   relationship exposes a large amount of information about by the client to not reveal their associations
   with servers.  Auditors MUST NOT share such SCTs in any way,
   including sending them to an external log, without first mixing them
   with multiple other SCTs learned through submissions from multiple
   other clients.  Suggestions for mixing SCTs are presented in
   Section 11.3.

   There is a possible fingerprinting attack where a log issues a unique
   SCT for targeted log client(s).  A colluding log and HTTPS server
   operator could therefore be a threat to the auditor.  In particular, it will identify the web sites that privacy of an HTTPS
   client.  Given all the client has visited other opportunities for HTTPS servers to the auditor.  Some
   fingerprint clients may already
   share - TLS session tickets, HPKP and HSTS headers,
   HTTP Cookies, etc. - this information to is considered acceptable.

   The fingerprinting attack described above would be mitigated by a third party, for example,
   requirement that logs must use a deterministic signature scheme when
   signing SCTs ([RFC-6962-BIS-09] Section 2.1.4).  A log signing using a
   server
   RSA is not required to synchronize browser history across devices in use a server-
   visible way, or when doing DNS lookups through deterministic signature scheme.

   Since logs are allowed to issue a trusted DNS
   resolver.  For clients with such new SCT for a relationship certificate already established,
   sending SCTs to a trusted auditor run by
   present in the same organization log, mandating deterministic signatures does not appear to expose any additional information to stop
   this fingerprinting attack altogether.  It does make the trusted third
   party.

   Clients who wish attack
   harder to contact a CT auditor pull off without associating their
   identities with their SCTs may wish to use being detected though.

   There is another similar fingerprinting attack where an anonymizing network
   like Tor to submit SCT Feedback to HTTPS server
   tracks a client by using a unique certificate or a variation of cert
   chains.  The risk for this attack is accepted on the auditor.  Auditors SHOULD
   accept same grounds as
   the unique SCT Feedback attack described above.

10.5.3.  Privacy for HTTPS clients performing STH Proof Fetching

   An HTTPS client performing Proof Fetching SHOULD NOT request proofs
   from a CT log that arrives over such anonymizing networks.

   Clients sending feedback to it doesn't accept SCTs from.  An HTTPS client
   SHOULD regularly request an auditor may prefer STH from all logs it is willing to reduce
   accept, even if it has seen no SCTs from that log.

   The time between two polls for new STH's SHOULD NOT be significantly
   shorter than the
   temporal granularity MMD of the history exposure to the auditor polled log divided by
   caching and delaying their SCT Feedback reports.  This is elaborated
   upon in Section 11.3.  This strategy its STH Frequency
   Count ([RFC-6962-BIS-09] section 5.1).

   The actual mechanism by which Proof Fetching is only as effective as the
   granularity done carries
   considerable privacy concerns.  Although out of scope for the timestamps embedded
   document, DNS is a mechanism currently discussed.  DNS exposes data
   in plaintext over the SCTs network (including what sites the user is
   visiting and STHs.

10.4.7.  HTTPS Clients as Auditors

   Some HTTPS Clients may choose to act as CT auditors themselves.  A
   Client taking on this role needs what sites they have previously visited) and may not be
   suitable for some.

10.5.4.  Privacy in STH Pollination

   An STH linked to consider the following:

   o an Auditing HTTPS Client potentially exposes its history to client may indicate the
      logs following about
   that client:

   o  that they query.  Querying the log through a cache or a proxy
      with many other users may avoid this exposure, but may expose
      information to client gossips;

   o  that the cache or proxy, in client has been using CT at least until the same way time that a non-
      Auditing HTTPS Client exposes information to a Trusted Auditor. the
      timestamp and the tree size indicate;

   o  an effective CT auditor needs a strategy about what  that the client is talking, possibly indirectly, to do in the
      event that it discovers misbehavior from log
      indicated by the tree hash;

   o  which software and software version is being used.

   There is a log.  Misbehavior from possible fingerprinting attack where a log involves issues a unique
   STH for a targeted HTTPS client.  This is similar to the
   fingerprinting attack described in Section 10.5.2, but can operate
   cross-origin.  If a log being unable to provide either (a) (or HTTPS server cooperating with a
      consistency proof between two valid STHs or (b) an inclusion proof
      for log)
   provides a certificate unique STH to an a client, the targeted client will be the
   only client pollinating that STH any time after cross-origin.

   It is mitigated partially because the log's MMD has
      elapsed from log is limited in the issuance number of the SCT.  The log's inability to
      provide either proof will not be externally cryptographically-
      verifiable, as
   STHs it may be indistinguishable from a network error.

11.  Policy Recommendations

   This section is intended as suggestions to implementors can issue.  It must 'save' one of its STHs each MMD to
   perform the attack.

10.5.5.  Privacy in STH Interaction

   An HTTPS
   Clients, client may pollinate any STH within the last 14 days.  An
   HTTPS Servers, and CT auditors.  It is not a requirement client may also pollinate an STH for
   technique of implementation, so long as privacy considerations
   established above are obeyed.

11.1.  Blocking Recommendations

11.1.1.  Frustrating blocking any log that it knows
   about.  When making gossip connections a client pollinates STHs to HTTPS Servers or Trusted Auditors, a server, it will release
   more than one STH at a time.  It is desirable unclear if a server may 'prime' a
   client and be able to minimize the plaintext metadata in reliably detect the connection client at a later time.

   It's clear that a single site can be used to identify the connection as track a gossip connection user any way they wish, but
   this attack works cross-origin and is therefore be of interest more concerning.  Two
   independent sites A and B want to block.  Additionally, introducing
   some randomness into collaborate to track a user cross-
   origin.  A feeds a client behavior may be important.  We assume
   that Carol some N specific STHs from the adversary is able M logs
   Carol trusts, chosen to inspect be older and less common, but still in the behavior
   validity window.  Carol visits B and chooses to release some of the HTTPS
   client and understand
   STHs she has stored, according to some policy.

   Modeling a representation for how it makes gossip connections.

   As an example, if a client, after establishing a TLS connection (and
   receiving an SCT, but not making its own HTTP request yet),
   immediately opens a second TLS connection for common older STHs are in the purpose pools
   of gossip,
   the adversary can reliably block this second connection clients, and examining that with a given policy of how to block
   gossip without affecting normal browsing.  For this reason choose
   which of those STHs to send to B, it is
   recommended should be possible to run the gossip protocols over an existing connection calculate
   statistics about how unique Carol looks when talking to the server, making use of connection multiplexing B and how
   useful/accurate such as HTTP
   Keep-Alives or SPDY.

   Truncation is also a concern.  If a client always establishes a TLS
   connection, makes a request, receives tracking mechanism is.

   Building such a response, model is likely impossible without some real world
   data, and then always
   attempts requires a gossip communication immediately following given implementation of a policy.  To combat
   this attack, suggestions are provided in Section 11.3 to attempt to
   minimize it, but follow-up testing with real world deployment to
   improve the first
   response, truncation policy will allow an attacker to block gossip reliably.

   For these reasons, we recommend that, if at all possible, clients
   SHOULD send gossip data in an already established TLS session.  This
   can be done through the use of HTTP Pipelining, SPDY, or HTTP/2.

11.1.2.  Responding required.

10.5.6.  Trusted Auditors for HTTPS Clients

   Some HTTPS clients may choose to possible blocking

   In some cirsumstances use a client may have trusted auditor.  This trust
   relationship exposes a piece large amount of data information about the client
   to the auditor.  In particular, it will identify the web sites that they
   have attempted
   the client has visited to the auditor.  Some clients may already
   share (via SCT Feedback or STH Pollination), but
   have been unable this information to do so: a third party, for example, when using a
   server to synchronize browser history across devices in a server-
   visible way, or when doing DNS lookups through a trusted DNS
   resolver.  For clients with every attempt they recieve an error.
   These situations are:

   1.  The client has an SCT and such a certificate, and attempts relationship already established,
   sending SCTs to retrieve
       an inclusion proof - but recieves an error on every attempt.

   2.  The client has an STH, and attempts a trusted auditor run by the same organization does
   not appear to resolve it expose any additional information to the trusted third
   party.

   Clients who wish to contact a newer STH
       via a consistency proof - but recieves an error on every attempt.

   3.  The client has attempted CT auditor without associating their
   identities with their SCTs may wish to share use an anonymizing network
   like Tor to submit SCT and constructed
       certificate via Feedback to the auditor.  Auditors SHOULD
   accept SCT Feedback - but recieves an error on every
       attempt.

   4.  The client has attempted that arrives over such anonymizing networks.

   Clients sending feedback to share an STH via STH Pollination -
       but recieves an error on every attempt.

   5.  The client has attempted auditor may prefer to share a specific piece of data with a
       Trusted Auditor - but recieves an error on every attempt.

   In reduce the case
   temporal granularity of 1 or 2, it is conceivable that the reason for history exposure to the
   errors auditor by
   caching and delaying their SCT Feedback reports.  This is that the log acted improperly, either through malicious
   actions or compromise.  A proof may not be able to be fetched because
   it does not exist (and only errors or timeouts occur).  One such
   situation may arise because of an actively malicious log, as
   presented elaborated
   upon in Section 10.1. 11.3.  This data strategy is especially important to
   share with only as effective as the broader internet
   granularity of the timestamps embedded in the SCTs and STHs.

10.5.7.  HTTPS Clients as Auditors

   Some HTTPS clients may choose to detect act as CT auditors themselves.  A
   Client taking on this situation.

   If an SCT has attempted to be resolved role needs to consider the following:

   o  an STH via an inclusion
   proof multiple times, and each time has failed, a Auditing HTTPS client SHOULD make
   every effort potentially exposes its history to send this SCT via SCT Feedback.  However the client
   MUST NOT share
      logs that they query.  Querying the data log through a cache or a proxy
      with any many other third party (excepting users may avoid this exposure, but may expose
      information to the cache or proxy, in the same way that a non-
      Auditing HTTPS Client exposes information to a Trusted Auditor should one exist).

   If Auditor.

   o  an STH has attempted to be resolved effective CT auditor needs a strategy about what to do in the
      event that it discovers misbehavior from a newer STH via log.  Misbehavior from
      a log involves the log being unable to provide either (a) a
      consistency proof multiple times, and each between two valid STHs or (b) an inclusion proof
      for a certificate to an STH any time after the log's MMD has failed, a client
   MAY share
      elapsed from the STH with an "Auditor issuance of Last Resort" even if the STH in
   question is no longer within the validity window.  This auditor SCT.  The log's inability to
      provide either proof will not be externally cryptographically-
      verifiable, as it may be pre-configured in the client, but the client SHOULD permit indistinguishable from a user
   to disable the functionality or change whom data network error.

11.  Policy Recommendations

   This section is sent to.  The
   Auditor intended as suggestions to implementors of Last Resort itself represents HTTPS
   Clients, HTTPS servers, and CT auditors.  It is not a point requirement for
   technique of failure, implementation, so if
   implemented, it should connect using public key pinning and not
   considered an item delivered until long as privacy considerations
   established above are obeyed.

11.1.  Blocking Recommendations

11.1.1.  Frustrating blocking

   When making gossip connections to HTTPS servers or Trusted Auditors,
   it recieves a confirmation.

   In is desirable to minimize the cases 3, 4, and 5, we assume plaintext metadata in the connection
   that can be used to identify the webserver(s) or trusted
   auditor in question is either experiencing an operational failure, or
   being attacked.  In both cases, connection as a gossip connection
   and therefore be of interest to block.  Additionally, introducing
   some randomness into client SHOULD retain behavior may be important.  We assume
   that the data for
   later submission (subject adversary is able to Private Browsing or other history-
   clearing actions taken by inspect the user.)  This is elaborated upon more in
   Section 11.3.

11.2.  Proof Fetching Recommendations

   Proof fetching (both inclusion proofs behavior of the HTTPS
   client and consistency proofs) should
   be performed at random time intervals.  If proof fetching occured all
   at once, in understand how it makes gossip connections.

   As an example, if a flurry of activity, client, after establishing a log would know that SCTs or STHs
   recieved around TLS connection (and
   receiving an SCT, but not making its own HTTP request yet),
   immediately opens a second TLS connection for the same time are more likely purpose of gossip,
   the adversary can reliably block this second connection to come from a
   particular client.  While proof fetching block
   gossip without affecting normal browsing.  For this reason it is required
   recommended to be done in a
   manner that attempts run the gossip protocols over an existing connection
   to be anonymous from the perspective server, making use of connection multiplexing such as HTTP
   Keep-Alive or SPDY.

   Truncation is also a concern.  If a client always establishes a TLS
   connection, makes a request, receives a response, and then always
   attempts a gossip communication immediately following the log, first
   response, truncation will allow an attacker to block gossip reliably.

   For these reasons, we recommend that, if at all possible, clients
   SHOULD send gossip data in an already established TLS session.  This
   can be done through the correlation use of activity HTTP Pipelining, SPDY, or HTTP/2.

11.1.2.  Responding to possible blocking

   In some circumstances a single client would still reveal
   patterns may have a piece of user behavior we wish data that they
   have attempted to keep confidential.  These
   patterns could be recognizable as a single user, share (via SCT Feedback or could reveal what
   sites are commonly visited together in the aggregate.

   [ TBD: What other recommendations do we want STH Pollination), but
   have been unable to make here?  We can
   talk more about the inadequecies of DNS... do so: with every attempt they receive an error.
   These situations are:

   1.  The first paragraph is 80%
   identical between here and above ]

11.3.  Record Distribution Recommendations

   In several components of the CT Gossip ecosystem, the recommendation
   is made that data from multiple sources be ingested, mixed, stored
   for client has an indeterminate period of time, provided (multiple times) to SCT and a
   third party, certificate, and eventually deleted. attempts to retrieve
       an inclusion proof - but receives an error on every attempt.

   2.  The instances of these
   recommendations in this draft are:

   o  When a client receives SCTs during SCT Feedback, it should store
      the SCTs has an STH, and Certificate Chain for some amount of time, provide
      some of them back attempts to resolve it to the server at some point, and may eventually
      remove them from its store

   o  When a newer STH
       via a consistency proof - but receives an error on every attempt.

   3.  The client has attempted to share an SCT and constructed
       certificate via SCT Feedback - but receives STHs during an error on every
       attempt.

   4.  The client has attempted to share an STH Pollination, it should
      store them for some amount via STH Pollination -
       but receives an error on every attempt.

   5.  The client has attempted to share a specific piece of time, mix them data with other STHs,
      release some a
       Trusted Auditor - but receives an error on every attempt.

   In the case of them them 1 or 2, it is conceivable that the reason for the
   errors is that the log acted improperly, either through malicious
   actions or compromise.  A proof may not be able to various servers at some point,
      resolve some be fetched because
   it does not exist (and only errors or timeouts occur).  One such
   situation may arise because of them an actively malicious log, as
   presented in Section 10.1.  This data is especially important to new STHs, and eventually remove them from
      its store

   o  When a server receives SCTs during
   share with the broader internet to detect this situation.

   If an SCT Feedback, it should store
      them for some period of time, provide them has attempted to auditors some number
      of be resolved to an STH via an inclusion
   proof multiple times, and may eventually remove them

   o  When each time has failed, this SCT might very
   well be a server receives STHs during STH Pollination, it should
      store them for some period compromising proof of time, mix them an attack.  However the client MUST
   NOT share the data with any other STHs,
      provide some of them to connecting clients, may resolve them to
      new STHs via Proof Fetching, and eventually remove them from its
      store

   o  When third party (excepting a Trusted
   Auditor receives SCTs or historical STHs from
      clients, it should store them for some period of time, mix them
      with SCTs received from other clients, and act upon them at some
      period of time

   Each of these instances have specific requirements for user privacy,
   and each have options that may not be invoked.  As one example, exist).

   If an
   HTTPS client should not mix SCTs from server A with SCTs from server
   B and release server B's SCTs to Server A.  As another example, an
   HTTPS server may choose STH has attempted to resolve STHs be resolved to a single more current newer STH via a
   consistency proof fetching, but it is under no obligation to do so.

   These requirements should be met, but the general problem of
   aggregating multiple pieces of data, choosing when and how many to
   release, times, and when to remove them each time has failed, a client
   MAY share the STH with an "Auditor of Last Resort" even if the STH in
   question is shared. no longer within the validity window.  This problem has
   previously been considered auditor may
   be pre-configured in the case of Mix Networks and Remailers,
   including papers such as "From a Trickle to client, but the client SHOULD permit a Flood: Active Attacks
   on Several Mix Types", [Y], and [Z].

   There are several concerns user
   to be addressed in this area, outlined
   below.

11.3.1.  Mixing Algorithm

   When SCTs disable the functionality or STHs are recorded by change whom data is sent to.  The
   Auditor of Last Resort itself represents a participant in CT Gossip point of failure and
   later used,
   privacy concerns, so if implemented, it is important SHOULD connect using public
   key pinning and not consider an item delivered until it receives a
   confirmation.

   In the cases 3, 4, and 5, we assume that they are selected from the datastore webserver(s) or trusted
   auditor in a non-deterministic fashion.

   This question is most important either experiencing an operational failure, or
   being attacked.  In both cases, a client SHOULD retain the data for servers, as they can be queried for SCTs
   and STHs anonymously.  If the server used a predictable ordering
   algorithm, an attacker could exploit the predictability
   later submission (subject to learn
   information about a client.  One such method would be Private Browsing or other history-
   clearing actions taken by observing
   the (encrypted) traffic to a server.  When a client of interest
   connects, the attacker makes a note.  They observe user.)  This is elaborated upon more clients
   connecting, in
   Section 11.3.

11.2.  Proof Fetching Recommendations

   Proof fetching (both inclusion proofs and predicts at what point the client-of-interest's data
   will consistency proofs) SHOULD
   be disclosed, and ensures that they query the server performed at that
   point.

   Although most important for servers, random ordering is still
   strongly recommended for clients and Trusted Auditors.  The above
   attack can still occur for these entities, although the circumstances
   are less straightforward.  For clients, an attacker could observe
   their behavior, note when they recieve an STH from time intervals.  If proof fetching occurred
   all at once, in a server, and use
   javascript to cause flurry of activity, a network connection at log would know that SCTs or
   STHs received around the correct same time are more likely to force come from a client
   particular client.  While proof fetching is required to disclose the specific STH.  Trusted Auditors are stewards
   of sensitive client data.  If an attacker had the ability be done in a
   manner that attempts to observe be anonymous from the activities perspective of a Trusted Auditor (perhaps by being a log, or
   another auditor), they could perform the same attack - noting log,
   the
   disclosure correlation of data from activity to a single client to the Trusted Auditor, and then
   correlating a later disclosure from the Trusted Auditor as coming
   from that client.

   Random ordering can be ensured by several mechanisms.  A datastore
   can would still reveal
   patterns of user behavior we wish to keep confidential.  These
   patterns could be shuffled, using a secure shuffling algorithm such recognizable as Fisher-
   Yates.  Alternately, a series single user, or could reveal what
   sites are commonly visited together in the aggregate.

11.3.  Record Distribution Recommendations

   In several components of random indexes into the data store
   can be selected (if a collision occurs, a new index is selected.)  A
   cryptographyically secure random number generator must be used in
   either case.  If shuffling is performed, CT Gossip ecosystem, the datastore must be marked
   'dirty' upon item insertion, and at least one shuffle operation
   occurs on a dirty datastore before data recommendation
   is retrieved made that data from it multiple sources be ingested, mixed, stored
   for use.

11.3.2.  Flushing Attacks

   A flushing attack is an attempt by an adversary indeterminate period of time, provided (multiple times) to flush a particular
   piece
   third party, and eventually deleted.  The instances of data from these
   recommendations in this draft are:

   o  When a pool.  In client receives SCTs during SCT Feedback, it should store
      the CT Gossip ecosystem, an attacker
   may have performed an attack SCTs and left evidence Certificate Chain for some amount of a compromised log
   on time, provide
      some of them back to the server at some point, and may eventually
      remove them from its store

   o  When a client or server.  They would be interested in flushing that
   data, i.e.  tricking the target into gossiping or pollinating the
   incriminating evidence with only attacker-controlled clients or
   servers receives STHs during STH Pollination, it should
      store them for some amount of time, mix them with the hope they trick the target into deleting it.

   Servers are most vulnerable to flushing attacks, as they other STHs,
      release
   records some of them them to anonymous connections.  An attacker can perform a Sybil
   attack - connecting various servers at some point,
      resolve some of them to the new STHs, and eventually remove them from
      its store

   o  When a server hundreds or thousands receives SCTs during SCT Feedback, it should store
      them for some period of times in
   an attempt time, provide them to trigger repeated release auditors some number
      of a record, times, and then
   deletion.  For this reason, servers must be especially aggressive
   about retaining data for may eventually remove them

   o  When a longer server receives STHs during STH Pollination, it should
      store them for some period of time.

   Clients are vulnerable to flushing attacks targetting time, mix them with other STHs, as these
   can be given to any cooperating server and an attacker can generally
   induce connections
      provide some of them to random servers using javascript.  It would be
   more difficult connecting clients, may resolve them to perform a flushing attack against SCTs, as the
   target server must be authenticated (and an attacker impersonating an
   authentic server presents
      new STHs via Proof Fetching, and eventually remove them from its
      store

   o  When a recursive problem for the attacker).
   Nonetheless, flushing SCTs should not be ruled impossible.  A Trusted Auditor may also be vulnerable to flushing attacks if receives SCTs or historical STHs from
      clients, it does not
   perform auditing operations itself.

   Flushing attacks are defended against using non-determinism and dummy
   messages.  The goal is to ensure that an adversary does not know should store them for
   certain if the data in question has been released or not, some period of time, mix them
      with SCTs received from other clients, and if it
   has been deleted or not.

   [ TBD: At present, we do not act upon them at some
      period of time

   Each of these instances have any support specific requirements for dummy messages.  Do
   we want to define a dummy message user privacy,
   and each have options that clients may not be invoked.  As one example, an
   HTTPS client should not mix SCTs from server A with SCTs from server
   B and servers alike know release server B's SCTs to ignore?  Will HTTP Compression leak Server A.  As another example, an
   HTTPS server may choose to resolve STHs to a single more current STH
   via proof fetching, but it is under no obligation to do so.

   These requirements should be met, but the presence general problem of >1 dummy
   messages?
   Is it sufficient
   aggregating multiple pieces of data, choosing when and how many to define a dummy message as _anything_ with an
   invalid siganture?
   release, and when to remove them is shared.  This would negatively impact SCT Feedback servers
   that log all things just problem has
   previously been considered in the case they're interesting. ]

11.3.3.  The Deletion Algorithm

   No entity in CT Gossip is required of Mix Networks and Remailers,
   including papers such as [trickle].

   There are several concerns to delete be addressed in this area, outlined
   below.

11.3.1.  Mixing Algorithm

   When SCTs or STHs at any
   time, except to respect user's wishes such as private browsing mode
   or clearing history.  However, requiring infinite storage space is
   not are recorded by a desirable characteristic participant in a protocol, so deletion is
   expected.

   While deletion of SCTs CT Gossip and STHs will occur, proof fetching can ensure
   that any misbehavior from a log will still be detected, even after
   the direct evidence from the attack
   later used, it is deleted.  Proof fetching
   ensures important that if a log presents a split view for a client, they must
   maintain that split view in perpetuity.  An inclusion proof are selected from an
   SCT to an STH does not erase the evidence - the new STH is evidence
   itself.  A consistency proof from that STH to datastore
   in a new one likewise -
   the new STH non-deterministic fashion.

   This is every bit as incriminating most important for servers, as the first.  (Client
   behavior in the situation where an SCT or STH cannot they can be resolved is
   suggested in Section 11.1.2.)  Because of this property, we recommend
   that if queried for SCTs
   and STHs anonymously.  If the server used a client is performing proof fetching, that they make every
   effort to not delete predictable ordering
   algorithm, an SCT or STH until it has been successfully
   resolved to a new STH via a proof.

   When it is time to delete a record, it is important that attacker could exploit the decision predictability to do so not learn
   information about a client.  One such method would be done deterministicly.  Introducing non-determinism in by observing
   the decision is absolutely necessary (encrypted) traffic to prevent an adversary from
   knowing with certainty that the record has been successfully flushed
   from a target.  Therefore, we speak server.  When a client of making interest
   connects, the attacker makes a record 'eligible for
   deletion' note.  They observe more clients
   connecting, and then being processed by predicts at what point the 'deletion algorithm'.
   Making a record eligible for deletion simply means that it will have client-of-interest's data
   will be disclosed, and ensures that they query the deletion algorithm run. server at that
   point.

   Although most important for servers, random ordering is still
   strongly recommended for clients and Trusted Auditors.  The deletion algorithm will use above
   attack can still occur for these entities, although the circumstances
   are less straightforward.  For clients, an attacker could observe
   their behavior, note when they receive an STH from a
   probability based system server, and use
   javascript to cause a secure random number generator network connection at the correct time to
   determine if force
   a client to disclose the record will be deleted.

   Although specific STH.  Trusted Auditors are stewards
   of sensitive client data.  If an attacker had the deletion algorithm is specifically designed ability to be non-
   deterministic, if observe
   the record has been resolved via proof activities of a Trusted Auditor (perhaps by being a log, or
   another auditor), they could perform the same attack - noting the
   disclosure of data from a client to the Trusted Auditor, and then
   correlating a new STH later disclosure from the record may be safely deleted, Trusted Auditor as long coming
   from that client.

   Random ordering can be ensured by several mechanisms.  A datastore
   can be shuffled, using a secure shuffling algorithm such as Fisher-
   Yates.  Alternately, a series of random indexes into the data store
   can be selected (if a collision occurs, a new STH index is retained.

   The actual deletion algorithm may selected.)  A
   cryptographically secure random number generator must be [STATISTICS HERE].  [ Something
   as simple as 'Pick an integer securely between 1 and 10. used in
   either case.  If it's
   greater than 7, delete shuffling is performed, the record.'  Or something more complicated. ]

   [ TODO Enumerating the problems of different types of mixes vs
   Cottrell Mix ]

11.3.3.1.  Experimental Algorithms

   More complex algorithms could datastore must be inserted marked
   'dirty' upon item insertion, and at any step.  Three
   examples are illustrated:

   SCTs are not eligible least one shuffle operation
   occurs on a dirty datastore before data is retrieved from it for use.

11.3.2.  The Deletion Algorithm

   No entity in CT Gossip is required to be submitted delete records at any time,
   except to an Auditor of Last Resort.
   Therefore, respect user's wishes such as private browsing mode or
   clearing history.  However, it is more important likely that they be resolved to STHs over time the
   accumulated storage will grow in size and
   reported via SCT feedback.  If fetching an inclusion need to be pruned.

   While deletion of data will occur, proof regularly
   fails for a particular SCT, one fetching can require it ensure that any
   misbehavior from a log will still be reported more times
   than normal via SCT Feedback before becoming eligible for deletion.

   Before an item detected, even after the direct
   evidence from the attack is made eligible deleted.  Proof fetching ensures that if
   a log presents a split view for deletion by a client, they must maintain that
   split view in perpetuity.  An inclusion proof from an SCT to an STH
   does not erase the client
   could aim evidence - the new STH is evidence itself.  A
   consistency proof from that STH to make it difficult for a point-in-time attacker to flush new one likewise - the pool by not making an item eligible for deletion until new STH
   is every bit as incriminating as the client
   has moved networks (as seen by either first.  (Client behavior in the local IP address,
   situation where an SCT or a
   report-back providing the client with its observed public IP
   address).  The HTTPS client could also require reporting over a
   timespan, e.g. it must be reported at least N time, M weeks apart.
   This strategy could STH cannot be employed always, or only when the client has
   disabled proof fetching and the Auditor resolved is suggested in
   Section 11.1.2.)  Because of Last Resort, as those two
   mechanisms (when used together) will enable this property, we recommend that if a
   client to report most
   attacks.

11.3.3.2.  Concrete Recommendations

   The recommendations for behavior are: - If proof fetching is enabled,
   do performing proof fetching, that they make every effort to
   not delete an SCT data until it has had been successfully resolved to a proof resolving new STH
   via a proof.

   When it is time to an STH.
   - If proof fetching continually fails delete a record, it can be done in a way that
   makes it more difficult for an SCT, do not make a successful flushing attack to to be
   performed.

   1.  When the
   item eligible for deletion of record cache has reached a certain size that is yet
       under the SCT until it limit, aggressively perform proof fetching.  This
       should resolve records to a small set of STHs that can be
       retained.  Once a proof has been released,
   multiple times, via SCT Feedback.  - fetched, the record is safer to
       delete.

   2.  If proof fetching continually
   fails for an STH, do not make the item eligible for deletion until it has been queued for release to an Auditor of Last Resort.  - Do not
   dequeue entries to an Auditor of Last Resort if reporting fails.
   Instead keep the items queued until they failed, or is disabled, begin by deleting
       SCTs and Certificate Chains that have been successfully sent.
   - Use reported.
       Deletion from this set of SCTs should be done at random.  For a probability based system, with
       client, a cryptographically secure
   random number generator, submission is not counted as being reported unless it
       is sent over a connection using a different SCT, so the attacker
       is faced with a recursive problem.  (For a server, this step does
       not apply.)

   3.  Attempt to determine if save any submissions that have failed proof fetching
       repeatedly, as these are the most likely to be indicative of an item should
       attack.

   4.  Finally, if the above steps have been followed and have not
       succeeded in reducing the size sufficiently, records may be deleted.
       deleted at random.

   Note that if proof fetching is disabled (which is expected although
   not required for servers) - Select items from the datastores by selecting algorithm collapses down to 'delete
   at random'.

   The decision to delete records at random indexes into is intentional.  Introducing
   non-determinism in the decision is absolutely necessary to make it
   more difficult for an adversary to know with certainty or high
   confidence that the datastore.  Use record has been successfully flushed from a cryptographically secure random number
   generator.

   [ TBD: More? ]
   target.

11.4.  Concrete Recommendations

   We present the following pseudocode as a concrete outline of our
   suggestion.

11.3.3.2.1.
   policy recommendations.

   Both suggestions presented are applicable to both clients and
   servers.  Servers may not perform proof fetching, in which case large
   portions of the pseudocode are not applicable.  But it should work in
   either case.

11.4.1.  STH Data Structures Pollination

   The STH class contains data pertaining specifically to the STH
   itself.

   class STH
   {
     uint32
     uint16   proof_attempts
     uint32
     uint16   proof_failure_count
     uint32   num_reports_to_thirdparty
     datetime timestamp
     byte[]   data
   }

   The broader STH store itself would contain all the STHs known by an
   entity participating in STH Pollination (either client or server).
   This simplistic view of the class does not take into account the
   complicated locking that would likely be required for a data
   structure being accessed by multiple threads.  One thing to note
   about data
   structure being accessed by multiple threads.  Something to note
   about this pseudocode is that it does not remove STHs once they have
   been resolved to a newer STH.  Doing so might make older STHs within
   the validity window rarer and thus enable tracking.

   class STHStore
   {
     STH[] sth_list

     //  This function is run after receiving a set of STHs from
     //  a third party in response to a pollination submission
     def insert(STH[] new_sths) {
       foreach(new in new_sths) {
         if(this.sth_list.contains(new))
           continue
         this.sth_list.insert(new)
       }
     }

     //  This function is called to delete the given STH
     //  from the data store
     def delete_now(STH s) {
       this.sth_list.remove(s)
     }

     //  When it is time to perform STH Pollination, the HTTPS client
     //  calls this function to get a selection of STHs to send as
     //  feedback
     def get_pollination_selection() {
       if(len(this.sth_list) < MAX_STH_TO_GOSSIP)
         return this.sth_list
       else {
         indexes = set()
         modulus = len(this.sth_list)
         while(len(indexes) < MAX_STH_TO_GOSSIP) {
           r = randomInt() % modulus
           // Ignore STHs that are past the validity window but not
           // yet removed.
           if(r not in indexes
              && now() - this.sth_list[i].timestamp < TWO_WEEKS)
             indexes.insert(r)
         }

         return_selection = []
         foreach(i in indexes) {
           return_selection.insert(this.sth_list[i])
         }
         return return_selection
       }
     }
   }
   We also suggest a function that will be called periodically in the
   background, iterating through the STH store, performing a cleaning
   operation and queuing consistency proofs.  This function can live as
   a member functions of the STHStore class.

//Just a suggestion:
#define MIN_PROOF_FAILURES_CONSIDERED_SUSPICIOUS 3

def clean_list() {
  foreach(sth in this.sth_list) {

    if(now() - sth.timestamp > TWO_WEEKS) {
      //STH is too old, we must remove it
      if(proof_fetching_enabled
         && auditor_of_last_resort_enabled
         && sth.proof_failure_count
            > MIN_PROOF_FAILURES_CONSIDERED_SUSPICIOUS) {
        queue_for_auditor_of_last_resort(sth,
                                        auditor_of_last_resort_callback)
      } else {
        delete_now(sth)
      }
    }

    else if(proof_fetching_enabled
            && now() - sth.timestamp > LOG_MMD
            && sth.proof_attempts != UINT16_MAX
            // Only fetch a proof is we have never received a proof
            // before. (This also avoids submitting something
            // already in the queue.)
            && sth.proof_attempts == sth.proof_failure_count) {
      sth.proof_attempts++
      queue_consistency_proof(sth, consistency_proof_callback)
    }
  }
}

   These functions also exist in the STHStore class.

//  This function is called after successfully pollinating STHs
//  to a third party. It is passed the STHs sent to the third
//  party, which is the output of get_gossip_selection(), as well
//  as the STHs received in the response.
def successful_thirdparty_submission_callback(STH[] submitted_sth_list,
                                              STH[] new_sths)
{
  foreach(sth in submitted_sth_list) {
    sth.num_reports_to_thirdparty++
  }

  this.insert(new_sths);
}

//  Attempt auditor of last resort submissions until it succeeds
def auditor_of_last_resort_callback(original_sth, error) {
  if(!error) {
    delete_now(original_sth)
  }
}

def consistency_proof_callback(consistency_proof, original_sth, error) {
  if(!error) {
    insert(consistency_proof.current_sth)
  } else {
    original_sth.proof_failure_count++
  }
}

11.4.2.  SCT Feedback

   The SCT class contains data pertaining specifically to an SCT itself.

   class SCT
   {
     uint16 proof_failure_count
     bool   has_been_resolved_to_sth
     bool   proof_outstanding
     byte[] data
   }

   The SCT bundle will contain the trusted certificate chain the HTTPS
   client built (chaining to a trusted root certificate.)  It also
   contains the list of associated SCTs, the exact domain it is
   applicable to, and metadata pertaining to how often it has been
   reported to the third party.

   class SCTBundle
   {
     X509[] certificate_chain
     SCT[]  sct_list
     string domain
     uint32 num_reports_to_thirdparty

     def equals(sct_bundle) {
       if(sct_bundle.domain != this.domain)
         return false
       if(sct_bundle.certificate_chain != this.certificate_chain)
         return false
       if(sct_bundle.sct_list != this.sct_list)
         return false

       return true
     }
     def approx_equals(sct_bundle) {
       if(sct_bundle.domain != this.domain)
         return false
       if(sct_bundle.certificate_chain != this.certificate_chain)
         return false

       return true
     }

     def insert_scts(sct[] sct_list) {
       this.sct_list.union(sct_list)
       this.num_reports_to_thirdparty = 0
     }

     def has_been_fully_resolved_to_sths() {
       foreach(s in this.sct_list) {
         if(!s.has_been_resolved_to_sth && !s.proof_outstanding)
           return false
       }
       return true
     }

     def max_proof_failures() {
       uint max = 0
       foreach(sct in this.sct_list) {
         if(sct.proof_failure_count > max)
           max = sct.proof_failure_count
       }
       return max
     }
   }
   For each domain, we store a SCTDomainEntry that holds the SCTBundles
   seen for that domain, as well as encapsulating some logic relating to
   SCT Feedback for that particular domain.  In particular, this data
   structure also contains the logic that handles domains not supporting
   SCT Feedback.  Its behavior is:

   1.  When a user visits a domain, SCT Feedback is attempted for it.
       If it fails, it will retry after a month (configurable).  If it
       succeeds, excellent.  SCT Feedback data is still collected and
       stored even if SCT Feedback failed.

   2.  After 3 month-long waits between failures, the domain will be
       marked as failing long-term.  No SCT Feedback data will be stored
       beyond meta-data, but SCT Feedback will still be attempted after
       month-long waits

   3.  If at any point in time, SCT Feedback succeeds, all failure
       counters are reset

   4.  If a domain succeeds, but then begins failing, it must fail more
       than 90% of the time (configurable) and then the process begins
       at (2).

   If a domain is visited infrequently (say, once every 7 months) then
   it will be evicted from the cache and start all over again (according
   to the suggestion values in the below pseudocode).

   [ Note: To be certain the logic is correct I give the following test
   cases which illustrate the intended behavior.  Hopefully the code
   matches!

 Succeed 1 Time        num_submissions_attempted=1    num_submissions_succeeded=1  num_feedback_loop_failures=0
 Fail 10 Times         num_submissions_attempted=11   num_submissions_succeeded=1  num_feedback_loop_failures=0
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=12   num_submissions_succeeded=1  num_feedback_loop_failures=1
 ... wait a month ...
 Succeed 1 month later num_submissions_attempted=13   num_submissions_succeeded=2  num_feedback_loop_failures=0(r) indicates (Reset)
 -> Feedback is attempted regularly.

 Succeed 1 Time        num_submissions_attempted=1    num_submissions_succeeded=1  num_feedback_loop_failures=0
 Fail 10 Times         num_submissions_attempted=11   num_submissions_succeeded=1  num_feedback_loop_failures=0
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=12   num_submissions_succeeded=1  num_feedback_loop_failures=1
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=13   num_submissions_succeeded=1  num_feedback_loop_failures=2
 ... wait a month ...
 Succeed 1 month later num_submissions_attempted=14   num_submissions_succeeded=2  num_feedback_loop_failures=0(r)
 -> Feedback is attempted regularly.

 Succeed 1 Time        num_submissions_attempted=1    num_submissions_succeeded=1  num_feedback_loop_failures=0
 Fail 10 Times         num_submissions_attempted=11   num_submissions_succeeded=1  num_feedback_loop_failures=0
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=12   num_submissions_succeeded=1  num_feedback_loop_failures=1
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=13   num_submissions_succeeded=1  num_feedback_loop_failures=2
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=14   num_submissions_succeeded=2  num_feedback_loop_failures=3
 ... clear_old_data() is run every hour ...
                       num_submissions_attempted=0    num_submissions_succeeded=0  num_feedback_loop_failures=3
                       sct_feedback_failing_longterm=True
 Fail 1 month later    num_submissions_attempted=1    num_submissions_succeeded=0  num_feedback_loop_failures=4
                       sct_feedback_failing_longterm=True
 ... clear_old_data() is run every hour ...
                       num_submissions_attempted=0(r) num_submissions_succeeded=0  num_feedback_loop_failures=3
                       sct_feedback_failing_longterm=True
 Succeed 1 month later num_submissions_attempted=2   num_submissions_succeeded=1  num_feedback_loop_failures=0(r)
                       sct_feedback_failing_longterm=False
 -> Feedback is attempted regularly.

 Note above that the second run of clear_old_data() will reset num_submissions_attempted from 1 to 0.  This is
 CRITICAL. Otherwise, we would have the below bug (where after 10 months of failures, a success would not hit
 the required ratio to keep going)

 //The below represents a bug.
 Succeed 1 Time        num_submissions_attempted=1   num_submissions_succeeded=1  num_feedback_loop_failures=0
 Fail 10 Times         num_submissions_attempted=11  num_submissions_succeeded=1  num_feedback_loop_failures=0
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=12  num_submissions_succeeded=1  num_feedback_loop_failures=1
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=13  num_submissions_succeeded=1  num_feedback_loop_failures=2
 ... wait a month ...
 Fail 1 month later    num_submissions_attempted=14  num_submissions_succeeded=2  num_feedback_loop_failures=3
 ... clear_old_data() is run every hour ...
                       num_submissions_attempted=0   num_submissions_succeeded=0  num_feedback_loop_failures=3
                       sct_feedback_failing_longterm=True
 Fail 1 month later    num_submissions_attempted=1   num_submissions_succeeded=0  num_feedback_loop_failures=4
                       sct_feedback_failing_longterm=True
 Fail 9 times for 9 months
                       num_submissions_attempted=10  num_submissions_succeeded=0  num_feedback_loop_failures=13
                       sct_feedback_failing_longterm=True
 Succeed 1 month later num_submissions_attempted=11  num_submissions_succeeded=1  num_feedback_loop_failures=0(r)
                       sct_feedback_failing_longterm=False
 -> Feedback is NOT attempted regularly. \]

//Suggestions:
//  After concluding a domain doesn't support feedback, we try again
//  after WAIT_BETWEEN_SCT_FEEDBACK_ATTEMPTS amount of time to see if
//  they added support
#define WAIT_BETWEEN_SCT_FEEDBACK_ATTEMPTS                     1 month

//  If we've waited MIN_SCT_FEEDBACK_ATTEMPTS_BEFORE_OMITTING_STORAGE
//  multiplied by WAIT_BETWEEN_SCT_FEEDBACK_ATTEMPTS amount of time, we
//  still attempt SCT Feedback, but no longer bother storing any data
//  until the domain supports SCT Feedback
#define MIN_SCT_FEEDBACK_ATTEMPTS_BEFORE_OMITTING_STORAGE      3

//  If this percentage of SCT Feedback attempts previously succeeded,
//  we consider the domain as supporting feedback and is just having
//  transient errors
#define MIN_RATIO_FOR_SCT_FEEDBACK_TO_BE_WORKING               .10

class SCTDomainEntry
{
  //  This is the primary key of the object, the exact domain name it
  //  is valid for
  string   domain

  //  This is the last time the domain was contacted. For client
  //  operations it is updated whenever the client makes any request
  //  (not just feedback) to the domain. For server operations, it is
  //  updated whenever any client contacts the domain. Responsibility
  //  for updating lies OUTSIDE of the class
  public datetime last_contact_for_domain

  //  This is the last time SCT Feedback was attempted for the domain.
  //  It is updated whenever feedback is attempted - responsibility for
  //  updating lies OUTSIDE of the class
  //  This is not used when this algorithm runs on servers
  public datetime last_sct_feedback_attempt

  //  This is the number of times we have waited an
  //  WAIT_BETWEEN_SCT_FEEDBACK_ATTEMPTS amount of time, and still failed
  //  e.g. 10 months of failures
  //  This is not used when this algorithm runs on servers
  private uint16   num_feedback_loop_failures

  //  This is whether or not SCT Feedback has failed enough times that we
  //  should not bother storing data for it anymore. It is a small function
  //  used for illustrative purposes
  //  This is not used when this algorithm runs on servers
  private bool     sct_feedback_failing_longterm()
    { num_feedback_loop_failures >= MIN_SCT_FEEDBACK_ATTEMPTS_BEFORE_OMITTING_STORAGE }

  //  This is the number of SCT Feedback submissions attempted.

  //  Responsibility for incrementing lies OUTSIDE of the class
  //  (And watch for integer overflows)
  //  This is not used when this algorithm runs on servers
  public uint16    num_submissions_attempted

  //  This is the number of successful SCT Feedback submissions. This
  //  variable is updated by the class.
  //  This is not used when this algorithm runs on servers
  private uint16   num_submissions_succeeded

  //  This contains all the bundles of SCT data we have observed for
  //  this domain
  SCTBundle[] observed_records

  //  This function can be called to determine if we should attempt
  //  SCT Feedback for this domain.
  def should_attempt_feedback() {
    // Servers always perform feedback!
    if(operator_is_server)
      return true

    // If we have not tried in a month, try again
    if(now() - last_sct_feedback_attempt > WAIT_BETWEEN_SCT_FEEDBACK_ATTEMPTS)
      return true

    // If we have tried recently, and it seems to be working, go for it!
    if((num_submissions_succeeded / num_submissions_attempted) >
       MIN_RATIO_FOR_SCT_FEEDBACK_TO_BE_WORKING)
      return true

    // Otherwise don't try
    return false
  }

  //  For Clients, this function is called after a successful
  //  connection to an HTTPS server, with a single SCTBundle
  //  constructed from that connection's certificate chain and SCTs.
  //  For Servers, this is called after receiving SCT Feedback with
  //  all the bundles sent in the feedback.
  def insert(SCTBundle[] bundles) {
    // Do not store data for long-failing domains
    if(sct_feedback_failing_longterm()) {
      return
    }

    foreach(b in bundles) {
      if(operator_is_server) {
        if(!passes_validity_checks(b))
          return
      }

      bool have_inserted = false
      foreach(e in this.observed_records) {
        if(e.equals(b))
          return
        else if(e.approx_equals(b)) {
          have_inserted = true
          e.insert_scts(b.sct_list)
        }
      }
      if(!have_inserted)
        this.observed_records.insert(b)
    }
    SCTStoreManager.update_cache_percentage()
  }

  //  When it is time to perform SCT Feedback, the HTTPS client
  //  calls this function to get a selection of SCTBundles to send
  //  as feedback
  def get_gossip_selection() {
    if(len(observed_records) > MAX_SCT_RECORDS_TO_GOSSIP) {
      indexes = set()
      modulus = len(observed_records)
      while(len(indexes) < MAX_SCT_RECORDS_TO_GOSSIP) {
        r = randomInt() % modulus
        if(r not in indexes)
          indexes.insert(r)
      }

      return_selection = []
      foreach(i in indexes) {
        return_selection.insert(this.observed_records[i])
      }

      return return_selection
    }
    else
      return this.observed_records
  }

  def passes_validity_checks(SCTBundle b) {
    //  This function performs the validity checks specified in
    //  {{feedback-srvop}}
  }
}
   The SCTDomainEntry is responsible for handling the outcome of a
   submission report for that domain using its member function:

//  This function is called after providing SCT Feedback
//  to a server. It is passed the feedback sent to the other party, which
//  is the output of get_gossip_selection(), and also the SCTBundle
//  representing the connection the data was sent on.
//  (When this code runs on the server, connectionBundle is NULL)
//  If the Feedback was not sent successfully, error is True
def after_submit_to_thirdparty(error, SCTBundle[] submittedBundles,
                               SCTBundle connectionBundle)
{
  // Server operation in this instance is exceedingly simple
  if(operator_is_server) {
    if(error)
      return
    foreach(bundle in submittedBundles)
      bundle.num_reports_to_thirdparty++
    return
  }

  // Client behavior is much more complicated
  if(error) {
    if(sct_feedback_failing_longterm()) {
      num_feedback_loop_failures++
    }
    else if((num_submissions_succeeded / num_submissions_attempted)
            > MIN_RATIO_FOR_SCT_FEEDBACK_TO_BE_WORKING) {
      // Do nothing. num_submissions_succeeded will not be incremented
      // After enough of these failures, the ratio will fall beyond
      // acceptable
    } else {
      // The domain has begun its three-month grace period. We will
      // attempt submissions once a month
      num_feedback_loop_failures++
    }
    return
  }
  // We succeeded, so reset all of our failure states
  // Note, there is a race condition here if clear_old_data() is called
  // while this pseudocode callback is that it aggressively removes STHs once outstanding.
  num_feedback_loop_failures     = 0
  if(num_submissions_succeeded != UINT16_MAX )
    num_submissions_succeeded++

  foreach(bundle in submittedBundles)
  {
    // Compare Certificate Chains, if they
   have been resolved to do not match, it counts as a newer STH (if proof fetching is configured).
   The only STHs in the store are ones
    // submission.
    if(!connectionBundle.approx_equals(bundle))
      bundle.num_reports_to_thirdparty++
    else {
      // This check ensures that have never been resolved to a newer STH, either because proof fetching does not occur, has
   failed, or because the STH SCT Bundle is not considered too new to request a proof
   for.  It seems less likely that servers will perform proof fetching.
   Therefore reported
      // if it would be recommended that is submitted over a connection with the various constants same SCTs. This
      // satisfies the constraint in use
   be increased considerably to ensure STHs are pollinated more
   aggressively.

   class STHStore
   {
     STH[] sth_list Paragraph 5 of {{feedback-clisrv}}
      //  This function Consider three submission scenarios:
      // Submitted SCTs      Connection SCTs    Considered Submitted
      // A, B                A, B               No - no new information
      // A                   A, B               Yes - B is run after receiving a set of STHs from new SCT
      // A, B                A                  No - no new information
      if(connectionBundle.sct_list is NOT a third party in response to a pollination submission
     def insert(STH[] new_sths) {
       foreach(new in new_sths) {
         if(this.sth_list.contains(new))
           continue
         this.sth_list.insert(new) subset of bundle.sct_list)
        bundle.num_reports_to_thirdparty++
    }
  }

     //
}

   Instances of the SCTDomainEntry class are stored as part of a larger
   class that manages the entire SCT Cache, storing them in a hashmap
   keyed by domain.  This function is called to possibly delete class also tracks the given STH
     //  from current size of the data store
     def delete_maybe(STH s)
   cache, and will trigger cache eviction.

//Suggestions:
#define CACHE_PRESSURE_SAFE                   .50
#define CACHE_PRESSURE_IMMINENT               .70
#define CACHE_PRESSURE_ALMOST_FULL            .85
#define CACHE_PRESSURE_FULL                   .95
#define WAIT_BETWEEN_IMMINENT_CACHE_EVICTION  5 minutes

class SCTStoreManager
{
  hashmap<String, SCTDomainEntry> all_sct_entries
  uint32                         current_cache_size
  datetime                       imminent_cache_pressure_check_performed

  float current_cache_percentage() {
       //Perform statistical test and see if I should delete this bundle
    return current_cache_size / MAX_CACHE_SIZE;
  }

  static def update_cache_percentage() {
    // This function is called to (certainly) delete calculates the given STH
     //  from current size of the data store
     def delete_now(STH s) {
       this.sth_list.remove(s)
     } cache
    //  When it is time to and updates current_cache_size
    /* ... perform STH Pollination, the HTTPS Client calculations ... */
    current_cache_size = /* new calculated value */

    //  calls this function Perform locking to get a selection prevent multiple of STHs to send as these functions being
    //  feedback
     def get_pollination_selection() called concurrently or unnecessarily
    if(current_cache_percentage() > CACHE_PRESSURE_FULL) {
       if(len(this.sth_list) < MAX_STH_TO_GOSSIP)
         return this.sth_list
        cache_is_full()
    }

    else if(current_cache_percentage() > CACHE_PRESSURE_ALMOST_FULL) {
         indexes = set()
         modulus = len(this.sth_list)
         while(len(indexes) < MAX_STH_TO_GOSSIP)
      cache_pressure_almost_full()
    }

    else if(current_cache_percentage() > CACHE_PRESSURE_IMMINENT) {
           r = randomInt() % modulus
           if(r
      // Do not in indexes
              && now() repeatedly perform the imminent cache pressure operation
      if(now() - this.sth_list[i].timestamp < ONE_WEEK)
             indexes.insert(r)
         }

         return_selection = []
         foreach(i in indexes) imminent_cache_pressure_check_performed >
          WAIT_BETWEEN_IMMINENT_CACHE_EVICTION) {
           return_selection.insert(this.sth_list[i])
        cache_pressure_is_imminent()
      }
         return return_selection
    }
  }
}

   We also suggest

   The SCTStoreManager contains a function that can will be called
   periodically in the background, iterating through the STH store, performing a cleaning
   operation all SCTDomainEntry
   objects and queuing consistency proofs.  This function can live as
   a member functions of the STHStore class.

   def clean_list() {
     foreach(sth in this.sth_list) {

       if(now() - sth.timestamp > ONE_WEEK) {
         //STH is too old, performing maintenance tasks.  It removes data for
   domains we must remove it
         if(proof_fetching_enabled
            && auditor_of_last_resort_enabled
            && (sth.proof_failure_count / sth.proof_attempts)
               > MIN_PROOF_FAILURE_RATIO_CONSIDERED_SUSPICIOUS) {
           queue_sth_for_auditor_of_last_resort(sth)
           delete_maybe(sth)
         } else {
           delete_now(sth)
         }
       }

       else if(proof_fetching_enabled
               && now() - sth.timestamp > TWO_DAYS
               && now() - sth.timestamp > LOG_MMD) {
         sth.proof_attempts++
         queue_consistency_proof(sth, consistency_proof_callback)
       }
     }
   }

11.3.3.2.2.  STH Deletion Procedure

   The STH Deletion Procedure is run after successfully submitting a
   list of STHs to a third party during pollination.  The following
   pseudocode would be included in the STHStore class, and called with
   the result of get_pollination_selection(), after the STHs have been
   (successfully) sent to the third party.

   // not contacted in a long time.  This function is called after successfully pollinating STHs
   //  to a third party. It is passed the STHs sent not
   intended to clear data if the third
   //  party, which cache is the output of get_gossip_selection() getting full, separate
   functions are used for that.

 // Suggestions:
 #define TIME_UNTIL_OLD_SUBMITTED_SCTDATA_ERASED     3 months
 #define TIME_UNTIL_OLD_UNSUBMITTED_SCTDATA_ERASED   6 months

 def after_submit_to_thirdparty(STH[] sth_list) clear_old_data()
 {
     foreach(sth
   foreach(domainEntry in sth_list) all_sct_stores)
   {
       sth.num_reports_to_thirdparty++
     // Queue proof fetches
     if(proof_fetching_enabled) {
         if(now() - sth.timestamp > LOG_MMD)
       foreach(sctBundle in domainEntry.observed_records) {
           sth.proof_attempts++
           queue_consistency_proof(sth, consistency_proof_callback)
         }

         if(auditor_of_last_resort_enabled
            && sth.proof_failure_count >
               MIN_PROOF_ATTEMPTS_CONSIDERED_SUSPICIOUS
            && (sth.proof_failure_count / sth.proof_attempts) >
               MIN_PROOF_FAILURE_RATIO_CONSIDERED_SUSPICIOUS)
         if(!sctBundle.has_been_fully_resolved_to_sths()) {
             queue_sth_for_auditor_of_last_resort(sth)
         }
       }
       else
           foreach(s in bundle.sct_list) { //proof fetching not enabled
         if(sth.num_reports_to_thirdparty
            > MIN_STH_REPORTS_TO_THIRDPARTY)
             if(!s.has_been_resolved_to_sth && !s.proof_outstanding) {
           delete_maybe(sth)
         }
       }
               sct.proof_outstanding = True
               queue_inclusion_proof(sct, inclusion_proof_callback)
             }
           }

   def consistency_proof_callback(consistency_proof,
                                  original_sth,
                                  error) {
     if(!error) {
       insert(consistency_proof.current_sth)
       delete_now(consistency_proof.original_sth)
         } else {
       original_sth.proof_failure_count++
       }
     }

11.3.3.2.3.  SCT Data Structures

   TBD TBD This section is

     // Do not well abstracted to be used for both
   servers and clients.  TKTK
   The SCT class contains store data pertaining specifically to the SCT
   itself.

   class for domains who are not supporting SCT
     if(!operator_is_server
        && domainEntry.sct_feedback_failing_longterm())
     {
     uint32 proof_attempts
     uint32 proof_failure_count
     bool   has_been_resolved_to_sth
     byte[] data
   }

   The SCT bundle will contain the trusted certificate chain the HTTPS
   client built (chaining to a trusted root certificate.)  It also
   contains the list of associated SCTs, the exact domain it
       // Note that reseting these variables every single time is
   applicable to, and metadata pertaining to how often it has been
   reported
       // necessary to the third party.

   class SCTBundle
   {
     X509[] certificate_chain
     SCT[]  sct_list
     string domain
     uint32 num_reports_to_thirdparty

     def equals(sct_bundle) {
       if(sct_bundle.domain != this.domain)
         return false
       if(sct_bundle.certificate_chain != this.certificate_chain)
         return false
       if(sct_bundle.sct_list != this.sct_list)
         return false

       return true
     }
     def approx_equals(sct_bundle) {
       if(sct_bundle.domain != this.domain)
         return false
       if(sct_bundle.certificate_chain != this.certificate_chain)
         return false

       return true
     }

     def insert_scts(sct[] sct_list) {
       this.sct_list.union(sct_list)
       this.num_reports_to_thirdparty avoid a bug
       all_sct_stores[domainEntry].num_submissions_attempted      = 0
       all_sct_stores[domainEntry].num_submissions_succeeded      = 0
       delete all_sct_stores[domainEntry].observed_records
       all_sct_stores[domainEntry].observed_records               = 0 NULL
     }

     def has_been_fully_resolved_to_sths() {
       foreach(s

     // This check removes successfully submitted data for
     // old domains we have not dealt with in this.sct_list) a long time
     if(domainEntry.num_submissions_succeeded > 0
        && now() - domainEntry.last_contact_for_domain
           > TIME_UNTIL_OLD_SUBMITTED_SCTDATA_ERASED)
     {
         if(!s.has_been_resolved_to_sth)
           return false
       all_sct_stores.remove(domainEntry)
     }
       return true
     }

     def max_proof_failure_count() {
       uint32 max = 0
       foreach(s

     // This check removes unsuccessfully submitted data for
     // old domains we have not dealt with in this.sct_list) {
         if(s.proof_failure_count a very long time
     if(now() - domainEntry.last_contact_for_domain
        > max)
           max = proof_failure_count
       }
       return max TIME_UNTIL_OLD_UNSUBMITTED_SCTDATA_ERASED)
     {
       all_sct_stores.remove(domainEntry)
     }

 SCTStoreManager.update_cache_percentage()
 }
   We suppose a large data structure

   Inclusion Proof Fetching is used, such as a hashmap, indexed
   by the domain name.  For each domain, the structure will contain a
   data structure that holds the SCTBundles seen for that domain, as
   well as encapsulating some logic relating to SCT Feedback for that
   particular domain.

   class SCTStore
   {
     string   domain
     datetime last_contact_for_domain
     uint32   num_submissions_attempted
     uint32   num_submissions_succeeded
     SCTBundle[] observed_records handled fairly independently

 // This function is called a callback invoked after recieving an SCTBundle. inclusion proof
 //  For Clients, has been retrieved. It can exist on the SCT class or independently,
 // so long as it can modify the SCT class' members
 def inclusion_proof_callback(inclusion_proof, original_sct, error)
 {
   // Unlike the STH code, this counter must be incremented on the
   // callback as there is after a successful connection to a
     //  HTTPS Server, calling race condition on using this function with an SCTBundle
     //  constructed from that certificate chain and SCTs counter in the
   //  For Servers, this is after receiving SCT Feedback
     def insert(SCTBundle b) {
       if(operator_is_server) cache_* functions.
   original_sct.proof_attempts++
   original_sct.proof_outstanding = False
   if(!error) {
         if(!passes_validity_checks(b))
           return
     original_sct.has_been_resolved_to_sth = True
     insert_to_sth_datastore(inclusion_proof.new_sth)
   }
       foreach(e in this.observed_records) {
         if(e.equals(b))
           return else if(e.approx_equals(b)) {
           e.insert_scts(b.sct_list)
           return
         }
     original_sct.proof_failure_count++
   }
       this.observed_records.insert(b)
 }

   If the cache is getting full, these three member functions of the
   SCTStoreManager class will be used.

//  When it -----------------------------------------------------------------
// This function is called when the cache is not yet full, but is time
// nearing it. It prioritizes deleting data that should be safe
// to perform SCT Feedback, delete (because it has been shared with the HTTPS Client site or resolved
//  calls this function to get a selection of SCTBundles to send
     //  as feedback STH)
def get_gossip_selection() cache_pressure_is_imminent()
{
       if(len(observed_records) > MAC_SCT_RECORDS_TO_GOSSIP) {
         indexes
  bundlesToDelete = set()
         modulus = len(observed_records)
         while(len(indexes) < MAX_SCT_RECORDS_TO_GOSSIP) []
  foreach(domainEntry in all_sct_stores) {
           r = randomInt() % modulus
           if(r not
    foreach(sctBundle in indexes)
             indexes.insert(r)
         }
         return_selection = []
         foreach(i domainEntry.observed_records) {

      if(proof_fetching_enabled) {
        // First, queue proofs for anything not already queued.
        if(!sctBundle.has_been_fully_resolved_to_sths()) {
          foreach(sct in indexes) bundle.sct_list) {
           return_selection.insert(this.observed_records[i])
            if(!sct.has_been_resolved_to_sth
               && !sct.proof_outstanding) {
              sct.proof_outstanding = True
              queue_inclusion_proof(sct, inclusion_proof_callback)
            }

         return return_selection
          }
       else
         return this.observed_records
        }

     def delete_maybe(SCTBundle b)

        // Second, consider deleting entries that have been fully
        // resolved.
        else {
       //Perform statistical test and see if I should delete this bundle
          bundlesToDelete.append( Struct(domainEntry, sctBundle) )
        }

     def delete_now(SCTBundle b) {
       this.observed_records.remove(b)
      }

     def passes_validity_checks(SCTBundle b) {

      //  This function performs the validity checks specified in Third, consider deleting entries that have been successfully
      //  {{feedback-srvop}} reported
      if(sctBundle.num_reports_to_thirdparty > 0) {
        bundlesToDelete.append( Struct(domainEntry, sctBundle) )
      }
    }

   We also suggest a function that can be called periodically in
  }

  // Third, delete the
   background, iterating through all SCTStore objects in eligible entries at random until the large
   hashmap (here called 'all_sct_stores') and removing old data.

   def clear_old_data()
   {
     foreach(storeEntry in all_sct_stores)
     {
       if(storeEntry.num_submissions_succeeded == cache is
  // at a safe level
  uint recalculateIndex                = 0
          && storeEntry.num_submissions_attempted
             > MIN_SCT_ATTEMPTS_FOR_DOMAIN_TO_BE_IGNORED)
       {
         all_sct_stores.remove(storeEntry)
       }
       else if(storeEntry.num_submissions_succeeded
  #define RECALCULATE_EVERY_N_OPERATIONS 50

  while(bundlesToDelete.length > 0 && now() - storeEntry.last_contact_for_domain
        current_cache_percentage() > TIME_UNTIL_OLD_SCTDATA_ERASED) CACHE_PRESSURE_SAFE) {
         all_sct_stores.remove(storeEntry)
       }
    uint rndIndex = rand() % bundlesToDelete.length
    bundlesToDelete[rndIndex].domainEntry.observed_records.remove(bundlesToDelete[rndIndex].sctBundle)
    bundlesToDelete.removeAt(rndIndex)

    recalculateIndex++
    if(recalculateIndex % RECALCULATE_EVERY_N_OPERATIONS == 0) {
      update_cache_percentage()
    }
  }

11.3.3.2.4.  SCT Deletion Procedure

   The SCT Deletion procedure is more complicated than the respective
   STH procedure.  This is because servers may elect not to participate
   in SCT Feedback, and this must be accounted for by being more
   conservative in sending SCT reports to them.

   The following pseudocode would be included in the SCTStore class, and
   called with the result of get_gossip_selection() after the SCT
   Feedback has been sent (successfully) to

  // Finally, tell the server.  We also note
   that proof fetching engine to go faster
  if(proof_fetching_enabled) {
    // This function would speed up proof fetching until an
    // arbitrary time has passed. Perhaps until it has fetched
    // proofs for the first experimental algorithm from above is included number of items currently in the
   pseudocode as an illustration. its queue? Or
    // a percentage of them?
    proof_fetch_faster_please()
  }
  update_cache_percentage();
}

// -----------------------------------------------------------------
// This function is called after successfully providing SCT Feedback
   //  to a server. It is passed when the feedback sent cache is almost full. It will
// evict entries at random, while attempting to the server, which save entries that
//  is the output of get_gossip_selection() appear to have proof fetching failures
def after_submit_to_thirdparty(SCTBundle[] submittedBundles)
   {
     foreach(bundle in submittedBundles)
     {
       bundle.num_reports_to_thirdparty++

       if(proof_fetching_enabled) {
         if(!bundle.has_been_fully_resolved_to_sths()) {
           foreach(s in bundle.sct_list) {
             if(!s.has_been_resolved_to_sth) {
               s.proof_attempts++
               queue_inclusion_proof(sct, inclusion_proof_callback)
             }
           }
         }
         else cache_pressure_almost_full()
{
           if(run_ct_gossip_experiment_one) {
             if(bundle.num_reports_to_thirdparty
  uint recalculateIndex                = 0
  uint savedRecords                    = 0
  #define RECALCULATE_EVERY_N_OPERATIONS 50

  while(all_sct_stores.length > MIN_SCT_REPORTS_TO_THIRDPARTY savedRecords && bundle.num_reports_to_thirdparty * 1.5
        current_cache_percentage() > bundle.max_proof_failure_count()) CACHE_PRESSURE_SAFE) {
               maybe_delete(bundle)
             }
           }
           else
    uint rndIndex1 = rand() % all_sct_stores.length
    uint rndIndex2 = rand() % all_sct_stores[rndIndex1].observed_records.length

    if(proof_fetching_enabled) { //Do not run experiment
             if(bundle.num_reports_to_thirdparty
      if(all_sct_stores[rndIndex1].observed_records[rndIndex2].max_proof_failures() > MIN_SCT_REPORTS_TO_THIRDPARTY)
         MIN_PROOF_FAILURES_CONSIDERED_SUSPICIOUS) {
               maybe_delete(bundle)
             }
           }
        savedRecords++
        continue
      }
    }
       else {//proof

    // If proof fetching is not enabled
         if(bundle.num_reports_to_thirdparty
            > (MIN_SCT_REPORTS_TO_THIRDPARTY
               * NO_PROOF_FETCHING_REPORT_INCREASE_FACTOR)) we need some other logic
    else {
           maybe_delete(bundle)
      if(sctBundle.num_reports_to_thirdparty == 0) {
        savedRecords++
        continue
      }
    }

    all_sct_stores[rndIndex1].observed_records.removeAt(rndIndex2)
    if(all_sct_stores[rndIndex1].observed_records.length == 0) {
      all_sct_stores.removeAt(rndIndex1)
    }

    recalculateIndex++
    if(recalculateIndex % RECALCULATE_EVERY_N_OPERATIONS == 0) {
      update_cache_percentage()
    }
  }

  update_cache_percentage();
}
// -----------------------------------------------------------------
// This function is a callback invoked after an inclusion proof called when the cache is full, and will evict
// has been retrieved cache entries at random
def inclusion_proof_callback(inclusion_proof, original_sct, error) cache_is_full()
{
     if(!error)
  uint recalculateIndex                = 0
  #define RECALCULATE_EVERY_N_OPERATIONS 50

  while(all_sct_stores.length > 0 &&
        current_cache_percentage() > CACHE_PRESSURE_SAFE) {
       original_sct.has_been_resolved_to_sth
    uint rndIndex1 = True
       insert_to_sth_datastore(inclusion_proof.new_sth) rand() % all_sct_stores.length
    uint rndIndex2 = rand() % all_sct_stores[rndIndex1].observed_records.length

    all_sct_stores[rndIndex1].observed_records.removeAt(rndIndex2)
    if(all_sct_stores[rndIndex1].observed_records.length == 0) {
      all_sct_stores.removeAt(rndIndex1)
    } else

    recalculateIndex++
    if(recalculateIndex % RECALCULATE_EVERY_N_OPERATIONS == 0) {
       original_sct.proof_failure_count++
      update_cache_percentage()
    }
  }

  update_cache_percentage();
}

12.  IANA considerations

   [ TBD ]

13.  Contributors

   The authors would like to thank the following contributors for
   valuable suggestions: Al Cutter, Ben Laurie, Benjamin Kaduk, Josef
   Gustafsson, Karen Seo, Magnus Ahltorp, Steven Kent, Yan Zhu.

14.  ChangeLog

14.1.  Changes between ietf-02 and ietf-03

   o  TBD's resolved.

   o  References added.

   o  Pseduocode changed to work for both clients and servers.

14.2.  Changes between ietf-01 and ietf-02

   o  Requiring full certificate chain in SCT Feedback.

   o  Clarifications on what clients store for and send in SCT Feedback
      added.

   o  SCT Feedback server operation updated to protect against DoS
      attacks on servers.

   o  Pre-Loaded vs Locally Added Anchors explained.

   o  Base for well-known URL's changed.

   o  Remove all mentions of monitors - gossip deals with adutitors. auditors.

   o  New sections added: Trusted Auditor protocol, attacks by actively
      malicious log, the Dual-CA compromise attack, policy
      recommendations,

14.2.

14.3.  Changes between ietf-00 and ietf-01

   o  Improve langugage language and readability based on feedback from Stephen
      Kent.

   o  STH Pollination Proof Fetching defined and indicated as optional.

   o  3-Method Ecosystem section added.

   o  Cases with Logs ceasing operation handled.

   o  Text on tracking via STH Interaction added.

   o  Section with some early recommendations for mixing added.

   o  Section detailing blocking connections, frustrating it, and the
      implications added.

14.3.

14.4.  Changes between -01 and -02

   o  STH Pollination defined.

   o  Trusted Auditor Relationship defined.

   o  Overview section rewritten.

   o  Data flow picture added.

   o  Section on privacy considerations expanded.

14.4.

14.5.  Changes between -00 and -01

   o  Add the SCT feedback mechanism: Clients send SCTs to originating
      web server which shares them with auditors.

   o  Stop assuming that clients see STHs.

   o  Don't use HTTP headers but instead .well-known URL's - avoid that
      battle.

   o  Stop referring to trans-gossip and trans-gossip-transport-https -
      too complicated.

   o  Remove all protocols but HTTPS in order to simplify - let's come
      back and add more later.

   o  Add more reasoning about privacy.

   o  Do specify data formats.

15.  References

15.1.  Normative References

   [RFC-6962-BIS-09]
              Laurie, B., Langley, A., Kasper, E., Messeri, E., and R.
              Stradling, "Certificate Transparency", October 2015,
              <https://datatracker.ietf.org/doc/draft-ietf-trans-
              rfc6962-bis/>.

   [RFC7159]  Bray, T., "The JavaScript Object Notation (JSON) Data
              Interchange Format", RFC 7159, March 2014.

15.2.  Informative References

   [double-keying]
              Perry, M., Clark, E., and S. Murdoch, "Cross-Origin
              Identifier Unlinkability", May 2015,
              <https://www.torproject.org/projects/torbrowser/
              design/#identifier-linkability>.

   [draft-ct-over-dns]
              Laurie, B., Phaneuf, P., and A. Eijdenberg, "Certificate
              Transparency over DNS", February 2016,
              <https://github.com/google/certificate-transparency-
              rfcs/blob/master/dns/draft-ct-over-dns.md>.

   [draft-ietf-trans-threat-analysis-03]
              Kent, S., "Attack Model and Threat for Certificate
              Transparency", October 2015,
              <https://datatracker.ietf.org/doc/draft-ietf-trans-threat-
              analysis/>.

   [dual-ca-compromise-attack]
              Gillmor, D., "can CT defend against dual CA compromise?",
              n.d., <https://www.ietf.org/mail-
              archive/web/trans/current/msg01984.html>.

   [gossip-mixing]
              Ritter, T., "A Bit on Certificate Transparency Gossip",
              June 2016, <https://ritter.vg/blog-
              a_bit_on_certificate_transparency_gossip.html>.

   [trickle]  Serjantov, A., Dingledine, R., and . Paul Syverson, "From
              a Trickle to a Flood: Active Attacks on Several Mix
              Types", October 2002,
              <http://freehaven.net/doc/batching-taxonomy/taxonomy.pdf>.

Authors' Addresses

   Linus Nordberg
   NORDUnet

   Email: linus@nordu.net

   Daniel Kahn Gillmor
   ACLU

   Email: dkg@fifthhorseman.net

   Tom Ritter

   Email: tom@ritter.vg