[Cryptography] Robust Linked Timestamps without Proof of Work.

Jameson Lopp jameson.lopp at gmail.com
Fri Aug 19 18:07:23 EDT 2016


On Fri, Aug 19, 2016 at 12:05 PM, Phillip Hallam-Baker <
phill at hallambaker.com> 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.
>
> Proof of work is kind of important for deterring denial of service and
sybil attacks.


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

Kind of; the longest blockchain isn't important - the blockchain with the
most cumulative proof of work is considered the correct chain. FYI, the "c"
in "Bitcoin" is never capitalized.


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

Sure; let's say for the sake of argument that I decide to run 10,000
OpenPGP KeyServers and sybil attack your network. It sounds like I'd be
able to falsify data with a high rate of success. The numbers you choose
are likely irrelevant; I suspect that any such system would inevitably turn
into a form of "proof of work" as described by Paul Sztorc:
http://www.truthcoin.info/blog/pow-cheapest/


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

>From one perspective, I suppose, though on the other hand you can't just
take a million dollars and buy a day's worth of hashing power - most of the
existing hashpower isn't for sale. To purchase enough new hashing power to
own 50% of the Bitcoin network (1,487,398 TH/S) would cost
approximately 114,415
Antminer S9 (13 TH/S) units at $2,500, or *$286m** in hardware costs *and 1.4
KW * 114,415 * $0.08 KW/H, or *$12,815** an hour in electricity costs*.
Except for the small fact that there aren't that many S9 units available
for purchase either...


>
> 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.
>
>
It's unclear if you're talking about a permissionless network where anyone
can run a validator or a permissioned network with a predetermined trusted
federation of validators. If it's the latter then we're talking about a
completely different security model than 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.
>
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20160819/90a99118/attachment.html>


More information about the cryptography mailing list