Selfish Mining Simulation

[eb3full]

I couldn't find a thread about this so I'll just post a new one.

kjj, Jeff Garzik and some others on the mailing list have put up a bounty for a:

I'm willing to pitch in 1 BTC as a
bounty for building a general bitcoin network simulator framework. The
simulator should be able to account for latency between nodes, and
ideally within a node.  It needs to be able to simulate an attacker that
owns varying fractions of the network, and make decisions based only on
what the attacker actually knows.  It needs to be able to simulate this
"attack" and should be generic enough to be easily modified for other
crazy schemes.

I've finished a basic implementation of this here:

http://ebfull.github.io/

Forgive its ugliness and the fact it's in javascript.

Explanation: 100 nodes are created which all mine with varying probabilities of solving a block every "second", they mine on the longest chain they see. Node 0 is an attacker which (if you press "sybil attack go" right at the start) has enormous network influence, and incidentally will act as a bootstrap node for the simulation. If you toggle the attack, node 0 will begin propagating blocks in deliberate attempts to orphan competing blocks (so-called selective propagation). You can see the effects this has, in my simulation given the right conditions the attacking node will have success.

The colors represent different chainstates (do reference client developers even still call it that?) and the nodes which are responsible for them. The chain doesn't include transactions or anything like that, just keeps track of the "revenue" of particular miners just as the SM paper describes. The visualization will show forks at the most recent height if there are any.

However, I'm not sure the simulator can be completed without having a public discussion about a number of topics. What is the bitcoin network topology, things like how many supernodes there are, the average latency between nodes, and some of the emergent behaviors of network propagation? Most of the discussion about this has been limited and sparse on the forums, but the simulator can adapt to it. How much of the attack do we need to simulate, and exactly what is controversial? It doesn't appear (to me) that throwing latency at the attack makes it less serious, just slightly less practical.

Whether the incentives are in place to deter this activity, is an economic discussion I'm not prepared for.

[1713966374]

1713966374

[1713966374]

1713966374

[impulse]

Is there any reason this couldn't be done on a dedicated testnet?

[Sukrim]

Well, you'd need to do real mining and also have real clients. This makes it a bit more complex than simulating with metrics that you either just guess or measure from the current live network.

[impulse]

Well, you'd need to do real mining and also have real clients. This makes it a bit more complex than simulating with metrics that you either just guess or measure from the current live network.

Agreed but perhaps some customizable testnet sandboxes would be of some benefit? I'm sure there are some block erupters out there that people would be willing to use to donate some hashing power to the cause. I'll offer up my old mining GPU

[Carlton Banks]

It's oh so amusing to me that the alternative to simulating this so-called attack is to buy upwards of 1 Petahash of mining equipment, call it 1.75 Ph/s to be sure, install and connect it, re-write miner software code to always attempt the Discard attack, deploy mining and wait for "success".

[revans]

If the attack vector is the non issue suggested by the development team, why not put out a modified client which implements a selfish mining strategy, and invite people to test the integrity of the network. That would put the issue to bed once and for all. The author of the paper was criticised for a lack of empirical evidence, so how bout a bit of empiricism from his detractors?

[Peter Todd]

I've been arguing for ages that miners don't have an incentive to broadcast their blocks to more than 50% of the hashing power; seems that my initial analysis was wrong and the threshold is actually only 29.3%:

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03200.html

Think you could add this to your simulator? Simplest version is to just create a single miner with, say 35% of the hashing power and see if they get more blocks than the others. (per unit hashing power) If that proves true, we can try simulating this by failing to relay blocks, large blocks etc.

[bitfreak!]

If the attack vector is the non issue suggested by the development team, why not put out a modified client which implements a selfish mining strategy, and invite people to test the integrity of the network. That would put the issue to bed once and for all. The author of the paper was criticised for a lack of empirical evidence, so how bout a bit of empiricism from his detractors?

Ummmm... isn't this attack protected by the fact that people are encouraged to use one of the "official" bitcoin clients and not a modified client which allows the bad nodes to get together and exploit the network in some way? Inviting people to use a purposely malicious client is ridiculous and proves nothing because the security of Bitcoin is based on the assumption that the majority of nodes are going to be running good clients.

[Peter Todd]

Ummmm... isn't this attack protected by the fact that people are encouraged to use one of the "official" bitcoin clients and not a modified client which allows the bad nodes to get together and exploit the network in some way? Inviting people to use a purposely malicious client is ridiculous and proves nothing because the security of Bitcoin is based on the assumption that the majority of nodes are going to be running good clients.

Yup.

Just like how as a Canadian I leave my keys in my unlocked car and protect it with a post-it note saying: "WARNING! If you steal this car I will politely ask you to apologize!"

[eb3full]

I've updated the simulation to complete it, and incorporate Peter's suggestions.

http://ebfull.github.io/

It's a lot more useful. You can specify the simulation parameters and completely simulate the selfish mining attack. The defaults are fine.

Here's how it works:

• Node 0 is given a specified "hashrate".
• If you enable the sybil attack, node 0 will have enormous network influence to simulate a real sybil attack. This is necessary to make the selfish mining attack practical.
• If you enable the selfish mining attack, node 0 will withhold blocks it finds as described in the selfish mining paper, and will propagate only what is necessary to retain a revenue advantage over the network.

It would be even better if I can specify the exact network conditions of the bitcoin network (average latency etc.) and see the threshold for the attack in practice.

[Dansker]

Could we not test it in "real life" on the testnet?

[Gavin Andresen]

Nice! Can you open source this?

Is the simulator accurately modeling how orphan blocks are (not) relayed?

