Topic: Selfish mining double spend (Read 874 times)
This subject is somewhat covered by Ayelet Sapirshtein, Yonatan Sompolinsky, and Aviv Zohar in "Optimal Selfish Mining Strategies in Bitcoin" (https://arxiv.org/pdf/1507.06183.pdf). They conclude:
"To summarize, the existence of a miner for which selfish mining is at least as
profitable as honest mining fundamentally undermines the security of payments,
as this attacker bears no cost for continuously attempting to double spending,
and it eventually must succeed. Similarly, an attacker that cannot profit from
selfish mining alone, might be profitable in the long run if it combines it with
double spending, which potentially has grave implications on the profit threshold."
They don't dig very deep into this though.
"To summarize, the existence of a miner for which selfish mining is at least as
profitable as honest mining fundamentally undermines the security of payments,
as this attacker bears no cost for continuously attempting to double spending,
and it eventually must succeed. Similarly, an attacker that cannot profit from
selfish mining alone, might be profitable in the long run if it combines it with
double spending, which potentially has grave implications on the profit threshold."
They don't dig very deep into this though.
> One would have to carefully calculate that taking every possible outcome of the chain race into account. And then you could estimate how long and adversary with mining power x would have to run his attack until (expected time) he succeeds in double spending.
Yes, and you could make as many of the outcomes as possible useful for double spending. Make sure to have many different outputs of different value. Create one transaction for each of those outputs and put them in your secret chain. As soon as you have N+1-k blocks for any N, make a purchase on a site that accepts N confirmations. Imagine you have108 outputs:
1: 0.01 BTC
2: 0.1 BTC
3: 1 BTC
4: 10 BTC
5: 100 BTC
6: 1000 BTC
7: 10000 BTC
8: 100000 BTC
Assume also that you have 25% hashpower (you get 1 block in about the same time others get 3 blocks).
Do your selfish mining thing. When you have a lucky streak of m blocks, make a purchase according to this table:
Note also that on each streak level, you can make several (hundreds) of double spends, if you have prepared such outputs, instead of just one, which makes this attack even more attractive.
Edit: number of outputs
Yes, and you could make as many of the outcomes as possible useful for double spending. Make sure to have many different outputs of different value. Create one transaction for each of those outputs and put them in your secret chain. As soon as you have N+1-k blocks for any N, make a purchase on a site that accepts N confirmations. Imagine you have
1: 0.01 BTC
2: 0.1 BTC
3: 1 BTC
4: 10 BTC
5: 100 BTC
6: 1000 BTC
7: 10000 BTC
8: 100000 BTC
Assume also that you have 25% hashpower (you get 1 block in about the same time others get 3 blocks).
Do your selfish mining thing. When you have a lucky streak of m blocks, make a purchase according to this table:
| Lucky streak | Use output | N | k | accumulated value |
| 2 | 1 | 1 | 0 | 0.01 |
| 3 | 2 | 2 | 0 | 0.11 |
| 3 | 3 | 3 | 1 | 1.11 |
| 4 | 4 | 4 | 1 | 11.11 |
| 5 | 5 | 5 | 1 | 111.11 |
| 5 | 6 | 6 | 2 | 1111.11 |
| 6 | 7 | 7 | 2 | 11111.11 |
| 7 | 8 | 8 | 2 | 111111.11 |
Note also that on each streak level, you can make several (hundreds) of double spends, if you have prepared such outputs, instead of just one, which makes this attack even more attractive.
Edit: number of outputs
I think you are basically right.
If you are mining selfishly anyway then double spending attempts do not cost you very much.
However, the probability that a selfish miner will get a lead of 5 blocks is rather small even with 25% mining power. If the adversary has a lead of 5, the honest network has a chance of 32% to find 4 blocks in a row, reducing the adversary's lead to just 1. The adversary would now have to publish his chain in order to not lose his block reward. Therefore the double spend would fail because the merchants do not yet have accepted the payment of the adversary because of the confirmations needed.
That's just one example of how a double spend attempt might fail. This further reduces the probability of a successful double spend.
So your idea is basically right but the probability for this to work should be rather small. One would have to carefully calculate that taking every possible outcome of the chain race into account. And then you could estimate how long and adversary with mining power x would have to run his attack until (expected time) he succeeds in double spending.
However, at the moment I don't consider this a threat to Bitcoin. Selfish mining increases your relative reward (how much you get compared to what the honest network gets) but it is not a rational strategy if you want to increase your absolute reward (how much Bitcoin you get for the computing power you provide). Therefore the attack you described would have a certain cost because performing honest mining would be more profitable than selfish mining.
If you are mining selfishly anyway then double spending attempts do not cost you very much.
However, the probability that a selfish miner will get a lead of 5 blocks is rather small even with 25% mining power. If the adversary has a lead of 5, the honest network has a chance of 32% to find 4 blocks in a row, reducing the adversary's lead to just 1. The adversary would now have to publish his chain in order to not lose his block reward. Therefore the double spend would fail because the merchants do not yet have accepted the payment of the adversary because of the confirmations needed.
That's just one example of how a double spend attempt might fail. This further reduces the probability of a successful double spend.
So your idea is basically right but the probability for this to work should be rather small. One would have to carefully calculate that taking every possible outcome of the chain race into account. And then you could estimate how long and adversary with mining power x would have to run his attack until (expected time) he succeeds in double spending.
However, at the moment I don't consider this a threat to Bitcoin. Selfish mining increases your relative reward (how much you get compared to what the honest network gets) but it is not a rational strategy if you want to increase your absolute reward (how much Bitcoin you get for the computing power you provide). Therefore the attack you described would have a certain cost because performing honest mining would be more profitable than selfish mining.
I've been thinking about double spends and selfish miners. Imagine a miner mining selfishly for some reason. Wouldn't she get to double spend for free?
So if sender has 25% hashpower and N=6, she needs to premine 5 blocks before sending the transaction and be pretty sure to succeed. This is because the sender will probably be able to produce 2 blocks during the time it takes the honest miners to produce 6 blocks. N+1-k=6+1-2=5.
Using this method, the sender can always keep a tx spending all her UTXOs in her private branch. As soon as she gets a lucky streak, she can place orders in one or many shops, spending all her money. and with high probability succeed with the double spending.
Peter Todd's calculations (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003607.html) on selfish mining shows that you don't need more than 30% of the total hashpower to find more blocks than the other miners.
Isn't the conclusion of this that a big (>29.3%) miner that mines selfishly for some reason, gets to double spend at no extra cost?
Another way to look at it may be that this double spend attack is a good reason to do selfish mining. But then it's at the cost of some lost blocks, since you have a higher risk of losing out on your block rewards when mining selfishly. Your gains from double spend must exceed those losses.
Are there any errors in my reasoning?
- Sender prepares a transaction paying herself and spending all her UTXOs
- Sender mines secretly on the honest best chain tip until she gets a lucky streak of N+1-k (not revealed) blocks in a row, while the honest miners get none. Her double spend tx is in any of those blocks.
- Sender places order, gets an address from receiver, and broadcast a transaction paying to the receiver's address.
- The honest transaction gets N confirmations on the honest chain, during which time the sender produces k more blocks secretly.
- Receiver accepts the payment and deliver the goods.
- Sender broadcasts her lucky streak containing the double spend tx which has more work than the honest chain.
So if sender has 25% hashpower and N=6, she needs to premine 5 blocks before sending the transaction and be pretty sure to succeed. This is because the sender will probably be able to produce 2 blocks during the time it takes the honest miners to produce 6 blocks. N+1-k=6+1-2=5.
Using this method, the sender can always keep a tx spending all her UTXOs in her private branch. As soon as she gets a lucky streak, she can place orders in one or many shops, spending all her money. and with high probability succeed with the double spending.
Peter Todd's calculations (https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-November/003607.html) on selfish mining shows that you don't need more than 30% of the total hashpower to find more blocks than the other miners.
Isn't the conclusion of this that a big (>29.3%) miner that mines selfishly for some reason, gets to double spend at no extra cost?
Another way to look at it may be that this double spend attack is a good reason to do selfish mining. But then it's at the cost of some lost blocks, since you have a higher risk of losing out on your block rewards when mining selfishly. Your gains from double spend must exceed those losses.
Are there any errors in my reasoning?
Jump to: