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

[gmaxwell]

but they require O(n^2) communication so

Forget that— even ignoring the scaling they require the participants to be enumerated in advance.  Thats generally a non-starter to begin with for what Bitcoin attempts to achieve.

[1714879354]

1714879354

[1714879354]

1714879354

[1714879354]

1714879354

[AnonyMint]

The issue still remains:  an attacker can double spend simply by building a longer chain
that doesn't include the transaction at all, effectively sending the coins back to himself.

Nope.

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

How do you which is "the next winning block" ?

If it is the very next block after a longest-chain-wins reorg, and the attacker
wins that block , the attacker could exclude it as well.

And if it doesn't have to be the very next block, then the attacker could work
the other side of the attack, create an orphan transaction on purpose and
spring it several blocks after a reorg, thus double spending that way.

EDIT:  Furthermore, even if an honest miner solves the "next winning block"
required to make the honest correction, what is to stop the 51% attacker
from undoing that block as well?  Where does it end?

Correct. The point is to stop the attacker who can't sustain that indefinitely. Eventually the majority sustained hashrate wins, because the attacker has an increasing rental cost over time to maintain the fixed amount of double-spends he earned.

[jonald_fyookball]

you didn't answer the first point I made, so I'm unconvinced.

[AnonyMint]

I don't know if the hash rate solution to byzantine-generals is in fact the right solution.  In the presence of rentable computer power, it doesn't necessarily fulfil the assumptions that the security of the model is based on.

The only purpose of the longest chain rule is to prevent double-spends, and it seems it continues to serve that function for as long as at-risk transactions wait for enough confirmations to make rentable computer power attacks impractical due to scale (?).

I offer a proposal to shift the cost of that wait to the time between transactions, which is an existing unutilized resource thus mitigating significantly the impact of this wait and also not requiring the user to do anything to institute the wait in many cases. In short, in my proposal the wait comes (in many cases) automatically and at no cost.

We have Eve, Sybil, and Trent to worry about.  

..  

Anyway:  No way to completely avoid Eve and Sybil without creating Trent.  No way to completely avoid Trent without tolerating Eve and Sybil.  

I have an idea for a solution to this problem but I am not revealing it now. Gmaxwell was on the correct direction with CoinJoin in terms of separating the anonymity from the linkability of the block chain, but DarkCoin shows that to implement it you end up with centralizing or Sybil attacked master nodes in order to holistically resolve the jammability problem of CoinJoin's two steps. Also the simultaneity requirement of CoinJoin is a problem.

As well my proposal revealed in this thread appears to be incompatible with unlinkable block chains, e.g. Monero/Cryptonote and Zerocash.

[AnonyMint]

you didn't answer the first point I made, so I'm unconvinced.

I did answer it. Think deeply.

[AnonyMint]

you didn't answer the first point I made, so I'm unconvinced.

I did answer it. Think deeply.

The hacker and the sustained hashrate are running parallel forks and copying each other's valid transactions whereas the latter continues to unwind the double-spends from the hacker's fork every time the hacker loses a block. The hacker can only defeat this by continuing to maintain > 50% of the hashrate indefinitely.

