[ots-dev] Disposable Key Trusted Timestamping Design

Riccardo Casatta riccardo.casatta at gmail.com
Sun May 14 01:22:26 AEST 2017

2017-05-13 4:12 GMT+02:00 Peter Todd <pete at petertodd.org>:
> ## 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 this case the trusted attestation is missing the unixTimestamp which is
claiming to, like:
verify TrustedTimestampAttestation(<pubkey>,<unixTimestamp>)

Also, considering the "Accuracy Promises" section could be interesting to
add also the accuracy information as a standard deviation of
< unixTimestamp >
verify TrustedTimestampAttestation(<pubkey>,< unixTimestamp >,<stddev>)

even if, for timestamping use case the accuracy could be expressed by
delaying the unixTimestamp accordingly

> 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

I like very much disposable key concept.
However the biggest problem of digital timestamping (unlimited backward
forging in case of hack) is time constrained by "Timestamping Trusted
Timestamp Signatures". So AFAIU using precision by reusing keys 2^16 isn't
useful (since you already have 18h precision from trustless timestamping)
and probably rotating keys is a lot simpler and only a little less secure.

> ## 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.

What do you mean?

> ## 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

Riccardo Casatta - @RCasatta <https://twitter.com/RCasatta>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.opentimestamps.org/pipermail/ots-dev/attachments/20170513/a67f45ea/attachment.html>

More information about the ots-dev mailing list