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.¶

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 executing the background monitoring protocol requires an amount of work 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, although migrating from a log operating in one deployment mode to another is possible if it becomes necessary (see Section 12.2).¶

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 service 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.¶

Every key stored in the tree is required to have the same length in bits, which allows every leaf node to exist at the same level of the tree (that is, every leaf has a direct path that's the same length). This effectively prevents users from being able to infer the total number of key-value pairs stored in the tree.¶

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 the leaf node 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, the parent's missing child is replaced with a series of intermediate nodes for each remaining bit of the search key, followed by a new leaf. If the search terminates at the leaf corresponding to the search key (indicating that this search key already has a value in the tree), the old leaf value is simply replaced with a new one.¶

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 pair of integers: a counter with the number of times the key has been updated, and the position in the log of the first instance of the key. Importantly, the root value of the prefix tree after adding the new key or updating the counter/position pair 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 efficiently authenticate searches.¶

To search the combined structure, the server first provides the user with the position of the first instance of the key in the log. The user then follows a binary search for the log entry where looking up the search key in the prefix tree at that entry yields the desired version counter. As such, the entry that a user arrives at through binary search contains the update with the key-value pair that the user is looking for, even though the log itself is not sorted.¶

Providing the position of the first instance of the key in the log is necessary because the prefix tree structure used isn't able to provide proofs of non-inclusion (which would leak information about the number of keys stored in the prefix tree). Without proofs of non-inclusion, users aren't able to lookup the same key in any version of the prefix tree -- only versions of the prefix tree that were created after the key was initially added to the log. Because the server provides this position, users are able to restrict their binary search to only touching log entries where the search key can be successfully looked up in the prefix tree.¶

Following a 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 rely on an implicit binary tree structure constructed over the leaves of the log tree (distinct from the structure of the log tree itself).¶

# The exponent of the largest power of 2 less than x. Equivalent to:
#   int(math.floor(math.log(x, 2)))
def log2(x):
    if x == 0:
        return 0
    k = 0
    while (x >> k) > 0:
        k += 1
    return k-1

# The level of a node in the tree. Leaves are level 0, their parents
# are level 1, etc. If a node's children are at different levels,
# then its level is the max level of its children plus one.
def level(x):
    if x & 0x01 == 0:
        return 0
    k = 0
    while ((x >> k) & 0x01) == 1:
        k += 1
    return k

def left_step(x):
    k = level(x)
    if k == 0:
        raise Exception('leaf node has no children')
    return x ^ (0x01 << (k - 1))

def right_step(x):
    k = level(x)
    if k == 0:
        raise Exception('leaf node has no children')
    return x ^ (0x03 << (k - 1))

def move_within(x, start, n):
    while x < start or x >= n:
        if x < start: x = right_step(x)
        else: x = left_step(x)
    return x

# The root index of a search, if the first instance of a key is at
# `start` and the log has `n` entries.
def root(start, n):
    return move_within((1 << log2(n)) - 1, start, n)

# The left child of an intermediate node.
def left(x, start, n):
    return move_within(left_step(x), start, n)

# The right child of an intermediate node.
def right(x, start, n):
    return move_within(right_step(x), start, n)

7.1. Commitment

As discussed in Section 5, commitments are stored in the leaves of the log tree and correspond to updated key-value pairs. Commitments are computed with HMAC [RFC2104], using the hash function specified by the ciphersuite. To produce a new commitment, the application generates a random 16 byte value called opening and computes:¶

commitment = HMAC(fixedKey, CommitmentValue)

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

d821f8790d97709796b4d7903357c3f5

and CommitmentValue is specified as:¶

struct {
  opaque opening<16>;
  opaque search_key<0..2^8-1>;
  UpdateValue update;
} CommitmentValue;

This fixed key allows the HMAC function, and thereby the commitment scheme, to be modeled as a random oracle. The search_key field of CommitmentValue contains the search key being updated (the search key provided by the user, not the VRF output) and the update field contains the value of the update.¶

The output value commitment may be published, while opening 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;
    uint64 position;
} PrefixLeaf;

