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

[justusranvier]

If you could trust nodes voting you wouldn't need mining to begin with.  There is no guarantee that all nodes know about all transaction at any point in time.  There is no guarantee nodes will learn of transactions with any guarantee on timeliness or nodes will learn of transactions in the same order.   The composition of the network is also continually changing

The network isn't a single unified block of memory it is a coalition of independent systems.   If we could trust anonymous decentralized nodes to "vote" in a secure manner they could simply agree on the ordering of transactions.  You wouldn't even need blocks and you certainly wouldn't need mining.   The unresolved problem is preventing a sybil attack.  Satoshi saw that in a pseudonymous decentralized network, where an attacker could cheaply create thousands or even hundreds of thousands of nodes, that no vote based on 1 node = 1 vote could be trusted.

Proof of work is the method to force a consensus on the network to create a canonical ordering of transactions.  If nodes could reject blocks based on "incorrect" ordering then it would imply they already know the canonical ordering.  If they know that, they you don't need mining to begin with.

"I found a way to solve the BGP without solving the BGP" is going to be the next generation's perpetual motion hoax.

All those people who make YouTube videos where claim to run a portable generator to electrolyze water which they use to power the generator engine? Soon they'll all switch to inventing new scamcoins.

[bitcoinbeliever]

If you could trust nodes voting you wouldn't need mining to begin with.

The post I linked to does not claim to invent a way to fully order all transactions.  It only proposes that nodes (the important ones being miners) reject (not build on top of) blocks that contain transactions that are not only double-spends --  but 20-second-late double-spends (the exact threshold would be determined later).

If they go ahead and build on top of such a block anyway, they risk the rest of the network (miners again) ignoring any block they find.

This would not make all 0-conf transactions safe.  But it could make them a lot safer than today, if a seller waited for example 20 seconds before completing a real-world transaction.

The safest path for a miner would be to NOT mine double spends.  Which of course is the point.  The only risk to a miner who adoped that strategy would be somehow missing a first-spend.

[DeathAndTaxes]

If you could trust nodes voting you wouldn't need mining to begin with.

The post I linked to does not claim to invent a way to fully order all transactions.  It only proposes that nodes (the important ones being miners) reject (not build on top of) blocks that contain transactions that are not only double-spends --  but 20-second-late double-spends (the exact threshold would be determined later).

If they go ahead and build on top of such a block anyway, they risk the rest of the network (miners again) ignoring any block they find.

This would not make all 0-conf transactions safe.  But it could make them a lot safer than today, if a seller waited for example 20 seconds before completing a real-world transaction.

The safest path for a miner would be to NOT mine double spends.  Which of course is the point.  The only risk to a miner who adoped that strategy would be somehow missing a first-spend.

It would also make confirmations horribly insecure as you would be reporting confirmation on a minor chain where you may be double spent in the main chain.  Worse it hides this fact from the user by ignoring the main chain because it contains tx "too close together".  It won't be deterministic between nodes until 6 confirmations which makes troubleshooting and analysis far more confusing for users.  Essentially not only are 0-confirm transactions now risk, 1 to 5 confirms are also highly risky too.  6 confirms becomes the new 1 confirm so the "clearing time" goes from 10 minutes to an hou.  

Miners are highly pragmatic they will build off the longest chain as it has the most chance of remaining the longest chain. You can suggest miners not build off the longest chain but unless a super majority of them follow that they simply lose money by doing so, which means they wont.   It is a modified prisoners dilemma where in almost all scenarios breaking from the longest chain is the worse choice.

[ncourtois]

This is work in progress. Thank you all for extremely valuable comments.
The most up to date version of this paper is available at:
http://arxiv.org/abs/1405.0534

[hashman]

Nice paper   It is indeed a complex ecosystem of competing currencies we find ourselves in. 

couple comments:

"Sudden jumps and rapid phase transitions are programmed at xed dates in time and are likely to ruin the life of these currencies"

Participants know in advance about the sudden jumps and value hashpower and currencies accordingly far in advance.  See 1st bitcoin halving.  Will people prefer this to the nondisclosed jumps/transitions in supply and mining rates we have seen in fiat or even gold? 

"We discovered that neither Satoshi nor bitcoin developers have EVER mandated any sort of transaction timestamp in bitcoin software."

I disagree.  Block height is one of the best timestamp mechanisms ever developed.  Second, more conventional dates ARE in the software as they are required to set difficulty properly.  In some commmodities there is not even a public record let alone a great timestamping system.   

"In this paper we show that most crypto curren-cies simply do NOT have ANY protection against double spending."

Participants all know and understand the possibility of a longer-chain or 51% attack and its cost.  We wait for the appropriate number of blocks (confirmations) until we know a double spend effort on a payment we are accepting would be a total loss for the payer.  Pretty good protection against double spend IMHO, especially compared to fiat            

[AnonyMint]

The most important point made in the paper is that an adversary potentially doesn't need to own 50+% of the network hashrate. Rather if sufficient hashrate can be rented then the adversary only needs to double-spend over a small window of time an amount that is more than the mining rental cost, which potentially makes the 50+% double-spend attack much more accessible given that at 25 BTC per block then a 6-confirmation rental cost should be in the range of only 150 BTC.

Another point made is that the double-spends could be spread out over smaller transactions, so large transaction fingerprinting can't be a solution. The point is also that waiting for 6-confirmations doesn't necessary give a high probability of protection against a double-spend (although the attacker wouldn't likely be able to monetize on sufficient scale some types of transactions, e.g. purchasing toddler shoes from a merchant).

The attack works by spending on the public chain fork and simultaneously employing the rented mining hardware to create a secret chain fork which omits or double-spends those spends. Then after the spends have received enough confirmations on the public fork, then publish the secret fork which has a longer block length which orphans the fork with the originating spends.

Proposed Solution

I hereby write down a rough sketch for an idea of a decentralized solution which is based on the attacker not being able to afford to sustain the high hashrate. I don't know if there is a prior art or discussion of this or a similar idea?

a. If a mining node receives a request to add a transaction which double-spends a prior seen transaction, the request is discarded.

b. If a mining node is attempting to add a transaction to the next block it will win and the received winning block double-spends the former, the former is discarded.

c. If a mining node is in possession of an orphaned block chain which contains transactions that are missing or double-spent in a received longer block chain, the mining node broadcasts this fact and all mining nodes which agree (i.e. had seen this fork before it was orphaned) are expected to add this fact to the next winning block which thus marks any double-spent coins as forfeited to the ether (or adds the spends that were omitted).

This accomplishes the following.

1. The more confirmations a merchant waits for, the less probable the typical spender could (after receiving what was paid for) propagate a double-spend to spite the merchant. Todo: quantify the probability.

2. The mining nodes in agreement would continue forever trying to add this forfeiture evidence to the attacker's fork after it is public. Only if they have a minority of the hashrate would they fail. Thus the attacker would need to maintain his 50+% advantage forever (or for a long enough time until those mining nodes in agreement became a minority which could be a significant period of time).

Any holes in my logic?

One issue is honest mining nodes are punished by attacker for as long as the adversary can sustain the 50+% hashrate, the honest miners lose their mining rewards. But they are going to be losing them without my idea if this attack becomes viable. If the attack becomes viable, the network would constantly be under attack (attackers wouldn't hold back to preserve Bitcoin market price due to their competing with each other in a Tragedy of the Commons) and all honest blocks would be orphaned.

(note I only invested roughly an hour into this idea, so I might have missed something obvious)

Edit: this rented 50+% attack is a Tragedy of the Commons, because the attackers would compete to drive rental costs higher and higher, crowding out honest miners. This is potentially a very dangerous risk as more and more mining hardware is put out for rent to obtain market prices. Note this becomes more likely as the trading volume in the exchanges become more liquid as a crypto-currency matures.

Edit#2: note the proposed solution doesn't deal with the issue of during network fragmentation where there are isolated public forks then the spender could issue a double-spend on each fork, because block chain fragmentation is an orthogonal problem (which I think currently has no known solution?).

Edit#3: the attacker must double-spend and not just omit the prior spends in the longer block chain, otherwise the other nodes will remember those spends and re-add them to the longer block chain after it is public.

Edit#4: the only reason I have thought of for not modifying the proposal to reinstate the originating spends instead of declaring the double-spent coins forfeited to the ether, is if the typical spender can somehow spend to himself first then to merchant secondly. Todo: analyze this along with quantifying the probability in #1 above.

[gmaxwell]

The most important point made in the paper

Huh, the fact that someone with <<50% hashpower can successfully double spend has been repeated many many times on this forum, by dozens of people (including myself), along with comments that mining pools or (especially) vertically integrated closed mining operations with double digit percentages of the hashrate are all concerning, even if its not near 50%. The original Bitcoin whitepaper gives the formal for calculating the success rates.

[AnonyMint]

The most important point made in the paper

Huh, the fact that someone with <<50% hashpower can successfully double spend has been repeated many many times on this forum, by dozens of people (including myself), along with comments that mining pools or (especially) vertically integrated closed mining operations with double digit percentages of the hashrate are all concerning, even if its not near 50%. The original Bitcoin whitepaper gives the formal for calculating the success rates.

I am aware of Meni Rosenfeld's white paper which calculates the probability of winning n blocks with LESS than 50% of the hashrate. But that is an orthogonal issue to one which I raise of sustaining an attack with MORE than 50% (see I wrote "50+%") of the hash power. I propose to defeat the attacker who can't sustain 50+% of the hashrate (up to) indefinitely.

Where was the following discussed before and where was my solution proposed before?

...is that an adversary potentially doesn't need to own 50+% of the network hashrate. Rather if sufficient hashrate can be rented then the adversary only needs to double-spend over a small window of time an amount that is more than the mining rental cost, which potentially makes the 50+% double-spend attack much more accessible given that at 25 BTC per block then a 6-confirmation rental cost should be in the range of only 150 BTC...

...this rented 50+% attack is a Tragedy of the Commons, because the attackers would compete to drive rental costs higher and higher, crowding out honest miners. This is potentially a very dangerous risk as more and more mining hardware is put out for rent to obtain market prices. Note this becomes more likely as the trading volume in the exchanges become more liquid as a crypto-currency matures...

[gmaxwell]

and where was my solution proposed before?

I don't believe your post contained a "proposed solution" when I initially responded, if it did— I missed it.

But it's not a solution, alas. Ignoring other issues, at best it still leaves it at a simple piece of extortion "return most of the funds to me or I will reliably destroy your payment". It that sense pretty much isomorphic to "replace by fee scorched earth". The ongoing effort has other problems— a txout can be spent again immediately in the same block. Imagine it takes months to get the fraud notice out (heck, imagine a malicious miner creating one and intentionally withholding it).  By that time perhaps virtually all coins in active circulation are deprived from the conflicted coins. Now they finally get the notice out (/finally stop hiding it). What do you do?  Nothing? Invalidate _everyone's_ coins? Partially invalidate everyone's coins?  Each option is horrible. Do nothing makes the 'fix' ineffective in all cases: the attacker just always sends the coins to themselves in the same block, the others make the failure propagate— potentially forever, and don't just hit the unlucky merchant with the potentially unwise policy.

(It should be noted that already systems reject from their mempool discard later double-spend transactions from their local perspective, because— duh)

Rather if sufficient hashrate can be rented [...] potentially makes the 50+% double-spend attack much more accessible

Many places, I'll pick an example from myself— (note the log I reference there 12:37 < gmaxwell> pirateat40: you can have 10% of the hash power and attack.)

[AnonyMint]

I don't believe your post contained a "proposed solution" when I initially responded, if it did— I missed it.

It was there— only the enumerated edits were added which are below the proposed solution.

I imagine you may have limited time to digest a lengthy post, if on first glance you thought it was rehashing an old issue.

But it's not a solution, alas. Ignoring other issues, at best it still leaves it at a simple piece of extortion "return most of the funds to me or I will reliably destroy your payment".

That specific threat was paramount in my mind as I was designing my proposal and I think I eliminated it.

The mining nodes reject any double-spend transaction which conflicts with the block chain. The only transactions that can be unwound are those which appear in a competing fork and only when that competing fork does not have enough sustained agreement. The premise is the attacker can't maintain 50+% of the hashrate indefinitely. Essentially what I am proposing is that orphaned chains are not forgotten by the sustained majority when the longer chain temporarily double-spends the orphaned chain, so the sustained majority (eventually) unwinds the temporary attack. The attack is differentiated from the majority because it is not sustained indefinitely. Abstractly I am proposing a smoothing filter on Proof-of-work longest chain rule. The ephemeral attacker is aliasing error.

And I think (perhaps) they can be unwound to eliminate the double-spend, rather than to the ether.

[jonald_fyookball]

I don't believe your post contained a "proposed solution" when I initially responded, if it did— I missed it.

It was there— only the enumerated edits were added which are below the proposed solution.

I imagine you may have limited time to digest a lengthy post, if on first glance you thought it was rehashing an old issue.

But it's not a solution, alas. Ignoring other issues, at best it still leaves it at a simple piece of extortion "return most of the funds to me or I will reliably destroy your payment".

That specific threat was paramount in my mind as I was designing my proposal and I think I eliminated it.

The mining nodes reject any double-spend transaction which conflicts with the block chain. The only transactions that can be unwound are those which appear in a competing fork and only when that competing fork does not have enough sustained agreement. The premise is the attacker can't maintain 50+% of the hashrate indefinitely. Essentially what I am proposing is that orphaned chains are not forgotten by the sustained majority when the longer chain temporarily double-spends the orphaned chain, so the sustained majority (eventually) unwinds the temporary attack. The attack is differentiated from the majority because it is not sustained indefinitely. Abstractly I am proposing a smoothing filter on Proof-of-work longest chain rule. The ephemeral attacker is aliasing error.

And I think (perhaps) they can be unwound to eliminate the double-spend, rather than to the ether.

Even if you unwind specific transactions without breaking the block headers, you still run into the issues DeathandTaxes mentioned earlier.  Namely, that having a certain number of confirmations won't mean what it used to.

[AnonyMint]

Even if you unwind specific transactions without breaking the block headers, you still run into the issues DeathandTaxes mentioned earlier.  Namely, that having a certain number of confirmations won't mean what it used to.

Incorrect. My proposal strengthens the insurance from n confirmations. If you disagree, then walk me through your logic.

[AnonyMint]

Note in my proposal unwinding only affects double-spent coins, so if you never send a double-spend then your transaction will never be unwound. Note a double-spend is not the same as resending the same transaction.

[gmaxwell]

Note in my proposal unwinding only affects double-spent coins, so if you never send a double-spend then your transaction will never be unwound. Note a double-spend is not the same as resending the same transaction.

As mentioned in my prior response— if you did this then your proposal is completely ineffective. First you double spend, and then you spend your double-spent coins to yourself.  If you do not also unwind the child transaction then the doublespender walks free for nothing but the cost of an extra transaction. If you do unwind the children then everyone is at constant risk.

[jonald_fyookball]

Note in my proposal unwinding only affects double-spent coins, so if you never send a double-spend then your transaction will never be unwound Note a double-spend is not the same as resending the same transaction.

As mentioned in my prior response— if you did this then your proposal is completely ineffective. First you double spend, and then you spend your double-spent coins to yourself.  If you do not also unwind the child transaction then the doublespender walks free for nothing but the cost of an extra transaction. If you do unwind the children then everyone is at constant risk.

Not to mention the obvious:  Double spent coins are the only ones we care about here.

The whole meaning of n confirmations is measuring security against double spends.
Otherwise, 1-2 confirmation would be enough to know the tx was formatted correctly
and was included in the blockchain.

So if you are talking about the possibility of winding them back, then
confirmations lose their meaning, and your "solution" does more harm
than good.

[AnonyMint]

Note in my proposal unwinding only affects double-spent coins, so if you never send a double-spend then your transaction will never be unwound. Note a double-spend is not the same as resending the same transaction.

As mentioned in my prior response— if you did this then your proposal is completely ineffective. First you double spend, and then you spend your double-spent coins to yourself.  If you do not also unwind the child transaction then the doublespender walks free for nothing but the cost of an extra transaction. If you do unwind the children then everyone is at constant risk.

I couldn't grok what you wrote before so I ignored it. Now I understand your point.

Definitely derivative transactions will be unwound too (thus my quoted statement is incorrect if you haven't waited the say 100 or so confirmations mentioned below), and this does not violate my assertion that insurance increases as n confirmations does.

As you admitted (in the part I didn't grok before), the risk you speak of applies whether my proposal is implemented or not. For example, in the current implementation of longest chain rule, if you got paid in the public orphaned chain and these are double-spent into the secret chain which becomes the longer chain when publicized (thus orphaning the other chain), then your payments are effectively unwound.

My proposal is that you don't trust the longest chain until considerable n confirmations have transpired, because the majority will be trying to unwind those bogus double-spends. So in my proposal, not only do you not deliver goods until a payment has n (usually 1 - 6) confirmations, but also you don't accept payment from a transaction (history) unless the prior transaction has much more than n (say 100 or so) confirmations. Abstractly the smoothing filter applies from both directions.

Note that CryptoNote ring signatures (and probably Zerocash and Zerocoin also) breaks the type of unwinding in my proposal because derivative transactions are unlinkable.

Edit: similar functionality can be obtained in the current implementation of the longest chain rule, by waiting for 100 or so confirmations before accepting a payment as final (to extend out the duration cost for the extended time attacker has to keep his chain secret so your payment isn't orphaned by the attacker's chain). Thus unlinkable coins could still defeat ephemeral 50+% double-spending attacks, but with very slow payments.

Not to mention the obvious:  Double spent coins are the only ones we care about here.

The whole meaning of n confirmations is measuring security against double spends.
Otherwise, 1-2 confirmation would be enough to know the tx was formatted correctly
and was included in the blockchain.

So if you are talking about the possibility of winding them back, then
confirmations lose their meaning, and your "solution" does more harm
than good.

You are confused by aliasing error, which can be ephemeral in my proposal.

The confirmations that matter are those in the chain that has the sustainable majority of the hashrate. The only way to differentiate aliasing error from signal, is for the width of the smoothing filter (i.e. the number of confirmations) to be greater than the period of the aliasing error (another way of stating the Nyquist-Shannon sampling theorem). That period is how long the attacker can sustain the hashrate to maintain the longest chain.

[AnonyMint]

Edit: similar functionality can be obtained in the current implementation of the longest chain rule, by waiting for 100 or so confirmations before accepting a payment as final (to extend out the duration cost for the extended time attacker has to keep his chain secret so your payment isn't orphaned by the attacker's chain). Thus unlinkable coins could still defeat ephemeral 50+% double-spending attacks, but with very slow payments.

Ah so thus the solution to these ephemeral (rented hashrate) 50+% attacks is either in the existing longest chain rule to increase the number of confirmations for finalizing payments to greater than the period the attacker can afford (i.e. 100 or so), or changing the longest chain rule to my proposal which shifts that wait to the duration that a prior transaction has to wait before it can be safely spent again. In my proposal payments still need 1- 6 confirmations as usual to defend against orphans due to propagation delay and < 50% attacks.

So what my proposal does is shift the smoothing filter from slower payments to slower re-spending, as the means of muting ephemeral 50+% (rented hardware) double-spending.

6 confirmations is on the order of 150 BTC cost for the attacker. 100 confirmations on the order of 2500 BTC. The attacker has to recoup that with double-spends.

[cAPSLOCK]

You are confused by aliasing error, which can be ephemeral in my proposal.

The confirmations that matter are those in the chain that has the sustainable majority of the hashrate. The only way to differentiate aliasing error from signal, is for the width of the smoothing filter (i.e. the number of confirmations) to be greater than the period of the aliasing error (another way of stating the Nyquist-Shannon sampling theorem). That period is how long the attacker can sustain the hashrate to maintain the longest chain.

Your sampling analogy deals with effects of aliasing OUTSIDE of the frequency set where the errors occur, whereas the double spend problem occurs in alternate versions of the current set.  In other words, the filter eliminates the audible aliasing by addressing it's consequences while a double spend happens at the exact same frequency as the actual (agreed upon) signal.

Does this flaw in the analogy not point out a possible crack in the thinking here?

[jonald_fyookball]

If miners who have a winning block can simply reroute funds or unwind transactions because they claim they saw a related transaction
in a previous orphaned block, what's to stop miners from doing that arbitrarily?  

[AnonyMint]

You are confused by aliasing error, which can be ephemeral in my proposal.

The confirmations that matter are those in the chain that has the sustainable majority of the hashrate. The only way to differentiate aliasing error from signal, is for the width of the smoothing filter (i.e. the number of confirmations) to be greater than the period of the aliasing error (another way of stating the Nyquist-Shannon sampling theorem). That period is how long the attacker can sustain the hashrate to maintain the longest chain.

Your sampling analogy deals with effects of aliasing OUTSIDE of the frequency set where the errors occur, whereas the double spend problem occurs in alternate versions of the current set.  In other words, the filter eliminates the audible aliasing by addressing it's consequences while a double spend happens at the exact same frequency as the actual (agreed upon) signal.

Does this flaw in the analogy not point out a possible crack in the thinking here?

Users want to band-limit the block chain, so they don't sample high frequency ephemeral attack block chains as being the true signal (because these can contain double-spends). They do this by applying a smoothing filter which is the number of confirmations they wait.

The only decentralized way I can see to defeat the ephemeral 50+% attack is to increase the period of time in which the attacker must be able to control the block chain, i.e. maintain 50+% of the hashrate.

In the current longest chain rule implementation, increasing the number of confirmations before accepting a payment as final forces the hacker to keep his double-spend chain secret longer.

In my proposed variation where the majority hashrate can unwind double-spends (and their derivative transactions), increasing the number of confirmations before accepting a prior transaction as final forces the attacker to maintain his public double-spend chain longer.

The smoothing filter applies to the attacker's period in both cases, and the choice of designs for the longest chain rule determines whether payments or re-spends should be delayed.