[Bitcoin-development] Auto-generated miner backbone
W.R.T. this paper and the oft-discussed miner backbone, http://arxiv.org/pdf/1311.0243v1.pdf I'm wondering about an alternative protocol change that perhaps has less subtle implications than their suggested change. Rather than address the problem by assuming the network is full of sybil nodes and changing the rules for selecting the chain to build on, how about if we wrote code to automatically build a miner backbone by having IP addresses of nodes embedded into coinbases, then having any bitcoind that is creating work automatically connect to IPs that appeared in enough recent blocks? This would have the effect of automatically linking all the major pools together, with no administration overhead. For bonus points, the IPs could be IPv6 and then the trick we use to pack hidden services into IPv6 address space would allow nodes to be reached via Tor. This might be useful in the case of pools that don't to reveal the location of their bitcoin node[s], like for anti-DoS reasons. It feels like this should be achievable with a few days of solid coding and a couple of new command line flags, and the impact is much easier to reason about than a fundamental rule change like the one proposed by the paper. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote: W.R.T. this paper and the oft-discussed miner backbone, http://arxiv.org/pdf/1311.0243v1.pdf I'm wondering about an alternative protocol change that perhaps has less subtle implications than their suggested change. Rather than address the problem by assuming the network is full of sybil nodes and changing the rules for selecting the chain to build on, how about if we wrote code to automatically build a miner backbone by having IP addresses of nodes embedded into coinbases, then having any bitcoind that is creating work automatically connect to IPs that appeared in enough recent blocks? I proposed this as a means of giving a mechanism for wallets to get non-sybilled peers as well. This would have the effect of automatically linking all the major pools together, with no administration overhead. For bonus points, the IPs could be IPv6 and then the trick we use to pack hidden services into IPv6 address space would allow nodes to be reached via Tor. This might be useful in the case of pools that don't to reveal the location of their bitcoin node[s], like for anti-DoS reasons. It feels like this should be achievable with a few days of solid coding and a couple of new command line flags, and the impact is much easier to reason about than a fundamental rule change like the one proposed by the paper. Doing so encourages pools to only bother connecting to other pools, which is a strong centralizing force. But given the nasty incentives present anyway - it's in your advantage to distribute your blocks to no more than a majority of hashing power if you can do so consistently - I'm unconvinced that this won't happen anyway. The maximal benefit would be if two sets of addresses were published: public and private. The issue with publishing addresses is DoS attacks, but publishing Tor addresses doesn't stop attacks. What would discourage attacks however would be to encrypt that data such that only the creators of specific prior blocks could decrypt it. This limits the audience to those with incentives not to commit a DoS attack. (DoS attack the IP, and you'll no longer get preferential peering) Say what you want about centralization, but for the pools involved it's a good idea. On a technical level, the coinbase is limited in size, and people use it for other purposes, so lets define a standard where this data is stored in an OP_RETURN txout of the form: OP_RETURN key value key value ... Multiple values with the same key should be allowed. This data should be placed in the last txout so that SPV nodes can eventually be given it with a SHA256 midstate. -- 'peter'[:-1]@petertodd.org 00080e395c361bdf9db583d5f4c0e144f476c229285b15eae59c signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 4, 2013 at 12:53 PM, Peter Todd p...@petertodd.org wrote: I proposed this as a means of giving a mechanism for wallets to get non-sybilled peers as well. Ah yes, good point. Doing so encourages pools to only bother connecting to other pools, which is a strong centralizing force. They could already create such a setup, but we don't observe it in practice. On a technical level, the coinbase is limited in size, and people use it for other purposes, so lets define a standard Given that IP address data is inherently transient, perhaps a better solution is to define a short hash in the coinbase that commits to extra data that is relayed along with block data (e.g. appended to the block message). It can then be stored temporarily in the block db and erased after some time, like a few months. It would therefore not really be a part of the chain, but could be extended as we see fit with any other semi-transient data required. A new getextra message would let nodes query for it. The hash can be short because it doesn't have to survive brute forcing attacks longer than the expected validity period of the transient data anyway. 80 bits would probably be overkill. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 01:03:50PM +0100, Mike Hearn wrote: The suggested change is actually very simple (minutes of coding) and elegant and addresses precisely the identified problem. Disagree. Unless I'm misunderstanding what they propose, their suggested change would mean anyone could broadcast a newly discovered block at any point and have a 50% chance of being the winner. That is a fundamental change to the dynamics of how Bitcoin works that would require careful thought and study. It's worth pointing out that my previous post on this list for near-block broadcasts - where blocks that almost but not quite met the proof-of-work threshold are also broadcast so that propagation of transactions can be proven - also naturally leads to their proposed solution. Any miner who sees a near-block-broadcast extending a chain fork that they aren't mining on would naturally see that as evidence that the other side has more hashing power, and thus it's in their interest to mine it rather than the side they are mining. You know, the whole paper follows the same logic as the point I made months ago in how if there is no explicit blocksize limit miners have incentives to make their blocks large enough that they only propagate to just over 50% of the hashing power, thus causing their competitors to waste effort. They analyze the situation in terms of a sybil attack, where I proposed a more fundemental mechanism to achieve the same goal based on simple physics. -- 'peter'[:-1]@petertodd.org 000719f061e0fa83343ddbe80d2b6a1fefc84691ffe8652385e0 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
We propose a simple, backwards-compatible change to the Bitcoin protocol to address this problem and raise the threshold. Specifically, when a miner learns of competing branches of the same length, it should propagate all of them, and choose which one to mine on uniformly at random. So only in the case of two competing chains... The Selfish Miner today has an advantage knowing which chain the other will work on, and by simply choosing the other they get their advantage making it likely that it is the other that will waste their effort. By using the random scheme this advantage is gone. Note again that it is only in the case of two competing chains, which will happen on average every 60 blocks. So it is only roughly once every 60 block that you change from choosing one chain to doing a 50% random. A rough calculation on earnings will be that you loose roughly 1/(2*60) ~ 1% of your blocks using this scheme. But at the same time you make it harder for such an attack to happen. (This number might be slightly higher, as working in parallel on both chains will make the two chains last longer, so agree that we need a bit more analysis...) I also agree that it is a kind of a Sybil attack, but I think we should accept the risk of a Sybil attack but of course minimize it, rather than introducing various social network (ip addresses) solutions, which in one way or the other always have some central auth / oracle assumption. On 4/11/13, 13:03 , Mike Hearn wrote: The suggested change is actually very simple (minutes of coding) and elegant and addresses precisely the identified problem. Disagree. Unless I'm misunderstanding what they propose, their suggested change would mean anyone could broadcast a newly discovered block at any point and have a 50% chance of being the winner. That is a fundamental change to the dynamics of how Bitcoin works that would require careful thought and study. Also, their solution doesn't really address the problem they bring up, it just changes the size of the threshold required. Fundamentally, their attack is a sybil attack. It doesn't work if they can't delay or block a pools competitors because mostly their block will come in second place and they'll lose the race. Thus the solution should be a solution to sybil attacks. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 12:26:30PM +0100, Mike Hearn wrote: W.R.T. this paper and the oft-discussed miner backbone, http://arxiv.org/pdf/1311.0243v1.pdf I'm wondering about an alternative protocol change that perhaps has less subtle implications than their suggested change. Rather than address the problem by assuming the network is full of sybil nodes and changing the rules for selecting the chain to build on, how about if we wrote code to automatically build a miner backbone by having IP addresses of nodes embedded into coinbases, then having any bitcoind that is creating work automatically connect to IPs that appeared in enough recent blocks? It feels like this should be achievable with a few days of solid coding and a couple of new command line flags, and the impact is much easier to reason about than a fundamental rule change like the one proposed by the paper. Actually on further reflection this idea will make the attack described in the paper easier to carry out, rather than harder. I think where you're misunderstanding originates is the description of this attack as requiring a sybil attack on the network - you see this underlying sybil as one of numerical advantage, when it's actually one of *informational* advantage. Remember that the selfish miner strategy outlined in the paper is essentially a way to use knowledge of what blocks miners will be mining on, from the first seen rule, and the ability to broadcast blocks you have mined more widely than other miners. That knowledge and ability is then used in conjunction with a small lead (obtainable by chance) to outpace the rest of the network. By making all miners easily identifiable you make gaining that informational and broadcast capability easier to obtain rather than harder. The attacker now only needs to connect to every identified miner with especially fast nodes. With judicious use of DoS attacks and low latency they can still gain the informational and broadcast upper hand over other miners and carry out the attack. Where the paper goes wrong is they don't recognize the fundemental nature of the strategy being based on an informational advantage. Their pick a random side of the fork strategy may work to some extent, but it's incomplete and isn't necessarily rational for the miners individually. The correct, and rational, approach for a miner is to always mine to extend the block that the majority of hashing power is trying to extend. The current relay rules don't give you that information at all, but they can if we do two things: 1) Relay all blocks that meet the PoW target. (as suggested in the paper) 2) Relay block headers that nearly meet the PoW target. Mining strategy is now to mine to extend the first block you see, on the assumption that the earlier one probably propagated to a large portion of the total hashing power. But as you receive near-blocks that are under the PoW target, use them to estimate the hashing power on each fork, and if it looks like you are not on the majority side, switch. This very effectively defeats the paper's selfish-miner strategy, as all miners will very quickly be mining on the block that truly has the majority of hashing power trying to extend it. This is also a better overall outcome, because it puts the 51% attack threshhold back at 51% -- 'peter'[:-1]@petertodd.org 0004ee9bb13b022c412d75692b5e85454013c53f89e5d6fa8c69 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd p...@petertodd.org wrote: The correct, and rational, approach for a miner is to always mine to extend the block that the majority of hashing power is trying to extend. The current relay rules don't give you that information at all, but they can if we do two things: 1) Relay all blocks that meet the PoW target. (as suggested in the paper) 2) Relay block headers that nearly meet the PoW target. Mining strategy is now to mine to extend the first block you see, on the assumption that the earlier one probably propagated to a large portion of the total hashing power. But as you receive near-blocks that are under the PoW target, use them to estimate the hashing power on each fork, and if it looks like you are not on the majority side, switch. Doesn't that mean that by selective blocking these near-PoW headers, you can bias peers into preferring to mine on those with near-PoW headers, turning the attack around? Of course, because of their size, headers are likely much harder to slow down (in propagation speed) than full blocks... -- Pieter -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 03:34:35PM +0100, Pieter Wuille wrote: Mining strategy is now to mine to extend the first block you see, on the assumption that the earlier one probably propagated to a large portion of the total hashing power. But as you receive near-blocks that are under the PoW target, use them to estimate the hashing power on each fork, and if it looks like you are not on the majority side, switch. Doesn't that mean that by selective blocking these near-PoW headers, you can bias peers into preferring to mine on those with near-PoW headers, turning the attack around? Of course, because of their size, headers are likely much harder to slow down (in propagation speed) than full blocks... Remember that the attack described in the paper *doesn't* depend on the ability to selectively block or even just slow down anything - it works even on a unlimited bandwidth jam-free network so long as latency is non-zero. As for other possible attacks, if you can selectively block or slow down certain near-target headers you haven't achieved anything novel. Why not use that ability to block or slow down blocks themselves? Even if you did block some PoW headers for whatever reason the original purpose of broadcasting them - getting all hashing power to work to extend the same block - is still achieved. -- 'peter'[:-1]@petertodd.org 0001d7eb7fceb2e27f3dd1eb5f516464a6b6874fdf6debbd0227 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 4, 2013 at 3:26 PM, Peter Todd p...@petertodd.org wrote: The attacker now only needs to connect to every identified miner with especially fast nodes. With judicious use of DoS attacks and low latency . So you're back to a complicated sybil attack. I don't follow your thought process here - I didn't say anything about numerical advantage. The attack outlined in the paper *requires* you to be able to race the rest of the network and win some non-trivial fraction of the time. If you can't do that then all it means is that when you try to release a private block to compete with the other found block, you're quite likely to lose and you sacrifice the block rewards by doing so. The correct, and rational, approach for a miner is to always mine to extend the block that the majority of hashing power is trying to extend. There's no stable way to know that. The whole purpose of the block chain to establish the majority. I think your near-miss headers solution is circular/unstable for that reason, it's essentially a recursive solution. Mining strategy is now to mine to extend the first block you see, on the assumption that the earlier one probably propagated to a large portion of the total hashing power. But as you receive near-blocks that are under the PoW target, use them to estimate the hashing power on each fork, and if it looks like you are not on the majority side, switch. But you can't reliably estimate that. You can't even reliably estimate the speed of the overall network especially not on a short term basis like a block interval. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote: Peter - how can you guarantee that the majority mines on the non-selfish block? Feedback basically. So suppose the hashing power is split exactly 50:50, with half the hashing power hearing about one block first, and half the other. Also suppose the near-target threshold is 1/64th, that is a block header that means a target with difficulty 1/64th of the actual difficulty will be broadcast around the network by nodes. With a 10 minute block interval, near-target block headers will be found on average every 9.4 seconds. Eventually one of the two halves will find a near-target PoW solution, and the corresponding block-header will be broadcast on the network. Now if you are a miner, and you receive such a PoW solution, that's evidence that whatever block that block header built on has more hashing power than other competing blocks. Thus you would be rational to switch, and start mining to extend that block if you aren't already. Once miners start doing that, very soon another near-block solution will be generated, giving even more certainty about what block the majority are mining on. Of course, it may be the case that competing near-block headers are found, but no matter: as long as miners switch to the block with the most hashing power, this forms a feedback effect that quickly brings everyone to consensus. With everyone mining to extend the same block, there's nothing the selfish miner can do; there's no disagreement to exploit. -- 'peter'[:-1]@petertodd.org 000771e068338fef7e2285b8a6db582e37473f42b76573677adf signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 4, 2013 at 3:58 AM, Michael Gronager grona...@ceptacle.com wrote: The suggested change is actually very simple (minutes of coding) and elegant and addresses precisely the identified problem. It is actually a mental shortcut in the assumption of how probability works when mining a chain. The paper simply corrects this error - nice work! This isn't so. Their solution creates a weaker form of the vulnerability at all times, not just when the attacker has a informational/positional advantage. Normally delaying your blocks is negative expectation because you will get orphaned by blocks that are announced before you most of the time because miners extend the first seen. However, if you can position yourself all over the network you can condition your announcements on other blocks being announced and still win the race even if you delayed. Eliminating the first seen rule means that a miner with enough hashpower (including the largest pools existing today) could execute this attack without positioning themselves all over the network, the improvement is that a low hashrate attacker couldn't do as well, even with positioning themselves all over the network. I don't think this can be described as simply corrects the error. The largest pool would gain an advantage in delaying their blocks and would receive a superliner share of mining income from doing so, something they can't simply do today without attacking the network. At the moment I believe we can improve the situation with propagation advantage without the other changes, so we should do that first while thinking carefully about this. Simply relaying late blocks might be fine, if anything it would at least make it easier to keep reliable orphan stats... though I'm concerned with the bandwidth overhead and risk of flooding if its not implemented carefully. -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
(not sure if you meant this to go to the list, my apologies if not) On Mon, Nov 04, 2013 at 10:50:25AM -0500, Ittay wrote: On Mon, Nov 4, 2013 at 10:46 AM, Peter Todd p...@petertodd.org wrote: On Mon, Nov 04, 2013 at 10:25:19AM -0500, Ittay wrote: Peter - how can you guarantee that the majority mines on the non-selfish block? Of course, it may be the case that competing near-block headers are found, but no matter: as long as miners switch to the block with the most hashing power, this forms a feedback effect that quickly brings everyone to consensus. With everyone mining to extend the same block, there's nothing the selfish miner can do; there's no disagreement to exploit. This is not the exploit! The majority you create might just as well follow the previously-private block, so we're back in square one. Right, but the thing is, if all miners quickly come to consensus and are all mining on the same block, there's nothing the attacker can exploit in the first place. Suppose Alice the attacker is 100 blocks ahead of the main network somehow. We'll say the other miners are working to extend block n, and she's in posession of 100 blocks extending that. She also has just under 50% of the hashing power. Now when the main network finds a block n+1, Alice can do one of two things: she can publish her own n+1 block, or she can do nothing. If she does nothing, the main network will find block n+2 faster than she finds n+101, so eventually she loses. Thus she has to publish. In your attack she publishes to a subset of nodes strategicly, splitting the hashing power between nodes working to extend her n+1, and the other n+1 found. However, with near-target headers, very quickly all hashing power will come to consensus and all work to extend the same block, either theirs or Alice's. Given that they have the majority, they will find another block faster on average than Alice can extend her lead, and thus eventually Alice will lose. Now there is still a slight advantage for Alice in that it takes some time for the whole network to come to consensus, but this is a much slimmer margin, maybe a few percentage points, so at best Alice might need, say, 45% of the total hashing power. -- 'peter'[:-1]@petertodd.org 0004b8381fe97338c8b710cb662160f08e391820f30a375bb9b9 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 11:24:33AM -0500, Ittay wrote: Yes - this is for the mailing list. Regarding the algorithm - as we explain in the paper, as long as the attacker is way ahead - the others can mine on whatever they like. Doesn't really matter. Once they almost close the gap (and they will, because they're the majority), leaving only 1 block lead, the selfish miners publish their secret blocks, loose their lead, but win the entire secret chain. The honest miners thus loose all the work they did so far. It doesn't really matter how the honest miners waste their time. Yes, they lose their work, but that's irrelevant: what's important is eventually Alice runs out of secret blocks and then has no advantage over the other miners. In your paper Alice created her lead by exploiting the fact that not all of the hashing power was working to extend the same block due to the first-wins rule. With my solution that situation doesn't happen in the first place: forks are resolved quickly because both sides have both forks, and consensus on which one is the winner is achieved very quickly by proving which side has the majority of hashing power through near-target PoW solutions. With the majority of hashing power in consensus and working to extend the same block there's nothing Alice can do to get ahead, defeating the attack. -- 'peter'[:-1]@petertodd.org 0008adb581077dcfa0bf067a4ee010fbabb92d136292625b2299 signature.asc Description: Digital signature -- Android is increasing in popularity, but the open development platform that developers love is also attractive to malware creators. Download this white paper to learn more about secure code signing practices that can help keep Android apps secure. http://pubads.g.doubleclick.net/gampad/clk?id=65839951iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote: On Mon, Nov 4, 2013 at 10:25 AM, Ittay ittay.e...@cornell.edu wrote: As for the rational motivation of the individual miners - that's a good point! Here is a solution we did not put in the paper due to space constraints that should alleviate your concern: Instead of locally choosing a block at random, have a deterministic pseudo-random mechanism for choosing between competing chains. E.g., take the one whose last block hash is smaller. This way all miners choose the same chain, and the guarantees of our solution hold. I take that back. Speaking of, I'm going to take back my solution as well; I misunderstood your paper. So here's your argument in a ELI5 nutshell: Alice is a miner with some amount of hashing power. She has the ability to detect new blocks on the network extremely effectively for whatever reason; in short she has unusually good knowledge of the state of the network. She is also very good at publishing her blocks and getting them to the majority of hashing power in very little time; she has unusually good connectivity to all miners. (low-latency and high bandwidth) She's so good at this that when she finds a new block, she keeps it a secret! She can get away with this because she knows that the moment Bob finds a block, she can immediately broadcast it to the rest of the network before the other block propagates. Instead of building on Bob's blocks, almost everyone builds on Alice's block, depriving Bob of the revenue. Gradually Alice gets more and more miners because Bob, and other pools, don't pay out as much. You propose a rule where essentially miners extend Bob's block 50% of the time, and show in your paper how that leads to a scenario where Alice needs to have at leastr 1/4 of the total hashing power to succesfully pull this attack off anyway. What I did succesfully show is that for a short-term rational miner they're still better off mining to extend the block they hear about first rather than using your pick-one-at-random rule, because when you hear about a block is important information about whether or not the majority is mining on it. This is true even if others are using the pick-one-at-random rule. (they're better defecting than doing what's right for the whole network) Even worse is that miners have a rational incentive to broadcast such near-target headers to try to encourage other miners to work on the same fork that they are working on. The near-target idea came about for a totally different reason, so it's something that might wind up being implemented anyway. Mike Hearn's idea of making it easy to identify nodes associated with hashing power is still wrong. Although again, it's something that miners themselves have rational incentives to do. (you always want to encourage others to send you their blocks, and you also want to be able to send your blocks to the majority of hashing power as quickly as possible) Where the idea goes wrong is it makes it easier for Alice to identify hashing power, specifically where she needs to send her blocks to distribute them to the majority as quickly as possible. The second problem occurs if those nodes also distribute blocks to connecting peers: this makes it easy for Alice to be sure she'll hear about a new block as soon as possible by connecting to every one of those peers with a high-speed, low-latency connection. Bizzarely the idea does work if the advertised nodes only accept blocks, and never send blocks - instead miners would *only* send their blocks to other miners who have proven their hashing power, and do so essentially largest miner to smallest. Now unless Alice already is a large miner, her strategy can't work. Of course this will strongly encourage further centralization of pools. But it is in the interests of rational miners sadly. That blocks take a finite amount of time to propagate makes the problem worse: for Alice to learn that another block has been mined only requires her to receive the small 80 byte header from a peer; she doesn't need the whole block. She thus can know the block exists well before it has a chance to propagate fully. Even if every miner were directly peered to every other as some suggest, Alice could simply make smaller blocks, faster propagating than everyone else and use especially low-latency connections to win the race. On the other hand, the Bitcoin protocol is currently designed such that a miner can mine a block without knowing the previous block in full. Given the large block reward and/or a supply of transactions they knew no other miner had a rational miner would start trying to extend the longest chain they know about prior to actually receiving and validating the full block. Again, when miners start doing this - perhaps out of desperation due to low revenue - as long as Alice has the lowest latency network she'll win. (she doesn't even need to have the highest bandwidth in this case) We can change
Re: [Bitcoin-development] Auto-generated miner backbone
Sorry guys, I'm a little late to the party here. I skimmed over the paper, and appreciated Peter Todd's recap of it. My first thought was that this seems profit-neutral at best, when you take into account all the races you lose by trying to beat the propagation of other miners' blocks. So given the assumption that Alice is well-connected as Peter mentioned, it seems like this is a concern. But is this a realistic assumption? All miners have an incentive to be thoroughly connected to one another, to make sure they minimize the amount of time they spend mining on forks and that their blocks win with minimal chance of being orphaned. Is it realistic that one miner can somehow monopolize the good connections when the big miners are already trying to do the same thing for honest reasons? If you have a network full of honest miners and this one selfish-miner, it seems that all the honest miners need to do is try to establish those connections to each other as well as Alice does, and Alice will end up orphaning all her profit away. Furthermore, you can de-incentivize it by simply randomizing the order of broadcasts. Although you are maintaining multiple concurrent connections, the data still exits your network card as a serial stream of packets, and it seems that if you randomize who gets your new-block broadcasts first, then it further reduces the Alice's advantage if she's not guaranteed to be first. Sure, she can do it sometimes, but it would seem that even a couple failures to beat the rest of the network is going to erase most/all of what she gained on the blocks/chains that she wins. I liked the statement by Chris WIllmer on the reddit thread: practice theory. The more we can theorize our way to believing the conclusions that this is a problem, the more incentive there is for someone intelligent to actually try it. It's very possible that the conditions needed to execute this attack just cannot be attained in practice. -Alan On 11/04/2013 04:04 PM, Peter Todd wrote: On Mon, Nov 04, 2013 at 02:12:44PM -0500, Ittay wrote: On Mon, Nov 4, 2013 at 10:25 AM, Ittay ittay.e...@cornell.edu wrote: As for the rational motivation of the individual miners - that's a good point! Here is a solution we did not put in the paper due to space constraints that should alleviate your concern: Instead of locally choosing a block at random, have a deterministic pseudo-random mechanism for choosing between competing chains. E.g., take the one whose last block hash is smaller. This way all miners choose the same chain, and the guarantees of our solution hold. I take that back. Speaking of, I'm going to take back my solution as well; I misunderstood your paper. So here's your argument in a ELI5 nutshell: Alice is a miner with some amount of hashing power. She has the ability to detect new blocks on the network extremely effectively for whatever reason; in short she has unusually good knowledge of the state of the network. She is also very good at publishing her blocks and getting them to the majority of hashing power in very little time; she has unusually good connectivity to all miners. (low-latency and high bandwidth) She's so good at this that when she finds a new block, she keeps it a secret! She can get away with this because she knows that the moment Bob finds a block, she can immediately broadcast it to the rest of the network before the other block propagates. Instead of building on Bob's blocks, almost everyone builds on Alice's block, depriving Bob of the revenue. Gradually Alice gets more and more miners because Bob, and other pools, don't pay out as much. You propose a rule where essentially miners extend Bob's block 50% of the time, and show in your paper how that leads to a scenario where Alice needs to have at leastr 1/4 of the total hashing power to succesfully pull this attack off anyway. What I did succesfully show is that for a short-term rational miner they're still better off mining to extend the block they hear about first rather than using your pick-one-at-random rule, because when you hear about a block is important information about whether or not the majority is mining on it. This is true even if others are using the pick-one-at-random rule. (they're better defecting than doing what's right for the whole network) Even worse is that miners have a rational incentive to broadcast such near-target headers to try to encourage other miners to work on the same fork that they are working on. The near-target idea came about for a totally different reason, so it's something that might wind up being implemented anyway. Mike Hearn's idea of making it easy to identify nodes associated with hashing power is still wrong. Although again, it's something that miners themselves have rational incentives to do. (you always want to encourage others to send you their blocks, and you also want to be able to send your blocks to the majority of hashing
Re: [Bitcoin-development] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 04:45:24PM -0500, Alan Reiner wrote: So given the assumption that Alice is well-connected as Peter mentioned, it seems like this is a concern. But is this a realistic assumption? All miners have an incentive to be thoroughly connected to one another, to make sure they minimize the amount of time they spend mining on forks and that their blocks win with minimal chance of being orphaned. Is it realistic that one miner can somehow monopolize the good connections when the big miners are already trying to do the same thing for honest reasons? If you have a network full of honest miners and this one selfish-miner, it seems that all the honest miners need to do is try to establish those connections to each other as well as Alice does, and Alice will end up orphaning all her profit away. Right, but as I said, I think this is likely to become a contest of who can create the lowest latency mining operation, or to be more precise, who can get the best ratio of latency per dollar. Unfortunately even with totally honest mining winning orphan rates is a function of latency; what this paper has done is mainly show a remarkably effective way of leveraging low-latency and very good visibility to the network. Regardless, globe-spanning low-latency networks cost a lot of money, so if they are something that makes mining more profitable, for whatever reason, that's an effect that will incentivise pools to grow larger and more centralized. Furthermore, you can de-incentivize it by simply randomizing the order of broadcasts. Although you are maintaining multiple concurrent connections, the data still exits your network card as a serial stream of packets, and it seems that if you randomize who gets your new-block broadcasts first, then it further reduces the Alice's advantage if she's not guaranteed to be first. Sure, she can do it sometimes, but it would seem that even a couple failures to beat the rest of the network is going to erase most/all of what she gained on the blocks/chains that she wins. Yeah, there's a lot of possible solutions, but what I'm seeing looking at them is they all tend to be not economically rational, in the short term, or even worse, they actually incentivize mining pools to get larger. For instance anything that tries to prevent Alice from sybiling the network by forcing nodes to prove they have mining capacity just means that larger miners will have an advantage over smaller ones in getting their blocks propagated as fast as possible. Once Alice does have a reasonable amount of mining capacity, she can still use the selfish miner attack to grow larger and more profitable. -- 'peter'[:-1]@petertodd.org 000aae6d13639c5b4555eeda301ebcbc53f12e8a633e267c8331 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] Auto-generated miner backbone
Mike Hearn wrote: how about if we wrote code to automatically build a miner backbone Yeah, let's build a backbone, or a cloud, and then we could have Google run it! Come on, Mike, your conflict-of-interest as an employee is hanging out in the open, flapping in the breeze here... Don't you think it's a bit obvious for somebody in your position to advocate centralization of infrastructure, especially when it comes to bitcoin? On the other hand, I guess your blind trust in IP addresses as a solid foundation for security is why you were so shocked when the NSA hacked your backbone. -- 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] Auto-generated miner backbone
On Mon, Nov 04, 2013 at 08:14:37PM -0800, Gustaw Wieczorek wrote: Mike Hearn wrote: how about if we wrote code to automatically build a miner backbone Yeah, let's build a backbone, or a cloud, and then we could have Google run it! Come on, Mike, your conflict-of-interest as an employee is hanging out in the open, flapping in the breeze here... Don't you think it's a bit obvious for somebody in your position to advocate centralization of infrastructure, especially when it comes to bitcoin? On the other hand, I guess your blind trust in IP addresses as a solid foundation for security is why you were so shocked when the NSA hacked your backbone. Go away. Mike specifically mentioned the idea of using Tor addresses, which are authenticated. In addition this mechanism to create a backbone *automatically* is exactly as decentralized as Bitcoin mining itself is. It has nothing to do with Google. I suggested the mechanism myself for slightly different reasons, and if you know me, you'd know I'm the first to jump on anyone pushing centralization. -- 'peter'[:-1]@petertodd.org 000517064a43348fa39325bdc244ffb1d0da11ab85676d494a85 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] Auto-generated miner backbone
On Mon, Nov 4, 2013 at 8:39 PM, Peter Todd p...@petertodd.org wrote: I suggested the mechanism myself for slightly different reasons, and if you know me, you'd know I'm the first to jump on anyone pushing centralization. Likewise, I did too and am also not very tolerant with trusted or centeralized things in general. An authenticated miner announced set of nodes is _far_ from a cure all, as any attack they stop can be recovered by adding and dos attacks the public miner announced nodes to the attack's requirements... but we build security with layers. Bitcoin's security is only improved when we can weave the network tighter and make partitioning it more difficult. -- 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
