On The Longest Chain Rule and Programmed Self-Destruction of Crypto Currencies

[otila]

http://cryptome.org/2014/05/bitcoin-suicide.pdf

[b!z]

Interesting paper. Thank you for sharing.

[ncsupanda]

http://cryptome.org/2014/05/bitcoin-suicide.pdf

Wow. This is actually a very interesting read. I'm not currently finished with it, but I had to stop and say thank you.

Most people completely disregard Dogecoin as having any clout in the cryptocurrency world, so I find the analysis in those sections fairly intriguing.

EDIT: Seems I was a bit misinformed, based on the post below. Re-reading....

[DeathAndTaxes]

Utter nonsense.   It is sad that they wrote a paper based on the premise that timestamps can be used to solve the double spend problem (they can't) and then never did any research as to why Bitcoin doesn't rely on timestamps.   I mean it isn't a minor note, it is the core claim of the article.

It surprising to discover that Satoshi did NOT introduce a transaction
timestamp in bitcoin software. It is NOT known WHY neither the original
creator of bitcoin nor later bitcoin developers did not mandate one. This could
can be seen as an expression of misplaced ideology. Giving an impression
showing that maybe the Longest Chain Rule does solve the problems in an
appropriate way. Unhappily it doesn't.

One would think that when writing a paper if you are surprised that it would lead you to question and seek information.  Maybe you are surprised because you are misinformed, or misunderstand the conditions. Generally speaking just assuming your surprise is due to someone else being wrong and then not verifying that in any way is not the start of a good paper.  Satoshi did not include tx timestamps because proving timestamps in a decentralized environment is an incredibly difficult (some would say impossible) task.  In the absence of verifiable timestamps it would simply be wasted bits.  Nodes can optionally record the timestamp of when they learn of the transaction but that will differ from node to node.

Currently an approximate timing of transactions is known in the bitcoin
network, it comes from the number of block in which a given transaction is
included: this gives a precision of approx. 10 minutes. Transactions without a
fee could be much older than the block. However all blocks are broadcast on the
network and it is very easy for the bitcoin software to obtain more precise timing
of transactions with a precision of 1 second, maybe better. A number of web sites
such as blockchain.info are already doing this: they publish timestamps for
all bitcoin transactions which correspond to the earliest moment at which these
transactions have been seen.

Seen by who?  Oh thats right one individual node with no guarantee or assurance that ANY OTHER NODE has even seen that transaction much less at that time.

Then the solution is quite simple:

1. In case of double spending if the second event is older than say 20 seconds
after the first transaction, the first transaction will simply be considered as
valid and the second as invalid. This based on the earliest timestamp in
existence which proves that one transaction was in existance earlier.
This seems reasonable knowing that the median time until a node receives
a block is 6.5 seconds cf. [8, 9].

How are you proving timestamps?  Timestamp is simply a number.  I can give you a timestamp from the birth of Jesus does that mean I have proven I made a bitcoin transaction thousands of years ago?

The implementation of such a mechanism is not obvious and will be discussed separately below. However it seems that it could be left to the free
market: several mechanisms could function simultaneously. For example one can immediately use timestamps published by blockchain.info and simultaneously use timestamps from other sources.

So the decentralized currency is based on the timestamps as decided by some centralized "super peers".  If I bribe the timestamp servers to say my tx is older then I can double spend without even using hashing power.

For solutions which would prevent various bitcoin web servers from manipulating these time stamps we will need to propose additional mechanisms,
such as secure bitstamps or additional distributed consensus mechanisms.
We will develop these questions in another paper.

Gee really?  You are saying that decentralized provable timestamps are an incredibly difficult problem to solve.  Maybe someone could use an append only linked list of timestamps, where each timestamp is proven by requiring the creator of an individual timestamp element use a non-trivial amount of resources.  Thus once an individual element of the list has a sufficient number of elements after it then users would have some assurances that modifying the element would be very difficult.  As part of the process to make the element of the list maybe we could put a hash of the txn in the element and thus substituting the txn becomes as difficult as changing the list.  To avoid a lot of work needed for every txn you could have each element store a hash which represents an entire set of txns.  Each user would always extend the longest valid list to force a consensus between multiple valid but incompatible lists.  We could probably call these list elements "blocks" and the linked list a "blockchain".

In case of double spending if both events come within at most 20 seconds
of each other, miners should NOT include any of these transactions in block
they mine. Some miners can nevertheless accept a transaction because they
have only received one of the two transactions, or because they are trying to
cheat. Then their block could simply be invalidated because they have not
been careful enough about collecting all the transactions which have been
around. For honest miners this would occur with small probability.

So it becomes trivial to fork the network.

I create two transaction (with magical 100% provable decentralized timestamps which don't exist and yet are the lynchpin of the paper yet are not discussed in the paper) within 20 seconds of each other and broadcast one, when it is included in a block I broadcast the other one and the block just mined is invalid.  

Again this decision on whether to include or not a given
transaction could be decentralized.
All this requires some form of timestamping and some security against manipulation of these timestamps to be implemented than in the current software,
either by consensus or secure timestamps.

By magic?  I mean it like saying taking a spacecraft to the moon is a flawed strategy when we could just teleport there instead.  Also teleporting to the moon will require some teleportation capabilities and stuff.

An alternative to timestamps could be a pure consensus mechanism by which
numerous network nodes would certify that that they have seen one transaction
earlier than another transaction. This can be very easy done: we can re-use shares
which are already computed by miners in vast quantities or select only certain
shares with a sucient number of zeros.  We could mandate that if transactions
are hashed in a certain order in a Merkle hash tree, it means that this miner
have seen certain transactions earlier

I am seeing a trend, when you say "easy" it actually means "this seems easy because I lack the basic knowledge to see why it isn't".  So a tx being in the merkle tree of a miner means it is first?  What if a miner ignores the first tx and puts the second tx in the merkle tree?  We have a tx in a merkle tree somehow it magically proves it was first?  However even if it did, we are still operating on magical provable decentralized timestamps.

or another similar mechanism assuming
that the majority of miners are honest.

Wait a minute.  Lets read this one again slowly "assuming that the majority of miners are honest", "assuming that the majority of miners are honest".  Really?

I know you can't mean majority as in >50% of the nodes by count because the entire concept of proof of work (or stake) is predicated on a well founded assumption that preventing a sybill attack in a decentealized network is infeasible.  If you could prevent a sybill attack, well miners could just vote and there would be no need for work or stake at all.  You wouldn't even need magical provable timestamps as each node would simply vote based on its own observations.  

So by "majority" you must mean more than 50% of the hashrate.  You didn't see where I am going when you wrote this?  In other words even this convoluted, nonsensical solution still fails to prevent double spends when the attacker has 51% of the hashrate.  Wasn't that the "flaw" that the entire paper is based on "fixing"?

[cr1776]

Utter nonsense.   It is sad that they wrote a paper based on the premise that timestamps can be used to solve the double spend problem (they can't) and then never did any research as to why Bitcoin doesn't rely on timestamps.   I mean it isn't a minor note, it is the core claim of the article.

It surprising to discover that Satoshi did NOT introduce a transaction
timestamp in bitcoin software. It is NOT known WHY neither the original
creator of bitcoin nor later bitcoin developers did not mandate one. This could
can be seen as an expression of misplaced ideology. Giving an impression
showing that maybe the Longest Chain Rule does solve the problems in an
appropriate way. Unhappily it doesn't.

One would think that when writing a paper if you are surprised that it would lead you to question and seek information.  Maybe you are surprised because you are misinformed, or misunderstand the conditions.  Generally speaking just assuming your surprise is due to someone else being wrong and then not verifying that in any way is not the start of a good paper.

Saved me having to look at it.

And It is known why - many reasons, which a little research would've discovered.

[jonald_fyookball]

Perhaps it is possible to replace proof of work with some other distributed time-based system,
although you would still need the longest chain as a basis for convergence.

[benjyz]

Academics have produced nothing but perfect nonsense on the topic of Bitcoin. This is one of the worst.

[DeathAndTaxes]

Perhaps it is possible to replace proof of work with some other distributed time-based system,
although you would still need the longest chain as a basis for convergence.

Possibly but it is a non trivial problem for which robust decentralized solution exists.  As I said it is like saying instead of taking a rocket to the moon we "could" teleport directly there although the technology does not exist and it may not ever be possible.  Hopefully you wouldn't write a paper saying nobody knows why NASA opted to use a rocket instead of teleport to the moon. 

[jonald_fyookball]

Perhaps it is possible to replace proof of work with some other distributed time-based system,
although you would still need the longest chain as a basis for convergence.

Possibly but it is a non trivial problem for which robust decentralized solution exists.  As I said it is like saying instead of taking a rocket to the moon we "could" teleport directly there although the technology does not exist and it may not ever be possible.  Hopefully you wouldn't write a paper saying nobody knows why NASA opted to use a rocket instead of teleport to the moon. 

Non trivial, although on the surface, seems deceptively simple.
(We just want a block every 10 minutes!)

Maybe there could be a list of 1000 different timestamp servers
that nodes can check, and by introducing a time element, the hashing
work could be reduced.   

[telepatheic]

Interestingly Satoshi didn't put much thought into the problem of time stamping, although he realised timekeeping was important. The general assumption he made was that all nodes would report the correct time. (This is not the case and has the potential to cause major problems with bitcoin if exploited in tandem with a Sybil attack)

In the code Satoshi wrote:

"Never go to sea with two chronometers; take one or three."
Our three chronometers are:
  - System clock
  - Median of other server's clocks
  - NTP servers

note: NTP isn't implemented yet, so until then we just use the median of other nodes clocks to correct ours.

The quote comes from "The Mythical Man Month" for those interested in Satoshi's background.

The code he implemented was:

Code:

nTimeOffset = nMedian;
if ((nMedian > 0 ? nMedian : -nMedian) > 5 * 60)
{
    // Only let other nodes change our clock so far before we
    // go to the NTP servers
    /// todo: Get time from NTP servers, then set a flag
    ///    to make sure it doesn't get changed again
}

Satoshi decided to contradict his quote and use two chronometers!

The idea was that if the offset between your node and the others was more than 5 minutes something is wrong. This was further relaxed in a subsequent version to a massive 70 minute offset! (Why 70 minutes, I have no idea, the change isn't documented anywhere public as far as I can tell) Edit: the changes can be found here and here but there is no explanation.

Code:

// Only let other nodes change our time by so much
if (abs64(nMedian) < 70 * 60)
{
      nTimeOffset = nMedian;
}

But still no NTP support.

[jonald_fyookball]

Thanks for the link. Funny how 2011 is ancient history in the bitcoin world.

Wasn't aware that time stamping was used at all, except for difficulty changes.
Seems it used as a sort of double checking for blocks, although seems unnecessary
or at least not critical because of the longest chain rule.

[DeathAndTaxes]

Wasn't aware that time stamping was used at all, except for difficulty changes.

It isn't.

Seems it used as a sort of double checking for blocks, although seems unnecessary or at least not critical because of the longest chain rule.

How is change in difficulty computed?  What would happen to difficulty computation if there was no timestamp checking on blocks (attacker could use any timestamp he wanted)?

[chriswilmer]

I know one shouldn't judge a book by its cover... but just glancing at the abstract one can tell that this isn't serious scholarly work.

[jonald_fyookball]

Wasn't aware that time stamping was used at all, except for difficulty changes.

It isn't.

Seems it used as a sort of double checking for blocks, although seems unnecessary or at least not critical because of the longest chain rule.

How is change in difficulty computed?  What would happen to difficulty computation if there was no timestamp checking on blocks (attacker could use any timestamp he wanted)?

No, I agree we need time stamps for the difficulty change.
However, the article isn't talking about that. 

The network time is used to validate new blocks.

.

Basically it is talking about double spends, etc. 

[DeathAndTaxes]

The network time is used to validate new blocks.

.
Basically it is talking about double spends, etc.  

The article is saying block timestamps are used to prevent double spends, it is showing how block timestamps can be manipulated to exploit the fact that nodes will validate the timestamp and use that to isolate nodes .   The timestamps are only validated to ensure difficulty can't be gamed.   No other function of the bitcoin protocol relies upon them.  To prevent difficulty from being gamed requires invalidating blocks outside of an acceptable range.  The article is pointing out that the validation of timestamps can be an attack vector for double spends.  The attack vector wouldn't exist if the network didn't validate block timestamps.  Of course if there were no validation of timestamps then there would be no secure provable way of setting difficulty.  It is a catch-22.  The article recommends reducing the window for validating blocks to make this attack more difficult (an attack which has been successfully executed).

Satoshi understood that timestamps are very difficult to authenticate as such limited them to areas where there is no solution which doesn't involve timestamps.

[jonald_fyookball]

Sorry but I am missing something here.

Why is there a possible attack vector if the protocol
is using the time stamps for anything other than
difficulty adjustments? (Using them to validate blocks)

 

[DeathAndTaxes]

Sorry but I am missing something here.

Why is there a possible attack vector if the protocol
is using the time stamps for anything other than
difficulty adjustments? (Using them to validate blocks)

 

I assume you mean isn't?

The article explains the attack in pretty simple language.  The attacker isolates the node and feeds it incorrect timestamps.  This causes the computed network time on the victim's node to be SLOWER than the rest of the network.  The attacker then creates a block with an incorrect timestamp that is faster than the correct time.  For most of the network although the timestamp is wrong it is still within the validation window and the block is accepted.  The victim's clock however has been slowed down enough that the block is outside the validation window and the block is rejected.

The victim has now been forked off the main network and can be fed false information and double spent at will.

The timestamps validation of blocks is only used to prevent manipulation of difficulty but the fact that nodes validate timestamps is exploited to isolate and attack the node.  In reality this attack would be rather difficult to pull off, is expensive as it requires mining full strength blocks which will be orphaned by the main network, and there are some pretty cheap and easy countermeasures. 


Essentially the target's proper checking of timestamps (to prevent manipulation of difficulty) is used against the target by careful manipulation of timestamps.  I don't believe this is a very effective attack in the real world for a couple of reasons.

[jonald_fyookball]

So they stamp all the blocks which could sort of be exploited for double spends but not really and then the stamp is used for the diff change.

[DeathAndTaxes]

So they stamp all the blocks which could sort of be exploited for double spends but not really and then the stamp is used for the diff change.

Correct.  All blocks contain a timestamp, all blocks timestamps are validated by all nodes to ensure they are within an acceptable window.  This is done to "keep miners honest".  Without it miners could use false timestamps to manipulate the 2016 block timespan, lower difficulty, and boost their profits. 

That validation in theory could be exploited to isolate and double spend a node.  The article describes how that attack could be executed.

[jonald_fyookball]

Got it. 

I need to be excused now.  My brain is full.