Segmented Block Relaying BIP draft.

Here is a BIP draft for improving the block relaying and validation so that it can be done in parallel and so that redundancy can be removed. This becomes more beneficial the larger the block sizes are.

https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal

Matthew Mitchell

On Mon, Sep 10, 2012 at 11:07 AM, Matthew Mitchell <matthewmitchell@godofgod•co•uk> wrote:

> Here is a BIP draft for improving the block relaying and validation so that
> it can be done in parallel and so that redundancy can be removed. This
> becomes more beneficial the larger the block sizes are.
>
> https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal

Why does this focus on actually sending the hash tree? The block header + transaction list + transactions a node doesn't already know (often just the coinbase) is enough.

I actually implemented parts of the header+ v<tx> stuff in a branch with my bloom filter stuff, you can see it here: https://github.com/TheBlueMatt/bitcoin/commits/bloom%2Brelayblock Its pretty stupid and would be pretty easy to DoS/get it stuck/etc, but in theory it works. I don't see much reason why we'd need anything significantly more complicated, but maybe there is a use-case I'm missing?

Matt

On Mon, 2012-09-10 at 11:14 -0400, Gregory Maxwell wrote:

> On Mon, Sep 10, 2012 at 11:07 AM, Matthew Mitchell
> <matthewmitchell@godofgod•co•uk> wrote:
> > Here is a BIP draft for improving the block relaying and validation so that
> > it can be done in parallel and so that redundancy can be removed. This
> > becomes more beneficial the larger the block sizes are.
> >
> > https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal
>
> Why does this focus on actually sending the hash tree?  The block
> header + transaction list + transactions a node doesn't already know
> (often just the coinbase) is enough.

On Monday, September 10, 2012 3:07:52 PM Matthew Mitchell wrote:

> Here is a BIP draft for improving the block relaying and validation so that
> it can be done in parallel and so that redundancy can be removed. This
> becomes more beneficial the larger the block sizes are.
>
> https://en.bitcoin.it/wiki/User:MatthewLM/ImprovedBlockRelayingProposal

Most of the problem with block propagation lies in implementation, not protocol... Distributing missing transaction on an as-needed basis is a possible improvement at the protocol level, but there hasn't (AFAIK) been any research into whether the little benefit outweighs the cost yet. In any case, I don't see why 6 new messages are needed instead of simply adding a single new type to getinv?

Do you mean getdata? Here is the reason for the 6 new messages:

getseginv,seginv - These are for learning about what segments of a block a node has. Else you could remove these messages and simply have nodes advertise blocks via inventory messages. In this case nodes would have to wait until they had fully received a block before relaying anything. No longer is there a benefit with nodes being able to relay segments of blocks before they have received the entire block.

gettreelevel,treelevel - These are to received a level of the merle tree. Instead you might use get data but gettreelevel is more compact than get data and is clearly differentiates itself as part of the new protocol. Perhaps these messages could include the block headers alongside the hashes and you could request many at once like with the getheaders message? If you skip these messages, then you could verify the transactions at the end but there would be problems when peers give bad segments where data would need to be downloaded again.

getsegment,segment - These are clearly important to request and receive segments for the blocks. These allows for nodes to download arbitrary segments of blocks. The optimum number of segments could be calculated by node software using measurements of download speeds and latency times, the number of connections and how likely redundancy is to occur. If a node is up-to-date and likely has many of the transactions in blocks, it can start asking for the deepest merle level (tx hashes) and ask nodes for segments, avoiding transactions it already has.

I'll get around to doing measurements myself sometime to estimate the benefit of this proposal. It will certainly be beneficial when block sizes reach some size but not much is really known except what can be assumed/guessed.

I should also mention the bitcointalk topic here: https://bitcointalk.org/index.php?topic=103295.0

On 10 Sep 2012, at 19:59, "Luke-Jr" <luke@dashjr•org> wrote:

>
> Most of the problem with block propagation lies in implementation, not
> protocol... Distributing missing transaction on an as-needed basis is a
> possible improvement at the protocol level, but there hasn't (AFAIK) been any
> research into whether the little benefit outweighs the cost yet. In any case,
> I don't see why 6 new messages are needed instead of simply adding a single
> new type to getinv?

It seems to me the whole idea of segmenting blocks would add very little (to nothing) with any sane block size. Sure, if a block were to be 10GB, it may make sense. However, even in that case, it would be easier to relay a list of tx hashes (which may be a bit expensive) and txes separately instead of using a notion of block segments. That said, I don't see blocks ever being that large and if they do become that large, as only a few full nodes will remain, upgrading their protocol would be (relatively) easy. I would instead encourage focus on decreasing block relay times for the current network and as blocks approach 10MB (so that they can approach 10MB).

Matt

On Mon, 2012-09-10 at 20:34 +0100, Matthew Mitchell wrote:

> Do you mean getdata? Here is the reason for the 6 new messages:
>
>
> getseginv,seginv - These are for learning about what segments of a
> block a node has. Else you could remove these messages and simply have
> nodes advertise blocks via inventory messages. In this case nodes
> would have to wait until they had fully received a block before
> relaying anything. No longer is there a benefit with nodes being able
> to relay segments of blocks before they have received the entire
> block.
>
>
> gettreelevel,treelevel - These are to received a level of
> the merle tree. Instead you might use get data but gettreelevel is
> more compact than get data and is clearly differentiates itself as
> part of the new protocol. Perhaps these messages could include the
> block headers alongside the hashes and you could request many at once
> like with the getheaders message? If you skip these messages, then you
> could verify the transactions at the end but there would be problems
> when peers give bad segments where data would need to be downloaded
> again.
>
>
> getsegment,segment - These are clearly important to request and
> receive segments for the blocks. These allows for nodes
> to download arbitrary segments of blocks. The optimum number of
> segments could be calculated by node software using measurements of
> download speeds and latency times, the number of connections and how
> likely redundancy is to occur. If a node is up-to-date and likely has
> many of the transactions in blocks, it can start asking for the
> deepest merle level (tx hashes) and ask nodes for segments, avoiding
> transactions it already has.
>
>
> I'll get around to doing measurements myself sometime to estimate the
> benefit of this proposal. It will certainly be beneficial when block
> sizes reach some size but not much is really known except what can be
> assumed/guessed.
>
>
> I should also mention the bitcointalk topic
> here: https://bitcointalk.org/index.php?topic=103295.0
>
> On 10 Sep 2012, at 19:59, "Luke-Jr" <luke@dashjr•org> wrote:
> >
> > Most of the problem with block propagation lies in implementation,
> > not
> > protocol... Distributing missing transaction on an as-needed basis
> > is a
> > possible improvement at the protocol level, but there hasn't (AFAIK)
> > been any
> > research into whether the little benefit outweighs the cost yet. In
> > any case,
> > I don't see why 6 new messages are needed instead of simply adding a
> > single
> > new type to getinv?

On Mon, Sep 10, 2012 at 3:53 PM, Matt Corallo <bitcoin-list@bluematt•me> wrote:

> It seems to me the whole idea of segmenting blocks would add very little
> (to nothing) with any sane block size.  Sure, if a block were to be
> 10GB, it may make sense.  However, even in that case, it would be easier

As you know there is a hard protocol limit of 1MB.

If you're going to talk about doing that you are screwing with the core economic promises of the system. (in particular, removing the cap eliminates the only armwave we have for long term security). But in any case, removing it requires a complete and totally incompatible hardfork, and at that point you can do whatever you want with the protocol. Changing how blocks are fetched is almost incidental to the number of other things that would be changed. I don't think it makes sense to design for that especially when something far simpler (as you pointed out) is prudent for the design of bitcoin.