It would also be useful to see total revenue, and total-revenue-expected-if-everybody-mines-honestly for both the entire network and the attacker.

[Sukrim]

Would be awesome if we could somehow create our own straegies (e.g. "new block arrives: ignore and mine on old block vs. accept and mine on new block").

If there could be a generalized model of this, then one could even do automated simulations with evolutionary algorithms (e.g. weakest 10% of miner strategies are killed off, 2% random strategies are introduced, best 4% of strategies are once mutated and once copied) to discover maybe yet unknown strategies that might be even better.

[kjj]

This is really cool.  I've been watching it run on a couple of computers here.

I'm getting consistent results here, showing that the selfish mining strategy is a really good way to lose 20-30% of your mining revenue.  I'll note that this is roughly what I was expecting.  In every other context, the whole world considers it obvious that getting your blocks out as fast as possible is a good thing.  Still, science is the art of not fooling yourself, and getting the result you expect is not the same as showing that a model has skill.

As fun as this is, it needs to be much faster to be really useful.  We need hundreds or thousands of runs, covering hundreds or thousands of blocks.  We also need to verify that model parameters are realistic, and that the simulation isn't adding or causing un-real effects.  We should also invite the authors to verify that the attack behavior is implemented correctly.*

* To the limited extent possible.

[Sukrim]

Yes, I'd love to have an UI like this on top of the real simulator, right now it seems a bit more concerned (CPU wise) to re-arrange it's nodes than to actually simulate, especially if you drop a few more nodes.

[Carlton Banks]

It would be interesting use the simulation to see what marginal benefit, if any, can be attained for a Block Discard attacker at 49.9%-50% hashing share. Could it help to give the attacker a leg-up into majority hashing?

[eb3full]

Nice! Can you open source this?

Is the simulator accurately modeling how orphan blocks are (not) relayed?

It would also be useful to see total revenue, and total-revenue-expected-if-everybody-mines-honestly for both the entire network and the attacker.

Here's my repo for it: https://github.com/ebfull/ebfull.github.io  (same license as bitcoin-qt)

I'll be better documenting and cleaning up the code. Also, orphaned blocks are now displayed with a strikethrough if they are absent on the best chain. In addition, the proposed patch (honest miners mining on random branches rather than the first branch received) has been added as a parameter.

This is really cool.  I've been watching it run on a couple of computers here.

I'm getting consistent results here, showing that the selfish mining strategy is a really good way to lose 20-30% of your mining revenue.  I'll note that this is roughly what I was expecting.  In every other context, the whole world considers it obvious that getting your blocks out as fast as possible is a good thing.  Still, science is the art of not fooling yourself, and getting the result you expect is not the same as showing that a model has skill.

As fun as this is, it needs to be much faster to be really useful.  We need hundreds or thousands of runs, covering hundreds or thousands of blocks.  We also need to verify that model parameters are realistic, and that the simulation isn't adding or causing un-real effects.  We should also invite the authors to verify that the attack behavior is implemented correctly.*

* To the limited extent possible.

I'd also like to know if the attack behavior is implemented correctly, as it appears the paper on the attack has many flaws -- the algorithm they describe is contradictory and has typos.

However, I think you're reading the revenue of the attacker wrong on the simulation. It's the revenue the attacker has accumulated as a percentage of all of the revenue of the best chain.

My approximate results (after 10000 blocks each):

Code:

35% normal, no attack: ~37.17% revenue
35% selfish, no sybil: ~37.57% revenue
35% sybil: ~37.05% revenue
35% selfish, sybil: ~48.8% revenue

Code:

20% normal, no attack: ~20.92% revenue
20% selfish, no sybil: ~10.9% revenue
20% sybil: ~21.55% revenue
20% selfish, sybil: ~23.11%

This is using a completely different network topology than bitcoin's network tends to have, but it does show that some mixture of parameters (like how well the attacker is connected, the propagation speed of blocks, the orphan rate) makes the attack practical. I've adjusted random things to see the effects: for example, with a higher natural orphan rate, the attack is much more effective as you might imagine, because the attacker can get a better lead on the honest miners.

Yes, I'd love to have an UI like this on top of the real simulator, right now it seems a bit more concerned (CPU wise) to re-arrange it's nodes than to actually simulate, especially if you drop a few more nodes.

I've changed the simulator, now it will not render as often as it will compute, especially at higher speeds. You can also turn off visualization if you'd like. This has improved it significantly.

Ultimately the best simulator will not be in javascript, I'll admit, but I think I can make this simulator efficient enough for rapid prototyping of ideas on a small scale.

[socrates1024]

kjj, jgarzik, is this bounty considered closed with eb3full's submission? Or is it still pending? Is anyone else currently attempting to claim it?

[d'aniel]

kjj, jgarzik, is this bounty considered closed with eb3full's submission? Or is it still pending? Is anyone else currently attempting to claim it?

I'm not sure if they were seeking the bounty, but these two were posted to the mailing list a few days ago:
https://github.com/rbrune/btcsim
https://github.com/christophebiocca/bitcoin-network-simulator

I'm also working on a discrete event simulation using SimPy, but not because of the bounty, so don't worry about mine regarding that.  It's more of a learning exercise.

[socrates1024]

At a quick glance, eb3full's post here predates the other two by a couple of weeks, and is more full featured.

I'm slightly biased here, but only because I saw an early prototype of ebfull's simulator months ago, thought it was really cool, and since then have been looking forward to seeing the improved version.

Mostly unrelated, but this simulation was also acknowledged by the ES authors: http://hackingdistributed.com/2013/11/09/no-you-dint/