Analysis of hashrate-based double-spending

[Meni Rosenfeld]

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.

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

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.

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.

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

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.

[Jan]

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.

[ShadowOfHarbringer]

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

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

[Meni Rosenfeld]

Thank you for the producing and publishing this paper (sent you a donation).

Thank you.

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?

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.

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?

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

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.

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.

I'll donate 5 BTC to you for your effort.

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.

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

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

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.

[ShadowOfHarbringer]

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

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

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.

[kwukduck]

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

[Meni Rosenfeld]

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

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

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.

This seems equivalent to cementing, see above.

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

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.

[Jan]

...
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. I haven't studied it in depth.
...

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

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

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 

[kwukduck]

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

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.

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?

[ShadowOfHarbringer]

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.

[cunicula]

Why are we still using bitcoin instead of litecoin again? because it's most accepted?

Because litecoin's algoriths 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.

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]

[ShadowOfHarbringer]

Why are we still using bitcoin instead of litecoin again? because it's most accepted?

Because litecoin's algoriths 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.

Why don't you just say yes, because it is more accepted instead of making up a bullshit reason?

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.

[Rotsor]

... it would be very easy ... to build their ASICs quickly and completely destroy Litecoin.

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!

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.

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

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

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)

[cunicula]

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.

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.

[ShadowOfHarbringer]

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!

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.

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.

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

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

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

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)

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.

[Rotsor]

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.

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!

[caveden]

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.

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.

[CIYAM]

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

[Rotsor]

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.

[ShadowOfHarbringer]

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.

This is right. Concern over double-spends is way overblown.

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 don't make economic sense.

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.