[ots-dev] Disposable Key Trusted Timestamping Design

[Peter Todd]

Here's a summary of some recent thoughts/discussions/etc. I've had on how to
add trusted timestamping to OpenTimestamps:

# Rational

For most use-cases, timestamps accurate to within a day or two are adequate: we
just need to prove data was created in the past - exactly when it was created
in the past isn't all that important. But we've gotten a few requests for
things like timestamping log file entries and so on for more accurate
timestamps, and I'm inclined to support these use-cases.

It's pretty clear that we need a trusted timestamping solution for
high-precision timestamps in addition to using Bitcoin. While Bitcoin block
headers have a nTime field with precision of one second, the accuracy of that
timestamp under adversarial conditions is very poor(1). Similarly, while some
other decentralized consensus systems attempt to require tighter accuracy,
doing so is dubious and creates a risk of consensus failure due to things like
incorrectly set timezones.

Meanwhile, a trusted timestamp provider can credibly provide precision to
within a second or so - similar to the round-trip uncertainty on the public
internet anyway. The Roughtime time syncronization protocol(2) does exactly
this, leveraging a timestamp on a nonce to set a local clock.


# Timestamping Timestamps

Trusted timestamps have two big vulnerabilities:

1) The notary is untrustworthy
2) The notary's keys get compromised, leading to #1

In either case, with trusted timestamping alone prior timestamps suddenly
become invalid, unless we can prove those timestamps were created prior to the
notary becoming untrustworthy. So obviously we'd like the signatures created by
a notary to in turn be timestamped, e.g. via the Bitcoin blockchain.


## Implementation

To actually do this, recall that in an OTS proof tree each node is basically
the following pseudo-Rust:

    struct Node {
        msg: [u8],
        ops: Map<Opcode,Node>,
        attestations: Set<Attestation>,
    }

In other words, the node is a message, edges between nodes are opcodes, and
attestations are metadata about a message; an attestation is *not* part of the
graph, as operations never act on metadata.

In the case of a Bitcoin block header attestation, the attestation itself is:

    struct BitcoinBlockHeaderAttestation {
        height: u32,
    }

The attestation acts on a timestamp proof node whose message is supposed to be
the merkleroot of the block; the height is there purely as a helpful hint so
validators don't have to keep an index of every single merkleroot. Notably, if
that hint is *wrong* the timestamp can be fixed by fixing the height; the
merkle root being wrong can't be fixed.


## Timestamping Trusted Timestamp Signatures

What does this look like for a trusted timestamp? Now, remember that if I give
you a signature created by a pubkey, if you don't know *which* pubkey created
that signature, but do have a list of pubkeys that you trust, you can figure
out which pubkey the signature is valid for by brute-force. So by that logic,
the pubkey is again metadata.

Thus a TrustedTimestampAttestation should be:

    struct TrustedTimestampAttestation {
        pubkey: <pubkey>,
    }

with the signature being part of the message the attestation verifies. This
means that such a timestamp have the following form:

    <digest>
    append <signature>
    verify TrustedTimestampAttestation(<pubkey>)

In the case where the attesting signature is also timestamped by something like
Bitcoin, the timestamp proof would be:

    <digest>
    append <signature>
    verify TrustedTimestampAttestation(<pubkey>)
    {ops}
    verify BitcoinBlockHeaderAttestation(<height>)

If a verifier wants to check the Bitcoin timestamp on the trusted timestamp
signature it's easy: the Bitcoin timestamp data is all child nodes in the tree.


# Disposable Keys