Nodes who come on to the scene after the fact have a problem of knowing which fork to trust. So if the hacker can maintain the attack for an extremely long duration (so that the majority of the sustained hashrate is from nodes who don't know which fork to trust), then my proposal fails (at least if I try to unwind to the original transaction instead of to the ether). But in that case there is no solution at all in any case (at-risk transaction would be delayed an extremely long duration) and Bitcoin is toast.

Maybe that is why I will decide it must be to the ether. Need to think more on this and would appreciate insight from other astute devs here.

However, that most of the hashrate is in a few pools makes this extremely difficult for the attacker. I tend to think even if mining were more decentralized than currently in Bitcoin, the hashrate will still be concentrated amongst long-lived nodes.

[jonald_fyookball]

I don't know if the hash rate solution to byzantine-generals is in fact the right solution.  In the presence of rentable computer power, it doesn't necessarily fulfil the assumptions that the security of the model is based on.

The only purpose of the longest chain rule is to prevent double-spends, and it seems it continues to serve that function for as long as at-risk transactions wait for enough confirmations to make rentable computer power attacks impractical due to scale (?).

It also is part of the consensus mechanism and works beautifully due to it's simplicity.
Any added complexity to that rule needs to be considered very carefully and needs
to provably establish consensus as the longest chain rule does.

[AnonyMint]

Edit: The absurd nature of the attack is today probably 50% of the hashrate is not rentable (thus greater than 6 confirmations is probably not necessary now). But this could change over time if the trend is towards getting market prices for ASICs.

How likely is it that 50% of the hashrate will become rentable?

Edit: on the one hand no one should offer for rent that much hashrate because attackers could destroy the value of their hardware if they destroy Bitcoin in a Tragedy of the Commons (assuming no other SHA2 coins to mine at same profitability). But another Tragedy of the Commons is that ASICs owners don't each have 50% of the hashrate so they may not have a coordinated vision.

[jonald_fyookball]

I have such a headache from trying to understand this thread so instead, I am bookmarking it for later.  

A lot of Anonymint's ideas (Aliasing) are analogies and technobabble, and really have nothing to do with Bitcoin or blockchain technology.

(He should really stop trying to impress everyone with big words and explain his ideas in plain English.)

Anyway, Anonymint, I don't think more devs need to see the proposal.  You've already got Gmaxwell and DeathandTaxes telling you it won't work, what more do you want?  I think I've also given some fairly clear arguments also.  The creativity is appreciated but there doesn't necessarily have to be a "solution" against a 51% attack, and it doesn't mean Bitcoin is toast.

51% attacks done for financial gain are prohibitively expensive and I doubt you can rent half the network power anyway.  Malicious sustained irrational 51% attacks are an extreme scenario that would need an extreme solution such as a fork to an alternative proof of work.

But you did get me thinking about timestamp block validation and whether we do or can limit unwinding of the block chain by a 51% attacker.

[AnonyMint]

I have such a headache from trying to understand this thread so instead, I am bookmarking it for later.  

A lot of Anonymint's ideas (Aliasing) are analogies and technobabble, and really have nothing to do with Bitcoin or blockchain technology.

(He should really stop trying to impress everyone with big words and explain his ideas in plain English.)

Hey ad hominem bullshit flows out of your mouth. I can't compensate for your intellectual handicap.

Anyway, Anonymint, I don't think more devs need to see the proposal.  You've already got Gmaxwell and DeathandTaxes telling you it won't work, what more do you want?

Neither Gmaxwell nor DeathandTaxes have stated that my idea won't work. D&T hasn't even addressed my idea. Gmaxell stated that the existing strategy has the same problem with derivative unwinds as my strategy-- that is not the same as saying my idea won't work. But you aren't even able to comprehend.

I think I've also given some fairly clear arguments also.

And I've addressed all of your posts.

I doubt you can rent half the network power anyway.

I've put that out there as an open question in my prior post and no one has credibly addressed it yet.

[surae.noether]

First impressions of the paper: there are some good insights, and it's written well.

But... time stamps can be manipulated by dishonest actors (addressed in the CryptoNote whitepaper) and hence can not be trusted to prevent double spending. Which is one motivation behind Nakamoto's development of the Blockchain-by-Proof-of-Work solution to the Byzantine General problem.

Proof-of-work methods had been utilized before for various applications, most notably, to mitigate spam e-mail, but, Nakamoto was the first to solve the problem of coming to a concensus about order-of-events in a distributed, peer-to-peer way without timestamps. Even Nakamoto's solution is not a true solution, but simply a method that converges to a solution probabilistically over time. It's provable that a one-time, 2-General problem requires a countable number of verifications for a closed solution. The only other alternative Blockchain-by-Proof-of-X method that has been proposed since Nakamoto's solution has been Blockchain-by-Proof-of-Stake (and it's variant, the Blockchain-by-Proof-of-Stake-Velocity). Other Proof-of-X methods, such as Proof-of-Burn and Proof-of-Publication, have not been proposed to verify transactions, but to bootstrap value from one cryptocurrency to another and to verify the existence of a file by some point in time on the blockchain, respectively.  If either of these methods can be utilized to verify transactions, no method has been proposed to my knowledge.  

Recent rigorous security analyses of Blockchain-by-Proof-of-Stake methods are troubling: unless some Proof-of-Work component is included, a dedicated attacker can "kill" a coin with no cost http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2393940, but the attack requires a vast amount of capital, requires rational behavior on the part of a market (ha!), and requires the actor to enact a PR campaign trying to kill the coin. It's is unlikely to generate profit for the attacker (i.e. it's a strictly malicious attack). Notice, however, this may not apply to Blockchain-by-Proof-of-Stake-Velocity, I'm not sure. This core solution to generating an order of events without time stamps, the Blockchain-by-Proof-of-Work (BPOW) has essentially remained unchanged since it's original inception by Nakamoto. This is the primary strength of any cryptocurrency protocol. Variants in measuring the blockchain, such as following the heaviest subtree, not the longest chain, have been proposed, and are the best hope at improving that basic piece of the protocol. https://eprint.iacr.org/2013/881.pdf

[AnonyMint]

I found my post where I had analyzed this paper on May 14.

Well I see as January 2014, others below started to expound upon what I had explained in November 2013 at the threads given by the quoted links above.

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

...

The rest of the point of the above paper regarding tx timestampes is really a flawed ad hoc way of attempting to achieve the decentralization that the prior sentence would achieve more correctly.

http://arxiv.org/pdf/1405.0534.pdf#page=29

