Re: [Bitcoin-development] Cut-through propagation of blocks
it: I'd be much more likely to run an experimental gateway in another process on a node than experimental p2p code inside my production bitcoinds themselves. Yes, it's certainly better to do that during the development phase. However if it does turn out to be good and valuable then it'd eventually need to be integrated or rewritten into Core anyway, lest we accidentally increase the setup cost of running a node and end up with a two-tier network. And if the code will eventually want to be merged into Core anyway, it might as well be implemented into it directly, perhaps behind a switch that can disable those codepaths if something goes wrong. So I think the tradeoffs here are rather complicated and subtle. -- The best possible search technologies are now affordable for all companies. Download your FREE open source Enterprise Search Engine today! Our experts will assist you in its installation for $59/mo, no commitment. Test it for FREE on our Cloud platform anytime! http://pubads.g.doubleclick.net/gampad/clk?id=145328191iu=/4140/ostg.clktrk___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
There is no need to have Bitcoin transport all using a single protocol, and we can get better robustness and feature velocity if there are a couple protocols in use (you could just run a block-transport-protocol daemon that connects to your local node via the classic protocol). Although this is a somewhat appealing notion, would it really improve feature velocity? I don't think the current p2p protocol is holding anything back, and having to implement features twice in two protocols would slow things down quite a bit. Probably the lowest hanging fruit now is fixing the 100msec sleep and just generally having tools to measure latency and queuing inside the code. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On Sun, May 25, 2014 at 2:36 AM, Mike Hearn m...@plan99.net wrote: Although this is a somewhat appealing notion, would it really improve feature velocity? I don't think the current p2p protocol is holding anything back, and having to implement features twice in two protocols would slow things down quite a bit. If someone wanted to implement swanky UDP non-blocking transports or complex network coding schemes I'd probably want to see the proven in actual use before sticking them in the reference code, so yes. It's also the case that the ~last addition we made to the P2P code added a remotely exploitable crash bug. There are some pretty distinct use cases out there— fast block relaying, supporting thin clients, minimizing bandwidth (e.g. via compression and tx/block redundancy elimination), etc. Some of them may not be well handled by an external gateway, some of them (e.g. block relaying) very much could be. The nice thing with alternative protocols and gatewaying is that it can proceed completely asynchronously with implementation development, e.g. revving versions as fast as the users of the protocol care, and could potentially be used immediately with other bitcoin implementations... and if its buggy it doesn't break the nodes using it: I'd be much more likely to run an experimental gateway in another process on a node than experimental p2p code inside my production bitcoinds themselves. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On Sat, May 24, 2014 at 5:57 AM, Ashley Holman dsc...@gmail.com wrote: * As far as I can tell, this shouldn't change any game theory or incentives because nodes still receive blocks exactly as they do now, just sooner. The difference is, invalid blocks that meet the PoW will be broadcast to everyone, but this is nothing new since someone can peer with you and send you an invalid block already. Network DoS should not be a possibility since it is very expensive to make invalid blocks that meet network PoW. The difference is that with cut-through forwarding of blocks, a sufficiently motivated attacker (being willing to blow 25BTC's worth of electricity on the effort) can subjugate the entire Bitcoin network to its DoS attack, rather than having to connect to every node individually and then still have those individual nodes reject that invalid block without relaying any knowledge of its existence. An attack could also take the form of a block body that never arrives - a sort of teergrube attack, where the goal is to get the network mining empty block upon empty block on top of that valid-PoW header whose body never arrives. It doesn't have to be with an explicitly invalid block. Could one mitigate such attacks by allowing nodes to send a message to the effect of, Oops, I know that header i just sent is valid PoW, but I'd like you to forget about it - I think its body is invalid? -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On Fri, May 23, 2014 at 8:57 PM, Ashley Holman dsc...@gmail.com wrote: Hi, On this list there has been some discussion around techniques to speed up block propagation, with a particular focus on reducing the extra orphan risk carried by larger blocks. The current store-and-forward method means that larger blocks will propagate with higher latency. FWIW, there are a lot of improvements which can be made before more complex changes like cut-through-forwarding that change the protocol. For example, the reference software has a 100ms sleep in p2p message processing which could be replaced with a semaphore, this would dramatically lower latency for block relaying. Likewise nodes which are becoming bandwidth overloaded could adapt their concurrent connection counts down (and ones that are underloaded could accept more connections). Relaying to multiple peers could be done in parallel instead of serialized, and the order in which peers are relayed to could be adapted to place more apparently useful and faster peers first, e.g. every time a peer is the first to tell you about a block or transaction you accept they move up the list, every time their socket send queue fills they move down. Luke-Jr had implemented cut through behavior previously and had posted a patch, but absent those other network processing improvements it didn't appear to help. If you want to go full out crazy in optimizing in this space, there are fancier things that can be done to further reduce latency and increase efficiency: https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding ... but some of this stuff really should be done as a seperate protocol. There is no need to have Bitcoin transport all using a single protocol, and we can get better robustness and feature velocity if there are a couple protocols in use (you could just run a block-transport-protocol daemon that connects to your local node via the classic protocol). -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On Sun, May 25, 2014 at 8:29 AM, Bernd Jendrissek bitc...@bpj-code.co.za wrote: The difference is that with cut-through forwarding of blocks, a sufficiently motivated attacker (being willing to blow 25BTC's worth of electricity on the effort) can subjugate the entire Bitcoin network to its DoS attack, rather than having to connect to every node individually and then still have those individual nodes reject that invalid block without relaying any knowledge of its existence. That is true, but they could also apply the same hash power to mine valid blocks and would achieve the same outcome (their blocks would go to everyone), except they would get paid for it. I wonder if it should even be called DoS, due to the extreme and costly rate-limiting thats implied. An attack could also take the form of a block body that never arrives - a sort of teergrube attack, where the goal is to get the network mining empty block upon empty block on top of that valid-PoW header whose body never arrives. It doesn't have to be with an explicitly invalid block. Thank you for raising this, as I share this concern. There is another similar attack: if I send you a new block very slowly, I occupy all your upstream peer slots indefinitely until the block is complete, because there is no out-of-band messaging capability or ability to cancel a message. There is also sub-optimal logic in choosing to download a block only from the first person to offer it. It means you are fetching it from the lowest latency path, but what really matters is who can give it to you fastest. If there are multiple people who can send you a block at once, and you have some idea of your spare upstream bandwidth capacity, why not let two or more peers compete to send you the block fastest? So to implement this type of thing, the p2p protocol should allow for multiplexing of messages. Something like HTTP chunked encoding. It could be in the form of: msgidchunksizerawbytes, msgidchunksizerawbytes, etc etc You only send a chunk once you've got the whole chunk in your buffer, so it's not possible to get hung up on a single slow message. One block can overtake another along the same hop path if it is being streamed faster. On Sun, May 25, 2014 at 8:46 AM, Gregory Maxwell gmaxw...@gmail.com wrote: If you want to go full out crazy in optimizing in this space, there are fancier things that can be done to further reduce latency and increase efficiency: https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding ... but some of this stuff really should be done as a seperate protocol. There is no need to have Bitcoin transport all using a single protocol, and we can get better robustness and feature velocity if there are a couple protocols in use (you could just run a block-transport-protocol daemon that connects to your local node via the classic protocol). What about a separate project which is a mesh router specifically designed for low-latency transmission of blocks? It could support things like a more sophisticated/configurable routing table, and have some kind of discovery where it tries to optimise its topology. There could even be some way for nodes to prove their hash power, so pools can find each other and directly peer / prioritise sends. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On 05/24/2014 07:41 PM, Ashley Holman wrote: On Sun, May 25, 2014 at 8:29 AM, Bernd Jendrissek bitc...@bpj-code.co.za mailto:bitc...@bpj-code.co.za wrote: The difference is that with cut-through forwarding of blocks, a sufficiently motivated attacker (being willing to blow 25BTC's worth of electricity on the effort) can subjugate the entire Bitcoin network to its DoS attack, rather than having to connect to every node individually and then still have those individual nodes reject that invalid block without relaying any knowledge of its existence. That is true, but they could also apply the same hash power to mine valid blocks and would achieve the same outcome (their blocks would go to everyone), except they would get paid for it. I wonder if it should even be called DoS, due to the extreme and costly rate-limiting thats implied. An attack could also take the form of a block body that never arrives - a sort of teergrube attack, where the goal is to get the network mining empty block upon empty block on top of that valid-PoW header whose body never arrives. It doesn't have to be with an explicitly invalid block. Thank you for raising this, as I share this concern. There is another similar attack: if I send you a new block very slowly, I occupy all your upstream peer slots indefinitely until the block is complete, because there is no out-of-band messaging capability or ability to cancel a message. There is also sub-optimal logic in choosing to download a block only from the first person to offer it. It means you are fetching it from the lowest latency path, but what really matters is who can give it to you fastest. If there are multiple people who can send you a block at once, and you have some idea of your spare upstream bandwidth capacity, why not let two or more peers compete to send you the block fastest? So to implement this type of thing, the p2p protocol should allow for multiplexing of messages. Something like HTTP chunked encoding. It could be in the form of: msgidchunksizerawbytes, msgidchunksizerawbytes, etc etc You only send a chunk once you've got the whole chunk in your buffer, so it's not possible to get hung up on a single slow message. One block can overtake another along the same hop path if it is being streamed faster. On Sun, May 25, 2014 at 8:46 AM, Gregory Maxwell gmaxw...@gmail.com mailto:gmaxw...@gmail.com wrote: If you want to go full out crazy in optimizing in this space, there are fancier things that can be done to further reduce latency and increase efficiency: https://en.bitcoin.it/wiki/User:Gmaxwell/block_network_coding ... but some of this stuff really should be done as a seperate protocol. There is no need to have Bitcoin transport all using a single protocol, and we can get better robustness and feature velocity if there are a couple protocols in use (you could just run a block-transport-protocol daemon that connects to your local node via the classic protocol). What about a separate project which is a mesh router specifically designed for low-latency transmission of blocks? It could support things like a more sophisticated/configurable routing table, and have some kind of discovery where it tries to optimise its topology. There could even be some way for nodes to prove their hash power, so pools can find each other and directly peer / prioritise sends. I think the most important change is modifying the way Bitcoin Core prioritizes blocks. Right now it uses the first full block verified. Instead, it should consider the first valid header received as highest priority, but only mine on it once it has done full verification of the block. In other words, nodes will mine on whatever full/verified block they have with the earliest header-received time. If another header comes in and the tx list is received before the first tx list is done, then the node will mine the second block *until* it receives and verifies the first block, then it will switch to mining that first block. Most of the time there's no race, it will simply mine the block N-1 for an extra 1-3 seconds until it receives and verifies the full block for the new header. This at least solves part of the problem: nodes are still only mining on full blocks, but priority is given to *headers* that come first which is independent of block size. As long as a block isn't found within the 1-3 seconds, then each miner will switch when they finish receiving and verifying it. If miners are concerned about that 1-3 second gap, they should perhaps focus on making sure the tx they are mining are well-propagated already, so that most of the network has most of the transactions already in their memory pool by the time their block is mined. -- Accelerate Dev Cycles with Automated
Re: [Bitcoin-development] Cut-through propagation of blocks
On Sat, May 24, 2014 at 5:04 PM, Alan Reiner etothe...@gmail.com wrote: I think the most important change is modifying the way Bitcoin Core prioritizes blocks. Right now it uses the first full block verified. Instead, it should consider the first valid header received as highest priority, but only mine on it once it has done full verification of the This directly opens an attack where as soon as you find a block you announce the header to the world and then you delay announcing the block content. You can continue to mine on the block but no one else can (or alternatively they break their rule and risk extending an invalid block— bad news for SPV wallets)— then when you find a successor block or someone else finds a competing block you immediately announce the content. It basically means that you can always delay announcing a block and be sure that doing so doesn't deprive you of your winning position. If miners are concerned about that 1-3 second gap, they should perhaps focus on making sure the tx they are mining are well-propagated already, so that most of the network has most of the transactions already in their memory pool by the time their block is mined. With an alternative transport protocol, assuming the content has already been relayed a block could be sent in a couple back to back UDP packets. (e.g. a few bytes per transaction to disambiguate the transaction order out of the already sent transactions). So I think very similar latency could be achieved without doing any thing which might increase the motivations for miners to misbehave. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On 05/24/2014 08:14 PM, Gregory Maxwell wrote: On Sat, May 24, 2014 at 5:04 PM, Alan Reiner etothe...@gmail.com wrote: I think the most important change is modifying the way Bitcoin Core prioritizes blocks. Right now it uses the first full block verified. Instead, it should consider the first valid header received as highest priority, but only mine on it once it has done full verification of the This directly opens an attack where as soon as you find a block you announce the header to the world and then you delay announcing the block content. You can continue to mine on the block but no one else can (or alternatively they break their rule and risk extending an invalid block— bad news for SPV wallets)— then when you find a successor block or someone else finds a competing block you immediately announce the content. It basically means that you can always delay announcing a block and be sure that doing so doesn't deprive you of your winning position. Would this not be solved by putting a expiration on application of this logic? For instance, if you haven't received the full new block within 5-10 seconds (perhaps adjusted based on local bandwidth), then the header-received time is ignored. Or is this too hacky? I suppose this is exactly what Ashley is trying to solve, she's just already made a few more leaps forward in the design process than I have. I'll stop derailing it. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs ___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
I have done some work on incentives arising from block propagation times and it turns out that Bitcoin is already quite good at establishing the primacy of blocks by time despite what people think. Part of the reason for this is the way that partitions on the network evolve as a block is propagated. Typically at the moment, blocks reach over 50% of the network in 5 seconds. Reach being defined as a node receiving and validating a block. If we make an assumption that the hashing power of the network is uniformly distributed over the nodes (I know it is not a good assumption but can discuss it off the list). Then 50% of the hashing power are already building a block that builds on top of the block that is already circulating. The probability that there is a collision on the network therefore falls fast and then the probability that the miner who propagated the first block wins given a collision occurs is rising. I think that block propagation times might actually be a bigger issue for miners who are less well connected to the network in the sense that they spend more time mining redundant problems and during that time may find blocks to compete with blocks that are already spreading throughout the network. I have a paper that models this more formally and has some numerical simulations but cannot publish it on the internet at present (University Regulations) but I am happy to share a version privately if anyone is interested. Best, Jonathan -- Jonathan Levin Co-Founder Coinometrics http://www.coinometrics.com/ Postgraduate Economist | St Antony's College | Oxford University @jony_levin @Coinometrics -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
[Bitcoin-development] Cut-through propagation of blocks
Hi, On this list there has been some discussion around techniques to speed up block propagation, with a particular focus on reducing the extra orphan risk carried by larger blocks. The current store-and-forward method means that larger blocks will propagate with higher latency. One proposed solution has been to broadcast two separate messages: a fast, fixed-size header message, and a 2nd, slower body message containing the full block. Whilst this allows larger blocks to compete equally with smaller blocks on the which came first rule, it creates a new area of uncertain delay between receiving the header, and receiving the body, where there may be perverse incentives to mine empty blocks on top of not-yet-valid headers. So I would like to propose another method which is hopefully a less significant change to the existing protocol rules, but should help reduce the latency gap between large and small blocks. * Skip the inv/getdata sequence for new blocks - just push them out directly to save 1 roundtrip per hop * When receiving a new block from a peer, as soon as we have the first 80 bytes (header) we can validate the PoW and, with only a low-level change to the networking code, begin streaming that block to our peers (in the style of cut-through switching). * No other rules need to change. Block primacy can still be determined as of the moment they are fully validated and accepted, but now the latency caused by larger blocks is only (1 * BlockSize * BottleneckHopSpeed), instead of (Sum[n=0 to NumHops](BlockSize * NodeBandwidth(n))). * As far as I can tell, this shouldn't change any game theory or incentives because nodes still receive blocks exactly as they do now, just sooner. The difference is, invalid blocks that meet the PoW will be broadcast to everyone, but this is nothing new since someone can peer with you and send you an invalid block already. Network DoS should not be a possibility since it is very expensive to make invalid blocks that meet network PoW. Thoughts? Thanks -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
Re: [Bitcoin-development] Cut-through propagation of blocks
On Sat, May 24, 2014 at 1:27 PM, Ashley Holman dsc...@gmail.com wrote: * Skip the inv/getdata sequence for new blocks - just push them out directly to save 1 roundtrip per hop Upon further reflection, I remove this from my proposal. It's an unrelated optimisation that probably distracts from the main point which is the cut-through forwarding. The rest of the proposal still works if the inv/getdata sequence is retained. -- Accelerate Dev Cycles with Automated Cross-Browser Testing - For FREE Instantly run your Selenium tests across 300+ browser/OS combos. Get unparalleled scalability from the best Selenium testing platform available Simple to use. Nothing to install. Get started now for free. http://p.sf.net/sfu/SauceLabs___ Bitcoin-development mailing list Bitcoin-development@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/bitcoin-development
