Tom's Blog

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.

blog comments powered by Disqus