Bitcoin Forum

In Satoshi's original whitepaper (http://bitcoin.org/bitcoin.pdf), he concludes with discussing double-spending attacks and their probabilities of success. This section does not get the attention it deserves, unfortunately, leading to several widespread myths:

Myth. Double-spending requires having more than half of the network hashrate.

Myth. Waiting for confirmations offers meaningful protection against an attacker with majority hashrate.

Myth. There is something special about 6 confirmations, and/or it grants absolute protection.

Myth. The important factor is the amount of time spent waiting for confirmations, rather than the number of blocks. (Still a myth if instead of actual time you look at #blocks * average time per block).

In Analysis of hashrate-based double-spending (https://bitcoil.co.il/Doublespend.pdf), I elucidate and build on Satoshi's work in this area. I explain the basics of double-spending and derive the probability for its success. I provide various graphs and charts for this probability. I also give a simplified model for the economics of double-spending.

Some of the key conclusions are:

• Hashrate-based double-spending boils down to a race between an attacker and the honest network. In every turn one of them moves a discrete step forward, each with a probability determined by their relative hashrate. A successful attempt means managing to catch up with the honest network, a failure means falling so far behind there is no longer a chance of catching up.
• Successful double-spending is possible with any attacker hashrate. There is no need for a majority to carry out this attack.
• Waiting for more confirmations exponentially decreases the probability of double-spending success. The decay rate depends on the attacker's relative hashrate.
• The probability of success depends on the number of confirmations and not on the amount of time waited. An alternative network with a shorter time between blocks can thus obtain more security with a given amount of wait time.
• The time constant might be relevant, if we assume that the attacker cannot sustain his hashrate for a prolonged period of time. In this case, even majority hashrate does not guarantee success, as the attack could take more time than available. However, it does not seem likely that an attacker would go through the trouble of obtaining enormous computational resources and only maintain them for a time short enough to make this consideration relevant.
• No amount of confirmations will reduce the success rate to 0.
• If the attacker controls more hashrate than the honest network, no amount of confirmations will reduce the success rate below 100%.
• There is nothing special about the default, often-cited figure of 6 confirmations. It was chosen based on the assumption that an attacker is unlikely to amass more than 10% of the hashrate, and that a negligible risk of less than 0.1% is acceptable. Both these figures are arbitrary, however; 6 confirmations are overkill for casual attackers, and at the same time powerless against more dedicated attackers with much more than 10% hashrate.
• In practice, the probabilities of success are less relevant directly, than as a major factor in determining the economics of an attack.
• Economic modeling is complicated, and some additional factors come into play. The time between blocks can affect the economics, and even with majority hashrate an attack might not be economical despite the guaranteed success. However, by the time the latter factor becomes relevant, the security is anyway weak beyond redemption.

Does a "checkpoint" not make it impossible to do a block re-org for all blocks before and including itself?

Yes, it does. I am explicitly discussing hashrate-based attacks with the vanilla protocol, disregarding additional layers of protection such as hardcoded checkpoints and proof of stake.

With the current schedule of checkpoints, it is not practical to consider waiting for a checkpoint to accept payment.

Understood - actually I've been wondering in regard to the "rewrite the whole history since the last checkpoint attack" that wouldn't the easiest solution to be to simply prevent blocks that are trying to replace older blocks being accepted if they are simply too old (or does the protocol already do that?).

I call this practice "cementing" and it has some problems, similar to what we would have if there was no blockchain at all. The basic idea is that a node could be stuck on "the wrong version" after being isolated and fed bad data from an attacker, and would have no way to recover even after being exposed to the honest network.

There are some ways to work with that but it's far from simple.

Very interesting - I do hope some more ideas about this could be hashed out as I think it would actually be a much better solution than using "proof of x" (where x is anything other than "work") to stop such attacks.

BTW - nice paper. :)

This was a much needed paper,  I've seen these myths propagated a lot.

Thanks,

It's great to see this topic given such formal treatment.  Very nice!

Regarding this myth:  "The probability of success depends on the number of confirmations and not on the amount of time waited. An alternative network with a shorter time between blocks can thus obtain more security with a given amount of wait time."

If you have two networks, A & B and both have the same hash rate, but one has a 1 minute block interval while the other has a 10 minute interval, is it not the case that for a given percentage of the network hashing power, an attacker would have an equivalent chance of executing a successful double spend on a time frame of say 1 hour or greater?  Blocks are a reflection of the amount of work that has been done to find them...I don't think people argue that waiting a certain amount of time buys you any more security (you could wait an hour, and if there still isn't a confirmation block, you're no more safe than waiting only 1 second).  However, I think what most people argue is that on two networks, with an equivalent amount of hashing power, 6 blocks emitted from one that calibrates to produce 1 block every 10 minutes is equivalent (in terms of security) to 60 blocks emitted from the network that produces one block every minute.  I think they may be correct, but I need to study your paper more closely (I do agree with the first part of your assertion though, which is that the probability of success does indeed depend on the number of confirmations).  

I like this term "cementing."  And I like how you frame it in comparison with having no blockchain at all.  I debate whether it's a good idea or not...if it is, then it should be a part of the protocol and not just something cooked into the source code.  One positive side effect of cementing is that it would force a would be attacker to reveal their blocks before cementing occurs.  I wonder if there is a way that could be accomplished without using cementing (because you'd really want to force an attacker to reveal themselves as soon as possible).

