Bitcoin Forum
August 11, 2022, 05:45:16 PM *
News: Latest Bitcoin Core release: 23.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 3 »  All
  Print  
Author Topic: Selfish Mining Simulation  (Read 14046 times)
eb3full
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
November 07, 2013, 12:00:15 AM
 #1

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:

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

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1660239916
Hero Member
*
Offline Offline

Posts: 1660239916

View Profile Personal Message (Offline)

Ignore
1660239916
Reply with quote  #2

1660239916
Report to moderator
impulse
Full Member
***
Offline Offline

Activity: 151
Merit: 100


View Profile
November 07, 2013, 12:07:51 AM
 #2

Is there any reason this couldn't be done on a dedicated testnet?
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 07, 2013, 12:47:05 AM
 #3

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.


https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
impulse
Full Member
***
Offline Offline

Activity: 151
Merit: 100


View Profile
November 07, 2013, 12:52:59 AM
 #4

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 Smiley
Carlton Banks
Legendary
*
Offline Offline

Activity: 3276
Merit: 2844



View Profile
November 07, 2013, 01:49:17 AM
 #5

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

Vires in numeris
revans
Sr. Member
****
Offline Offline

Activity: 336
Merit: 250


View Profile
November 07, 2013, 02:42:58 AM
 #6

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
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1097


View Profile
November 07, 2013, 04:06:11 AM
 #7

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!
Legendary
*
Offline Offline

Activity: 1536
Merit: 1000


electronic [r]evolution


View Profile WWW
November 07, 2013, 04:22:50 AM
 #8

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.

XCN: CYsvPpb2YuyAib5ay9GJXU8j3nwohbttTz | BTC: 18MWPVJA9mFLPFT3zht5twuNQmZBDzHoWF
Cryptonite - 1st mini-blockchain altcoin | BitShop - digital shop script
Web Developer - PHP, SQL, JS, AJAX, JSON, XML, RSS, HTML, CSS
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1120
Merit: 1097


View Profile
November 07, 2013, 04:48:26 AM
 #9

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
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
November 07, 2013, 06:48:51 PM
Last edit: November 07, 2013, 10:27:54 PM by eb3full
 #10

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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
Dansker
Hero Member
*****
Offline Offline

Activity: 740
Merit: 500


Hello world!


View Profile
November 07, 2013, 08:43:30 PM
 #11

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

Gavin Andresen
Legendary
*
qt
Offline Offline

Activity: 1652
Merit: 1876


Chief Scientist


View Profile WWW
November 07, 2013, 10:42:19 PM
 #12

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.

How often do you get the chance to work on a potentially world-changing project?
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 07, 2013, 11:26:56 PM
 #13

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.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
kjj
Legendary
*
Offline Offline

Activity: 1302
Merit: 1016



View Profile
November 08, 2013, 04:24:46 AM
 #14

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.

17Np17BSrpnHCZ2pgtiMNnhjnsWJ2TMqq8
I routinely ignore posters with paid advertising in their sigs.  You should too.
Sukrim
Legendary
*
Offline Offline

Activity: 2618
Merit: 1006


View Profile
November 08, 2013, 08:27:18 AM
 #15

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.

https://www.coinlend.org <-- automated lending at various exchanges.
https://www.bitfinex.com <-- Trade BTC for other currencies and vice versa.
Carlton Banks
Legendary
*
Offline Offline

Activity: 3276
Merit: 2844



View Profile
November 08, 2013, 06:01:45 PM
 #16

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?

Vires in numeris
eb3full
VIP
Full Member
*
Offline Offline

Activity: 198
Merit: 101


View Profile
November 08, 2013, 09:09:51 PM
 #17

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.

"With four parameters I can fit an elephant, and with five I can make him wiggle his trunk." John von Neumann
buy me beer: 1HG9cBBYME4HUVhfAqQvW9Vqwh3PLioHcU
socrates1024
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
November 23, 2013, 05:34:29 PM
 #18

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

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
d'aniel
Sr. Member
****
Offline Offline

Activity: 461
Merit: 250


View Profile
November 23, 2013, 07:48:20 PM
 #19

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
Full Member
***
Offline Offline

Activity: 126
Merit: 108


Andrew Miller


View Profile
November 23, 2013, 08:34:32 PM
 #20

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/

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
Pages: [1] 2 3 »  All
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!