Topic: Selfish Mining Simulation - page 2. (Read 14062 times)

Ok. Thanks for the response, I'm satisfied for now that this is a clear enough goal of things to model somehow.

I've already posted a means to overrule my judgment.  If you feel that it should be paid now, just get a couple of the guys from my list to say so and I'll pay it.

My intention in providing the bounty was to encourage the development of a tool that would be useful for researchers to test their ideas.  For the most part, that means that it needs to model how nodes actually work.  That means it needs to have a model of connections and latency (network, disk and memory), a model of how long it takes to verify blocks, including taking into account transactions already verified.  You may have missed it, but I also posted a bounty for patches to enable profiling in the client so that we can collect real world performance data that can be used to plug back into the simulation.

In short, I'm looking for a simulator of the real network, not an implementation of the nonsense model they used in their paper.

Please say what you think would count as "general" enough and what is "fast" enough, because imo it is already sufficient in both ways.

Here is evidence that it is both reasonably general and reasonably fast:
a) In fact ebfull's implementation is a fully general purpose network simulator, mostly developed before the selfish mining paper was written. He only modified it to illustrate the selfish mining attack after this thread showed up! I unfortunately don't have a link to give you to show the original interface, which illustrates the generality. Maybe eb3full will respond to this thread with one... Additionally, the Selfish Mining simulation interface already supports varying the main parameter (alpha), as well as whether or not network dominance is assumed (essentially gamma=ordinary or gamma=1.0 from the paper), and whether or not the paper's suggested patch is implemented. What more generality is it you are expecting?
b) I just ran an experiment, with 100 nodes, on my browser at 1000x speed (with graphics turned off). Back of envelope, this means I could do 100k blocks in 16 hours. So it would cost roughly about a $160 worth of EC2 nodes to do a hundred sessions out to a thousand blocks. That seems tolerable to me.

I'm annoyed just because I feel like you're trying to avoid honoring your bounty by being vague about the conditions - a simulation can always be "faster" and more "general."

This will definitely be my target then, but it depends on what you're simulating. If you're simulating a selfish mining attack, you don't need to simulate transactions (unless you're testing transactionseconds or some other idea). If you're simulating transaction propagation, you don't really need to simulate a blockchain.

I'm actually pretty happy with V8's performance, it's not native, but it gets the job done and gives you the rapid prototyping advantage. With WebWorkers, and perhaps using some node.js fun, it could be scaled to large network simulations. I just enjoy building it, for what it teaches you about bitcoin. It could be a useful educative tool even if someone comes up with a super-efficient Haskell simulator to obviate mine.

Oh, sorry.  I thought I clarified this already.

The initial release was not general enough, and also seemed unlikely to become fast enough.

I've been a bit short on free time lately, so I haven't been following his progress.  He's done some amazing work, and it sounded like he was working hard on the first part.

Java has a reputation for being, shall we say, not quick.  I'd be delighted to be wrong about this, but I have a hard time seeing it being able to run a few hundred sessions with a few thousand nodes out to several hundred thousand blocks, with an appropriate level of detail and accuracy.

Bump because I am still waiting for kjj to clarify his statement, or for the other people who committed to the bounty (jgarzik, etc) to chime in.

Yeah, makes sense to get to "full selfishness" in a kind of quasistatic process in order to avoid any significant loss of revenue during the transition.

A miner could (I think, haven't simulated it) become "gradually" selfish, by just withholding some blocks for a little bit of time, to keep the difficulty down and his percentage of the revenue up!

Getting from a non-selfish steady state to a selfish one would certainly be risky and expensive for the attacker - he'd have to struggle to maintain his fraction of the overall hashing power along the way - but it might be worthwhile for him in the long run.  I guess that's one reason why a simulator would be nice to have

The attack assumes a lot of things.  My personal favorite is that global block spread can be described by a state machine with percentage chances for state transitions.

I think the idea is that if the attack can be sustained long enough for the difficulty to adjust downward to reflect the much higher orphan rates induced by the attack, then that higher percentage of revenue will equate to a higher overall revenue.

I intend to release a much more polished, documented and approachable general simulator in the coming days, far more efficient than my original post. Here some progress was made implementing difficulty adjustments, transactions (mempool, UTXO) and even niche things like mapOrphans, and bitcoind's SendMessages-style polling. (It's also now tested to work on firefox, chrome is still better.)

I intend for it to use a middleware pattern when I'm all done:


You can attach to network events with .on, and do PoW tasks/polling with .prob and .tick.

Ultimately I just hope my simulator architecture can help inspire future research for the community. Thanks for the feedback.

Can I infer from this that you do not believe the requirements are satisfied, specifically because it is not generic enough? Otherwise could you clarify why not?

So far, this does not meet my requirements.  Given that it is written in Javascript, I doubt it ever will.*

Still, this is really neat work, and I've enjoyed watching several runs of it evolving.  I was planning to send him a tip just for that, and I'd encourage others to also.

* Note that I can be outvoted on this matter.  From the later email, "Also, I don't want anyone to think that they need to satisfy me personally to collect on either of these two bounties.  I will pay mine for a product that is generally along the lines I have laid out, if a couple of the core devs (Gavin, Greg, Jeff, sipa, Luke, etc) agree that your work is useful."

I started writing my simulation because this one didn't appear to be fast enough to do proper Monte Carlo simulations.  I think there'd be a lot of value in being able to do this.

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/

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.

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

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.


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):



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.


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.

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?