User:MatthewLM/ImprovedBlockRelayingProposal: Difference between revisions
mNo edit summary |
No edit summary |
||
| (2 intermediate revisions by the same user not shown) | |||
| 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 | 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 | 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. | ||
</pre> | </pre> | ||
| Line 73: | Line 72: | ||
| 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 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 | 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== | ||
| Line 129: | Line 129: | ||
* 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 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. | ||
Latest revision as of 14:49, 10 September 2012
|
This page describes a BIP (Bitcoin Improvement Proposal). |
Title: Segmented Block Relaying Author: Matthew Mitchell <cbitcoin@thelibertyportal.com> Status: Draft Type: Standards Track
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 the communications protocol for these new messages and does not describe how nodes can utilise the protocol for improved validation.
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:
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.
| 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. 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
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.
| 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 0x0101000203 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.
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
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".
| 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. 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.
| Field Size | Name | Data type | Comments |
|---|---|---|---|
| 32x? | hashes | char[][32] | The hashes for a merkle tree level. |
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.
| 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
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.
| Field Size | Name | Data type | Comments |
|---|---|---|---|
| ? | txns | 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. 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 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
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.
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.