where key is the VRF-output search key, counter is the counter of times that the key has been updated (starting at 0 for a key that was just created), position is the position in the log of the first occurrence of this key, 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 standIn(seed, level)
  else if node.type == leafNode:
    return Hash(0x00 || node.key || node.counter || node.position)
  else if node.type == parentNode:
    return node.value

where Hash denotes the ciphersuite hash function. Whenever a parent's left or right child is missing, a stand-in value is computed from a random seed. The stand-in value is computed as:¶

standIn(seed, level):
  return Hash(0x02 || seed || level)

The seed value is a randomly sampled byte string of 16 bytes and level is an 8-bit integer that represents the level of the prefix tree where the stand-in value is stored.¶

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 node.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;
  int64 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),
  (255)
} 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;
  int64 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 relevant LogLeaf or LogParent structures through the nodeValue function in Section 7.3. For individual inclusion proofs, the contents of the elements array is kept in bottom-to-top order. For batch inclusion proofs, 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^8-1>;
} ConsistencyProof;

Again, each NodeValue is computed by passing the relevant 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:¶

struct {
  NodeValue elements<8*VRF.Nh>;
  uint32 counter;
} PrefixProof;

The elements array consists of the copath of the leaf node, in bottom-to-top order. That is, the leaf's sibling would be first, followed by the leaf's parent's sibling, and so on. In the event that a node is not present, then the random value generated when computing the parent's value is provided instead.¶

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.¶

The position field of the PrefixLeaf structure isn't provided in PrefixProof to save space, as this value is expected to be the same across several proofs.¶

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>;
} ProofStep;

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

Each ProofStep structure in steps is one leaf that was inspected as part of the binary search. The steps of the binary search are determined by starting with the "middle" leaf (according to the root function in Section 4.3.1), which represents the first node touched by the search. From there, the user moves incrementally left or right, based on the version counter found in each previous step.¶

The prefix_proof field of a ProofStep 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.¶

The proof can be verified by checking that:¶

1. The elements of steps represent a monotonic series over the leaves of the log, and¶

