Key Transparency (KT)¶

1. Overview¶

This system implements Centralized Key Transparency, the same model used by WhatsApp, Google, and Signal. Every device's public key is recorded in an append-only Merkle Tree (powered by Tessera + Torchwood).

Threat Model¶

The system defends against two categories of attacks:

The goal is not to prevent these attacks from happening — it is to detect them after the fact ("catch them red-handed"). The append-only Merkle Tree ensures tmarkdownhat any tampering leaves a permanent, cryptographic trail that cannot be erased.

graph LR
    subgraph "Threats"
        T1["Malicious DevOps<br/>(injects fake key into log)"]
        T2["MitM Attacker<br/>(substitutes key in transit)"]
    end

    subgraph "KT Defenses"
        D1["Append-only Log<br/>(cannot erase evidence)"]
        D2["Checkpoint Signature<br/>(cannot forge log state)"]
        D3["Merkle Inclusion Proof<br/>(proves key is in the tree)"]
        D4["Client Key Comparison<br/>(detects any key change)"]
    end

    T1 -->|"detected by"| D1
    T1 -->|"detected by"| D4
    T2 -->|"detected by"| D3
    T2 -->|"detected by"| D4
    D1 --- D2

2. Architecture¶

2.1 System Components¶

graph TB
    subgraph "KT Server"
        GRPC["gRPC Server<br/>(Register)"]
        HTTP["HTTP Server<br/>(GetPublicKeys, Tile Serving)"]
        LM["Log Manager"]
        TESS["Tessera<br/>(Append-only Merkle Tree)"]
        DISK["POSIX Storage<br/>(Tiles + Checkpoint)"]
    end

    subgraph "Clients"
        APP_A["Alice iOS"]
        APP_B["Bob iOS"]
    end

    subgraph "External"
        API["Ecall API"]
        AUD["Third-Party Auditor"]
    end

    API -- "gRPC: Register" --> GRPC
    APP_A -- "HTTP: GetPublicKeys" --> HTTP
    APP_B -- "HTTP: GetPublicKeys" --> HTTP
    AUD -- "HTTP: GET /checkpoint, /tile/..." --> HTTP
    GRPC --> LM
    HTTP --> LM
    LM --> TESS
    TESS --> DISK

2.2 Registration Flow¶

sequenceDiagram
    participant D as Device (iOS)
    participant API as Ecall API
    participant KT as KT Server

    D->>D: Generate Ed25519 keypair
    D->>D: Store private key in Keychain
    D->>API: Login / Register device
    API->>KT: gRPC Register(userID, deviceID, publicKey)
    KT->>KT: VRF.Prove(userID_deviceID) -> vrfHash
    KT->>KT: entry = vrfHash + newline + publicKey + newline
    KT->>KT: Append entry to Merkle Tree
    KT-->>API: index: 42, vrfHash: "..."
    API->>API: Store publicKeyIndex=42, vrfHash in device record
    API-->>D: Registration success

2.3 Third-Party Auditor Flow¶

sequenceDiagram
    participant AUD as Auditor (Go/Rust)
    participant KT as KT Server (HTTP)

    AUD->>KT: GET /checkpoint
    KT-->>AUD: Signed checkpoint
    AUD->>AUD: Verify checkpoint Ed25519 signature

    loop For each entry index 0..treeSize-1
        AUD->>KT: GET /tile/entries/...
        KT-->>AUD: Entry bundle (tile data)
        AUD->>AUD: Parse entry: extract vrfHash, publicKey
        AUD->>AUD: Compute leafHash = SHA256(0x00 || entry)
        AUD->>AUD: VRF.Verify(vrfPublicKey, vrfProof, input)
        AUD->>AUD: Verify leafHash against Merkle tree
    end

    AUD->>AUD: Verify full tree hash == checkpoint rootHash
    AUD->>AUD: Log integrity confirmed or discrepancy found

3. Security Model¶

3.1 Verification Responsibilities¶

3.2 Why VRF Verification Is Server-Side Only¶

The VRF scheme used is ristretto255-based (filippo.io/mostly-harmless/vrf-r255). There is no native Swift library for this curve. Wrapping C code is fragile and adds maintenance burden. Since the server already holds the VRF private key and can simply re-derive the hash, VRF verification is performed server-side. The client trusts the vrfHash returned by the server but independently verifies everything else (checkpoint signature, Merkle proof, key comparison).

The VRF Public Key exists for third-party auditors — external parties running Go or Rust tools that can verify VRF proofs without trusting the server.

4. Key Material¶

4.1 Key Generation¶

Private key:     PRIVATE+KEY+e2ecall-kt+95d01f0d+AUXu...
Private VRF key: byEHDWjz...
Public key:      e2ecall-kt+95d01f0d+AVJYpVX/pIhNVyoJ4+WTZr0PpvySTELbyLATnWftZBx6
Public VRF key:  tAcYYn1n0+V0OKbeOGaHTh2ta5rrSQwAnwfFp/lyyGU=

4.2 Key Distribution¶

5. Data Formats¶

5.1 Log Entry Format¶

Each entry appended to the Merkle Tree:

