Transparency logs, explained

A transparency log is a tamper-evident record. Its operator can add entries but cannot remove, reorder or rewrite them unnoticed, because every reader can check two things alone: that an entry is in the log, and that today’s log extends yesterday’s. Certificate Transparency, the Go checksum database and Sigstore’s signature log all work this way.

Entries become leaves

Each entry is hashed into a leaf of a Merkle tree, and each pair of hashes into the node above them, up to a single root hash. A leaf and a node are hashed with different prefixes, so one cannot pass for the other. Change one byte of any entry and its leaf hash changes, then every hash on the way to the root.

Leaves fill tiles

The tree is stored as tiles: each tile holds 256 hashes of one level of the tree. A full tile never changes, and the tile at the log’s right edge is published as a partial tile, which is replaced by a longer one as entries arrive. The entries themselves are stored in bundles of 256 beside the tiles. Every tile and bundle has a fixed path, so a log is a directory of static files that any web server, bucket or CDN can serve, and caches can keep forever.

Checkpoints commit

The log regularly signs its size and root hash. That signed checkpoint is a short text: the log’s name (its origin), the number of entries, the root hash, then one signature line per signer. Because the root depends on every entry, the signature commits the log to all of them, in order, for good.

Proofs replace trust

A reader does not need the whole log to check it. An inclusion proof shows that an entry is in the tree under a checkpoint: it is the hashes of the subtrees beside the entry’s path to the root, and hashing them in order with the entry must give the checkpoint’s root. In the figure, entry 5 needs three hashes, not eight entries; a log of a billion entries needs about 30.

A consistency proof shows that a newer checkpoint extends an older one, with nothing removed or changed. A client that keeps the last checkpoint it saw, and checks each new one this way, knows the log has only grown.

Receipts travel

A receipt bundles an entry’s index, its inclusion proof and the checkpoint the proof is relative to. Whoever holds the receipt, the entry and the log’s public key can check it offline, without asking the log anything. webtessera’s append() returns one, verified, in the C2SP tlog-proof format.

Witnesses keep it honest

A log could still show one history to some readers and another to the rest. Witnesses prevent that: they are independent services that check each new checkpoint is consistent with the last one they saw, and cosign it. A reader who requires cosignatures from enough witnesses knows that everyone sees the same log. A monitor goes further, and reads every entry.

Specifications

• RFC 6962, section 2.1: the Merkle tree, its hashes and its proofs.
• C2SP signed-note and tlog-checkpoint: the checkpoint’s text and signatures.
• C2SP tlog-tiles: the tiles, the bundles and their paths.
• C2SP tlog-proof: the receipt.
• C2SP tlog-witness and tlog-cosignature: witnesses and their cosignatures.
• Transparent Logs for Skeptical Clients, by Russ Cox: the design, explained from first principles.

To see these pieces in a running log, append to the log on the home page. To build one, start with the safe API.