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.
Ok. Thanks for the response, I'm satisfied for now that this is a clear enough goal of things to model somehow. |
|
|
|
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.
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." |
|
|
|
So far, this does not meet my requirements. Given that it is written in Javascript, I doubt it ever will.*
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? 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. |
|
|
|
So the random numbers are part of the blockchain transaction? How would it work with 3 people?
For N people, every draws a random number between 0 and N-1, you add up all the numbers, and mod by N to determine the winner. The result is uniformly distributed between 0 and N-1, if even one party chooses their number randomly. |
|
|
|
Can you describe the process in a plainer way, like to a redneck. It appears that 3 equal inputs ended up in one of the input addresses. It solved the unequal contribution issue but from where does the external coin flip/lottery component comes from?
I can try... but it is a little tricky, so it may take a few attempts before we get a great description. Two people each bet 1 coin, commit to random numbers, and also post an additional 1 coin security deposit. When they both reveal their committed random numbers, the numbers are xor'ed and one of them is chosen as a winner, and gets both coins, and both players get their security deposit back. The only tricky thing is that you need some way to make sure both players actually *do* reveal their random number, rather than just disappearing. This is why the security deposit is important - the *only* way to get your security deposit back is to reveal your random number and finish the game - if you don't do this, the other player gets the security deposit *and* the prize. How was that? Clear? |
|
|
|
So, now that the remaining challenges with this protocol have all been solved by academic researchers at University of Warsaw, (see this thread and this paper), and in fact they have demonstrated a real live execution of the 3-player lottery game using Bitcoin transactions (see https://blockchain.info/tx-index/96964833), let's actually build this as a game! I hereby promise to chip in 0.1btc as a bounty for building an interface (web-based, or even command line script) for two or more players to do the fair coin flip described in the paper. |
|
|
|
I thought iddo/adams protocol only worked for the two party case?
Yes but generalizing it to multiple parties (as in the paper) is trivial. The only substantial way it improves on iddo's is using OP_SIZE to be compatible with existing opcodes. |
|
|
|
Does someone want to summarise their protocol?
This paper has a clever solution to the problem we were stuck on in Iddo's coinflip protocol, which relies on curently-disabled op codes. The problem is only due to an incidental quirk in Bitcoin's scripting language anyway, so it's clever rather than fundamental. Iddo's hashlocked lottery protocol requires each party to select an arbitrary number, and a deterministic function of those numbers is used to decide the winner. The problem is the script language doesn't let us do math (like OP_ADD) on larger-than-4-byte numbers, and more than 4 bytes of randomness are needed for it to be very safe/fair. The solution they propose is to use OP_SIZE to effectively compress a large string down to a small math-friendly number. The key step goes like this: each player selects a random number i, in the range 0, 1, ..., N (for an N-player lottery). Then, they select random string s with 20+i bytes. The commitment is the hash of s, and to reveal it you do "{s} OP_SIZE OP_DUP {20} {20+n} OP_WITHIN OP_VERIFY {20} OP_SUB" in the script to get out just "i". |
|
|
|
This neat paper was recently posted on the cryptography e-print server; http://eprint.iacr.org/2013/784The main idea is that Bitcoin can be used to provide "fairness" for arbitrary multi-party computations. Fairness means that if one party interrupts the protocol (e.g., by playing dead, or unplugging their computer and not sending any more messages after some point), the outcome is still "tolerable" to the other (honest) parties. This fairness property is not generally impossible for pure multiparty computations, and typically requires some kind of trusted third party as a mediator. Bitcoin's function as a timestamp server can replace this third party, and "tolerable" is interpreted (in a compelling way) as the the interrupting party forfeits some security deposit. This generalizes the hash-lock transaction techniques, used in e.g., Iddo's two player coin-flip lottery protocol, the mixing transaction from the Bitter-to-Better paper, and CoinSwap. |
|
|
|
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  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! |
|
|
|
|
The difficulty for the next block is fixed by the protocol, as a deterministic function of the previous blocks. There is no choice involved in setting the difficulty.
|
|
|
|
So far, this does not meet my requirements. Given that it is written in Javascript, I doubt it ever will.*
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? |
|
|
|
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/ |
|
|
|
|
kjj, jgarzik, is this bounty considered closed with eb3full's submission? Or is it still pending? Is anyone else currently attempting to claim it?
|
|
|
|
|
Just because a transaction exists that destroys a Bitcoin doesn't mean that it is accepted in the main chain. So how would the altchain ensure that only valid bitcoin transactions count? I think this is possible, but it would be strange for an altcoin to have to rely on bitcoin validation as well. For example, validators on the altchain would also have to validate the bitcoin chain. A couple months ago there was a large fork in which dozens of blocks were rewound. This would affect the altchain too?
|
|
|
|
|
Bump because the deadline is in 11 days!
|
|
|
|
I wrote the following email to someone asking about this paper, and I feel like publishing it in this thread. I don't have any insight to add about the substance of the paper itself, but I want to suggest how to put it in context. This paper is far from unique in pointing out ways that Bitcoin is not incentive compatible. We DO need to try to find and fix these economic glitches - they are REAL problems - but they also aren't immediate life-or-death urgent, because the network at the moment consists of a large number of well meaning and responsive participants. We can expect that more problems like these are coming. The larger and more mainstream Bitcoin's userbase gets, the more important it will be to design incentives to predict and steer participation. I was annoyed at first about the sensationalistic headlines, but I've gotten over it. We're used to these by now, from the press and everyone else. A tweet from the author convinced me that his interests are in the right place: ":-) but we're all good guys. The BTC community deserves a strong, robust currency. Identifying potential attacks is critical". This is true, and we really need more distributed systems experts and theoreticians working at this. I think the net effect of this event is that Bitcoin becomes more popular/attractive as an academic research topic, and that can only help. Despite the overhyped headline, this paper is important. It's part of a (long past due) movement towards modeling "rational participation" in Bitcoin. We are (surprisingly?) in a blind spot here as far as theoretical foundations go (the 30+ years of research in distributed systems, game theory, etc., have not looked at anything resembling Bitcoin). We do not yet have a sound way to argue that "Bitcoin (or X variant thereof) surely works," nor any impossibility results saying "nothing resembling Bitcoin can ever work." Main points: - Bitcoin is clearly *intended* to be incentive-compatible and encourage correct behavior. However the whitepaper only gives a proof for the "51% honest" model, which is unrealistic/trivial (if we just assume everyone's honest, there's no need for rewards in the first place). Even in this easy model, Bitcoin is novel among byzantine consensus protocols. Academics *should* have worked on this twenty years ago, but missed it! (except for this 2005 tech report) - Practically speaking, we still seem to have a while to figure this stuff out before any systemic economic collapse will manifest. Even the mining pools still run bitcoind, not RationalMiner software. For the time being, majority honest is a reasonable approximation. - Even if a 51% majority has limited ability to profit or attack, a systematic trend towards enabling 51% attacks would be a design flaw and existential threat. So we really need to find and fix things like this. This paper fits neatly into a class of papers/posts that point out a particular way in which Bitcoin is not incentive-compatible (to call it an *attack* is just cyberhype), yet a simple fix (typically just to the messaging layer) is often at hand. - Bitcoin and Red Balloons. There's no incentive for peers to relay transactions. Solution: bribe your peer conditional on the transaction getting accepted, now it's their problem too. - This paper: If a mining pool is confident in its ability to detect and out-propagate competing blocks, then it can profit by witholding blocks until the last minute, making everyone else waste work. Solution: relay faster so no peer can get this advantage, or use random tie-breaking so this attack can't be pulled off consistently (the following two examples are me plugging my own posts). Regardless of propagation, a miner with more than 33% of the network's hashpower can profit disproportionately by witholding one block at a time. [edited, due to author pointing out this was oversimplified]. - https://gist.github.com/amiller/cf9af3fbc23a629d3084 An anomalously large single transaction fee would encourage miners to fight over the previous block, rather than building on each other's work. Solution: remove the 100-block coinbase maturity rule, which actually prevents a simple cooperative equilibrium where you take a cut of the huge fee for yourself and leave the rest for the next miners to fight over. - https://bitcointalk.org/index.php?topic=309073.0 Natural economies of scale mean that "outsourced hosted mining" will be more cost effective and might drive out other participants, leading to more centralized control of resources, susceptible to coercion etc. Solution: a modified puzzle using (efficient) zero-knowledge proofs would make hosted mining (and mining pools, incidentally) impractical. There are other similar "attacks" along the lines of "this may be a problem when people eventually run RationalMiner rather than HonestSatoshiReferenceClient", but for which the solutions are less obvious... - Feather forking: https://bitcointalk.org/index.php?topic=312668.0 a small cartel of miners that want to enforce a transaction black-list could easily make it so that rational participants indifferent to the blacklist would rather appease the cartel than resist it. Possible solution: Adam Back is thinking very hard about how to make miners verify the correctness of transactions without learning anything else about them. - Kroll. et al: Following *any* of the rules is at best a *focal point*, and slight rule tweaks like inflating the 21 million limit (just by a little bit) are probably a lot more plausible and easier to pull off than most people think. Possible solution: no idea But we're still just scratching the surface of incentive-alignment glitches like this. Bitcoin will overcome the problems with easy fixes. I hope (but am skeptical) that if there's a bigger fix required, we can work it out and adopt it without waiting until it's too late and having to restart from scratch. Above all, I wish we had a strong theoretical model we could use to knock out entire classes of problems rather than pointing them out and patching them one at a time. By analogy, the academic cryptography community did such a great job of moving from ad hoc ciphers to "provable security" that the mainstream security mantra is "don't roll your own crypto" unless you've proved a theorem first. Maybe someday they'll say the same thing about rolling your own incentive-consensus protocols. But the work hasn't been done yet, and we're currently still in the dark ages. |
|
|
|
|
Show Posts
