[Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
Hello, Please see below our BIP for raising the selfish mining threshold. Looking forward to your comments. Best, Ittay --- Bitcoin Improvement Proposal Owners: Ittay Eyal and Emin Gun Sirer We suggest a change in the propagation and mining algorithm for chains of the same difficulty, to raise the threshold on Selfish Mining attacks. * Current situation: When a miner is notified of a new chain of the same difficulty as the one it is mining on, it will ignore it. * Background: The selfish mining attack and its implications were described in detail in the following research paper: http://arxiv.org/abs/1311.0243v1 * Proposal: To thwart selfish mining attacks launched by less than 25% of the mining power, we propose the following change to the protocol: When a miner learns of more than one chain of the same difficulty, it should propagate all of them, and choose one of them to mine on uniformly at random among all chains of the same difficulty. When hearing of a chain of maximal difficulty that it did not know of before: 1. Add it to a local list of maximal difficulty chains. 2. Propagate it to its neighbors. 3. Choose a branch uniformly at random from the local list, and mine on it. * Example: t0: learn of chain A of difficulty x. propagate A to neighbors. start mining on A. t1: learn of chain B of difficulty x. propagate B to neighbors. toss a coin between A and B; if B wins, switch to mining on B. t2: learn of chain C of difficulty x. propagate C to neighbors. toss a 3 faced coin among A, B, and C; switch to mining on the winning chain. * Concerns and answers: 1. No harm to miners when all are honest. Mining blocks is a random Poisson process, which is memoryless. Having mined on the block in the past does not provide an advantage in locating a solution in the future. Therefore, a miner is not harmed by switching the chain on which it mines. 2. No new vulnerabilities introduced: Currently the choice among equal-length chains is done arbitrarily, depending on network topology. This arbitrariness is a source of vulnerability. We replace it with explicit randomness, which is at the control of the protocol. The change does not introduce executions that were not possible with the old protocol. 3. Complete backward compatibility: Any subset of the miners can switch to the proposed protocol. 4. Progressive improvement: Each miner that adopts the change raises the threshold a little bit. The threshold will reach 25% with universal adoption. -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote: Hello, Please see below our BIP for raising the selfish mining threshold. Looking forward to your comments. snip 2. No new vulnerabilities introduced: Currently the choice among equal-length chains is done arbitrarily, depending on network topology. This arbitrariness is a source of vulnerability. We replace it with explicit randomness, which is at the control of the protocol. The change does not introduce executions that were not possible with the old protocol. Credit goes to Gregory Maxwell for pointing this out, but the random choice solution does in fact introduce a vulnerability in that it creates incentives for pools over a certain size to withhold blocks rather than immediately broadcasting all blocks found. The problem is that when the pool eventually choses to reveal the block they mined, 50% of the hashing power switches, thus splitting the network. Like the original attack this can be to their benefit. For pools over a certain size this strategy is profitable even without investing in a low-latency network; Maxwell or someone else can chime in with the details for deriving that threshold. I won't get a chance to for a few hours, but someone should do the analysis on a deterministic switching scheme. -- 'peter'[:-1]@petertodd.org 0005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707 signature.asc Description: Digital signature -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
On Tue, Nov 05, 2013 at 12:05:41PM -0500, Peter Todd wrote: On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote: Hello, Please see below our BIP for raising the selfish mining threshold. Looking forward to your comments. snip 2. No new vulnerabilities introduced: Currently the choice among equal-length chains is done arbitrarily, depending on network topology. This arbitrariness is a source of vulnerability. We replace it with explicit randomness, which is at the control of the protocol. The change does not introduce executions that were not possible with the old protocol. Credit goes to Gregory Maxwell for pointing this out, but the random choice solution does in fact introduce a vulnerability in that it creates incentives for pools over a certain size to withhold blocks rather than immediately broadcasting all blocks found. The problem is that when the pool eventually choses to reveal the block they mined, 50% of the hashing power switches, thus splitting the network. Like the original attack this can be to their benefit. For pools over a certain size this strategy is profitable even without investing in a low-latency network; Maxwell or someone else can chime in with the details for deriving that threshold. I won't get a chance to for a few hours, but someone should do the analysis on a deterministic switching scheme. Oh, and I don't want to give the wrong impression: there's no need to rush to get this problem fixed. Even if someone wanted to launch an attack right now, with a fair amount of resources, there's a lot of counter-measures based on human intervention that can definitely stop the attack in the short-term; what's needed is at worst moderate-term, and much more likely a long-term approach. In addition, keep in mind that this attack is very easy to detect, so if one is actually launched we will know immediately and can start taking direct counter-measures at that time. That Gregory Maxwell so quickly identified a flaw in this proposed solution suggests we should proceed carefully. It'd be good to do a test of this attack, as well as possible solutions, on testnet to better explore it and possible counter-measures. -- 'peter'[:-1]@petertodd.org 000a03ea8c90161a275ee63d077ec35c1b582c77934c0be12a02 signature.asc Description: Digital signature -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
Patrick, could you please explain us why the solution proposed by Ittay would drop the actual honest miners ratio, becoming so backfire? Thanks a lot 2013/11/5 Patrick patr...@intersango.com The ratio of honest miners that mine the first block they see is 0.5 Your proposed solution would reduce that ratio to 0.5 In other words your proposed change would make the attack you describe easier not harder. On 11/05/2013 09:26 AM, Ittay wrote: That sounds like selfish mining, and the magic number is 25%. That's the minimal pool size. Today the threshold is 0% with good connectivity. If I misunderstood your point, please elaborate. Ittay On Tue, Nov 5, 2013 at 12:05 PM, Peter Todd p...@petertodd.org wrote: On Tue, Nov 05, 2013 at 11:56:53AM -0500, Ittay wrote: Hello, Please see below our BIP for raising the selfish mining threshold. Looking forward to your comments. snip 2. No new vulnerabilities introduced: Currently the choice among equal-length chains is done arbitrarily, depending on network topology. This arbitrariness is a source of vulnerability. We replace it with explicit randomness, which is at the control of the protocol. The change does not introduce executions that were not possible with the old protocol. Credit goes to Gregory Maxwell for pointing this out, but the random choice solution does in fact introduce a vulnerability in that it creates incentives for pools over a certain size to withhold blocks rather than immediately broadcasting all blocks found. The problem is that when the pool eventually choses to reveal the block they mined, 50% of the hashing power switches, thus splitting the network. Like the original attack this can be to their benefit. For pools over a certain size this strategy is profitable even without investing in a low-latency network; Maxwell or someone else can chime in with the details for deriving that threshold. I won't get a chance to for a few hours, but someone should do the analysis on a deterministic switching scheme. -- 'peter'[:-1]@petertodd.org 0005e25ca9b9fe62bdd6e8a2b4527ad61753dd2113c268bec707 -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and registerhttp://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk ___ Bitcoin-development mailing listBitcoin-development@lists.sourceforge.nethttps://lists.sourceforge.net/lists/listinfo/bitcoin-development -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi startit...@gmail.com wrote: I agree with Ittay: when bugs are found, they must be fixed ASAP, expecially when they affect a sensitive sw such as Bitcon; in IT security, every flaw that is exploitable in abstract, is going to be exploited in real, sooner or later, also taking into account the increasing parallel computing power; beware of false sense of security That is quite ignorant. Bitcoin is far more complex than standard IT security fix ASAP mantra. Distributed consensus is a new field of computer science, and blindly applying standard logic to bitcoin will quickly result in large problems. Every fix has the chance of changing the game theory or economics of bitcoin. A change to the core consensus protocol within bitcoin -- mining -- is even more game-theory- and economically-critical to the core system. Changes thus have more impact, where any change potentially reduces bitcoin's value to zero in the worst case. Bitcoin is akin to medical device or avionics software. We cannot just change at will, without significant research, analysis and testing. It is a bug, it must be fixed ASAP is ignorant and dangerous. Further, this is at present a THEORETICAL problem, and the solution presented has some obvious flaws, that would make our current, WORKING SYSTEM more fragile, and less secure. -- Jeff Garzik Senior Software Engineer and open source evangelist BitPay, Inc. https://bitpay.com/ -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
Thank you very much for your fair response, Sir; this means that anytime a bug is found in Bitcoin protocol, chances are that it would take a lot more time to get fixed 2013/11/5 Jeff Garzik jgar...@bitpay.com On Tue, Nov 5, 2013 at 1:07 PM, Alessandro Parisi startit...@gmail.com wrote: I agree with Ittay: when bugs are found, they must be fixed ASAP, expecially when they affect a sensitive sw such as Bitcon; in IT security, every flaw that is exploitable in abstract, is going to be exploited in real, sooner or later, also taking into account the increasing parallel computing power; beware of false sense of security That is quite ignorant. Bitcoin is far more complex than standard IT security fix ASAP mantra. Distributed consensus is a new field of computer science, and blindly applying standard logic to bitcoin will quickly result in large problems. Every fix has the chance of changing the game theory or economics of bitcoin. A change to the core consensus protocol within bitcoin -- mining -- is even more game-theory- and economically-critical to the core system. Changes thus have more impact, where any change potentially reduces bitcoin's value to zero in the worst case. Bitcoin is akin to medical device or avionics software. We cannot just change at will, without significant research, analysis and testing. It is a bug, it must be fixed ASAP is ignorant and dangerous. Further, this is at present a THEORETICAL problem, and the solution presented has some obvious flaws, that would make our current, WORKING SYSTEM more fragile, and less secure. -- Jeff Garzik Senior Software Engineer and open source evangelist BitPay, Inc. https://bitpay.com/ -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
On Tue, Nov 5, 2013 at 1:55 PM, Alessandro Parisi startit...@gmail.com wrote: this means that anytime a bug is found in Bitcoin protocol, chances are that it would take a lot more time to get fixed Correct. There is significant potential that a fix can create other problems... and any major mistake could instantly destroy $2 billion worth of value. -- Jeff Garzik Senior Software Engineer and open source evangelist BitPay, Inc. https://bitpay.com/ -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
Great paper Ittay, thanks for all your work on this. Today the threshold is 0% with good connectivity.Fig. 2 captures this well, the threshold is only zero if 'y' is 1. In Section 6 and 6.1 you argue y - 1 but the sybil attack you describe, isn't that more like how *all* sophisticated miners would want to ensure their blocks are widely propagated? I think you can't assume only the selfish miner is doing it.Based on the current 'first seen' algorithm, as you say, competing longest chains happen about every 60 blocks. The rest of the time, a single block propagates through the vast majority of the network 'uncontested'. If there are multiple valid longest blocks being simultaneously propagated, then propagation pattern of the competing blocks will determine hash rate on each.Selfish mining requires exploiting the race condition between learning about a competing block, and publishing your own. Usually we talk about minimizing publishing latency so that your block ends up uncontested 59/60 times, and in the 1/60 times, even then your block has the best chance of winning.Selfish mining forgoes the 59/60 chance of your block being uncontested, and instead chooses to 'race the network' every time. You start 'one step behind' the competing block (since of course you only learn about it after it starts propagating), so you must rely on being able to outrace propagation of the competing block through a private low-latency side-network which can inject your block at multiple points throughout the bitcoin p2p network to outrace the competitor.I think it's a stretch to say 'y' is 0 with good connectivity. Even the best connected mining pools today are concerned with this 'y' factor.Here's a probably very dumb idea... to throw out one possible "solution"...You want a way to fake-out the 'selfish miner' into disclosing their blocks -- how can your force their hand to prevent them from accumulating longer private chains?What if you propagate (and relay) an encrypted block header which honest miners will timestamp when they receive it, then 10 seconds later propagate the decryption key to unblind it. But here's the catch - maybe the decryption results in junk, maybe it results a new longer block. If it's a real block then it gets priority based on when the ciphertext was received instead of when the decryption key was received. Now 'selfish miner' can't race the network anymore, because they are always in state 0' and can't tell if they are up against a ghost, or a real competing block. If they wait for the decryption key to check, it's too late, and they are guaranteed to lose unless they can out-race the network, e.g. back at t=50%. Of course there would need to be some way to anti-DDoS this which allows for some amount of these fake-outs without letting them get out of hand.Thanks,Jeremy-- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
The conversations that spawned from this paper have been fascinating to read, but I have a problem with the conclusions. To quote the paper: The Bitcoin ecosystem is open to manipulation, and potential takeover, by miners seeking to maximize their rewards. This paper presented Selfish-Mine, a mining strategy that enables pools of colluding miners that adopt it to earn revenues in excess of their mining power. Higher revenues can lead new rational miners to join sel sh miner pools, leading to a collapse of the decentralized currency. Please explain to me why any rational miner would collude to earn slightly higher short term profits at the expense of then wiping out the value of all their bitcoins in the long term. Also, if you felt that this vulnerability is an immediate danger to the Bitcoin network, why publish the vulnerability publicly rather than first disclosing it privately to the core developers? Apologies if you did disclose it privately in the past; I've seen no mention of it. -- Jameson Lopp Software Engineer Bronto Software On 11/05/2013 01:58 PM, Jeff Garzik wrote: On Tue, Nov 5, 2013 at 1:55 PM, Alessandro Parisi startit...@gmail.com wrote: this means that anytime a bug is found in Bitcoin protocol, chances are that it would take a lot more time to get fixed Correct. There is significant potential that a fix can create other problems... and any major mistake could instantly destroy $2 billion worth of value. -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] BIP proposal - patch to raise selfish mining threshold.
On Tue, Nov 5, 2013 at 1:57 PM, Jeremy Spilman jer...@taplink.co wrote: I think it's a stretch to say 'y' is 0 with good connectivity. Even the best connected mining pools today are concerned with this 'y' factor. Check out the following paper for the effect a single node can have on propagation, and on the relation between block size and propagation speed. This strongly supports our assumption. http://www.tik.ee.ethz.ch/file/49318d3f56c1d525aabf7fda78b23fc0/P2P2013_041.pdf Here's a probably very dumb idea... to throw out one possible solution... You want a way to fake-out the 'selfish miner' into disclosing their blocks -- how can your force their hand to prevent them from accumulating longer private chains? What if you propagate (and relay) an encrypted block header which honest miners will timestamp when they receive it, then 10 seconds later propagate the decryption key to unblind it. But here's the catch - maybe the decryption results in junk, maybe it results a new longer block. If it's a real block then it gets priority based on when the ciphertext was received instead of when the decryption key was received. Now 'selfish miner' can't race the network anymore, because they are always in state 0' and can't tell if they are up against a ghost, or a real competing block. If they wait for the decryption key to check, it's too late, and they are guaranteed to lose unless they can out-race the network, e.g. back at t=50%. Of course there would need to be some way to anti-DDoS this which allows for some amount of these fake-outs without letting them get out of hand. That's a dangerous way to go, opening the door to DoS attacks, as you mention. Besides, it makes a simple algorithm complicated, and doing such changes may lead to different vulnerabilities that are difficult to cover. Best, Ittay -- November Webinars for C, C++, Fortran Developers Accelerate application performance with scalable programming models. Explore techniques for threading, error checking, porting, and tuning. Get the most from the latest Intel processors and coprocessors. See abstracts and register http://pubads.g.doubleclick.net/gampad/clk?id=60136231iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
