Re: [Bitcoin-development] Cut-through propagation of blocks

Re: [Bitcoin-development] Cut-through propagation of blocks

[Jonathan Levin]

[-- 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 --]

[Bitcoin-development] Cut-through propagation of blocks

[Ashley Holman]

[-- 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 --]

Re: [Bitcoin-development] Cut-through propagation of blocks

[Ashley Holman]

[-- 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 --]

Re: [Bitcoin-development] Cut-through propagation of blocks

[Bernd Jendrissek]

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"?

Re: [Bitcoin-development] Cut-through propagation of blocks

[Gregory Maxwell]

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).

Re: [Bitcoin-development] Cut-through propagation of blocks

[Ashley Holman]

[-- 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 --]

Re: [Bitcoin-development] Cut-through propagation of blocks

[Alan Reiner]

[-- 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 --]

Re: [Bitcoin-development] Cut-through propagation of blocks

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Cut-through propagation of blocks

[Alan Reiner]

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.

Re: [Bitcoin-development] Cut-through propagation of blocks

[Mike Hearn]

[-- 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 --]

Re: [Bitcoin-development] Cut-through propagation of blocks

[Gregory Maxwell]

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.

Re: [Bitcoin-development] Cut-through propagation of blocks

[Mike Hearn]

[-- 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 --]