Key Transparency Protocol

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

struct {
    uint8 present;
    select (present) {
        case 0: struct{};
        case 1: T value;
    };
} optional<T>;

def compare_roots(roots_a, roots_b):
    if len(roots_a) != len(roots_b):
        raise Exception('lists must be the same size')

    N = len(roots_a)

    for x in range(N):
        if roots_a[:N-x] == roots_b[x:] or roots_b[:N-x] == roots_a[x:]:
            return True

    raise Exception('no valid overlap found')

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:
      uint64 max_auditor_lag;
      uint64 auditor_start_pos;
      opaque auditor_public_key<0..2^16-1>;
  };

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

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

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

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

enum {
  reserved(0),
  same(1),
  updated(2),
  (255)
} FullTreeHeadType;

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

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

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

struct {
  Configuration config;
  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>;
  uint32 version;
  UpdateValue update;
} CommitmentValue;

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

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

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

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

leaf.value = Hash(0x02 || vrf_output || commitment)

parent.value = Hash(0x03 || parent.leftChild.value || parent.rightChild.value)

opaque HashValue[Hash.Nh];

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

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

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

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

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

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

  InclusionProof inclusion;
} CombinedTreeProof;

struct {
  optional<uint64> last;

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

struct {
  opaque proof[VRF.Np];
  optional<HashValue> commitment;
} BinaryLadderStep;

struct {
  FullTreeHead full_tree_head;

  select (SearchRequest.version) {
    case absent:
      uint32 version;
  };
  opaque opening[Nc];
  UpdateValue value;

  BinaryLadderStep binary_ladder<0..2^8-1>;
  CombinedTreeProof search;
} SearchResponse;

struct {
  uint64 position;
  uint32 version;
} MonitorMapEntry;

struct {
  optional<uint64> last;

  opaque label<0..2^8-1>;
  MonitorMapEntry entries<0..2^8-1>;
} ContactMonitorRequest;

struct {
  FullTreeHead full_tree_head;
  CombinedTreeProof monitor;
} ContactMonitorResponse;

struct {
  optional<uint64> last;

  opaque label<0..2^8-1>;
  uint64 start;
} OwnerInitRequest;

struct {
  FullTreeHead full_tree_head;

  uint32 greatest_versions<0..2^8-1>;
  BinaryLadderStep binary_ladder<0..2^16-1>;
  CombinedTreeProof init;
} OwnerInitResponse;

struct {
  optional <uint64> last;

  opaque label<0..2^8-1>;
  MonitorMapEntry entries<0..2^8-1>;
  uint64 start;
  optional<uint32> greatest_version;
} OwnerMonitorRequest;

struct {
  FullTreeHead full_tree_head;
  CombinedTreeProof monitor;
} OwnerMonitorResponse;

struct {
  opaque value<0..2^32-1>;
} LabelValue;

struct {
  optional<uint64> last;

  opaque label<0..2^8-1>;
  optional<uint32> greatest_version;
  LabelValue values<0..2^8-1>;
} UpdateRequest;

struct {
  opaque opening[Nc];
  UpdateSuffix suffix;
} UpdateInfo;

struct {
  FullTreeHead full_tree_head;

  uint64 position;
  LabelValue values<0..2^8-1>;
  UpdateInfo info<0..2^8-1>;

  BinaryLadderStep binary_ladder<0..2^8-1>;
  CombinedTreeProof update;
} UpdateResponse;

struct {
  optional<uint64> last;
  optional<uint64> stop;
} DistinguishedRequest;

struct {
  FullTreeHead full_tree_head;
  CombinedTreeProof distinguished;
} DistinguishedResponse;

enum {
  reserved(0),
  standard(1),
  provisional(2),
  (255)
} CredentialType;

struct {
  opaque label<0..2^8-1>;

  uint32 version;
  opaque opening[Nc];
  UpdateValue value;
  BinaryLadderStep binary_ladder<0..2^8-1>;

  uint64 position;
  CredentialType credential_type;
  select (Credential.credential_type) {
    case standard:
      PrefixProof distinguished;
    case provisional:
      TreeHead tree_head;
      CombinedTreeProof search;
  };
} Credential;

struct {
  uint64 position;
  CombinedTreeProof monitor;
} CredentialUpdate;

struct {
  UpdateRequest request;
  optional<uint64> last;

  opaque label<0..2^8-1>;
  optional<uint32> greatest_version;
  UpdateValue values<0..2^8-1>;

  uint32 signed_version;
} ManagerUpdateRequest;

struct {
  uint64 timestamp;

  PrefixLeaf added<0..2^16-1>;
  PrefixLeaf removed<0..2^16-1>;

  PrefixProof proof;
} AuditorUpdate;

uint16 CipherSuite;
CipherSuite KT_LVL_HASH_SIG = VALUE;

# 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

# Returns the set of versions that would be looked up to establish that n was
# the greatest version of a label that existed.
def base_binary_ladder(n):
    out = []

    # Output powers of two minus one until reaching a value greater than n.
    while True:
        value = (1 << len(out)) - 1
        out.append(value)
        if value > n:
            break

    # Binary search between the established lower and upper bounds.
    lower_bound = out[-2]
    upper_bound = out[-1]

    while lower_bound+1 < upper_bound:
        value = (lower_bound + upper_bound) // 2
        out.append(value)
        if value <= n:
            lower_bound = value
        else:
            upper_bound = value

    return out

# Returns the set of versions that would be looked up in a search binary ladder
# where the target version is t and the greatest version of the label that
# exists in a given version of the prefix tree is n.
def search_binary_ladder(
    t, n,
    left_inclusion = [], right_non_inclusion = []
):
    def would_end(v):
        # (Proof of inclusion for a version greater than t) OR
        # (Proof of non-inclusion for a version less than or equal to t)
        return (v <= n and v > t) or (v > n and v <= t)

    def would_be_duplicate(v):
        return (v in left_inclusion) or (v in right_non_inclusion)

    out = base_binary_ladder(n)
    end = next((i+1 for i,v in enumerate(out) if would_end(v)), len(out))
    filtered_out = [v for v in out[:end] if not would_be_duplicate(v)]

    return filtered_out

# Returns the set of versions that would be looked up in a monitoring binary
# ladder where the monitored version of the label is t.
def monitoring_binary_ladder(t, left_inclusion = []):
    out = base_binary_ladder(t)
    filtered_out = [v for v in out if v <= t and v not in left_inclusion]

    return filtered_out

Internet-Draft	Key Transparency Protocol	July 2026
McMillion & Linker	Expires 7 January 2027	[Page]

Value	Name	R	Ref
0x0000	RESERVED	-	RFC XXXX
0x0001	KT_128_SHA256_P256	Y	RFC XXXX
0x0002	KT_128_SHA256_Ed25519	Y	RFC XXXX
0xF000 - 0xFFFF	Reserved for Private Use	-	RFC XXXX