Key Transparency

3.1. Basic Operations

The operations that can be executed by a client are as follows:¶

1. Search: Performs a lookup on a specific key in the most recent version of the log. Clients may request either a specific version of the key, or the most recent version available. If the key-version pair exists, the server returns the corresponding value and a proof of inclusion. If the key-version pair does not exist, the server returns a proof of non-inclusion instead.¶
2. Update: Adds a new key-value pair to the log, for which the server returns a proof of inclusion. Note that this means that new values are added to the log immediately in response to an Update operation, and are not queued for later insertion with a batch of other values.¶
3. Monitor: While Search and Update are run by the client as necessary, monitoring is done in the background on a recurring basis. It both checks that the log is continuing to behave honestly (all previously returned keys remain in the tree) and that no changes have been made to keys owned by the client without the client's knowledge.¶

3.2. Deployment Modes

In the interest of satisfying the widest range of use-cases possible, three different modes for deploying a Transparency Log are described in this document. Each mode has slightly different requirements and efficiency considerations for both the service operator and the end-user.¶

Third-party Management and Third-party Auditing are two deployment modes that require the service operator to delegate part of the operation of the Transparency Log to a third party. Users are able to run more efficiently as long as they can assume that the service operator and the third party won't collude to trick them into accepting malicious results.¶

With both third-party modes, all requests from end-users are initially routed to the service operator and the service operator coordinates with the third party themself. End-users never contact the third party directly, however they will need a signature public key from the third party to verify its assertions.¶

With Third-party Management, the third party performs the majority of the work of actually storing and operating the log, and the service operator only needs to sign new entries as they're added. With Third-party Auditing, the service operator performs the majority of the work of storing and operating the log, and obtains signatures from a lightweight third-party auditor at regular intervals asserting that the service operator has been constructing the tree correctly.¶

Contact Monitoring, on the other hand, supports a single-party deployment with no third party. The tradeoff is that the background monitoring protocol requires a number of requests that's proportional to the number of keys a user has looked up in the past. As such, it's less suited to use-cases where users look up a large number of ephemeral keys, but would work ideally in a use-case where users look up a small number of keys repeatedly (for example, the keys of regular contacts).¶

The deployment mode of a Transparency Log is chosen when the log is first created and isn't able to be changed over the log's lifetime. This makes it important for operators to carefully consider the best long-term approach based on the specifics of their application.¶

3.3. Security Guarantees

A client that executes a Search or Update operation correctly (and does any required monitoring afterwards) receives a guarantee that the Transparency Log operator also executed the operation correctly and in a way that's globally consistent with what it has shown all other clients. That is, when a client searches for a key, they're guaranteed that the result they receive represents the same result that any other client searching for the same key would've seen. When a client updates a key, they're guaranteed that other clients will see the update the next time they search for the key.¶

If the Transparency Log operator does not execute an operation correctly, then either:¶

1. The client will detect the error immediately and reject the result of an operation, or¶
2. The client will permanently enter an invalid state.¶

Depending on the exact reason that the client enters an invalid state, it will either be detected by background monitoring or the next time that out-of-band communication is available. Importantly, this means that clients must stay online for some fixed amount of time after entering an invalid state for it to be successfully detected.¶

The exact caveats of the above guarantee depend naturally on the security of underlying cryptographic primitives, but also the deployment mode that the Transparency Log relies on:¶

• Third-Party Management and Third-Party Auditing require an assumption that the Transparency Log operator and the third-party manager/auditor do not collude to trick clients into accepting malicious results.¶
• Contact Monitoring requires an assumption that the client that owns a key and all clients that look up the key do the necessary monitoring afterwards.¶

4.1. Log Tree

Log trees are used for storing information in the chronological order that it was added and are constructed as left-balanced binary trees.¶