Thank you.

This is indeed what they argue, and this is wrong.

I understand the distinction and not trying to set up a strawman, it's just too wordy. Their actual argument as stated above really is a myth.

The key observation is that the process is entirely non-temporal. It's a series of discrete turns where each party has a chance to move a step ahead. The probability of success relies on the properties of this Markov chain, and there is no place where the time constant can have an effect. Of course, if we were talking about the time it takes to complete the attack, things would be different.

Yes, and hence reflect the average amount of work an attacker would need to do to overturn them. But not the probability of success, when the actual number of blocks (and the hashrate) is invariant.

I've been meaning to write a post discussing a framework for various levels of synchronization, where each can be cemented but overturned by the next. For a few months now, haven't gotten around to it yet.

Where did this erroneous argument come from anyways? It is a very basic mistake.
Anyways, thanks for helping to provide some rigorous documentation for people. It helps greatly in the fight against BS.

So an attach on the quicker blockchain would succeed of fail more quickly but the probability of success for both chains would be equal, right?

Right. (When the number of confirmations is equal.)


Another way to look at this: If the attacker does not have majority, he will find on average less blocks than the honest network. If the average thing always happened, he would always fail. Variance in the number of blocks works to his advantage, because he has a chance to be lucky and get more than the average number of blocks, enough to beat the network. Assuming a fixed (#blocks * avg. time), the smaller the avg. time, the more individual items are being tracked, and so (as is the case with these Poisson processes) the lower the relative variance, and the lower the chance to luck out. This is similar to how mining pools reduce variance by basing the reward on tracking the number of abundant shares, rather than the number of rare blocks.

I don't know. It's pretty old.

But assuming two networks with the same hash rate, a smaller avg. time causes reduced difficulty. This increases variance and counters this effect, no?

It also seems more economical to try an attack on the chain with the lower difficulty, since the expected cost for one attempt is lower, but the expected return is realistically the same.

Difficulty doesn't matter for the success of an attack. The attacker is racing the rest of miners.

Imagine a magic network with no latency and difficulty so low that every hash made a valid bock. You could comfortably accept 1000 blocks or so with no risk of (lucky) double spend and it would take a microsecond or less.

Meni, thanks for the paper, it was well written and informative.

An attacker could choose to hold off the tranaction(s) they are sending to the merchant(s) until they find a block that double-spends those transactions. Then, they send off those transactions with a good fee and hope to god that they are included in the next block, otherwise it would be as if the merchant got the benefit of waiting an extra block. However, unless you only started mining after the transactions made it into a block (which would be stupid, since you'd start a block behind), it is better to premine and hope that the transactions make it into the next block than it is to start mining when the transactions are sent since the transactions could still make it into the next block, except you might not have one mined yet, yourself.

Because then you risk wastefully reverting more blocks than you need to because your transaction(s) didn't get into the first block on the honest side of the fork, decreasing your chance of success.

Assuming the same number of confirmations, there is the same variance in the number of blocks found by the attacker.

Assuming the same wait time, a reduced difficulty means more blocks found on average. For Poisson-distributed variables, the variance is equal to the mean, so the standard deviation is equal to the square root of the mean. With a larger mean, the relative standard deviation is lower.

Yes. But this is dwarfed by the fact that with a lower difficulty, you can increase the number of confirmations with the same wait time and greatly reduce the probability of success (which is the main factor in the economics of the attack).

The attacker can mine away and only start the attack when he finds a block. This is easy to do even with a low hashrate. If you are familiar with the Finney attack, it is a special case of this where the number of confirmations is 0, and hence the probability of success is 100%, with any hashrate.

He could do that, and a fuller treatment of this is under the scope of the economic discussion. However, there is a big gap in the effectiveness of pre-mining one vs. two. Pre-mining 1 block is a "sure thing" as the attacker counts on finding a block anyway, so he may as well postpone the attack until he does. But after he finds the first block, waiting to get more blocks just puts him at risk that the honest network will regain the lead. If this happens he loses the reward of the block he found. He is in a hashrate disadvantage so he's better off pressing his head start.

If the only attack cost is the lost block reward, then he should pre-mine just one block because the risk of losing the reward is the same and this gives him a better chance to benefit from it. If, however, the main cost is the illiquidity of the goods purchased, he should indeed make multiple attempts to pre-mine several blocks, and call the thing off with every failure.

Is it?  Note, there is no time component being discussed here.  It is simply saying that 6 confirmations is equivalent to 60 confirmations (given equivalent overall hash rate).  It doesn't matter if the 6 or 60 blocks take 10 hours or 10 seconds to arrive.

Just out of curiosity is a "time stamp" being included in the block header?

It is. 6 confirmations is equivalent to 6 confirmations and 60 confirmations is equivalent to 60 confirmations. The probability of success is uniquely determined by the number of confirmations and the attacker's percentage of the total hashrate. With these two fixed, it does not at all matter what are the difficulty, the total hashrate, the average time between blocks, or the actual time it took to find those confirmations.

Frankly, I don't see why I have to repeat myself. I have stated my result, provided a derivation for it, and clarified it in previous comments. If you disagree, you should either point out a flaw in my argument, or provide a derivation for an alternative result which we can then discuss.

Yes (which means once a block is found its timestamp cannot be changed), but there is some wiggle room. Also, a new node joining the network has no idea whether blocks which are given to him were actually found at the time specified by their timestamp.

Thank you for the producing and publishing this paper (sent you a donation). We need much more of this kind of work. I would really like to see more academic papers on Bitcoin.

A couple of questions/thoughts:

Are you considering to publish this elsewhere, submitting it as a conference paper?
Are you associated with a university or an old graduate like myself?

The paper describes probabilities of doing double-spending attacks where the attacker has some amount of hashing power. To have a significant probability of a successful attack he would need quite a bit of hashing power as todays hash rate is quite high. I believe that such an attack would be costly, and only feasible for high value transactions.
However, there are many merchants today who accept zero-confirmation transactions using merchant solutions such as BitPay (Tony, Steve, correct me if I am wrong).

So assuming that the attacker has no hashing power at all, how easy would it be to mount a double-spending attack against a zero-confirmation accepting merchant? And what can you do to detect a zero-confirmation double spend attack or avoid to accept the transaction if a double-spend is happening?

So basically the attacker broadcasts two conflicting transactions (T1 and T2) and hopes that T1 reaches the merchant while T2 reaches as many miners as possible.

I see two ways of protecting against this attack with some probability of success:

1. Listen to the network for a few seconds and see how well T1 propagates: Since nodes will not relay T2 if they have seen T1 you should receive fewer transaction inventory broadcasts containing the hash of T1 than what you would normally receive. The better you are connected to the network the more material you have to base your decision on.

2. When you receive T1 you listen for a conflicting transaction for a few seconds. If you find one there was a double-spend attempt. This sounds simple, but since nodes do not relay T2 if they have seen T1 you only receive T2 if you have connections to nodes that received T2 before T1. The more connections you have the higher probability there is of you getting T1 and T2.

There may be other smarter ways of detecting/preventing zero-confirmation double-spends, but this is what I came up with. However, the above raises some questions:

• On a network of N nodes, how many nodes should you be connected to in order to have probability P of getting both T1 and T2?
• How long time should I listen to the network for approach 1 and 2?
• Within what margin should the "propagation-level" be for me to have probability P that the transaction is not a double-spend?

So here is my suggestion: If you write a paper of the same quality on this topic and answer some of the above questions I'll donate 5 BTC to you for your effort. I could imagine that BitPay and others would be interested in your analysis as well.

Interesting... the conclusions presented in the paper seem valid.

I wonder if the devs are already working on this, because it seems serious.

Thank you.

I'm not currently associated with any university, but I originate from the Weizmann Institute of Science, so if I push this forward it may be done in collaboration with them. My thesis advisor is a member of a group that is interested in Bitcoin.

I've never published any papers so I don't know what the procedure would be, and for now I'm sticking to myself and maybe ArXiv.

If the attacker has some minimal hashrate, he can double spend quite easily with the Finney attack.

If not and the attack is based purely on propagation, I should point out that there is already a paper on this subject, Two Bitcoins at the Price of One? Double-Spending Attacks on Fast Payments in Bitcoin (http://eprint.iacr.org/2012/248.pdf). I haven't studied it in depth.

I agree with your analysis, but would like to add that the client can be modified to respond to queries "Do you know of a transaction that conflicts with T1?". This way, if a peer hears about T1 and then T2, he will not forward T2 to the merchant, but he may respond that he is aware of it, giving the merchant another chance at detecting a possible double-spend.

I think these questions can be answered with some modeling assumptions (and this may have been done in the linked paper). If more is required I'm open to solicitations for further research.

Thank you again for your generosity. I should point out though that (assuming this is relevant) more pledges would be needed for me to undertake entirely new research at this point.


This is out of the scope of the devs, it's a core protocol issue. I think defending against casual double-spenders is certainly feasible. The real problem is with well-funded entities trying to harm Bitcoin with majority attacks.

There are some proposals for alternative systems (e.g. proof of stake), but they are fairly controversial. I think the solution to DoS attacks is a DAG system as was described once by Maged.

I did a little thinking and came with this quick&dirty trick, but it will probably be a stupid idea, so please dont bite me:

Wouldn't it be possible to completely disable resending/re-broadcasting valid transactions having X or more confirmations ?

I mean if a client knows that sufficient amount of other clients from enough different IP ranges has the transaction confirmed, then it will reject the same transaction broadcasted with different parameters.

So, does this mean that litecoin and the like are way more secure against these double spends compared to bitcoin? assuming it would have the same hashrate backing it....

This seems equivalent to cementing, see above.

Yes, for a given amount of average waiting time. In practice you'll start with the level of security you want, from it deduce the number of confirmations, and this will determine the average wait time; in Litecoin it will be shorter than in Bitcoin.

Thanks for the link, I'll give it a spin.

Yes, absolutely, there is a lot of time and effort in producing a sound paper. I think some people (Tony, Steve, vink vink) have a lot at stake on accepting zero-confirmation transactions. I am merely trying to get something rolling  :)

So, say i find 3 confirmations acceptably safe. That's exactly 3 confirmations in litecoin too for the same safety?
That's 30 minutes vs 6 minutes (it was 2min/block iirc)... on average.
Why are we still using bitcoin instead of litecoin again? because it's most accepted?

Because litecoin's algorithms are built so that mining with GPUs is infeasible, so it would be very easy for a large & powerful entity (US govt, FED or whatever) to build their ASICs quickly and completely destroy Litecoin.

Litecoin is basically ASIC-only thing, there is nothing else that will mine them efficiently.

Why don't you just say yes, because it is more accepted instead of making up a bullshit reason?
[sigh; I will let someone else take care of this idiot]

This is not a bullshit reason. I was thinking about buying some litecoins myself, but i resigned because of this.
Litecoin can be easily killed by creating a simple FPGA or ASIC which will make 51% or even 95% attacks very easy, because there are no GPUs in the game.

Don't you see how big of a flaw is this ?

EDIT:
Also, because of litecoin's blocks are produced 4 times as often, Litecoin will require few times as much bandwidth and disk space comparing to bitcoin.

EDIT2:
Merged mining is also impossible with Litecoin, as its algo is completely different.

Maybe you didn't know, but ASICs for Bitcoin are being built already and are a couple orders of magnitude more efficient than GPUs. They are going to destroy Bitcoin!!! What was your point again? Bullshit!

Bullshit! The bandwidth is almost entirely consisting of transactions. Block headers are negligibly small.

This cuts both ways, you know. Bitcoin is not compatible with Litecoin. It's algo is completely different!

Why try and invent a bullshit reason when there is a legitimate one? (the wider adoption of Bitcoin)

This is right. Concern over double-spends is way overblown. They don't make economic sense. Majority attacks should be the #1 concern, not double-spends.

That said, I thought it might be useful to point out that the superior double-spending properties of litecoin are not intrinsically tied to the shorter block interval.

You could arrange bitcoin so that you had to submit n different PoW hashes in each block; each of which met a difficulty target (about n-fold lower than the current one).
Right now n=1. You could increase n. Doing this would reduce variance in the block arrival rate and make it harder to do execute the type of minority attacks Meni describes in his paper.

This is the approach I suggested using to improve Colbee's PoA lotteries.

You are actually right, however my point is not completely bullshit.
It will be much easier to gain 51% in Litecoin than in Bitcoin, because there is (and probably will be) much less hashing power, as there are no GPUs in the game.


OK, i didn't know that. My point is invalid.


I don't think you understand.
Because Bitcoin's adoption is wider, if Litecoin had the same algo, all the equipment used to mine Bitcoin could be used to mine Litecoins AND Bitcoins at the same time (with some modifications of course).

https://en.bitcoin.it/wiki/Merged_mining

So i find it a critical flaw that this isn't possible. It that was possible, Litecoin could quickly gain hashing power close to Bitcoin, which would make it stronger. Without it, it may take long, long, long years.

Do you mean there will be n independent nonce's to search, each affecting its own hash? If so, I think it would give an unfair advantage to the larger pool, thus discouraging decentralisation. Not good at all!

Could somebody link to these proposals, please? Both this "proof of stake" and "DAG". I don't even know what DAG stands for... if I remember well there was this blocktree thing Maged once discussed in these forums, it didn't really prevented chain freezing (I'm assuming that's what you mean by DoS), but it created some difficulties to the attacker. I wonder if these proposals you talk about are better.

EDIT: Ok, it didn't take me long to find this https://en.bitcoin.it/wiki/Proof_of_Stake
Still don't know what DAG stands for though.

I'm not sure exactly about the context but DAG normally refers to a "Directed Acyclic Graph" (think of an OS folder structure).

DAG stands for Directed Acyclic Graph. The PoS article you linked to mentions this once, not going into detail. I think it refers to the structure of the block relations. The blockchain currently forms a tree, where different branches are not reconcilable, with one having to be eventually forfeighted. I guess the proposal is to make it possible for branches to join back. I don't know of any such proposals though.

If I understood the paper correctly, using the method described by @Meni Rosenfeld, it is possible to double spend as many transactions as one wants simultaneously, thus completely paralyzing the entire network (Somebody correct me if I am wrong).


They make sense, if you are a government or a banker with millions of USD in accounts.
Few millions is really nothing for destroying your greatest competitor.

Sorry to be offtopic
but guys, Litecoin has been mined on GPU for a long time, starting with Solidcoin's Reaper having scrypt algo and in July of this year I held pledges for to pay cgminer's developer to have scrypt support added

Thanks to Meni :)

Thanks. It's probably the blocktree thing then. I was aware of that, but until now hadn't seen this proof-of-stake concept, and there's even an implementation already. And I thought I followed bitcoin world closely enough...

Not quite like that, no. More like the pool broadcasts block t and then (n-1) people come up with additional solutions for block t and broadcast them in no particular order. Then the block t+1 builds on the original block t as well as the extra (n-1) solutions. You can just think of it as inserting (n-1) empty blocks as spacers between each block pair. The spacers act as variance killers. The information in a spacer is just the winning hash together plus an address to send block reward to.

I'm assuming here that block solutions are really tiny in terms of information and that (unlike full blocks) solutions could diffuse very rapidly through the network. Is this true? This question has been kind of nagging me. How long does it take 200 bytes to diffuse through the network vs. 200 kilobytes?

If there is no significant difference in diffusion time, then you might as well include closely spaced complete blocks (as in litecoin).

OK, I see. However, it's still not clear why a large block (of size n*k) followed by a few (n-1) empty ones would be better than a few (n) smaller ones (of size k).

This is my explanation. Under normal circumstances, blocks are built in sequence. This means I have to see block t-1 before I can build block t.

Spacer blocks are different. A spacer block wouldn't have any function except inserting work and a time delay between blocks. It would need to build on the last full block t, but would not need to be aware of the last spacer block. Therefore, spacer blocks are not ordered. They could be constructed in parallel rather than in sequence. It would be fine for everyone to have their own copy of the blockchain which orders the spacer blocks between blocks t and t-1 differently. Unlike a regular block, disagreements about spacer block order would not cause the network to fork. This should mean that spacer blocks could be mined at relatively narrow time intervals without causing a network disruption.

I know next to nothing about P2P networks. So please anyone who is enlightened jump in to set me straight.

[This is irrelevant in any case. Because as Meni points out it is the majority attacks that are the real problem and adding spacer blocks doesn't help with this.]

Thanks. It does make sense now. This sounds like a very special case of DAG proposal, whatever that is. Do you have a link to a discussion of that?

I wasn't around for the DAG proposal. I don't even know what a direct acyclic graph is. Sounds interesting though!

If you allow the branches of a tree to merge, you don't have a tree anymore: you only have DAG. This is what DAG is.

In your proposal it's similar, although very limited: you allow the blockchain to be forked into (n-1) blocks just to be joined back immediately. I guess relaxing this requirement and allowing the parallel branches to be non-empty and arbitrary length (as opposed to 1) could give more flexibility.

Yes. (It's 2.5 min so 7.5 min).

1. Yes, because it's more accepted. If we switched to a new currency every year because of some alleged trivial benefit, we would miss the point.
2. Decreasing the average block time has the obvious benefit of reducing time for confirmations. But it has equally obvious disadvantages:
a. There is more forking, meaning an attacker has more effective hashrate. I've ignored inadvertent forking completely in the paper, but it starts being a problem if we go wild with reducing the time constant.
b. There are more blocks, and hence more block headers. For a full node this is negligible but for an SPV (aka lightweight) client this makes a world of difference, especially if it is to be run on weak mobile devices.
So some tradeoff needs to be chosen. It can be argued that 2.5 min is better than 10 min, but it's far from clear-cut.
3. It doesn't really matter ultimately. If you can afford to wait more than a few seconds, you can usually afford to wait an hour. If not, I believe the gap can be bridged with Trustless, instant, off-the-chain Bitcoin payments (https://bitcointalk.org/index.php?topic=91732.0).
4. Because Litecoin might be more prone to botnets.

Interesting, need to think about this.

This is indeed what a DAG is and I think we're thinking about the same proposal. I might try linking to it sometime.

I didn't get this. Can you explain in more detail ?

TL;DR (or rather: TL;DW). I watched first 30 seconds and I see no connection.

I don't have time to watch the entire video just to get your point. So get to it.

The bomb in the video says something to the effect of "I must think of this". There is no point, just bad trolling.

Excellent paper & thread, posted to reddit (http://www.reddit.com/r/Bitcoin/comments/14rbxv/analysis_of_hashratebased_doublespending_a/).

1.


I think the time constraint assumption does have merit. The attacker can rent hash power on a hash market (https://en.bitcoin.it/wiki/Hash_Market) (or just rent GPUs/ASICs directly from a cloud provider), he does not necessary need to exclusively own a large hash rate himself.

2.
Added Block Cementing (https://en.bitcoin.it/wiki/Block_Cementing) to the wiki.

A lot of big thinking behind this paper.. Thanks for doing it, as I see, it seems to raise some serious tought, and may help bitcoin become better in the future.

Meni Rosenfeld : You seem to have put a lot of time and effort in studying this, and writing a such good paper..

Why have you done this ?  I mean, what was you motivation to study this so deeply ?

Yeah, I think you could do a lot with this concept of a DAG. It would allow for a lot of asynchronous computation. For example, suppose that all coins are colored based on their block origin. Spacer blocks contain txns of one color only. Then rearranging the ordering of spacer blocks does not result in forks unless you alter the order of two blocks of the same color. Hmmm... I think there is something useful here, but it also seems really complicated.

The problem with litecoin isn't the future possibility of a shadow government creating a litcoin ASIC, it's the real present danger of the network being taken over by bot-herders.

Also because no one accepts it.

Yes, I see it now.  I believe it's a correct analysis (and not what I had previously thought).

Nice analysis, and well written. Thank you for not making it overly alarming. More of this research is always interesting.

I guess this is Maged proposal, isn't it? https://bitcointalk.org/index.php?topic=57647.msg686497#msg686497

I don't think it's feasible. You don't just walk into a store and buy plut rent this kind of hashrate, it still requires a lot of preparation. GPUs will soon be obsolete and ASICs are Application Specific, a provider of SHA-256 ASICs is a hash market. And I still think if it becomes possible we lose anyway, since the security will be only linear in the number of confirmations. A fuller treatment of this is under the scope of more accurate economic modeling.

Great.

Well, first it's worth pointing out exactly how much effort was involved. I have spent about 12 hours working on this paper. It is this low because the paper is something of a "v Pravde net izvestiy, v Izvestiyakh net pravdy". There is really nothing new in sections 1-5. 1-2 are just common knowledge (added for context), 3-5 (which are what I really wanted to write) are just drilling down the analysis in Satoshi's paper. The only differences are:

1. Instead of a Poisson distribution, I used a more accurate negative binomial distribution.
2. I assumed the attacker needs to be 1 block ahead to win, but also that he pre-mines a block a la Finney; these two cancel out. Also, there is some ambiguity about how Satoshi counts the confirmations.

Writing when you know what you want to write doesn't take that much time. (It does require a specific state of mind which is not always available.) Half the time was spent figuring out how to properly align the blockchain diagrams.

Section 6 is mostly novel and required some research, but it's not meant to be authoritative, more of a starting point for additional analysis. I included it because the paper wouldn't be complete without it.

My primary motivations for writing this were:

1. I hate misinformation and myths. When I see important mistakes constantly being repeated I want to do something about it. It might end up saving me time by sparing the need to correct the mistakes every time.
2. It can signal my skills and commitment to Bitcoin, which may help expand my business opportunities (aka indirect monetization).
3. While it is hard work, some of it can also be fun (the math part, not the figuring out xy-pic part).

Altruism plays variable roles in different things I do, but I can't honestly say it had more than a minor influence on this in particular. So all in all #1 is why I wanted to do this, #2 is why I could justify allocating time to it, and #3 is a perk.

That's the one. I haven't spent time thinking about it in a while, AFAIR it's not completely fleshed out yet, but I think these ideas are the key to preventing a majority attack that rejects all transactions.

That is an excellent paper discussing the hash-rate with a very straight mathematical explanation. I appreciated very much.

Only this part I could not understand completely:


What did you mean by 'cost of neutrally mining' and how the 'number of confirmations required becomes linear'?

'Cost of neutrally mining' = how much it costs to mine each block without trying to double-spend.

The cost of double-spending is roughly inversely proportional to the probability of success. If the hashrate isn't too high, the probability is exponentially decreasing with the number of confirmations, hence the cost is exponentially increasing. So the needed number of confirmations is logarithmic in the value of the transaction. If the attacker has majority hashrate, the probability of success is essentially 1, so it cannot help us make the attack expensive. The cost to double-spend in this case is roughly proportional to n/(2q-1), where n is the number of confirmations and q is the attacker's hashrate. Thus the number of confirmations needed is linear in the value of the transaction.

Meni R.,

I ready your paper and got most of it.  I have to admit my knowledge of binomial distributions and such is a little rusty, but I get your points.  Of course, rhetorically speaking, what is the optimal balance between the proof of work difficulty and the target time between blocks? Why not reduce the target time to 30 seconds instead of 10 minutes?  Great paper, though, and thank you for your contribution, certainly worth a donation.

Finding out an optimal tradeoff would require more analysis. Essentially, about t/T of the honest network's total hashrate is lost due to forking, where T is the time between blocks and t is the typical time to propagate a block on the network. If we assume t = 10 sec, then for T=10 min 1.7% is wasted, and for T=30 sec 33% is wasted. How this compares with the ability to get more confirmations in a unit of time depends on the specific scenario. The additional resource cost to SPV clients (inversely proportional to T) should also be considered.

I had a suggestion once for self-adjusting dynamic block frequency (https://bitcointalk.org/index.php?topic=79837.0) but I don't think it's really going to work. Even with a static system 2-3 minutes is probably better than 10, but I doubt this will be changed for Bitcoin.

Thank you for the donation.

The few major issues I've come to realize with that proposal are:
1) It will most likely require cementing at some level so that miners don't "save up" their mined blocks to guarantee themselves a block in the main chain that won't be kicked out by someone else by chance.
2) On a similar note, Finney attacks are guaranteed to be successful, unless some form of block discouraging is used. This wouldn't be that big of a deal if the main chain gets extended every few seconds, though.
3) Any currently-backwards-compatible change that only requires a majority of the miners to upgrade to go into effect would require a hard fork if this were used. This might not be that much of a problem once the Bitcoin network is more mature.

Speaking of #3, that directly relates to that whole contract thing theymos brought up recently: it would truly become impossible to make lost coins unspendable if ECDSA is ever broken, so that would have to be considered too.

Anyway, that's the update on that.

Inetresting paper for the modelling part but rather weak in dealing with the economics of the double-spend.
A thorough economic analysis of the double-spend cannot go very far without game theory (Nash equilibrium in particular).

For example
"An attacker with majority hashrate can not only double-spend any trans- action at no cost (above the cost of running the mining hardware normally)"

Wrong: the attacker can only double-spend his own coins, meaning he must earn or buy a stash of coins upfront. As a result of his attack, his cost includes the initial value of the coins (before the attack) minus whatever value is reached after the attack is stopped by counter-measures (like new check points in the blockchain or merchants temporarily holding deliveries on bitcoin payments).

Also, the cost of performing a criminal activity (theft from merchants) with serious legal consequences (financial dammage to the stakeholders) must be factored in unless your assumption is the perfect crime (the promoters of the attack remain perfectly anonymous: a fairly aggressive assumption).

In short, if Visa or a similar organisation (incumbent stakeholder) were to engage in such attack, it would not be long before a disgruntled employee aired the story. Harnessing enough power to perform a serious attack is not something that could go unnoticed.

The same flaw (silo thinking) was found in the microsoft paper that dealt with bitcoin endogenous inventives (algorithmic rewards) while ignoring completely exogenous incentives (contractual rewards).

I tend to agree, the economics part is not meant to be conclusive, rather act as a starting point for how an analysis could be done.

This cost exists but as I explicitly stated, I don't think it's significant since other factors limit the possible scale of attack.

More generally, you can include most "practical" costs as terms in the model. Future work will include formulating a model that can encompass most such things and be tractable to solve. Then it's just a matter of figuring out all the costs and plugging them in.

There's something very basic about research papers that some people seem not to get. You can't give and solve a model that 100% accurately reflects reality. You need to make some simplifying assumptions and even if those assumptions aren't correct per se, they often have less effect on the final conclusions as it seems; even if the effect is significant, the more accurate model will rely on the intuitions of the simpler case. You don't formulate general relativity without first having a firm grasp of Newtonian mechanics. A big part of the trick is knowing when the assumptions are adequate, and how to refine them when they are not.

I have a question about this paper.

We will not
use this assumption, but rather model m more accurately as a negative binomial variable; it
is the number of successes (blocks found by the attacker) before n failures (blocks found by
the honest network), with a probability q of success. The probability for a given value of m
is
P(m) = (m + n − 1) p ^n * q ^m
                 m

I doubt this is correct. When the attacker is preparing a fork, he is not competing with the others. There are two completely independent mining process. I don't know why this can be modelled as a negative binomial variable.

When others find a block, it's not the attacker's failure. He will not restart a mining based on other's block, but has to continue mining based on his own previous block.

Moreover

"We will denote by az the probability that the attacker will be able to catch up when he is
currently z blocks behind. Clearly, if z < 0 then az = 1 as the attacker already has a longer
branch. To find az when z ≥ 0, we condition on the first step. If the next block found will
be by the honest network, which happens with probability p, the attacker will now be z + 1
blocks behind and his probability of success will be az+1. If the next block found will be by
the attacker, which happens with probability q, his probability of success will be az−1. It
follows that az satisfies the recurrence relation
   az = paz+1 + qaz−1."


This is also not so straightforward. As I said, there's no competition, so what's the meaning of 'next block'. They are working on two different chains. When you find a block earlier, your opponents do not need to start from the scratch. They keep on working on their current block, on which they have spent , so the probability for they to get the next block earlier than you is much much higher than 'p'.

It seems that if all these words in this paper make sense, actually the author assumes the mining block is a memoryless process. It means no matter how much time you have spent on mining the current block, the expecting time from now to the moment you get the block is always the same (around 10 minutes). Begin computing early does not bring you any advantage. This is quite counter-intuitive.

Therefore, now I really doubt the correctness of this paper.

It's a well-known fact that block finding is memoryless. Miners "start from scratch" every fraction of a second. They try a hash, and it being a valid block is completely random and independent. If the hash is not valid, it does not make the next hashes any more likely to be valid. If a miner mines for 20 minutes and finds no block, he is not any closer to finding one than when he began.


"Failure" is the standard term used when discussing negative binomial distributions. It doesn't mean anything.

If you look at continuous time these are two separate process. However, we are certainly allowed to introduce an abstraction that puts all the blocks found in a sequence. Each such block will have probability p to be honest and q to be the attackers (independent of other blocks). The rest of the analysis follows.

Yes, if the mining is really memoryless, then I agree that everything makes sense.

So it means because the nonce space is almost infinite, excluding part of it does not help at all.

If the mining is memoryless, then does it make another popular paper published last year less meaningful? (http://arxiv.org/abs/1311.0243). They argue that if a selfish miner get a block, they can hide it and starts to mine the next block based on it earlier than others so they can have an advantage.

What's the advantage then? The only advantage is that they have a slight chance to find the block before others having a chance to work on it. If they publish the block before finding the next one, then no matter how long they have worked on it, they don't have any advantage.

That paper correctly treats block finding as memoryless (it may or may not be correct about other things). You'd need to examine their analysis to understand why the attack works. The basic idea is that the attackers are attempting to build a long chain which is unknown to the network. If they manage to find 2 blocks in a row, they have the ability to evaporate a block found by the honest network, by releasing their longer, previously hidden chain.

As long as the attacker can use their hashpower to confirm a block that contains the double spend then the attack will be successful. The success rate of executing this attack increases as your hashrate increases until being 100% success when you control more then 1/2 the network.


This could be true if the seller was willing to accept a 0/unconfirmed transaction. A seller would want to wait some time for the transaction to propagate throughout the network prior to releasing gods as an attacker could potentially release a TX to a very well connected node then one second later release a transaction to a poorly connected node that the "attackee" is suppose to believe will go through. For some period of time both transactions will appear to be valid on some parts of the network but after some time the TX will likely fall out of the pending pool on nodes.

Are you agreeing this is a myth or disagreeing?

Anyway, it's not just "confirm a block", it's make an alternative longer chain after the seller waited for n confirmation.

Note that this is an analysis of hashrate-based double spending, not double-spends of 0-conf based on network topology.

I am trying to give clarity to the facts that contradict the myth. You don't need 51% to be successful in double spending coins but the more hashpower you have the more effective this attack will be.

Well, clarifying the facts is what the titular paper is about...

No, the security comes from the average hashpower needed to produce a block. If you adjust the difficulty down, you reduce the security one block provides.

Due to similar flaws, even put into account while projecting I believe PoS coins are the future. Yes, bitcoin will still stay the king, however, if more people vote, why not turn BTC into PoS??

That's the myth that I'm refuting.

Though to be accurate - reducing the time per block does reduce the security one confirmation provides, but not in the way you think.