User:MatthewLM/ImprovedBlockRelayingProposal - Revision history

MatthewLM at 14:49, 10 September 2012

2012-09-10T14:49:45Z

← Older revision		Revision as of 14:49, 10 September 2012
Line 113:		Line 113:


	If a node has at least one block segment it relays "inv" messages containing the block hash to peers that use this protocol. For peers not using this protocol, the node must wait until the entire block is ready for relaying until it advertises it in "inv" messages. Nodes must revert to using "getdata" to peers not using this protocol, if a block cannot be downloaded via segmented block relaying. Nodes must always continue to respond to "getdata" requests ~~from nodes not using this protocol, but nodes which are using this protocol must not use "getdata" and 'block" for block relaying to peers also using this protocol~~. It is recommended that clients verify before downloading any segments, that the peers using this protocol collectively contain the entire block and revert to "getdata" if they do not.		If a node has at least one block segment it relays "inv" messages containing the block hash to peers that use this protocol. For peers not using this protocol, the node must wait until the entire block is ready for relaying until it advertises it in "inv" messages. Nodes must revert to using "getdata" to peers not using this protocol, if a block cannot be downloaded via segmented block relaying. Nodes must always continue to respond to "getdata" requests. It is recommended that clients verify before downloading any segments, that the peers using this protocol collectively contain the entire block and revert to "getdata" if they do not.

	==Backwards Compatibility==		==Backwards Compatibility==

MatthewLM at 23:53, 29 August 2012

2012-08-29T23:53:40Z