A binary tree is balanced if its size is a power of two and for any parent node in the tree, its left and right subtrees have the same size. A binary tree is left-balanced if for every parent, either the parent is balanced, or the left subtree of that parent is the largest balanced subtree that could be constructed from the leaves present in the parent's own subtree. Given a list of n items, there is a unique left-balanced binary tree structure with these elements as leaves. Note also that every parent always has both a left and right child.¶

Log trees initially consist of a single leaf node. New leaves are added to the right-most edge of the tree along with a single parent node, to construct the left-balanced binary tree with n+1 leaves.¶

While leaves contain arbitrary data, the value of a parent node is always the hash of the combined values of its left and right children.¶

Log trees are special in that they can provide both inclusion proofs, which demonstrate that a leaf is included in a log, and consistency proofs, which demonstrate that a new version of a log is an extension of a past version of the log.¶

An inclusion proof is given by providing the copath values of a leaf. The proof is verified by hashing together the leaf with the copath values and checking that the result equals the root value of the log. Consistency proofs are a more general version of the same idea. With a consistency proof, the prover provides the minimum set of intermediate node values from the current tree that allows the verifier to compute both the old root value and the current root value. An algorithm for this is given in section 2.1.2 of [RFC6962].¶

4.2. Prefix Tree

Prefix trees are used for storing key-value pairs while preserving the ability to efficiently look up a value by its corresponding key.¶

Each leaf node in a prefix tree represents a specific key-value pair, while each parent node represents some prefix which all keys in the subtree headed by that node have in common. The subtree headed by a parent's left child contains all keys that share its prefix followed by an additional 0 bit, while the subtree headed by a parent's right child contains all keys that share its prefix followed by an additional 1 bit.¶

The root node, in particular, represents the empty string as a prefix. The root's left child contains all keys that begin with a 0 bit, while the right child contains all keys that begin with a 1 bit.¶

A prefix tree can be searched by starting at the root node, and moving to the left child if the first bit of a search key is 0, or the right child if the first bit is 1. This is then repeated for the second bit, third bit, and so on until the search either terminates at a leaf node (which may or may not be for the desired key), or a parent node that lacks the desired child.¶

New key-value pairs are added to the tree by searching it according to this process. If the search terminates at a parent without a left or right child, a new leaf is simply added as the parent's missing child. If the search terminates at a leaf for the wrong key, one or more intermediate nodes are added until the new leaf and the old leaf would no longer reside in the same place. That is, until we reach the first bit that differs between the new key and the old key.¶