2. The steps array has the expected number of entries (no more or less than are necessary to execute 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.¶

struct {
  opaque search_key<0..2^8-1>;
  optional<uint32> version;
  optional<Consistency> consistency;
} SearchRequest;

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

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

struct {
  FullTreeHead full_tree_head;
  opaque vrf_proof<0..2^16-1>;
  SearchProof search;

  opaque opening<16>;
  UpdateValue value;
} SearchResponse;

If consistency is present, then the Transparency Log MUST provide a consistency proof between the current tree and the tree when it had Consistency.last entries, in the consistency field of FullTreeHead. If consistency is present, and its distinguished field is present, then the Transparency Log MUST provide a consistency proof between the current tree and the tree when it had Consistency.distinguished entries, in the distinguished field of FullTreeHead.¶

Users verify a search response by following these steps:¶

1. Evaluate the VRF proof in vrf_proof against the requested search key SearchRequest.search_key to obtain the search 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. Verify that the commitment in the terminal search step opens to SearchResponse.value with opening SearchResponse.opening.¶

4. 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.¶

5. If the user has monitoring information for this search key (because they own it or are performing Contact Monitoring), verify that SearchProof.position is the same as in previous requests, and that the entry's version and position in the log are consistent with other known versions.¶

Depending on the deployment mode of the Transparency Log, the value field may or may not require additional verification, specified in Section 9, before its contents may be consumed.¶

To be able to later perform monitoring, users retain the claimed position of the key's first occurrence in the log, SearchProof.position. They also retain, for each version of the key observed, the version number and its position in the log. Users MUST retain this information if the Transparency Log's deployment mode is Contact Monitoring, and they SHOULD retain the entire SearchResponse structure to assist with debugging or to provide non-repudiable proof if misbehavior is detected. If one of the third-party modes is being used, users MAY retain this information to perform Contact Monitoring even though it is not required.¶

10.2. Update

Users initiate an Update operation by submitting an UpdateRequest to the Transparency Log containing the new key and value to store.¶

struct {
  opaque search_key<0..2^8-1>;
  opaque value<0..2^32-1>;
  optional<Consistency> consistency;
} UpdateRequest;

If the request is acceptable by application-layer policies, the Transparency Log adds the new key-value pair to the log and returns an UpdateResponse structure:¶

struct {
  FullTreeHead full_tree_head;
  opaque vrf_proof<0..2^16-1>;
  SearchProof search;

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

Users verify the UpdateResponse as if it were a SearchResponse for the most recent version of search_key. To aid verification, the update response provides the UpdatePrefix structure necessary to reconstruct the UpdateValue.¶

Users MUST retain the information required to perform monitoring as described in Section 10.1.¶

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.¶

struct {
  opaque search_key<0..2^8-1>;
  uint64 entries<0..2^8-1>;
} MonitorKey;

struct {
  MonitorKey owned_keys<0..2^8-1>;
  MonitorKey contact_keys<0..2^8-1>;
  optional<Consistency> consistency;
} MonitorRequest;

Users include each of the keys that they own in owned_keys. If the Transparency Log is deployed with Contact Monitoring (or simply if the user wants a higher degree of confidence in the log), they also include any keys they've looked up in contact_keys.¶

Each MonitorKey structure contains the key being monitored in search_key, and a list of entries in the log tree corresponding to the keys of the map described in Section 4.3.2.¶

The Transparency Log verifies the MonitorRequest by following these steps, for each MonitorKey structure:¶

1. Verify that the requested keys in owned_keys and contact_keys are all distinct.¶

2. Verify that the user owns every key in owned_keys, and is allowed to lookup every key in contact_keys, based on the application's policy.¶

3. Verify that each entries array is sorted in ascending order.¶

4. Verify that the entries in each entries array are all between the initial position of the requested key and the end of the log.¶

5. Verify each entry lies on the direct path of different versions of the key.¶

If the request is valid, the Transparency Log responds with a MonitorResponse structure:¶

struct {
  ProofStep steps<0..2^8-1>;
} MonitorProof;

struct {
  FullTreeHead full_tree_head;
  MonitorProof owned_proofs<0..2^8-1>;
  MonitorProof contact_proofs<0..2^8-1>;
  InclusionProof inclusion;
} MonitorResponse;

The elements of owned_proofs and contact_proofs correspond one-to-one with the elements of owned_keys and contact_keys. Each MonitorProof 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 MonitorProof consist of the proofs required to update the user's monitoring data following the algorithm in Section 4.3.2, including proofs along the current frontier of the log. The steps are provided in the order that they're consumed by the monitoring algorithm. If same proof is consumed by the monitoring algorithm multiple times, it is provided in the MonitorProof structure only the first time. Proofs along the frontier are provided from left to right, excluding any proofs that have already been provided, and excluding any entries of the frontier which are to the left of the leftmost entry being monitored.¶

Users verify a MonitorResponse by following these steps:¶

1. Verify that the lengths of owned_proofs and contact_proofs are the same as the lengths of owned_keys and contact_keys.¶

2. For each MonitorProof structure, evalute the monitoring algorithm in Section 4.3.2. Abort with an error if the monitoring algorithm detects that the tree is constructed incorrectly, or if there are fewer or more steps provided than would be expected.¶

3. Construct a candidate root value for the tree by combining the PrefixProof and commitment of ProofStep, with the provided inclusion proof.¶

4. Verify that all of the candidate root values are the same. With the candidate root value, verify FullTreeHead as in Section 10.1.¶

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 proof for each search key is not provided, or each key's initial position in the log, given that both of these can be cached from the original Search or Update query for the key.¶

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. The service operator MUST maintain its own records (independent of the third-party manager) for the most recent version of each key, for the purpose of producing this signature. The service operator SHOULD also attempt to proactively detect forks presented by the third-party manager.¶

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 responses for 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. Both of these parameters SHOULD be small relative to the log's normal operating scale so that misbehavior can be detected quickly.¶

Failing to verify an auditor's signature in a query MUST result in an error that prevents the query's response 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:¶

enum {
  reserved(0),
  newTree(1),
  emptyTree(2),
  differentKey(3),
  sameKey(4),
  (255)
} AuditorProofType;

struct {
  AuditorProofType proof_type;
  select (AuditorProof.proof_type) {
    case newTree:
    case emptyTree:
      opaque old_seed<16>;
    case differentKey:
      NodeValue copath<0..2^8-1>;
      opaque old_seed<16>;
    case sameKey:
      NodeValue copath<0..2^8-1>;
      uint32 counter;
      uint64 position;
  };
} AuditorProof;

enum {
  reserved(0),
  real(1),
  fake(2),
  (255)
} AuditorUpdateType;

struct {
  AuditorUpdateType update_type;
  opaque index<VRF.Nh>;
  opaque seed<16>;
  opaque commitment<Hash.Nh>;
  AuditorProof proof;
} AuditorUpdate;

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

The update_type field of each AuditorUpdate specifies whether the update was real or fake (see Section 12.3). Real updates genuinely affect a leaf node of the prefix tree, while fake updates only change the random stand-in value for a non-existent child. The index field contains the VRF output of the search key that was updated, seed contains the seed used to compute new random stand-in values for non-existent children in the prefix tree, and commitment contains the service provider's commitment to the update. The proof field contains a cryptographic proof with the information necessary to compute both the current prefix tree root value, and the prefix tree root value after the update has been applied.¶

The AuditorProof structure represents the result of searching for AuditorUpdate.index in the prefix tree. The proof_type field specifies whether the search results in:¶

• newTree: no search was done because this is the first modification to the tree.¶

• emptyTree: no search was done because there are no populated leaf nodes in the prefix tree, though there's a stand-in value for the root which can be computed with old_seed.¶

• differentKey: the search terminates at a stand-in value in the copath of another key. The copath for AuditorUpdate.index, up to and including the first bit difference between the two keys, is given in copath. The seed for computing the stand-in value is provided in old_seed.¶

• sameKey: the search terminates at a populated leaf node for AuditorUpdate.index. The copath (excluding stand-in values, which can be computed with AuditorUpdate.seed) is given in copath. The version and position fields of the leaf node are also given.¶

An auditor processes a single AuditorUpdate by following these steps:¶

1. Evaluate the provided AuditorProof and verify that it's consistent with the current prefix tree root.¶

2. Use the information in the proof, along with AuditorUpdate.seed, to determine the new prefix tree root. The auditor MUST return an error and refuse to continue if the proof_type field is sameKey but the update_type is fake.¶

3. Combine the new prefix tree root with the provided commitment to produce the leaf hash value.¶

4. Combine the leaf hash value with the current log root to produce the new log root.¶

With all AuditorUpdate structures processed, 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 an AuditorTreeHead struct:¶

struct {
  opaque root_value<Hash.Nh>;
  ConsistencyProof consistency;
} AuditorContext;

struct {
  TreeHead tree_head;
  optional<AuditorContext> context;
} AuditorTreeHead;

The context field is populated when the tree_size of the auditor's TreeHead is less than the size of the most recent TreeHead provied to the user by the service provider. 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 less than or equal to, and sufficiently close to the most recent tree head from the service operator.¶

4. If required, verify the consistency proof AuditorContext.consistency between this tree head and the most recent tree head from the service operator.¶

12.1. Detecting Forks

It is sometimes possible for a Transparency Log to present forked views of data to different users. This means that, from an individual user's perspective, a log may appear to be operating correctly in the sense that all of a user's Monitor operations succeed. However, the Transparency Log has presented a view to the user that's not globally consistent with what it has shown other users. As such, the log may be able to associate data with keys without the key owner's awareness.¶

The protocol is designed such that users always remember the last TreeHead that they observed when querying the log, and require subsequent queries to prove consistency against this tree head. As such, users always stay on an individually-consistent view of the log. If a user is ever presented with a forked view, they hold on to this forked view forever and reject the output of any subsequent queries that are inconsistent with it.¶

This provides ample opportunity for users to detect when a fork has been presented, but isn't in itself sufficient for detection. To detect forks, users must either use out-of-band communication with other users or anonymous communication with the Transparency Log.¶

With out-of-band communication, a user obtains a "distinguished" TreeHead, for example by looking up a well-known key. The user then sends the root hash of the TreeHead to other users over some out-of-band communication channel (for example, an in-app screen with a QR code / scanner). The other users check that the root hash matches their own view of the log. If the TreeHead verifies successfully on its own but doesn't match a user's view of the log, this proves the existence of a fork.¶

With anonymous communication, a user first obtains a "distinguished" TreeHead. They then send the same request, omitting any identifying information and leaving the consistency field empty, over an anonymous channel. If the log responds with a different TreeHead over the anonymous channel, this proves the existence of a fork.¶

In the event that a fork is successfully detected, the two signatures on the differing views of the log provide non-repudiable proof of log misbehavior which can be published.¶

12.2. Combining Multiple Logs

There are some cases where it may make sense to operate multiple cooperating log instances. For example, a service provider may decide that it's prudent to migrate to a new deployment mode. They can do this by creating a new log instance operating under the new deployment mode, and gradually migrating their data from the old log to the new log while users are able to query both. In another case, a service provider may choose to operate multiple logs to improve their ability to scale or to provide higher availability. Similarly, a federated system may allow each party in the federation to operate their own log for their own users.¶

When this happens, all users in the system MUST have a consistent policy for executing Search, Update, and Monitor queries against the multiple logs that maintains the high-level security guarantees of KT:¶

• If all logs behave honestly, then users observe a globally-consistent view of the data associated with each key.¶

• If any log behaves dishonestly such that the prior guarantee is not met (some users observe data associated with a key that others do not), this will be detected either immediately or in a timely manner by background monitoring.¶

In the specific case of migrating from an old log to a new one, this policy may look like:¶

1. Search queries should be executed against the old log first, and then against the new log only if the most recent version of a key in the old log is a tombstone.¶

2. Update queries should only be executed against the new log, adding a tombstone entry to the old log if one hasn't been already created.¶

3. Both logs should be monitored as they would be if they were run individually. Once the migration has completed and the old log has stopped accepting changes, the old log SHOULD stay operational long enough for all users to complete their monitoring of it (keeping in mind that some users may be offline for a significant amount of time).¶

Placing a tombstone entry for each key in the old log gives users a clear indication as to which log contains the most recent version of a key and prevents them from incorrectly accepting a stale version if the new log rejects a search query.¶

12.3. Obscuring Update Rate

While the protocol already prevents outside observers from determining the total number of key-value pairs stored by a server, some applications may also wish to obscure the frequency of updates. Revealing the frequency of updates may make it possible to deduce the total size of the tree, or it may expose sensitive information about an application's usage patterns. However, fully hiding the frequency of updates is impossible with any hash-based KT construction. Instead, an application may pad real updates with "fake" random updates, such that the update rate measured by observers is fixed to an arbitrary upper-bound value.¶

The service provider produces a fake update by first choosing three random values: one to represent the VRF output of the key being updated, one to represent the commitment to the update, and one which will be the seed for generating a new stand-in value in the prefix tree. It then traverses the prefix tree according to the random VRF output, and replaces the first stand-in value it reaches with the one generated from the chosen seed. Note that this means that fake updates don't affect a leaf of the prefix tree. Finally, the service provider adds a new entry to the log tree with the random commitment value and the updated prefix tree root.¶

The VRF output and commitment value can be chosen randomly, instead of being computed with the actual VRF or commitment scheme, because the server will never be required to actually open either of these values. No legitimate search for a key will ever terminate at this entry in the log.¶

13.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 the 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.¶

13.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 13.1, this is also apparent to the key owner through monitoring.¶

13.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 responses that would be accepted by users.¶

14.1. KT Ciphersuites

uint16 CipherSuite;

TODO¶

14.2. KT Designated Expert Pool

TODO¶