<vrfHash_base64>\n<publicKey_base64>\n

The leaf hash is computed per RFC 6962:

LeafHash = SHA256(0x00 || entry_bytes)

Internal (non-leaf) node hashes:

NodeHash = SHA256(0x01 || left_hash || right_hash)

5.2 Checkpoint Format (note)¶

Follows the golang.org/x/mod/sumdb/note format:

e2ecall-kt                          <- origin name
100                                  <- tree size (number of entries)
Um9vdEhhc2hCYXNlNjQ=                <- root hash (base64, 32 bytes)

— e2ecall-kt AZbA...signature...    <- Ed25519 signature line

Signature line format: — <origin> <4-byte-key-id + 64-byte-ed25519-sig in base64>

5.3 Proof Format (c2sp.org/tlog-proof@v1)¶

c2sp.org/tlog-proof@v1              <- header (fixed)
extra QmFzZTY0X1ZSRl9Qcm9vZg==     <- VRF proof bytes (base64, for auditors)
index 42                             <- log index of the entry
SGFzaF8xX0Jhc2U2NA==               <- Merkle sibling hash #1 (base64)
SGFzaF8yX0Jhc2U2NA==               <- Merkle sibling hash #2 (base64)
                                     <- empty line (separator)
e2ecall-kt                           <- checkpoint begins here
100
Um9vdEhhc2hCYXNlNjQ=

— e2ecall-kt AZbA...sig...          <- checkpoint signature

5.4 API Response Format¶

{
  "results": [
    {
      "publicKey": "MCowBQYD...",
      "vrfHash":   "pG7mFJ3CxK8df7R2gY5xN1K9vQz0bHm...",
      "proof":     "c2sp.org/tlog-proof@v1\nextra ...\nindex 42\n..."
    }
  ]
}

6. Server API Reference¶

6.1 gRPC — Register¶

Called by the main API server when a device registers.

service KTService {
  rpc Register(RegisterRequest) returns (RegisterResponse);
}

message RegisterRequest {
  uint64 userID    = 1;
  uint64 deviceID  = 2;
  string publicKey = 3;
}

message RegisterResponse {
  uint64 index = 1;
  string vrfHash = 2;
}

Server logic: 1. Compute VRF.Prove(userID_deviceID) to get vrfHash 2. Format entry: vrfHash + "\n" + publicKey + "\n" 3. Append to Merkle Tree via Tessera 4. Return the assigned index

6.2 HTTP — POST /api/get-public-keys¶

Called by client devices to retrieve public keys and audit proofs directly from KT.

Request:

{
  "targets": [
    { "publicKeyHash": "pG7mFJ3CxK8df7R2gY5xN1K9vQz0bHm..." }
  ]
}

Response:

{
  "results": [
    {
      "publicKey": "base64...",
      "vrfHash":   "base64...",
      "proof":     "c2sp.org/tlog-proof@v1\n..."
    }
  ]
}

Server logic: 1. Read checkpoint and verify its signature 2. For each target publicKeyHash: a. Query local database to find publicKeyIndex, userId, and deviceId b. Read entry at publicKeyIndex from Merkle Tree via torchwood.Client c. Parse entry to extract oldVrfHash and publicKey d. Re-compute VRF.Prove(userID_deviceID) to verify identity binding e. If oldVrfHash != publicKeyHash then return error (identity mismatch) f. Generate Merkle inclusion proof with FormatProofWithExtraData 3. Return list of publicKey, vrfHash, and proof

6.3 HTTP — Static Tile Serving¶

The HTTP server serves the raw Tessera storage directory, enabling direct tile access:

Used by third-party auditors to crawl the entire log.

7. Third-Party Auditor Guide¶

A third-party auditor is an independent process (not the server, not the client) that crawls the entire log and verifies its integrity. It holds the VRF Public Key but NOT the VRF Private Key.

7.1 Prerequisites¶

7.2 What the Auditor Verifies¶

7.3 Implementation (Go)¶

package main

import (
    "context"
    "encoding/base64"
    "fmt"
    "log"
    "strings"

    vrf "filippo.io/mostly-harmless/vrf-r255"
    "filippo.io/torchwood"
    "golang.org/x/mod/sumdb/tlog"
)

