Difference between revisions of "User:MatthewLM/ImprovedBlockRelayingProposal"

From Bitcoin Wiki
Jump to: navigation, search
(Created page with "{{bip}} <pre> Title: Segmented Block Relaying Author: Matthew Mitchell <cbitcoin@thelibertyportal.com> Status: Draft Type: Standards Track Created: 28-08-2012 </pre...")
 
Line 11: Line 11:
 
==Abstract==
 
==Abstract==
  
−
This BIP describes four new bitcoin messages, "gettreelevel", "treelevel", "getsegment" and "segment" which provide a method for downloading, validating and relaying segments of bitcoin blocks.
+
This BIP describes six new bitcoin messages, "getseginv", "seginv", "gettreelevel", "treelevel", "getsegment" and "segment" which provide a method for downloading, validating and relaying segments of bitcoin blocks.
  
 
==Motivation==
 
==Motivation==
Line 19: Line 19:
 
==Specification==
 
==Specification==
  
 +
A node will communicate via this protocol to peers with advertise a version at or above the protocol version for which this is to be implemented. Peers must also advertise NODE_NETWORK in the services flag.
  
 +
This BIP proposes the following new messages:
  
 +
'''getsiginv'''
 +
 +
Requests a "seginv" message for a block. Once this message is given for a block, the block field can be removed if sending again for the same block. When receiving this message, a node will store the block hash for the peer. The node will understand all requests from a peer to be for this block until the peer sends another "getsiginv" with another block hash. This message must therefore always be sent before any other messages below.
 +
 +
{|class="wikitable"
 +
! Field Size !! Name !! Data type !! Comments
 +
|-
 +
| 32 || block || char[32] || The hash of the block to obtain a segment inventory for. Not sent if referring to previous block.
 +
|}
 +
 +
'''seginv'''
 +
 +
This message will be structured to contain information describing the transactions a node has for a block. First the message contains one byte which describes the deepest level of the merkle tree the node has. Next the node lists merkle tree hash locations by a single byte for the depth followed by the index. The hash locations are placed one after the other and terminated with a null byte. If the node has all transactions, instead of three null bytes (for the depth, index and then termination), it should send one null byte which nodes should recognise as representing all transactions.
 +
 +
The index is either one byte, two bytes or four bytes depending upon the depth.
 +
 +
{|class="wikitable"
 +
! Depth !! Data type
 +
|-
 +
| 0-8 || uint8_t
 +
|-
 +
| 9-16 || uint16_t
 +
|-
 +
| 17-32 || uint32_t
 +
|}
 +
 +
The merkle root (covers all transactions) has the level 0. The far left hashes have the index 0. If the payload is 0x010100020300 it can be interpreted as:
 +
 +
<pre>
 +
0x01 -  The node has all hashes on level one which can be provided by "gettreelevel".
 +
0x0100 - The node has all transactions on the far left (index 0) of the first level, ie. It has the first half of transactions.
 +
0x0203 - The node has all transactions for index 3 of the second level, ie. It has the 3rd quarter of transactions.
 +
0x00 - Termination. This is all the node has.
 +
</pre>
 +
 +
'''gettreelevel'''
 +
 +
This message requests to a peer to respond with a "treelevel" message. A node can only request a level which is no deeper than the level returned by "seginv". This message requests hashes for the block specified by "getseginv".
 +
 +
{|class="wikitable"
 +
! Field Size !! Name !! Data type !! Comments
 +
|-
 +
| 1 || level || uint8_t || The level of the merkle tree to obtain. 0 is the root.
 +
|}
 +
 +
'''treelevel'''
 +
 +
This message respondes to "gettreelevel" with a list of all the merkle tree hashes at the specified level. Merkle trees in bitcoin can contain duplication. The hashes in this message should not contain duplicates. This message allows nodes to verify segments of the block belong to the merkle tree when dividing in powers of two.
 +
 +
{|class="wikitable"
 +
! Field Size !! Name !! Data type !! Comments
 +
|-
 +
| 32x? || hashes || char[][32] || The hashes for a merkle tree level.
 +
|}
 +
 +
