OpenTimestamps

[Peter Todd]

I'm the developer behind OpenTimestamps(1), a generalized timestamping system
that (currently) uses Bitcoin as a time attestation notary, but under the hood
supports multiple simultaneous and/or chained time attestations.

Roughtime would be an excellent addition to OpenTimestamps - a Roughtime
response is after all ultimately a trusted timestamp on a digest, and the ten
second latency goal is already a huge improvement on Bitcoin's multiple
hours(2).

I'm definitely interested in adding support to it, and would do so in such a
way that Roughtime responses are in turn timestamped by other means such as the
Bitcoin blockchain to allow them to be verified later even if the associated
keys are expired/revoked at a later date. Equally, I'm planning to add notary
misbehavior monitoring to OpenTimestamps as well, and monitoring Roughtime
servers for misbehavior fits in well to that goal.

OpenTimestamps uses a set of centralized aggregation and calendar servers to
aggregate timestamps in intervals of one second; all submitted digests within
an interval are hashed in a merkle tree, and the tip of that tree is saved
permanently and timestamped via Bitcoin (currently). Adding Roughtime support
would be a simple matter of having those calendar servers also use Roughtime
servers to timestamp those per-second commitments; the Roughtime response
signatures would be added to the calendar to be timestamped by Bitcoin as well.

So tl;dr: count me up as interested in implementing Roughtime. :)


FWIW, I actually proposed something quite similar to Roughtime a few years
ago(3) in response to someone else proposing a signed nonce NTP replacement;
I'm really happy to see this actually get implemented!

1) https://petertodd.org/2016/opentimestamps-announcement
2) https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-September/013120.html
3) https://lists.randombit.net/pipermail/cryptography/2013-September/005151.html https://lists.randombit.net/pipermail/cryptography/2013-September/005306.html

--
https://petertodd.org 'peter'[:-1]@petertodd.org

[Adam Langley]

On Tue, Sep 20, 2016 at 12:35 PM, Peter Todd <pe...@petertodd.org> wrote:

So tl;dr: count me up as interested in implementing Roughtime. :)

Cool! The fact that Roughtime could be used as a general timestamping protocol did not escape our attention but we don't currently have any plans to exploit this fact.

Cheers

AGL 

[Peter Todd]

So long as you have no plans to prevent that use-case sounds good to me!


On Tue, Sep 20, 2016 at 04:56:00PM -0700, Adam Langley wrote:
> > I can't speak for what the "official" plan is, but it'd be very easy to setup
> > "slave" Roughtime servers that created a merkle tree of requests in some
> > interval, then submitted the tip of that tree to a master Roughtime server. The
> > protocol can even support this as-is: you'd just concatenate the two
> > merkle-paths and set the index field appropriately. Of course, this would make
> > it look like you had an unusually large merkle tree if nested multiple times,
> > but a standards compliant client should accept such a response just fine.
> >
> > Note though that you can't do this without the co-operation of the server: the
> > hash calculation for a leaf is 0x00 + <nonce> while the hash calculation for an
> > inner node in the tree is 0x01 + <left> + right.
> >
> > Of course, the above does increase latency with every level of horizontal
> > scaling.
>
> It would be possible to move the packet processing to untrusted
> machines which built small Merkle trees and forwarded their roots to a
> trusted machine that signed larger Merkle trees. There is a limit in
> the protocol about how large the tree can be (based on the size of the
> response), but batches of 1,024 should be doable.

Ah right, because of UDP packet size limits.

Reminds me of a related issue: Why full SHA512 rather than SHA256 or truncated
SHA512? For timestamping, the birthday attack isn't relevant - a colision still
proves both messages existed at that point in time - so 512 bits is unusually
strong, particularly when Roughtime's intended use-case is so ephemeral
(there's a comment in the OpenTimestamps source noting that for timestamping
even MD5 doesn't have any practical attacks yet). Going from 512-bit hashes to
256-bit would make batches of 1,048,576 doable for the same packet size, which
could make the difference between a slow HSM being usable as the signer or not.
Equally, you've declared that the protocol and infrastructure is subject to
change and upgrades, so that'd sets expectations appropriately if you do need
to upgrade to more bits in the future.


But I may be biased: being a Bitcoin guy if SHA256 fails I'm going to have a
very bad day indeed. :)

[Adam Langley]

On Tue, Sep 20, 2016 at 9:47 PM, Peter Todd <pe...@petertodd.org> wrote:

Reminds me of a related issue: Why full SHA512 rather than SHA256 or truncated
SHA512? For timestamping, the birthday attack isn't relevant - a colision still
proves both messages existed at that point in time - so 512 bits is unusually
strong, particularly when Roughtime's intended use-case is so ephemeral
(there's a comment in the OpenTimestamps source noting that for timestamping
even MD5 doesn't have any practical attacks yet). Going from 512-bit hashes to
256-bit would make batches of 1,048,576 doable for the same packet size, which
could make the difference between a slow HSM being usable as the signer or not.
Equally, you've declared that the protocol and infrastructure is subject to
change and upgrades, so that'd sets expectations appropriately if you do need
to upgrade to more bits in the future.

I agree that SHA-256 would be fine. Roughtime is using SHA-512 because, by using Ed25519, we were already committed to using SHA-512 and so it seemed to make sense to keep the same hash function elsewhere. The batch sizes were expected to be 32 or 64 (at most) because that seemed to be enough to amortise the signing sufficiently. Very slow HSMs were not in mind. (HSMs generally don't support Ed25519 anyway!)

But I already expected to add HTTP as a transport at some point in order to be "firewall friendly". If you wanted really large batches then 1M would only need 1280 bytes of tree data in each reply, even with SHA-512.

Cheers

AGL

[Peter Todd]

On Wed, Sep 21, 2016 at 11:31:23AM -0700, Adam Langley wrote:
> I agree that SHA-256 would be fine. Roughtime is using SHA-512 because, by
> using Ed25519, we were already committed to using SHA-512 and so it seemed
> to make sense to keep the same hash function elsewhere. The batch sizes
> were expected to be 32 or 64 (at most) because that seemed to be enough to
> amortise the signing sufficiently. Very slow HSMs were not in mind. (HSMs
> generally don't support Ed25519 anyway!)

Yeah, few HSM's do, although I think that's beginning to change due to Bitcoin
stuff: while not as physically secure as traditional HSM's, people are building
HSM-like things that can run arbitrary code, and thus Ed25519. Some of them are
even being designed with fairly accurate battery-backed TCXO's like the DS3232,
±2ppm from 0°C to 40°C, or ±1 minute/year. Not by itself good enough for your
10 second accuracy goal, but good enough for a sanity check on an externally
provided GPS timesource.

> But I already expected to add HTTP as a transport at some point in order to
> be "firewall friendly". If you wanted really large batches then 1M would
> only need 1280 bytes of tree data in each reply, even with SHA-512.

Great!