* Re: [Bitcoin-development] Cut-through propagation of blocks [not found] <mailman.177181.1400974908.2207.bitcoin-development@lists.sourceforge.net> @ 2014-05-24 23:57 ` Jonathan Levin 0 siblings, 0 replies; 12+ messages in thread From: Jonathan Levin @ 2014-05-24 23:57 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 1652 bytes --] 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 [-- Attachment #2: Type: text/html, Size: 5300 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* [Bitcoin-development] Cut-through propagation of blocks
@ 2014-05-24 3:57 Ashley Holman
2014-05-24 5:11 ` Ashley Holman
` (2 more replies)
0 siblings, 3 replies; 12+ messages in thread
From: Ashley Holman @ 2014-05-24 3:57 UTC (permalink / raw)
To: bitcoin-development
[-- Attachment #1: Type: text/plain, Size: 2027 bytes --]
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
[-- Attachment #2: Type: text/html, Size: 2255 bytes --]
^ permalink raw reply [flat|nested] 12+ messages in thread* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 3:57 Ashley Holman @ 2014-05-24 5:11 ` Ashley Holman 2014-05-24 22:59 ` Bernd Jendrissek 2014-05-24 23:16 ` Gregory Maxwell 2 siblings, 0 replies; 12+ messages in thread From: Ashley Holman @ 2014-05-24 5:11 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 436 bytes --] On Sat, May 24, 2014 at 1:27 PM, Ashley Holman <dscvlt@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. [-- Attachment #2: Type: text/html, Size: 855 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 3:57 Ashley Holman 2014-05-24 5:11 ` Ashley Holman @ 2014-05-24 22:59 ` Bernd Jendrissek 2014-05-24 23:16 ` Gregory Maxwell 2 siblings, 0 replies; 12+ messages in thread From: Bernd Jendrissek @ 2014-05-24 22:59 UTC (permalink / raw) To: Ashley Holman; +Cc: Bitcoin Dev On Sat, May 24, 2014 at 5:57 AM, Ashley Holman <dscvlt@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"? ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 3:57 Ashley Holman 2014-05-24 5:11 ` Ashley Holman 2014-05-24 22:59 ` Bernd Jendrissek @ 2014-05-24 23:16 ` Gregory Maxwell 2014-05-24 23:41 ` Ashley Holman 2014-05-25 9:36 ` Mike Hearn 2 siblings, 2 replies; 12+ messages in thread From: Gregory Maxwell @ 2014-05-24 23:16 UTC (permalink / raw) To: Ashley Holman; +Cc: Bitcoin Development On Fri, May 23, 2014 at 8:57 PM, Ashley Holman <dscvlt@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). ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 23:16 ` Gregory Maxwell @ 2014-05-24 23:41 ` Ashley Holman 2014-05-25 0:04 ` Alan Reiner 2014-05-25 9:36 ` Mike Hearn 1 sibling, 1 reply; 12+ messages in thread From: Ashley Holman @ 2014-05-24 23:41 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 3335 bytes --] On Sun, May 25, 2014 at 8:29 AM, Bernd Jendrissek <bitcoin@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: <msgid><chunksize><rawbytes>, <msgid><chunksize><rawbytes>, 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 <gmaxwell@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. [-- Attachment #2: Type: text/html, Size: 4490 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 23:41 ` Ashley Holman @ 2014-05-25 0:04 ` Alan Reiner 2014-05-25 0:14 ` Gregory Maxwell 0 siblings, 1 reply; 12+ messages in thread From: Alan Reiner @ 2014-05-25 0:04 UTC (permalink / raw) To: bitcoin-development [-- Attachment #1: Type: text/plain, Size: 4971 bytes --] On 05/24/2014 07:41 PM, Ashley Holman wrote: > On Sun, May 25, 2014 at 8:29 AM, Bernd > Jendrissek <bitcoin@bpj-code•co.za > <mailto:bitcoin@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: > > <msgid><chunksize><rawbytes>, <msgid><chunksize><rawbytes>, 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 <gmaxwell@gmail•com > <mailto:gmaxwell@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. [-- Attachment #2: Type: text/html, Size: 7593 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-25 0:04 ` Alan Reiner @ 2014-05-25 0:14 ` Gregory Maxwell 2014-05-25 0:38 ` Alan Reiner 0 siblings, 1 reply; 12+ messages in thread From: Gregory Maxwell @ 2014-05-25 0:14 UTC (permalink / raw) To: Alan Reiner; +Cc: Bitcoin Development On Sat, May 24, 2014 at 5:04 PM, Alan Reiner <etotheipi@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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-25 0:14 ` Gregory Maxwell @ 2014-05-25 0:38 ` Alan Reiner 0 siblings, 0 replies; 12+ messages in thread From: Alan Reiner @ 2014-05-25 0:38 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Development On 05/24/2014 08:14 PM, Gregory Maxwell wrote: > On Sat, May 24, 2014 at 5:04 PM, Alan Reiner <etotheipi@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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-24 23:16 ` Gregory Maxwell 2014-05-24 23:41 ` Ashley Holman @ 2014-05-25 9:36 ` Mike Hearn 2014-05-25 9:51 ` Gregory Maxwell 1 sibling, 1 reply; 12+ messages in thread From: Mike Hearn @ 2014-05-25 9:36 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 685 bytes --] > > 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. [-- Attachment #2: Type: text/html, Size: 947 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-25 9:36 ` Mike Hearn @ 2014-05-25 9:51 ` Gregory Maxwell 2014-05-26 15:08 ` Mike Hearn 0 siblings, 1 reply; 12+ messages in thread From: Gregory Maxwell @ 2014-05-25 9:51 UTC (permalink / raw) To: Mike Hearn; +Cc: Bitcoin Development On Sun, May 25, 2014 at 2:36 AM, Mike Hearn <mike@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. ^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [Bitcoin-development] Cut-through propagation of blocks 2014-05-25 9:51 ` Gregory Maxwell @ 2014-05-26 15:08 ` Mike Hearn 0 siblings, 0 replies; 12+ messages in thread From: Mike Hearn @ 2014-05-26 15:08 UTC (permalink / raw) To: Gregory Maxwell; +Cc: Bitcoin Development [-- Attachment #1: Type: text/plain, Size: 728 bytes --] > > 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. [-- Attachment #2: Type: text/html, Size: 1046 bytes --] ^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2014-05-26 15:08 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <mailman.177181.1400974908.2207.bitcoin-development@lists.sourceforge.net>
2014-05-24 23:57 ` [Bitcoin-development] Cut-through propagation of blocks Jonathan Levin
2014-05-24 3:57 Ashley Holman
2014-05-24 5:11 ` Ashley Holman
2014-05-24 22:59 ` Bernd Jendrissek
2014-05-24 23:16 ` Gregory Maxwell
2014-05-24 23:41 ` Ashley Holman
2014-05-25 0:04 ` Alan Reiner
2014-05-25 0:14 ` Gregory Maxwell
2014-05-25 0:38 ` Alan Reiner
2014-05-25 9:36 ` Mike Hearn
2014-05-25 9:51 ` Gregory Maxwell
2014-05-26 15:08 ` Mike Hearn
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox