[Cryptography] Robust Linked Timestamps without Proof of Work.

[Phillip Hallam-Baker]

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.

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.


​The ​metric I use for evaluating the security of a PKI is a time based
work factor priced in dollars. Obtaining bogus Domain Validated
certificates in quantity in the WebPKI has a certain cost, lets say $500,
an EV certificate has a much higher cost, about $5000. The cost values here
are not just the price of acquiring the cert, they are also the cost of
covering their tracks. The out of pocket cost of obtaining a single bogus
cert is much lower because it is very unlikely that is going to be
detected. But obtaining large numbers without establishing a pattern is
hard.

So how does BitCoin fare? well the cost of mining 24 hours of bitcoins is
large but its less than a million dollars.

The work factor of my scheme is rather higher because in order to backdate
the timestamp by one hour without detection, the attacker has to compromise
ten servers and every user that has recorded the timestamp values. To go
back 6 hours without detection, the attacker has to compromise all the
servers. To have a chance of fooling someone in a detectable fashion it is
necessary to compromise more than half.

While it is certainly conceivable that someone might be able to compromise
100 independently operated servers at the same time, the cost of doing so
is a heck of a lot more than mining 6 hours worth of bitcoin.


This approach is not theoretical either, it is my design for phase 2 of the
Mathematical Mesh, the Meta-Mesh. I have to finish part 1 first of course
though.

Ben Laurie has proposed similar ideas in his critique of BitCoin but I
think I came to this independently.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160819/12bd4015/attachment.html>