The value of a leaf node is the encoded key-value pair, while the value of a parent node is the hash of the combined values of its left and right children (or a stand-in value when one of the children doesn't exist).¶

4.3. Combined Tree

Log trees are desirable because they can provide efficient consistency proofs to assure verifiers that nothing has been removed from a log that was present in a previous version. However, log trees can't be efficiently searched without downloading the entire log. Prefix trees are efficient to search and can provide inclusion proofs to convince verifiers that the returned search results are correct. However, it's not possible to efficiently prove that a new version of a prefix tree contains the same data as a previous version with only new keys added.¶

In the combined tree structure, which is based on [Merkle2], a log tree maintains a record of updates to key-value pairs while a prefix tree maintains a map from each key to a counter with the number of times it's been updated. Importantly, the root value of the prefix tree after adding the new key or increasing the counter of an existing key, is stored in the log tree alongside the record of the update. With some caveats, this combined structure supports both efficient consistency proofs and can be efficiently searched.¶

To search the combined structure, users do a binary search for the first log entry where looking up the search key in the prefix tree at that entry yields the desired counter. As such, the entry that a user arrives at through binary search contains the update with the key-value pair that they're looking for, even though the log itself is not sorted.¶

Binary search also ensures that all users will check the same or similar entries when searching for the same key, which is necessary for the efficient auditing of a Transparency Log. To maximize this effect, users start their binary search at the entry whose index is the largest power of two less than the size of the log, and move left or right by consecutively smaller powers of two.¶

So for example in a log with 70 entries, instead of starting a search at the "middle" with entry 35, users would start at entry 64. If the next step in the search is to move right, instead of moving to the middle of entries 64 and 70, which would be entry 67, users would move 4 steps (the largest power of two possible) to the right to entry 68. As more entries are added to the log, users will consistently revisit entries 64 and 68, while they may never revisit entries 35 or 67 after even a single new entry is added to the log.¶

While users searching for a specific version of a key jump right into a binary search for the entry with that counter, other users may instead wish to search for the "most recent" version of a key. That is, the key with the highest counter possible. Users looking up the most recent version of a key start by fetching the frontier of the log, which they use to determine what the highest counter for a key is.¶

The frontier of a log consists of the entry whose index is the largest power of two less than the size of the log, followed by the entry the largest power of two possible to the right, repeated until the last entry of the log is reached. So for example in a log with 70 entries, the frontier consists of entries 64, 68, and 69 (with 69 being the last entry).¶

7.1. Commitment

Commitments are computed with HMAC [RFC2104], using the hash function specified by the ciphersuite. To produce a new commitment to a value called message, the application generates a random 16 byte value called opening and then computes:¶

commitment = HMAC(fixedKey, opening || message)

where fixedKey is the 16 byte hex-decoded value:¶

d821f8790d97709796b4d7903357c3f5

This fixed key allows the HMAC function, and thereby the commitment scheme, to be modeled as a random oracle.¶

The output value commitment may be published, while opening and message should be kept private until the commitment is meant to be revealed.¶

7.2. Prefix Tree

The leaf nodes of a prefix tree are serialized as:¶

struct {
    opaque key<VRF.Nh>;
    uint32 counter;
} PrefixLeaf;

where key is the full search key, counter is the counter of times that the key has been updated (starting at 0 for a key that was just created), and VRF.Nh is the output size of the ciphersuite VRF in bytes.¶

The parent nodes of a prefix tree are serialized as:¶

struct {
  opaque value<Hash.Nh>;
} PrefixParent;

where Hash.Nh is the output length of the ciphersuite hash function. The value of a parent node is computed by hashing together the values of its left and right children:¶

parent.value = Hash(0x01 ||
                   nodeValue(parent.leftChild) ||
                   nodeValue(parent.rightChild))

nodeValue(node):
  if node.type == emptyNode:
    return make([]byte, Hash.Nh)
  else if node.type == leafNode:
    return Hash(0x00 || node.key || node.counter)
  else if node.type == parentNode:
    return node.value

where Hash denotes the ciphersuite hash function.¶

7.3. Log Tree

The leaf and parent nodes of a log tree are serialized as:¶

struct {
  opaque commitment<Hash.Nh>;
  opaque prefix_tree<Hash.Nh>;
} LogLeaf;

struct {
  opaque value<Hash.Nh>;
} LogParent;

The value of a parent node is computed by hashing together the values of its left and right children:¶

parent.value = Hash(hashContent(parent.leftChild) ||
                    hashContent(parent.rightChild))

hashContent(node):
  if node.type == leafNode:
    return 0x00 || nodeValue(node)
  else if node.type == parentNode:
    return 0x01 || nodeValue(node)

nodeValue(node):
  if node.type == leafNode:
    return Hash(node.commitment || node.prefix_tree)
  else if node.type == parentNode:
    return parent.value

7.4. Tree Head Signature

The head of a Transparency Log, which represents the log's most recent state, is represented as:¶

struct {
  uint64 tree_size;
  uint64 timestamp;
  opaque signature<0..2^16-1>;
} TreeHead;

where tree_size counts the number of entries in the log tree and timestamp is the time that the structure was generated, in milliseconds since the Unix epoch. If the Transparency Log is deployed with Third-party Management then the public key used to verify the signature belongs to the third-party manager; otherwise the public key used belongs to the service operator.¶

The signature itself is computed over a TreeHeadTBS structure, which incorporates the log's current state as well as long-term log configuration:¶

enum {
  reserved(0),
  contactMonitoring(1),
  thirdPartyManagement(2),
  thirdPartyAuditing(3),
} DeploymentMode;

struct {
  CipherSuite ciphersuite;
  DeploymentMode mode;
  opaque signature_public_key<0..2^16-1>;
  opaque vrf_public_key<0..2^16-1>;

  select (Configuration.mode) {
    case contactMonitoring:
    case thirdPartyManagement:
      opaque leaf_public_key<0..2^16-1>;
    case thirdPartyAuditing:
      opaque auditor_public_key<0..2^16-1>;
  };
} Configuration;

struct {
  Configuration config;
  uint64 tree_size;
  uint64 timestamp;
  opaque root_value<Hash.Nh>;
} TreeHeadTBS;

8.1. Log Tree

An inclusion proof for a single leaf in a log tree is given by providing the copath values of a leaf. Similarly, a bulk inclusion proof for any number of leaves is given by providing the fewest node values that can be hashed together with the specified leaves to produce the root value. Such a proof is encoded as:¶

opaque NodeValue<Hash.Nh>;

struct {
  NodeValue elements<0..2^16-1>;
} InclusionProof;

Each NodeValue is a uniform size, computed by passing the relevent LogLeaf or LogParent structures through the nodeValue function in Section 7.3. Finally, the contents of the elements array is kept in left-to-right order: if a node is present in the root's left subtree, its value must be listed before any values provided from nodes that are in the root's right subtree, and so on recursively.¶

Consistency proofs are encoded similarly:¶

struct {
  NodeValue elements<0..2^16-1>;
} ConsistencyProof;

Again, each NodeValue is computed by passing the relevent LogLeaf or LogParent structure through the nodeValue function. The nodes chosen correspond to those output by the algorithm in section 2.1.2 of [RFC6962].¶

8.2. Prefix Tree

A proof from a prefix tree authenticates that a search was done correctly for a given search key. Such a proof is encoded as:¶

enum {
  reserved(0),
  inclusion(1),
  nonInclusionLeaf(2),
  nonInclusionParent(3),
} PrefixSearchResult;

struct {
  PrefixSearchResult result;
  NodeValue elements<0..2^16-1>;
  select (PrefixProof.result) {
    case inclusion:
      uint32 counter;
    case nonInclusionLeaf:
      PrefixLeaf leaf;
    case nonInclusionParent:
  };
} PrefixProof;

The result field indicates what the terminal node of the search was:¶

• inclusion for a leaf node matching the requested key¶
• nonInclusionLeaf for a leaf node not matching the requested key¶
• nonInclusionParent for a parent node that lacks the desired child¶

The elements array consists of the copath of the terminal node, in bottom-to-top order. That is, the terminal node's sibling would be first, followed by the terminal node's parent's sibling, and so on. In the event that a node is not present, an all-zero byte string of length Hash.Nh is listed instead.¶

Depending on the result field, any additional information about the terminal node that's necessary to verify the proof is also provided. In the case of nonInclusionParent, no additional information is needed because the non-terminal child's value is already in elements.¶

The proof is verified by hashing together the provided elements, in the left/right arrangement dictated by the search key, and checking that the result equals the root value of the prefix tree.¶

8.3. Combined Tree

A proof from a combined log and prefix tree follows the execution of a binary search through the leaves of the log tree, as described in Section 4.3. It is serialized as follows:¶

struct {
  PrefixProof prefix_proof;
  opaque commitment<Hash.Nh>;
} SearchStep;

struct {
  SearchStep steps<0..2^8-1>;
  InclusionProof inclusion;
} SearchProof;

Each SearchStep structure in steps is one leaf that was inspected as part of the binary search, starting with the "middle" leaf (i.e., the leaf whose index is the largest power of two less than the size of the log). The prefix_proof field of a SearchStep is the output of searching the prefix tree whose root is at that leaf for the search key, while the commitment field is the commitment to the update at that leaf. The inclusion field of SearchProof contains a batch inclusion proof for all of the leaves accessed by the binary search, relating them to the root of the log tree.¶

A verifier interprets the output of each prefix_proof as -1 if it is a non-inclusion proof, or as counter if it is an inclusion proof. The proof can then be verified by checking that:¶

1. The elements of steps represent a monotonic series over the leaves of the log, and¶
2. The elements of steps correspond exactly to the lookups that would be made by the verifier while conducting the binary search.¶

Once the validity of the search steps has been established, the verifier can compute the root of each prefix tree represented by a prefix_proof and combine it with the corresponding commitment to obtain the value of each leaf. These leaf values can then be combined with the proof in inclusion to check that the output matches the root of the log tree.¶

10.1. Search

Users initiate a Search operation by submitting a SearchRequest to the Transparency Log containing the key that they're interested in. Users can optionally specify a version of the key that they'd like to receive, if not the most recent one. They can also include the tree_size of the last TreeHead that they successfully verified.¶

struct {
  opaque search_key<0..2^16-1>;
  optional<uint32> version;
  optional<uint64> last;
} SearchRequest;

In turn, the Transparency Log responds with a SearchResult structure:¶

struct {
  TreeHead tree_head;
  optional<ConsistencyProof> consistency;
  select (Configuration.mode) {
    case thirdPartyAuditing:
      AuditorTreeHead auditor_tree_head;
  };
} FullTreeHead;

struct {
  opaque index<VRF.Nh>;
  opaque proof<0..2^16-1>;
} VRFResult;

struct {
  opaque opening<16>;
  opaque value<0..2^32-1>;
} SearchValue;

struct {
  FullTreeHead full_tree_head;
  VRFResult vrf_result;
  SearchProof search;

  optional<SearchValue> value;
} SearchResult;

If last is present, then the Transparency Log MUST provide a consistency proof between the current tree and the tree when it was this size, in the consistency field of FullTreeHead.¶

Users verify a search result by following these steps:¶

1. Verify the VRF proof in VRFResult.proof against the requested search key SearchRequest.search_key and the claimed VRF output VRFResult.index.¶
2. Evaluate the search proof in search according to the steps in Section 8.3. This will produce a verdict as to whether the search was executed correctly, and also a candidate root value for the tree. If it's determined that the search was executed incorrectly, abort with an error.¶

3. With the candidate root value for the tree:¶

   1. Verify the proof in FullTreeHead.consistency, if one is expected.¶
   2. Verify the signature in TreeHead.signature.¶
   3. Verify that the timestamp in TreeHead is sufficiently recent. Additionally, verify that the timestamp and tree_size fields of the TreeHead are greater than or equal to what they were before.¶
   4. If third-party auditing is used, verify auditor_tree_head with the steps described in Section 11.2.¶
4. If the proof in search determined that a valid entry was found, check that value is populated, and that the commitment in the terminal search step opens to SearchValue.value with opening SearchValue.opening. If the proof determined that a valid entry was not found, check that value is empty.¶

Provided that the above verification is successful, users decode the encoded UpdateValue structure in SearchValue.value. Depending on the deployment mode of the Transparency Log, the UpdateValue may or may not require additional verification, specified in Section 9, before its contents may be consumed.¶

If the Transparency Log is deployed with Contact Monitoring, users MUST retain the most recent version of the key that they've seen (even if that is not the most recent version overall) and the position of that it was stored at in the log. Users MAY retain the entire SearchResult if they wish to later be able to provide non-repudiable proof of misbehavior.¶

10.2. Update

Users initiate an Update operation by submitting an UpdateRequest to the Transparency Log containing the new key and value to store. Users can also optionally include the tree_size of the last TreeHead that they successfully verified.¶

struct {
  opaque search_key<0..2^16-1>;
  opaque value<0..2^32-1>;
  optional<uint64> last;
} UpdateRequest;

If the request is valid, the Transparency Log adds the new key-value pair to the log and returns an UpdateResult structure:¶

struct {
  FullTreeHead full_tree_head;
  VRFResult vrf_result;
  SearchProof search;

  opaque opening<16>;
  UpdatePrefix prefix;
} UpdateResult;

Users verify the UpdateResult as if it were a SearchResult for the most recent version of search_key.¶

Note that the contents of UpdateRequest.value is the new value of the lookup key and NOT a serialized UpdateValue object. To aid verification, the update result provides the UpdatePrefix structure necessary to reconstruct the UpdateValue.¶

Users MUST retain the new version of the key and the position that it is stored at in the log for the purpose of monitoring. Users MAY retain the entire UpdateResult if they wish to later be able to provide non-repudiable proof of misbehavior.¶

10.3. Monitor

Users initiate a Monitor operation by submitting a MonitorRequest to the Transparency Log containing information about the keys they wish to monitor. Similar to Search and Update operations, users can include the tree_size of the last TreeHead that they successfully verified.¶

opaque SearchKey<0..2^16-1>;

struct {
  opaque search_key<0..2^16-1>;
  uint32 version;
} ContactKey;

struct {
  SearchKey search_keys<0..2^16-1>;
  select (Configuration.mode) {
    case contactMonitoring:
      ContactKey contact_keys<0..2^16-1>;
  };
  optional<uint64> last;
} MonitorRequest;

Users include each of the keys that they own in search_keys. If the Transparency Log is deployed with Contact Monitoring, users also include any keys they've looked up in contact_keys, potentially omitting any that they reasonably expect will not produce new monitoring data.¶

The Transparency Log responds with a MonitorResponse structure:¶

struct {
  PrefixProof prefix_proof;
  opaque commitment<Hash.Nh>;
} ContactProofStep;

struct {
  ContactProofStep steps<0..2^8-1>;
  InclusionProof inclusion;
} ContactProof;

struct {
  FullTreeHead full_tree_head;
  SearchProof search_proofs<0..2^16-1>;
  select (Configuration.mode) {
    case contactMonitoring:
      ContactProof contact_proofs<0..2^16-1>;
  };
} MonitorResponse;

Each proof in search_proofs represents a search for the most recent version of the corresponding key in search_keys. If MonitorRequest.last is populated, any search steps in SearchProof.steps for entries of the log before last are omitted to save space.¶

The elements of contact_proofs also correspond one-to-one with the elements of contact_keys. Each ContactProof is meant to convince the user that the key they looked up is still properly included in the log and has not been surreptitiously concealed.¶

The steps of a ContactProof represent the parents of the entry that contain the specified version of the search key. That is, the parents of an entry are defined as the log entries that are accessed while following a binary search to the given entry, before the entry itself is reached. However, if MonitorRequest.last is populated, then any parents before last are omitted to save space.¶

Each step contains a prefix_proof which is a search for the user-specified key in the prefix tree rooted at that parent, along with the commitment contained in the parent. Users verify that the prefix_proof is an inclusion proof and that the included counter is greater than or equal to what they'd expect, assuring them that the tree is being constructed correctly. The prefix_proof combined with the commitment allow the user to compute the value of each parent's log entry which, combined further with ContactProof.inclusion, produces the root value of the tree for verification against full_tree_head.¶

In full, users verify a monitor response by following these steps:¶

1. Verify that the length of search_proofs is the same as search_keys. For each proof in search_proof:¶

   1. Evaluate the search proof according to the steps in Section 8.3, which will produce a verdict as to whether the search was executed correctly and also a candidate root value for the tree.¶
   2. Verify that each search arrives at the expected version of the key, at the expected position in the tree (based on the original Update query).¶

2. Ensure that all of the candidate root values are the same. With the candidate root value:¶

   1. Verify the proof in FullTreeHead.consistency, if one is expected.¶
   2. Verify the signature in TreeHead.signature.¶
   3. Verify that the timestamp in TreeHead is sufficiently recent. Additionally, verify that the timestamp and tree_size fields of the TreeHead are greater than or equal to what they were before.¶
   4. If third-party auditing is used, verify auditor_tree_head with the steps described in Section 11.2.¶

3. If contact monitoring is used, verify that the length of contact_proofs is the same as contact_keys. For each proof in contact_proofs:¶

   1. Verify that steps has the expected number of entries, based on any new parents that have been created over the entry being monitored.¶
   2. For each new parent, which should be in steps in the same order that each entry is stored in the log tree, verify that prefix_proof is an inclusion proof and that the included version counter is greater than or equal to the most recent version of the key observed by the user.¶
   3. Compute the log entry represented by each ContactProofStep and evaluate the inclusion proof inclusion with these log entries. Verify that the root value outputted is equal to the candidate root value verified in step 2.¶

Some information is omitted from MonitorResponse in the interest of efficiency, due to the fact that the user would have already seen and verified it as part of conducting other queries. In particular, the VRF output and proof for each search key is not provided, given that it can be cached from the original Search or Update query for the key.¶

Generally, users MUST retain the most recent TreeHead they've successfully verified as part of any query result, and populate the last field of any query request with the tree_size from this TreeHead.¶

11.1. Management

With the Third-party Management deployment mode, a third party is responsible for the majority of the work of storing and operating the log, while the service operator serves mainly to enforce access control and authenticate the addition of new entries to the log. All user queries specified in Section 10 are initially sent by users directly to the service operator, and the service operator proxies them to the third-party manager if they pass access control.¶

The service operator only maintains one private key that is kept secret from the third-party manager, which is the private key corresponding to Configuration.leaf_public_key. This private key is used to sign new entries before they're added to the log.¶

As such, all requests and their corresponding responses from Section 10 are proxied between the user and the third-party manager unchanged with the exception of UpdateRequest, which needs to carry the service operator's signature over the update:¶

struct {
  UpdateRequest request;
  opaque signature<0..2^16-1>;
} ManagerUpdateRequest;

The signature is computed over the UpdateTBS structure from Section 9.¶

11.2. Auditing

With the Third-party Auditing deployment mode, the service operator obtains signatures from a lightweight third-party auditor attesting to the fact that the service operator is constructing the tree correctly. These signatures are provided to users along with the results of their queries.¶

The third-party auditor is expected to run asynchronously, downloading and authenticating a log's contents in the background, so as not to become a bottleneck for the service operator. This means that the signatures from the auditor will usually be somewhat delayed. Applications MUST specify a maximum amount of time after which an auditor signature will no longer be accepted. It MUST also specify a maximum number of entries that an auditor's signature may be behind the most recent TreeHead before it will no longer be accepted. Failing to verify an auditor's signature in a query MUST result in an error that prevent's the query's result from being consumed or accepted by the application.¶

The service operator submits updates to the auditor in batches, in the order that they were added to the log tree:¶

struct {
  opaque index<VRF.Nh>;
  opaque commitment<Hash.Nh>;
} AuditorUpdate;

struct {
  AuditorUpdate updates<0..2^16-1>;
} AuditorRequest;

The index field of each AuditorUpdate contains the VRF output of the search key that was updated and commitment contains the service provider's commitment to the update. The auditor responds with:¶

struct {
  TreeHead tree_head;
} AuditorResponse;

The tree_head field contains a signature from the auditor's private key, corresponding to Configuration.auditor_public_key, over the serialized TreeHeadTBS structure. The tree_size field of the TreeHead is equal to the number of entries processed by the auditor and the timestamp field is set to the time the signature was produced (in milliseconds since the Unix epoch).¶

The auditor TreeHead from this response is provided to users wrapped in the following struct:¶

struct {
  TreeHead tree_head;
  opaque root_value<Hash.Nh>;
  ConsistencyProof consistency;
} AuditorTreeHead;

The root_value field contains the root hash of the tree at the point that the signature was produced and consistency contains a consistency proof between the tree at this point and the most recent TreeHead provided by the service operator.¶

To check that an AuditorTreeHead structure is valid, users follow these steps:¶

1. Verify the signature in TreeHead.signature.¶
2. Verify that TreeHead.timestamp is sufficiently recent.¶
3. Verify that TreeHead.tree_size is sufficiently close to the most recent tree head from the service operator.¶
4. Verify the consistency proof consistency between this tree head and the most recent tree head from the service operator.¶

12.1. Contact Monitoring

Contact Monitoring works by splitting the monitoring burden between both the owner of a key and those that look it up. Stated as simply as possible, the monitoring obligations of each party are:¶

1. The key owner, on a regular basis, searches for the most recent version of the key in the log. They verify that this search results in the expected version of the key, at the expected position in the log.¶
2. The user that looks up a key, whenever a new parent is established on the key's direct path, searches for the key in the prefix tree stored in this new parent. They verify that the version counter returned is greater than or equal to the expected version.¶

To understand why this is secure, we look at what happens when the service operator tampers with the log in different ways.¶

First, say that the service operator attempts to cover up the latest version of a key, with then goal of causing a "most recent version" search for the key to resolve in a lower version. To do this, the service operator must add a parent over the latest version of the key with a prefix tree that contains an incorrect version counter. Left unchanged, the key owner will observe that the most recent version of their key is no longer available the next time they perform monitoring. Alternatively, the service operator could add the new version of the key back at a later position in the log. But even so, the key owner will observe that the key's position has changed the next time they perform monitoring. The service operator is unable to restore the latest version of the key without violating the log's append-only property or presenting a forked view of the log to different users.¶

Second, say that the service operator attempts to present a fake new version of a key, with the goal of causing a "most recent version" search for the key to resolve to the fake version. To do this, the service operator can simply add the new version of the key as the most recent entry to the log, with the next highest version counter. Left unchanged, or if the log continues to be constructed correctly, the key owner will observe that a new version of their key has been added without their permission the next time they perform monitoring. Alternatively, the service operator can add a parent over the fake version with an incorrect version counter to attempt to conceal the existence of the fake entry. However, the user that previously consumed the fake version of the key will detect this attempt at concealment the next time they perform monitoring.¶

12.2. Third-party Management

Third-party Management works by separating the construction of the log from the ability to approve which new entries are added to the log, such that tricking users into accepting malicious data requires the collusion of both parties.¶

The service operator maintains a private key that signs new entries before they're added to the log, which means that it has the ability to sign malicious new entries and have them successfully published. However, without the collusion of the third-party manager to later conceal those entries by constructing the tree incorrectly, their existence will be apparent to the key owner the next time they perform monitoring.¶

Similarly, while the third-party manager has the ability to construct the tree incorrectly, it cannot add new entries on its own without the collusion of the service operator. Without access to the service operator's signing key, the third-party manager can only attempt to selectively conceal the latest version of a key from certain users. However, as discussed in Section 12.1, this is also apparent to the key owner through monitoring.¶

12.3. Third-party Auditing

Third-party Auditing works by requiring users to verify a signature from a third-party auditor attesting to the fact that the service operator has been constructing the tree correctly.¶

While the service operator can still construct the tree incorrectly and temporarily trick users into accepting malicious data, an honest auditor will no longer provide its signatures over the tree at this point. Once there are no longer any sufficiently recent auditor tree roots, the log will become non-functional as the service operator won't be able to produce any query results that would be accepted by users.¶

13.1. KT Ciphersuites

TODO¶

13.2. KT Designated Expert Pool

TODO¶