While I've discussed adding Roughtime to OpenTimestamps in the past(3) I think
we can do even better with disposable keys. The idea is quite simple: rather
than the trusted notary pubkey being a pubkey, we make it a merkle tree
committing to many different pubkeys, each valid only for a specific time
interval. This allows the notary to delete the corresponding secret keys as the
time interval passes (regardless of whether or not the secret keys were ever
used), preventing the creation of backdated timestamps. (an identity-based
signature scheme(4) such as bilinear pairings is an alternative, but such
crypto isn't very commonly used)


## Merkle Tree Depth

For OpenTimestamps, I think we can make a good case that 1 second resolution is
fine - that's roughly the same order of magnitude as network latencies. So a
32-level deep tree is certainly enough, and would result in 1KiB attestations.

How frequently should keys be deleted? If less frequent, we could reduce
attestation size by reusing keys. For example, if a key is used 2^16 times
that's 18 hours, resulting in a 2^16 deep tree -> 512byte attestations.

Frankly, I'm not sure what arguments are correct here. I think we'd have to
consider in detail some compromise/recovery scenarios, which I haven't done
yet. Equally, I see dispoable keys as a "belt-and-suspenders" measure, as I
expect to see them used in conjunction with PoW blockchain timestamps.

Note that the size of the attestations is also somewhat misleading: if users
continue to predominantly use calendars with pending attestations - and those
calendars have responsibility for getting calendar contents timestamped by
trusted timestamp notaries - the signature and merkle tree won't actually be
stored in most timestamp proofs themselves. Secondly because the merkle trees
get reused, the repeated parts will get compressed away when storing copies of
calendars.

So with a good implementation, the cost of the disposable key merkle trees
should be a small multiple of the size of the keys themselves: with 2^16 keys
that's just 2MiB of data; 512MiB for 2^24 keys.


## Multisig

While there's some clever stuff that could be done with schnorr multisig here,
that'd require low-latency co-ordination between signers. Also, apparently
there's some issues with schnorr signatures: Andrew Poelstra tells me that they
don't commit to the pubkey natively, which is potentially a big problem in our
use-case given the pubkey is modifiable metadata. The proposed merkle tree
would prevent this, maybe?, but this deserves more thought.

Probably easiest just to use client-side multisig, which in the timestamp case
is "latest timestamp reported via M-of-N signers"


## Certificate^H^H^H Notary Transparency

Obviously we can have notaries link make their timestamps be a publicly
available blockchain.


## Secret Key Derivation Tree

Again obvious, but the concept of a secret key derivation tree - already used
in the OpenTimestamps Server(5) - is an obvious way to reduce risks in the
event of a compromise, and reduce the amount of secret key material that you
need to move around.


## Accuracy Promises

Roughtime timestamps return a timestamp radius and midpoint, with the promise
that the true time was within that range. I think we should copy this design
exactly.

Notably, a good hardware implementation of a timestamp notary would be a
reasonably high accuracy clock, such as a DS3232 RTC, allowed to free run to
ensure no outside source could manipulate it. The implementation could then do
either of:

1) Estimate drift and expand the radius over time as necessary.
2) Use an external clock source (like GPS), and expand the radius as neccessary
   to include both the internal clock and external clock. Note how such an
   implementation may return a useless result in the event of an attack, but it
   won't return a false timestamp.


# References

1) "[bitcoin-dev] Interpreting nTime for the purpose of Bitcoin-attested timestamps",
   Peter Todd, 2016-09-18,
   https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-September/013120.html

2) Roughtime announcement, accessed 2017-05-12,
   https://www.imperialviolet.org/2016/09/19/roughtime.html

3) "OpenTimestamps", proto-roughtime mailing list,
   Peter Todd, 2016-09-20,
   https://groups.google.com/a/chromium.org/d/msg/proto-roughtime/jYLxSDKPc4o/AjyUk_BDBAAJ

4) https://en.wikipedia.org/wiki/ID-based_cryptography

5) https://github.com/opentimestamps/opentimestamps-server/blob/f71e1f3ae902316e17760a5ba56ba322014959c5/otsserver/calendar.py#L34

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 455 bytes
Desc: Digital signature
URL: <https://lists.opentimestamps.org/pipermail/ots-dev/attachments/20170512/6a2aa21c/attachment.sig>