Key Transparency Protocol

Brendan McMillion Email: brendanmcmillion@gmail.com · label-version pairs

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

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

  uint64 max_ahead;
  unit64 max_behind;
  uint64 reasonable_monitoring_window;
  optional<uint64> maximum_lifetime;
} Configuration;

struct {
  Configuration config;
  uint64 tree_size;
  opaque root[Hash.Nh];
} TreeHeadTBS;

struct {
  select (Configuration.mode) {
    case thirdPartyManagement:
      opaque signature<0..2^16-1>;
  };
} UpdatePrefix;

struct {
  UpdatePrefix prefix;
  opaque value<0..2^32-1>;
} UpdateValue;

struct {
  opaque label<0..2^8-1>;
  uint32 version;
  opaque value<0..2^32-1>;
} UpdateTBS;

commitment = HMAC(Kc, CommitmentValue)

struct {
  opaque opening[Nc];
  opaque label<0..2^8-1>;
  UpdateValue update;
} CommitmentValue;

struct {
  opaque label<0..2^8-1>;
  uint32 version;
} VrfInput;

struct {
  uint64 timestamp;
  opaque prefix_tree[Hash.Nh];
} LogLeaf;

struct {
  opaque value[Hash.Nh];
} LogParent;

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.timestamp || node.prefix_tree)
  else if node.type == parentNode:
    return node.value

struct {
    opaque vrf_output[VRF.Nh];
    opaque commitment[Hash.Nh];
} PrefixLeaf;

struct {
  opaque value[Hash.Nh];
} PrefixParent;

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

nodeValue(node):
  if node.type == emptyNode:
    return 0 // all-zero vector of length Hash.Nh
  else if node.type == leafNode:
    return Hash(0x00 || node.vrf_output || node.commitment)
  else if node.type == parentNode:
    return node.value

opaque NodeValue[Hash.Nh];

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

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

struct {
  PrefixSearchResultType result_type;
  select (PrefixSearchResult.result_type) {
    case nonInclusionLeaf:
      PrefixLeaf leaf;
  };
  uint8 depth;
} PrefixSearchResult;

struct {
  PrefixSearchResult results<0..2^8-1>;
  NodeValue elements<0..2^16-1>;
} PrefixProof;

struct {
  uint64 timestamps<0..2^8-1>;
  PrefixProof prefix_proofs<0..2^8-1>;
  NodeValue prefix_roots<0..2^8-1>;
} CombinedTreeProof;

struct {
  TreeHead tree_head;
  select (Configuration.mode) {
    case thirdPartyAuditing:
      AuditorTreeHead auditor_tree_head;
  };
} FullTreeHead;

struct {
  optional<uint32> last;

  opaque label<0..2^8-1>;
  optional<uint32> version;
} SearchRequest;

struct {
  opaque proof[VRF.Np];
  opaque commitment[Hash.Nh];
} BinaryLadderStep;

struct {
  FullTreeHead full_tree_head;

  optional<uint32> version;
  BinaryLadderStep binary_ladder<0..2^8-1>;
  CombinedTreeProof search;
  InclusionProof inclusion;

  opaque opening[Nc];
  UpdateValue value;
} SearchResponse;

struct {
  optional<uint32> last;

  opaque label<0..2^8-1>;
  opaque value<0..2^32-1>;
} UpdateRequest;

struct {
  FullTreeHead full_tree_head;

  BinaryLadderStep binary_ladder<0..2^8-1>;
  CombinedTreeProof search;
  InclusionProof inclusion;

  opaque opening[Nc];
  UpdatePrefix prefix;
} UpdateResponse;

struct {
  uint64 position;
  uint32 version;
} MonitorMapEntry;

struct {
  opaque label<0..2^8-1>;
  MonitorMapEntry entries<0..2^8-1>;
  optional<uint64> rightmost;
} MonitorLabel;

struct {
  optional<uint32> last;
  MonitorLabel labels<0..2^8-1>;
} MonitorRequest;

struct {
  uint32 versions<0..2^8-1>;
} MonitorLabelVersions;

struct {
  FullTreeHead full_tree_head;
  MonitorLabelVersions label_versions<0..2^8-1>;
  CombinedTreeProof monitor;
  InclusionProof inclusion;
} MonitorResponse;

uint16 CipherSuite;

# 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

# The root index of a search if the log has `n` entries.
def root(n):
    return (1 << log2(n)) - 1

# The left child of an intermediate node.
def left(x):
    k = level(x)
    if k == 0:
        raise Exception('leaf node has no children')
    return x ^ (0x01 << (k - 1))

# The right child of an intermediate node.
def right(x, n):
    k = level(x)
    if k == 0:
        raise Exception('leaf node has no children')
    x = x ^ (0x03 << (k - 1))
    while x >= n:
        x = left(x)
    return x

Internet-Draft	Key Transparency Protocol	February 2025
McMillion & Linker	Expires 1 September 2025	[Page]