[Cryptography] Robust Linked Timestamps without Proof of Work.

Fri Aug 19 21:24:10 EDT 2016

On Fri, Aug 19, 2016 at 12:05:33PM -0400, Phillip Hallam-Baker wrote:
> On Thu, Aug 18, 2016 at 1:44 PM, Peter Todd <pete at petertodd.org> wrote:
> 
> > On Thu, Aug 18, 2016 at 01:29:11AM -0400, Jerry Leichter wrote:
> > > There are plenty of useless (both to theory and to practice) theoretical
> > results; in fact, the vast majority of published theory papers probably
> > include just such results!  And there are plenty of useful but not very
> > deep practical results.  But trying to argue that Bitcoin "solved this
> > problem the theory people couldn't solve" is just silly.
> > >                                                         -- Jerry
> >
> > Note that Bitcoin - specifically proof-of-work - does solve a problem that
> > signature-based approaches can't: even if the people building consensus in
> > Bitcoin (miners) all conspire to change history, it's provably expensive
> > for
> > them to rewrite history because they have to re-do all the proof-of-work.
> > That's not true in signature based consensus, as forging a signature is
> > free.
> >
> >
> I disagree. What gives robustness to the blockchain is the use of linked
> timestamps, not the proof of work part.

What Bitcoin provides is _not_ just timestamps, it's proof-of-publication.

The difference is a timestamp simply proves that data existed prior to a
certain point in time; a timestamp does not say anything about whether or not
conflicting data exists.

For instance, if I claimed I sold you a house, I could show you a series of
validly signed, timestamped, deed documents showing that the prior history of
ownership including the deed transferring ownership to you. The timestamps
prove that those deed documents existed in the past - I didn't just make them
up yesterday. But there still might be a competing claim of ownership on that
house: I might have already sold the house to Bob, rendering your apparently
valid deed worthless.

Bitcoin solves this problem by providing a medium where transactions - or deeds
in the above example - can be authoritively published, with (probabalistic)
proof that the publication reached a well-defined audience (all Bitcoin
miners/users). Secondly, Bitcoin allows you to be sure that something was _not_
already published.

In the above deed example, I'd show you that not only were those deed documents
valid, they were the _first_ valid deed documents for each owership. Equally, a
Bitcoin transaction is only valid if for each coin spent, the transaction is
the first transaction that tried to spend it. Of course, as an optimization
Bitcoin goes a step further and disallows invalid transactions to be published
in the blockchain at all, but that's the thing: that's just an optimization
that full-nodes don't actually need to operate.

Timestamp proofs have trivially additive security. For instance, my PGP
signature on this email gives a tiny bit more confidence to the timestamp
security provided by this block hash:

    000000000000000004c99ddc28747cbd3e4dadb9186dd57451f7c12c2b396ed1

Basically, any data committed by that hash has both my PGP signature, and PoW
security, providing evidence that that data existed prior to 2016-08-20
00:50:21 UTC. GuardTime famously takes advantage of this additive security by
publishing hashes of their timestamp commitment chain in various news papers.

> Whenever dealing with claims about blockchain, we have to analyze two
> separate systems:
> 
> 1) The ideal blockchain deployment that gives perfect security
> 2) The actually deployed blockchain that has any number of kludges to make
> it work.
> 
> Yes, in theory the blockchain is determined by the longest chain. In
> practice, it is not. There is a consensus among the users that once the
> blockchain has advanced n blocks it is not going to be rewritten. And that
> consensus is in fact essential to making BitCoin marginally practical as a
> value transfer scheme.
> 
> Of course, I can't propose a scheme that is more robust than the ideal
> Bitcoin deployment in which all operational practicalities are ignored. But
> I have built real world PKIs that have endured a lot longer than BitCoin
> and I am pretty sure that I can provide a scheme that at least matches
> BitCoin for security without proof of work.
> 
> Let us say for the sake of argument that in the near future there will be
> 100 OpenPGP KeyServers that operate in a manner similar to today's servers
> based on Brian LaMachias' MIT server with two changes:
> 
> 1) Every key server maintains a link timestamp of all data submitted (keys,
> signatures, etc.)
> 
> 2) Every hour, each server cross-timestamps their current timestamp value
> with at least ten other servers chosen at random
> 
> Let us further assume that I can establish a userbase of a million users.
> Which I think is actually quite plausible if I can persuade the S/MIME folk
> to use the infrastructure as well as the OpenPGP folk.
> 
> To verify a timestamp value, a verifier checks the timestamp chain of five
> or so randomly chosen servers.

Again, with timestamps this kind of cross-checking is relatively easy to do
because every additional timestamp adds to the confidence you have in your
timestamp proof. Equally, I could also take those timestamps and timestamp them
in the Bitcoin blockchain - my OpenTimestamps project is intended to
(eventually) provide that kind of multi-factor timestamp proof.

You haven't actually clarified what time of proofs your "100 PKI servers"
example are producing? Are you actually thinking of something more like
Certificate Transparency, which is a proof-of-publication system? Or do you
really mean just timestamps?

-- 
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: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160820/337c2117/attachment.sig>