Great to see these ideas used for general security applications.
Also:
> It is the case that the signature, even assuming one request per batch, will add some number of microseconds of latency to the reply. Roughtime is not going to displace PTP for people who care about microseconds.
I'm not convinced that this should prevent extremely precise timestamping a la PTP. The server just needs to indicate, outside the signature, how long its processing took. Sure, this prevents authentication of the fine-grained time, but a client could easily bound the amount that a server can cheat.
One challenge would be around server scale -- for the servers to maintain a strict chain, they would need to coordinate amongst themselves, which can be costly. The proposed approach doesn't introduce that requirement.
But they could get close by maintaining a branching history, like what you might see in a git history, or a vector clock. Neither of those approaches provides the same causality assurances as your proposal, but either would provide something close without incurring any blocking server-side state management.
As it is, Semaphor clients include a local timestamp among the signed content of most actions, and the server rejects actions that aren't within some tolerance (strict ordering however is accomplished via hash chain.) Roughtime would allow improving this situation from several angles.
One of the logistical challenges is client network traffic footprint. Enterprises that deploy a collaboration solution often want to have a strict definition of which upstream servers it can be expected to talk to. Would it be possible for a single Roughtime service to incorporate verifiable information from a larger Roughtime community, such that end user clients don't have to communicate with additional addresses?
OpenNTPD has "constraints" where it makes HTTP requests (using TLS) to webservers and checks that the time provided by the NTP server is within a certain threshold of the time returned in the HTTP Date header.
Much simpler and doesn't require dedicated servers.
The 'Date' header is tricky because it is a timestamp of when the document was generated, not when it was served. Caching proxies have no obligation to (and in most cases shouldn't) update the value.
If you're worried about a caching proxy you can set the constraint to a URL that returns something dynamic. Although it would be interesting to see what % of the top TLS-enabled webservers don't return something recent for HEAD / HTTP/1.1