[Cryptography] What has Bitcoin achieved?

[Bear]

On Tue, 2014-06-24 at 08:21 +1000, James A. Donald wrote:

> For cost so defined to be comparable to other concepts of cost, need to 
> assume that mining is only moderately profitable, which appears to be 
> true, and that the cost of mining is largely the cost of massively 
> replicating and validating transactions, which is not true, but becoming 
> increasingly true.
> 
> Not a workable system.
> 
> We need blockchain money system that is more scalable - transactions are 
> only moderately replicated and moderately duplicate stored, and in which 
> authority more reliably corresponds to ownership of the money, rather 
> than ownership of computing power.

What you are describing is called a "proof-of-stake" system, as 
opposed to a "proof-of-work" system.  

Several cryptocurrencies have implemented proof-of-stake, but, as 
yet, the versions of it that they have implemented are subject to 
attacks based on what has been called the "nothing-at-stake" problem.

I outline the problem and a partial solution below.

In order to distinguish a "correct" blockchain from an orphan 
(or attacking) blockchain, proof-of-work relies on the provable
expenditure of a finite resource - compute power.  The nothing-
at-stake problem arises when there is no ability to prove 
expenditure of a similarly finite resource to distinguish a 
correct from an orphan blockchain in a proof-of-stake 
cryptocurrency.

Proof-of-stake as implemented in existing cryptocurrencies treats 
"coin days" as the finite resource whose expenditure distinguishes 
correct from attack blockchains.   The idea behind this is that 
when a txout is used in a transaction, the time since it was created 
is multiplied by the number of coins it represents to get a number 
of "coin days."  And the assumption is that whichever blockchain 
has created (or used up, depending on how you think of it) the 
greatest number of coin days is accepted as legitimate.

Nothing-at-stake arises because "coin days" are not a finite resource
in the way we need a resource to be finite in order to resist attacks.
When there is a fork, stake is duplicated on both sides of the fork. 
This leads to attacks based on the use of stake that the attacker 
has already spent in the other fork.  Also, the same unspent txout 
can generate more or fewer "coin days" depending on when it is spent, 
so an attacker can spend coins on both sides of a fork while 
choosing which side to generate more "coin days" in.  

Also, under proof-of-stake, there is no need for a miner to forsake
one side of a fork in order to support another;  The miner has the 
same stake on both sides of the fork, and would be an idiot to stop
generating blocks supporting either side until he is absolutely 
certain which side which will be orphaned.  That makes the support  
of miners effectively useless for deciding which side is to be
orphaned.

Finally, new unspent txouts are generated by transactions, including
coinbase transactions, on both sides of the fork, and expenditures 
of these txouts are 'noise' that an attacker (in an attack which gives
the attacker control of a higher proportion of the coinbase txouts on 
one side of a fork) can take advantage of to generate more coin days 
in his attack chain than in the legitimate chain. 


A partial solution to "nothing at stake" is to focus on a resource
which really is finite in the way we need it to be:  Uncontested 
expenditures of txouts that existed at the moment when the blockchains
diverged.

When comparing two sides of a fork, instead of counting coin days, 
we should count the expenditure of txouts that existed at the moment 
of divergence.  But we should count only those transactions that do
not conflict with (do not use any of the same txouts as) transactions
on the other fork.  And we should count them strictly for the number
of coins spent, rather than varying it by block height as in counting 
"coin days". 

This means it is transactions, and not mining, that supports the 
security of the blockchain.   In order for transaction support to 
be finite (necessarily count for only one side of the fork) it is 
necessary for transactions to give a block hash from the blockchain
they support.  Any transaction that gives a pre-fork block hash can 
be replayed into either side of the fork, thus cancelling its support
for the other side.  Any transaction that gives a post-fork block 
hash can be counted as support only for the fork in which that 
block hash appears.  Thus, transactions that name more recent block
hashes (within the last 1-3 blocks) are more valuable for securing 
the chain than transactions that name later block hashes (within the 
last 4-7 blocks), and if compensated via proof-of-stake 'interest' 
payments for securing the chain, should be compensated more. 
Transactions giving block hashes older than 8 blocks are not 
terribly useful in securing the chain, and should not be accepted.  

Because this solution is not subject to nothing-at-stake, at 
the very least attackers have to use real as opposed to already-
spent stake to attack it, and cannot support their attacks by
making transactions using the same coinbases they are trying to 
steal via their attacks.  

But this is still a partial solution.  There is still a flaw in
that someone making a transaction can easily make it in both 
sides of a fork, therefore supporting neither.  Further, there 
is some motive for them to do so, unless such transactions can 
be demonstrated based on information to be recorded in the main 
branch and their proof-of-stake payment for securing the chain withheld.
I believe that this is possible, but complex and 
possibly unnecessary.

				Bear