← Older revision		Revision as of 23:53, 29 August 2012
Line 38:		Line 38:
	'''seginv'''		'''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.		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. If the node has all transactions, instead of two null bytes (for the depth and index), it should send an empty payload which nodes should recognise as representing all transactions.

	The index is either one byte, two bytes or four bytes depending upon the depth.		The index is either one byte, two bytes or four bytes depending upon the depth.
Line 52:		Line 52:
	\|}		\|}

	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:		The merkle root (covers all transactions) has the level 0. The far left hashes have the index 0. If the payload is 0x0101000203 it can be interpreted as:

	<pre>		<pre>
Line 58:		Line 58:
	0x0100 - The node has all transactions on the far left (index 0) of the first level, ie. It has the first half of transactions.		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.		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>		</pre>

MatthewLM at 17:50, 28 August 2012

2012-08-28T17:50:40Z

← Older revision		Revision as of 17:50, 28 August 2012
Line 73:		Line 73:
	\| 1 \|\| level \|\| uint8_t \|\| The level of the merkle tree to obtain. 0 is the root.		\| 1 \|\| level \|\| uint8_t \|\| The level of the merkle tree to obtain. 0 is the root.
	\|}		\|}


	'''treelevel'''		'''treelevel'''
Line 129:		Line 130:
	* By requesting the transaction hashes, a node then only needs to download transactions it does not already have.		* By requesting the transaction hashes, a node then only needs to download transactions it does not already have.

	By allowing a node to request any level of the merkle tree, the node can divide the block verification arbitrarily. Clients could have various levels of sophistication is determining how to split blocks in the most efficient manner.		By allowing a node to request any level of the merkle tree, the node can divide the block verification arbitrarily. Clients could have various levels of sophistication in determining how to split blocks in the most efficient manner.

	The segmented block relaying protocol is designed to be lightweight and pass as little data as possible, therefore the messages may not be the most straightforward but are designed to be small.		The segmented block relaying protocol is designed to be lightweight and pass as little data as possible, therefore the messages may not be the most straightforward but are designed to be small.

MatthewLM at 17:49, 28 August 2012

2012-08-28T17:49:44Z

← Older revision		Revision as of 17:49, 28 August 2012
Line 34:		Line 34:

	If this message is received with block hash that a node has not advertised or if the block header has not been sent to the peer, then the message invalidates the protocol.		If this message is received with block hash that a node has not advertised or if the block header has not been sent to the peer, then the message invalidates the protocol.


	'''seginv'''		'''seginv'''
Line 61:		Line 62:

	A node must respond to a peer with this message if the block specified in "getsiginv" is valid (See above). If it does not then this violates the protocol. Bitcoin clients can use response timeouts for detecting failed responses. A node must also correctly describe what transactions it has and provide the number of the deepest level of the merkle tree it can provide in a "treelevel" message.		A node must respond to a peer with this message if the block specified in "getsiginv" is valid (See above). If it does not then this violates the protocol. Bitcoin clients can use response timeouts for detecting failed responses. A node must also correctly describe what transactions it has and provide the number of the deepest level of the merkle tree it can provide in a "treelevel" message.


	'''gettreelevel'''		'''gettreelevel'''
Line 81:		Line 83:
	\| 32x? \|\| hashes \|\| char[][32] \|\| The hashes for a merkle tree level.		\| 32x? \|\| hashes \|\| char[][32] \|\| The hashes for a merkle tree level.
	\|}		\|}


	'''getsegment'''		'''getsegment'''
Line 93:		Line 96:
	\| ? \|\| num \|\| [[Protocol_specification#Variable_length_integer\|var_int]] \|\| The number of transactions to receive.		\| ? \|\| num \|\| [[Protocol_specification#Variable_length_integer\|var_int]] \|\| The number of transactions to receive.
	\|}		\|}


	'''segment'''		'''segment'''

MatthewLM at 17:47, 28 August 2012

2012-08-28T17:47:59Z

← Older revision		Revision as of 17:47, 28 August 2012
Line 60:		Line 60:
	</pre>		</pre>

	A node must respond to a peer with this message if the block specified in "getsiginv" is valid (See above). If it does not then this violates the protocol. Bitcoin clients can use response timeouts for detecting failed responses.		A node must respond to a peer with this message if the block specified in "getsiginv" is valid (See above). If it does not then this violates the protocol. Bitcoin clients can use response timeouts for detecting failed responses. A node must also correctly describe what transactions it has and provide the number of the deepest level of the merkle tree it can provide in a "treelevel" message.

	'''gettreelevel'''		'''gettreelevel'''
Line 125:		Line 125:
	* By requesting the transaction hashes, a node then only needs to download transactions it does not already have.		* By requesting the transaction hashes, a node then only needs to download transactions it does not already have.

	By allowing a node to request any level of the merkle tree, the node can divide the block verification arbitrarily. Clients could have various levels of sophistication		By allowing a node to request any level of the merkle tree, the node can divide the block verification arbitrarily. Clients could have various levels of sophistication is determining how to split blocks in the most efficient manner.

			The segmented block relaying protocol is designed to be lightweight and pass as little data as possible, therefore the messages may not be the most straightforward but are designed to be small.

MatthewLM at 17:29, 28 August 2012

2012-08-28T17:29:08Z

← Older revision		Revision as of 17:29, 28 August 2012
Line 6:		Line 6:
	Status: Draft		Status: Draft
	Type: Standards Track		Type: Standards Track
	~~Created: 28-08-2012~~
	</pre>		</pre>

Line 110:		Line 109:


	If a node has at least one block segment it relays "inv" messages containing the block hash to peers that use this protocol. ~~To other~~ peers, the node must wait until the entire block is ready for relaying until it advertises it in "inv" messages. Nodes must revert to using ~~getblocks~~		If a node has at least one block segment it relays "inv" messages containing the block hash to peers that use this protocol. For peers not using this protocol, the node must wait until the entire block is ready for relaying until it advertises it in "inv" messages. Nodes must revert to using "getdata" to peers not using this protocol, if a block cannot be downloaded via segmented block relaying. Nodes must always continue to respond to "getdata" requests from nodes not using this protocol, but nodes which are using this protocol must not use "getdata" and 'block" for block relaying to peers also using this protocol. It is recommended that clients verify before downloading any segments, that the peers using this protocol collectively contain the entire block and revert to "getdata" if they do not.

			==Backwards Compatibility==

			Backwards compatibility is maintained because nodes using this protocol must still respond to "getdata" block requests by peers not using the protocol and nodes using this protocol must revert to using "getdata" to receive blocks when the peers using the protocol cannot provide the full block.

	==Rationale==		==Rationale==
Line 121:		Line 124:
	* If a connection is lost to a peer, a node can continue to download segments from other peers without needing to restart from nothing.		* 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.		* By requesting the transaction hashes, a node then only needs to download transactions it does not already have.

			By allowing a node to request any level of the merkle tree, the node can divide the block verification arbitrarily. Clients could have various levels of sophistication

MatthewLM at 17:05, 28 August 2012

2012-08-28T17:05:43Z

← Older revision		Revision as of 17:05, 28 August 2012
Line 23:		Line 23:
	This BIP proposes the following new messages:		This BIP proposes the following new messages:

	'''~~getsiginv~~'''
			'''getseginv'''

	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.		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.
Line 107:		Line 108:
	\| ? \|\| txns \|\| [[Protocol_specification#tx\|tx]][] \|\| The transactions for this segment.		\| ? \|\| txns \|\| [[Protocol_specification#tx\|tx]][] \|\| The transactions for this segment.
	\|}		\|}


			If a node has at least one block segment it relays "inv" messages containing the block hash to peers that use this protocol. To other peers, the node must wait until the entire block is ready for relaying until it advertises it in "inv" messages. Nodes must revert to using getblocks

	==Rationale==		==Rationale==

MatthewLM at 16:57, 28 August 2012

2012-08-28T16:57:42Z

← Older revision		Revision as of 16:57, 28 August 2012
Line 11:		Line 11:
	==Abstract==		==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.		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. This BIP describes the communications protocol for these new messages and does not describe how nodes can utilise the protocol for improved validation.

	==Motivation==		==Motivation==
Line 30:		Line 30:
	! Field Size !! Name !! Data type !! Comments		! 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.		\| 32 \|\| block \|\| char[32] \|\| The hash of the block to obtain a segment inventory for. Not sent if referring to previous block. The block must have been advertised by the peer in an "inv" message or the block header must have been sent by the peer.
	\|}		\|}

			If this message is received with block hash that a node has not advertised or if the block header has not been sent to the peer, then the message invalidates the protocol.

	'''seginv'''		'''seginv'''
Line 57:		Line 59:
	0x00 - Termination. This is all the node has.		0x00 - Termination. This is all the node has.
	</pre>		</pre>

			A node must respond to a peer with this message if the block specified in "getsiginv" is valid (See above). If it does not then this violates the protocol. Bitcoin clients can use response timeouts for detecting failed responses.

	'''gettreelevel'''		'''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".		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", otherwise the protocol has been violated. This message requests hashes for the block specified by "getseginv".

	{\|class="wikitable"		{\|class="wikitable"
Line 70:		Line 74:
	'''treelevel'''		'''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.		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. If the message contains duplicates, it violates the protocol. The hashes must validate to the merkle root of a block and match the level requested, otherwise the message is in violation fo the protocol. This message allows nodes to verify segments of the block belong to the merkle tree when dividing in powers of two. If a valid "gettreelevel" message has been received, this message must be sent in response.

	{\|class="wikitable"		{\|class="wikitable"
Line 80:		Line 84:
	'''getsegment'''		'''getsegment'''

			This message requests a segment of a block. The message specifies a starting transaction index and then the number of transactions to receive. The message violates the protocol if the index and number of transactions falls out of the range of the block, except in the case where the range covers duplicated transactions in the merkle tree. For example if a block has 3 transactions, the hash on level one to the right will have two children to the 3rd transaction. It is okay for this message to cover the 3rd transaction as if it were two.

	{\|class="wikitable"		{\|class="wikitable"
Line 91:		Line 95:

	'''segment'''		'''segment'''

			This message responds to "getsegment" with a list of transactions. The transactions should match the starting index and number of transactions specified by "getsegment", except where there is duplication, in which case duplicates are not sent and the number of transactions may be less.

			This message does not contain the number of transactions. Transactions can be linearly de-serialised until no more space is found.

			Nodes must respond to valid "getsegment" messages with this message.

	{\|class="wikitable"		{\|class="wikitable"
	! Field Size !! Name !! Data type !! Comments		! 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.		\| ? \|\| txns \|\| [[Protocol_specification#tx\|tx]][] \|\| The transactions for this segment.
	\|}		\|}

	~~This BIP also proposes the modification of ""~~
	==Rationale==		==Rationale==

MatthewLM at 16:17, 28 August 2012

2012-08-28T16:17:45Z

@@ Line 11: / Line 11: @@
 ==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==
@@ Line 19: / Line 19: @@
 ==Specification==
 ==Rationale==

MatthewLM: Created page with "{{bip}}

   Title: Segmented Block Relaying   Author: Matthew Mitchell    Status: Draft   Type: Standards Track   Created: 28-08-2012 
2012-08-28T14:10:28Z
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..."
New page
{{bip}}



<pre>

  Title: Segmented Block Relaying

  Author: Matthew Mitchell <cbitcoin@thelibertyportal.com>

  Status: Draft

  Type: Standards Track

  Created: 28-08-2012

</pre>



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



==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==







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