'''getsegment'''
 +
 +
 +
 +
{|class="wikitable"
 +
! Field Size !! Name !! Data type !! Comments
 +
|-
 +
| ? || index || [[Protocol_specification#Variable_length_integer|var_int]] || The index of the first transaction to receive.
 +
|-
 +
| ? || num || [[Protocol_specification#Variable_length_integer|var_int]]  || The number of transactions to receive.
 +
|}
 +
 +
'''segment'''
 +
 +
{|class="wikitable"
 +
! Field Size !! Name !! Data type !! Comments
 +
|-
 +
| ? || count || [[Protocol_specification#Variable_length_integer|var_int]] || The number of transactions in this segment.
 +
|-
 +
| ? || txns || [[Protocol_specification#tx|tx]][] || The transactions for this segment.
 +
|}
 +
 +
This BIP also proposes the modification of ""
 
==Rationale==
 
==Rationale==
  

Revision as of 16:17, 28 August 2012

This page describes a BIP (Bitcoin Improvement Proposal).
Please see BIP 2 for more information about BIPs and creating them. Please do not just create a wiki page.

 
  Title: Segmented Block Relaying
  Author: Matthew Mitchell <cbitcoin@thelibertyportal.com>
  Status: Draft
  Type: Standards Track
  Created: 28-08-2012

Abstract

This BIP describes six new bitcoin messages, "getseginv", "seginv", "gettreelevel", "treelevel", "getsegment" and "segment" which provide a method for downloading, validating and relaying segments of bitcoin blocks.

Motivation

Currently the bitcoin protocol is designed so that it is only possible to download an entire block from a single peer. This may have been effective when block sizes were small but as blocks increase in size there should be methods for increasing parallelism, dealing with communication failure and removing redundancy to improve the efficiency of the bitcoin network.

Specification

A node will communicate via this protocol to peers with advertise a version at or above the protocol version for which this is to be implemented. Peers must also advertise NODE_NETWORK in the services flag.

This BIP proposes the following new messages:

getsiginv

Requests a "seginv" message for a block. Once this message is given for a block, the block field can be removed if sending again for the same block. When receiving this message, a node will store the block hash for the peer. The node will understand all requests from a peer to be for this block until the peer sends another "getsiginv" with another block hash. This message must therefore always be sent before any other messages below.

Field Size Name Data type Comments
32 block char[32] The hash of the block to obtain a segment inventory for. Not sent if referring to previous block.

seginv

This message will be structured to contain information describing the transactions a node has for a block. First the message contains one byte which describes the deepest level of the merkle tree the node has. Next the node lists merkle tree hash locations by a single byte for the depth followed by the index. The hash locations are placed one after the other and terminated with a null byte. If the node has all transactions, instead of three null bytes (for the depth, index and then termination), it should send one null byte which nodes should recognise as representing all transactions.

The index is either one byte, two bytes or four bytes depending upon the depth.

Depth Data type
0-8 uint8_t
9-16 uint16_t
17-32 uint32_t

The merkle root (covers all transactions) has the level 0. The far left hashes have the index 0. If the payload is 0x010100020300 it can be interpreted as: 

0x01 -  The node has all hashes on level one which can be provided by "gettreelevel".
0x0100 - The node has all transactions on the far left (index 0) of the first level, ie. It has the first half of transactions.
0x0203 - The node has all transactions for index 3 of the second level, ie. It has the 3rd quarter of transactions.
0x00 - Termination. This is all the node has.

gettreelevel

This message requests to a peer to respond with a "treelevel" message. A node can only request a level which is no deeper than the level returned by "seginv". This message requests hashes for the block specified by "getseginv".

Field Size Name Data type Comments
1 level uint8_t The level of the merkle tree to obtain. 0 is the root.

treelevel

This message respondes to "gettreelevel" with a list of all the merkle tree hashes at the specified level. Merkle trees in bitcoin can contain duplication. The hashes in this message should not contain duplicates. This message allows nodes to verify segments of the block belong to the merkle tree when dividing in powers of two.

Field Size Name Data type Comments
32x? hashes char[][32] The hashes for a merkle tree level.

getsegment


Field Size Name Data type Comments
 ? index var_int The index of the first transaction to receive.
 ? num var_int The number of transactions to receive.

segment

Field Size Name Data type Comments
 ? count var_int The number of transactions in this segment.
 ? txns tx[] The transactions for this segment.

This BIP also proposes the modification of ""

Rationale

By allowing for nodes to download blocks in segments as described in this BIP there are these advantages:

  • Nodes can complete validation of block segments before the download of other segments are completed.
  • Nodes can relay block segments before the download of other segments are completed.
  • Nodes can download different block segments from different peers at the same time.
  • If a connection is lost to a peer, a node can continue to download segments from other peers without needing to restart from nothing.
  • By requesting the transaction hashes, a node then only needs to download transactions it does not already have.
Retrieved from "https://en.bitcoin.it/w/index.php?title=User:MatthewLM/ImprovedBlockRelayingProposal&oldid=30210"