[Cryptography] Securing cryptocurrencies

[Ray Dillinger]

On 03/11/2015 05:37 PM, Tony Arcieri wrote:
> On Tue, Mar 10, 2015 at 9:52 PM, Ray Dillinger <bear at sonic.net> wrote:
> 
>> On 03/10/2015 12:52 PM, ianG wrote:
>>>  I have suggested that the PoW algorithm
>>> should be something that could be more usefully used by the rest of
>>> society, like house-heating
> 
> 
> I think a better solution is to create a protocol that doesn't rely on a
> proof-of-work function. Still something of an open problem though.
> 
> I think the proof-of-stake approach used by systems like Tendermint are
> interesting, and really what's holding back those sort of protocols now is
> the simple fact that engineering a distributed consensus algorithm is
> incredibly hard. Tendermint doesn't have a formal proof of correctness (in
> terms of e.g. TLA+)


The usual problem with proof-of-stake systems is that in a chain
fork, the attacker has stake on both sides of the fork.  He can
use this stake on both branches of a fork rather than having to
commit a finite resource (such as hashing power in the Proof-of-
work coins) to one branch or the other.

The usual method of determining proof-of-stake (as "coin days
destroyed" or similar) allows the attacker to manipulate the
timing of his double spends on the attack chain to generate more
stake than the spends of the same coins on the main branch, or
to spend his coins (to himself) multiple times generating more
proof-of-stake each time.

Finally, the usual protocol has a weakness in that the
transactions made on one branch of the fork, unless specific
conditions are met which ordinary users will never meet, can be
replayed into another branch of the fork and contribute to stake
in that branch - meaning nobody other than the attacker chooses
any preferential generation of stake on one branch or the other
because they're making transactions that can be included on both
sides.  In fact, if the attacker moves some transactions to a later
block of the attack branch, they typically generate more stake
in that position, so the attacker can manipulate the priority of
the attack chain in another way by using a replay attack.

I have dreamed up a potentially workable protocol variation
which hybridizes proof-of-work with proof-of-stake, addressing
some of these problems.   It uses transactions as proof-of-
stake, but addresses the replay attack by having each transaction
'stake' a recent block in the block chain it is contributing
security to.  Transactions are not valid in any block chains
in which the staked block does not appear. Thus, an attacker
cannot replay transactions that staked a block he wants to
disappear in a reorganization, into the same chain he intends
to replace it with.  The 'stake' of a  block chain branch (ie,
the sum total of txouts that existed before the fork and are
used in tx that are staked in a block after the fork) are
used for choosing between branches in a proof-of-stake
determination.

The downside of this, of course, is that now staked transactions
are annihilated by any chain reorganization that occurs before
their staked block.  But it should be very hard to achieve such
a reorganization without relying on the replay attack to get
stake support from other users' transactions and also unable
to manipulate the 'stake' generated by your own spends by spending
them earlier or later or more times in one branch vs. another.

This makes it impossible to prepare a *long* attack chain in
secret - everybody else will be staking all transactions in
the chain they can see, so unless you have a substantial
fraction of the money, your would-be attack chain will have
stake that's pathetic by comparison to the total volume
everybody else is doing.

But it's not so good for preventing *short* reorgs, because
spending is, in the very short term, a lot more bursty and
occasional than the constant, steady effort of hashing which
remains nearly constant at the miner's capacity.  As a
result, using spends to determine branch priority is very
sensitive to the exact timing of large spends.  When combined
with the possibility of annihilating staked transactions by
removing the staked block in a reorg, this opens the field
to a class of short-term timing attacks that are better
prevented by proof-of-work systems.

So this type of proof-of-stake protocol could work at large
scale (where the law of large numbers smooths out the volume
of transactions or the rate of flow of money to something
steadier) but in smaller scales would have to be part of a
hybrid protocol with proof-of-work.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20150312/ca1d7cc0/attachment.sig>