eb3full (OP)
VIP
Full Member
Offline
Activity: 198
Merit: 101
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 12:00:15 AM |
|
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.
|
"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
|
|
|
impulse
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 12:07:51 AM |
|
Is there any reason this couldn't be done on a dedicated testnet?
|
|
|
|
Sukrim
Legendary
Offline
Activity: 2618
Merit: 1007
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 12:47:05 AM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 12:52:59 AM |
|
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](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
Carlton Banks
Legendary
Offline
Activity: 3430
Merit: 3080
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 01:49:17 AM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 02:42:58 AM |
|
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
Offline
Activity: 1120
Merit: 1152
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 04:06:11 AM |
|
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.htmlThink 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
Activity: 1536
Merit: 1000
electronic [r]evolution
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 04:22:50 AM |
|
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
Offline
Activity: 1120
Merit: 1152
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 04:48:26 AM |
|
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 (OP)
VIP
Full Member
Offline
Activity: 198
Merit: 101
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 06:48:51 PM Last edit: November 07, 2013, 10:27:54 PM by 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.
|
"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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 08:43:30 PM |
|
Could we not test it in "real life" on the testnet?
|
|
|
|
Gavin Andresen
Legendary
Offline
Activity: 1652
Merit: 2300
Chief Scientist
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 10:42:19 PM |
|
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
Activity: 2618
Merit: 1007
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 07, 2013, 11:26:56 PM |
|
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
Legendary
Offline
Activity: 1302
Merit: 1026
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 08, 2013, 04:24:46 AM |
|
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
Activity: 2618
Merit: 1007
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 08, 2013, 08:27:18 AM |
|
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
Legendary
Offline
Activity: 3430
Merit: 3080
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 08, 2013, 06:01:45 PM |
|
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 (OP)
VIP
Full Member
Offline
Activity: 198
Merit: 101
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 08, 2013, 09:09:51 PM |
|
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): 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 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
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 126
Merit: 110
Andrew Miller
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 23, 2013, 05:34:29 PM |
|
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
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 23, 2013, 07:48:20 PM |
|
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/btcsimhttps://github.com/christophebiocca/bitcoin-network-simulatorI'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
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 126
Merit: 110
Andrew Miller
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 23, 2013, 08:34:32 PM |
|
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/
|
|
|
|
|