## Trusted timestamping with Certificate Transparency style Merkle Trees

**tl;dr** *CT-style Merkle Trees can be used to provide trusted timestamping.*

## What is Trusted Timestamping?

Trusted timestamping is “the process of securely keeping track of the creation and modification time of a document.” For example, a researcher may wish to prove that they made a particular discovery at a particular time.

More formally, researcher `R`

needs to be able to demonstrate to a person `V`

that document `D`

existed at time `T`

.

## Solutions

### Trusted third-party

If there exists a trusted third-party `T3P`

with public key `T3P_PK`

, `R`

can send `hash(D)`

at time `T`

, to which `T3P`

replies with `digitallySigned(T || hash(D), T3P_PK)`

. Later, when `R`

needs to prove `D`

existed at time `T`

, `R`

can reveal `D`

, `T`

, `digitallySigned(T || hash(D), T3P_PK)`

, which `V`

can use to verify that indeed `D`

existed at time `T`

, according to `T3P`

.

We require that `T3P`

be trusted because, at any time, `T3P`

can produce timestamps for any time. For example, when our researcher releases `D`

, the `T3P`

could, in a fit of jealousy, modify `D`

to be authored by the `T3P`

to produce `D'`

, and release `D'`

and `digitallySigned(T-1 || hash(D'), T3P_PK)`

, which would “prove” `D'`

existed before `D`

, and that `R`

wasn’t the original discoverer!

Trusted third-parties are hard to find, however. Even in the case that you trust an entity, you may not trust their ability to not be coerced/exploited into producing invalid timestamps.

### Hash and publish

If there exists a public tamper-evident log `L`

, `R`

can submit `hash(D)`

at time `T`

to `L`

. `L`

records `hash(D)`

at time `T`

in a tamper-evident manner. Later, when `R`

needs to prove `D`

existed at time `T`

, `V`

simply queries `L`

to see whether `hash(D)`

existed at time `T`

.

We needn’t fully trust `L`

, since if `L`

is tampered with (e.g. `hash(D')`

with timestamp `T-1`

is inserted at timestamp `T+100`

) this would be evident, and upon discovering such tampering, we would find an alternative tamper-evident log.

Hash chains and merkle trees are common implementations of tamper-evident logs. Unfortunately, a full implementation is not as simple as “use merkle trees”. This is where Certificate Transparency might be useful.

Certificate Transparency (CT) is a realisation of this idea, using merkle trees. CT’s purpose is to hold certificate authorities accountable for the certificates they sign, to avoid another DigiNotar incident. To do this, `L`

contains TLS certificates, which browsers query.

In particular, Certificate Transparency:

- defines a HTTP interface which serves:
- the log (which is large)
- proofs that certificates are in the log (which are small)
- proofs that the log is not misbehaving (which are small)

- describes a possible ecosystem of actors (and some open source implementations):
- auditors, who verify certificates are in the log (e.g. web browsers)
- monitors, who verify the log is misbehaving

- will tackle the problem of ensuring all clients of the log see the same log

As CT becomes more widespread, we may see CT-style Merkle Trees applied to more problems, including trusted timestamping!

*Thanks to Chris West for proof reading.*