func main() {
    // 1. Set up tile reader pointing to KT server
    tf, _ := torchwood.NewTileFetcher("https://kt.example.com/")
    client, _ := torchwood.NewClient(tf)

    // 2. Load public keys
    checkpointVKey := "e2ecall-kt+95d01f0d+AVJYpVX/pIhNVyoJ4+WTZr0PpvySTELbyLATnWftZBx6"
    vrfPubKeyB64 := "tAcYYn1n0+V0OKbeOGaHTh2ta5rrSQwAnwfFp/lyyGU="

    verifier, _ := torchwood.NewCosignatureVerifier(checkpointVKey)
    policy := torchwood.SingleVerifierPolicy(verifier)

    vrfPubKeyBytes, _ := base64.StdEncoding.DecodeString(vrfPubKeyB64)
    vrfPubKey, _ := vrf.NewPublicKey(vrfPubKeyBytes)
    _ = vrfPubKey // used for VRF verification below

    // 3. Fetch and verify checkpoint
    ctx := context.Background()
    cpBytes, _ := tf.ReadEndpoint(ctx, "checkpoint")
    cp, _, _ := torchwood.VerifyCheckpoint(cpBytes, policy)
    fmt.Printf("Verified checkpoint: tree size = %d\n", cp.N)

    // 4. Crawl all entries and verify
    for i, entry := range client.AllEntries(ctx, cp.Tree, 0) {
        parts := strings.SplitN(string(entry), "\n", 3)
        if len(parts) < 2 {
            log.Fatalf("Entry %d: invalid format", i)
        }
        storedVrfHash := parts[0]
        publicKey := parts[1]

        // Leaf hash integrity is already verified internally
        // by client.AllEntries against the Merkle tree

        fmt.Printf("Entry %d: vrfHash=%s... key=%s...\n",
            i, storedVrfHash[:16], publicKey[:16])
    }
    if err := client.Err(); err != nil {
        log.Fatalf("Error crawling entries: %v", err)
    }

    fmt.Printf("Full audit complete: %d entries verified\n", cp.N)
}

7.4 VRF Proof Verification (via API)¶

When individual proofs are fetched via the API, the extra field contains the VRF proof bytes:

// Fetch proof for a specific entry via the HTTP API
resp := httpGet("/api/get-public-keys", targets)

for _, result := range resp.Results {
    // Extract VRF proof from the "extra" field in the proof string
    extraBytes, err := torchwood.ProofExtraData([]byte(result.Proof))
    if err != nil {
        log.Fatalf("Failed to extract VRF proof: %v", err)
    }

    // Reconstruct VRF proof and verify with Public Key
    vrfProof, _ := vrf.UnmarshalProof(extraBytes)
    input := []byte(fmt.Sprintf("%d_%d", userID, deviceID))

    // Verify: does this VRF proof match the claimed identity?
    expectedHash := vrfProof.Hash()
    storedHash, _ := base64.StdEncoding.DecodeString(result.VrfHash)

    if !bytes.Equal(expectedHash, storedHash) {
        log.Fatalf("VRF hash mismatch for user %d_%d!", userID, deviceID)
    }

    // Verify VRF proof was generated by the known VRF key
    ok := vrfPubKey.Verify(input, vrfProof)
    if !ok {
        log.Fatalf("VRF proof invalid for user %d_%d!", userID, deviceID)
    }
}

7.5 Consistency Monitoring¶

To detect split-world attacks (server showing different trees to different observers), the auditor should:

1. Store each verified checkpoint locally (timestamp + tree size + root hash)
2. Fetch the latest checkpoint periodically
3. Verify consistency between the old and new checkpoint:

// Prove that the new tree (size M) contains
// the old tree (size N) as a prefix
oldTree := previousCheckpoint.Tree   // size N
newTree := latestCheckpoint.Tree     // size M

proof, _ := tlog.ProveTree(newTree.N, oldTree.N,
    torchwood.TileHashReaderWithContext(ctx, newTree, tileReader))

err := tlog.CheckTree(
    proof, newTree.N, newTree.Hash, oldTree.N, oldTree.Hash,
)
if err != nil {
    log.Fatal("CONSISTENCY VIOLATION - server rewrote history!")
}

7.6 Gossip Protocol (Optional)¶

For maximum security, multiple auditors and clients should cross-check their observed checkpoints:

graph LR
    A["Auditor A"] -.->|gossip| B["Auditor B"]
    A -.->|gossip| C["Client Alice"]
    B -.->|gossip| C

If any party observes a checkpoint with a different root hash for the same tree size, a split-world attack has been detected.

8. Attack Scenarios & Defenses¶

8.1 Server Operator Creates a Fake Key for Alice (MitM)¶

graph TD
    A["Server operator appends<br/>Fake PublicKey for Alice"] --> B["Fake entry pinned<br/>permanently in Merkle Tree"]
    B --> C["Alice device runs periodic audit"]
    C --> D{"publicKey from server<br/>== localPublicKey?"}
    D -->|YES| E["All clear"]
    D -->|NO| F["RED ALERT<br/>Key mismatch detected!"]

Defense: Client compares the server-returned publicKey against its locally stored key. A mismatch is immediately flagged.

8.2 Server Operator Rewrites Log History¶

Defense: Append-only Merkle Tree. If any past entry is modified, the root hash changes, which breaks: - Merkle inclusion proofs for all clients - Consistency proofs for auditors comparing old vs. new checkpoints

8.3 Split-World Attack¶

Server operator shows Tree A to Alice and Tree B to Bob.

Defense: Checkpoints are signed. If auditors or clients gossip their checkpoints and find different root hashes for the same tree size, the attack is detected.

8.4 Attacker Queries Wrong Identity¶

An attacker tries to query a key for a specific user but attempts to trick the server into returning a different user's key or a fake key.

Defense: Server-side VRF check. The server re-computes the VRF hash using the userID/deviceID found in the database and compares it with the vrfHash stored in the append-only Merkle Tree. If they don't match, the server returns an identity mismatch error, preventing the use of a key that wasn't properly bound to that identity in the log.