Topic: Analysis of hashrate-based double-spending - page 3. (Read 14832 times)

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.

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

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.

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!

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.

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.

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

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]

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.

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?

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 

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.

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

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.

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

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

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.

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