A big question is whether timestamps are needed at all, see Section 7.3. An
alternative to timestamps could be various pure consensus mechanisms without
timestamps by which numerous network nodes would certify that that they have
seen one transaction earlier than another transaction. In this paper we take the
view that they should be present by default and further conrmed by (the same)
sorts of additional mechanisms.

[AnonyMint]

The only other alternative Blockchain-by-Proof-of-X method that has been proposed since Nakamoto's solution has been Blockchain-by-Proof-of-Stake...

Recent rigorous security analyses of Blockchain-by-Proof-of-Stake methods are troubling...

Proof-of-stake == centralization.

[AnonyMint]

...Gmaxell stated that the existing strategy has the same problem with derivative unwinds as my strategy-- that is not the same as saying my idea won't work...

The cited paper:

Variants in measuring the blockchain, such as following the heaviest subtree, not the longest chain, have been proposed, and are the best hope at improving that basic piece of the protocol. https://eprint.iacr.org/2013/881.pdf

Perhaps the most important question that will affect Bitcoin’s success,
is whether or not it will be able to scale to support the
high volume of transactions required from a global currency system.
We investigate the restrictions on the rate of transaction processing in Bitcoin as a
function of both the bandwidth available to nodes and the network delay, both of which
lower the efficiency of Bitcoin’s transaction processing.

Summarizes Gmaxell's point as reinterpreted as quoted above, and also my orthogonal point that there is an unbounded increase in number of confirmations needed to protect against an attacker who can sustain > 50% of the network hashrate:

https://eprint.iacr.org/2013/881.pdf#page=7

The replacement of the current world-view with an alternative one has far reaching conse-
quences: some transactions may be removed from the current ledger. This fact can be used by
an attacker to reverse transactions. The attacker may pay some merchant and then secretly
create a blockchain that is longer than that of the network that does not include his payment.
By releasing this chain he can trigger a switch that effectively erases the transaction, or redirects
the payment elsewhere. This is a difficult undertaking, since the honest nodes usually have a
great deal of computational power, and the attacker must get very lucky if he is to replace
long chains. The longer the chain, the more difficult it becomes to generate the proof-of-work
required to replace it. Satoshi’s original security analysis defines a policy for receivers of pay-
ments: a transaction is only considered sufficiently irreversible after it was included in a block
and some n additional blocks were built on top of it. With this policy, Satoshi shows that the
probability of a successful attack can be made arbitrarily low. As a receiver of funds waits for
more blocks (larger n ), this probability goes down exponentially.

However, if an attacker has more computational power than the rest of the network combined
(i.e., it holds at least 50% of the computing power), it is always able to generate blocks faster
than the rest of the network and thus to reverse transactions at will (given enough time). This
stronger form of attack is known as the 50% attack.

The paper even points out that with network propagation advantages the attacker may be able to sustain the longest chain indefinitely with < 50% of the network hashrate:

In fact, the assumption that at least 50% of the computational power is required for such an
attack to succeed with high probability is inaccurate. If we assume the attacker is centralized
and does not suffer from delays, he can beat a network that does suffer from delays using fewer
resources. We formulate the exact conditions for safety from this attack, and amend Satoshi’s
analysis below. We return to the analysis of the weaker double spend attack in Sections 6 and
7.

The following calculation applies to a block period of 3.5 (1/0.29) seconds and 17 (59/3.5) confirmations:

https://eprint.iacr.org/2013/881.pdf#page=17

in some network configurations that match the assumptions above, an attacker with just over
24% of the hash-rate can successfully execute a so-called 50% attack, i.e., to replace the main chain
at will

The paper has some related insights as I did for my idea:

https://eprint.iacr.org/2013/881.pdf#page=18

The basic observation behind the protocol modification that we suggest, is that blocks that
are off the main chain can still contribute to a chain’s irreversibility. Consider for example
a block B, and two blocks that were created on top of it C₁ and C₂, i.e.,
parent(C₁) = parent(C₂) = B. The Bitcoin protocol, at its current form, will
eventually adopt only one of the sub-chains rooted at C₁ and C₂, and will discard
the other. Note however, that both blocks were created by nodes that have accepted block B and its
entire history as correct. The heaviest sub-tree protocol we suggest makes use of this fact, and adds
additional weight to block B, helping to ensure that it will be part of the main chain.

However it is not trying to address the ephemeral > 50% attack that my idea does. Instead the paper's GHOST protocol mitigates the fact that otherwise network propagation delay topologies can give the attacker an advantage such that it can execute attacks with the same probability of success with less than 50% (actually less than any probability curve calculated in Meni Rosenfeld's paper as cited).

GHOST aggregates the proof-of-work over n confirmations of all forks in the subtree above (i.e. after) B, i.e. it is a smoothing function:

¹⁰We are in fact interested in the sub-tree with the hardest combined proof-of-work, but for the sake of
conciseness, we write the size of the subtree instead.

https://eprint.iacr.org/2013/881.pdf#page=19

Thus, if we wait long enough, the honest subtree above B will be larger than the one constructed
by the attacker, with sufficiently high probability.

In my idea the nodes of the network utilize an additional piece of information which is the observation that a fork above B was orphaned by a fork which double-spends transactions in B (which applies weighting to the forks of the subtree above B by the observations of the nodes). Thus I believe my idea is more powerful and able to address the ephemeral > 50% attack (as well as < 50% attacks with greater probability) because it utilizes more information.

That paper and my idea are applying smoothing filters which incorporate more information, so that aliasing error is mitigated. There is a general concept in sampling theory-- don't discard information, filter it instead.

The paper also says we also shouldn't discard information when retargeting the difficulty:

https://eprint.iacr.org/2013/881.pdf#page=21

Retargeting (difficulty adjustment).
Given potentially complex relations between the
growth rate of the main chain and the rate of created blocks, and the fact that
GHOST depends more on the total rate of block creation, we suggest a change in the way difficulty
adjustments to the proof-of-work are done. Instead of targeting a certain rate of growth for
the longest chain, i.e., Beta (which is Bitcoin’s current strategy), we suggest that the total rate of
block creation be kept constant (Lambda). As our protocol requires knowledge of off chain blocks by
all nodes, we propose that information about off chain blocks be embedded inside each block
(blocks can simply hold hashes of other blocks they consider off-chain). This can be used to
measure and re-target the difficulty level so as to keep the total block creation rate constant.

[jonald_fyookball]

I have such a headache from trying to understand this thread so instead, I am bookmarking it for later.  

A lot of Anonymint's ideas (Aliasing) are analogies and technobabble, and really have nothing to do with Bitcoin or blockchain technology.

(He should really stop trying to impress everyone with big words and explain his ideas in plain English.)

Hey ad hominem bullshit flows out of your mouth. I can't compensate for your intellectual handicap.

Anyway, Anonymint, I don't think more devs need to see the proposal.  You've already got Gmaxwell and DeathandTaxes telling you it won't work, what more do you want?

Neither Gmaxwell nor DeathandTaxes have stated that my idea won't work. D&T hasn't even addressed my idea. Gmaxell stated that the existing strategy has the same problem with derivative unwinds as my strategy-- that is not the same as saying my idea won't work. But you aren't even able to comprehend.

I think I've also given some fairly clear arguments also.

And I've addressed all of your posts.

I doubt you can rent half the network power anyway.

I've put that out there as an open question in my prior post and no one has credibly addressed it yet.

Uh, pretty sure they did say your idea won't work...more than once.

Notice they stopped posting because they are probably sick of
your antics...AGAIN.  You earned your badge in trolling long ago with
your hysterics that Bitcoiners are going to be broke and
also go to jail because of clawbacks.  

And no, you didn't address all my points.  You didn't solve the
51% attack problem in any way, shape, or form.

And if you want to disprove my assertion that you're a
pseudo-intellectualist, go ahead... explain in plain,
simple English how "Aliasing" relates to blockchains or
distributed consensus or anything related.

[AnonyMint]

Uh, pretty sure they did say your idea won't work...more than once.

Quote them to document your assertion. You can't.

[jonald_fyookball]

gmaxwell said "your proposal is completely ineffective".

But whatever, keep arguing... its what you're best at.

[AnonyMint]

gmaxwell said "your proposal is completely ineffective".

But whatever, keep arguing... its what you're best at.

I am not arguing, I am clarifying that you (are intellectually handicapped—which I avoided stating until you attacked me—and) don't understand what Gmaxell wrote:

and where was my solution proposed before?

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.

The "makes the 'fix' ineffective in all cases" refers to "The ongoing effort has other problems", so he means there is no solution in Bitcoin (in "the ongoing effort").

And my response:

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.

Gmaxell asserted that if transactions can be unwound then any recipient of funds could be under threat by the payer to send a double-spend and invalidate the transaction.

I rebutted by explaining that transactions are only unwound if a double-spend appeared in a block chain, but that consensus nodes were not going to accept a double-spend into the block chain. The only way to get a double-spend into the block chain is to do a 50% attack, thus payers won't be able to make such a threat.

And Gmaxell admitted that for the 50% attack scenario, Bitcoin has the same weakness in that transactions can be unwound when a chain is orphaned.

If I have misinterpreted his writings, he will I assume point that out.

[jonald_fyookball]

the bottom line is your proposal just shifts around the conditions for an attack , it doesn't really add additional security without trading off security elsewhere.

If you disagree, the only person you seem to have convinced is yourself.

[gmaxwell]

If I have misinterpreted his writings, he will I assume point that out.

You have, but I've given up responding.