Bitcoin Forum
November 23, 2017, 07:22:34 AM *
News: Latest stable version of Bitcoin Core: 0.15.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Low latency block distribution without validation  (Read 767 times)
TierNolan
Legendary
*
Offline Offline

Activity: 1120


View Profile
March 18, 2015, 10:31:38 AM
 #1

Notifying all nodes that a new block has (probably) been found can be accomplished by broadcasting block headers.

If a header is received that extends the main chain, then it can be broadcast to all peers.  If all nodes follow this rule, then the header will be distributed across the network.  A new block that meets the POW is highly likely to be valid, though it would still need to be checked.

The problem with this policy is that it facilitates transaction withholding.  If a miner finds a block and just sends the header, then all other miners have an incentive to mine on top of that block.  Since they don't know which transactions are in the block, they have to mine a block which is coinbase only.

The network rule is that nodes should only forward blocks once the block has been fully validated.  This means that a node must receive the block, in full, before forwarding it to peers.  It also has to fully validate the block.  All this adds to latency.

Additionally, this means that SPV clients cannot forward blocks.  If full validation was not required, an SPV client on a smartphone that is connected to Wifi and has > 95% battery charge could be set to help forward blocks.  This would improve network redundancy.

There is no need for full validation of blocks in order to confirm that the block has been fully published.  The block POW inherently acts as DDOS protection.

I suggest two new messages "chaintip" and "newblock".

The chaintip message would contain a single hash and a transaction index.  It indicates to the peer the tip of the longest chain that the node knows about.  Normally, the transaction index would be equal to the number of transactions in the block, meaning all transactions were received for that block (setting it to all ones would also mean the block was fully received).

When a node receives a new block, it would forward it to all peers that has its parent set as chaintip, using the newblock messages.

A block is broken down into multiple "newblock" message of the following format:

int256 blockid
int32 message_index = starts from zero for each block
block header (or empty array for message_index > 0)
encoded merkle branch(es)
varint tx_count
txs[tx_count]: transactions

The message is required to either contain exactly one transaction or have a length less than 8kB.  This means that the block is broken up into lots of small parts.  Large transactions can still be sent, but are sent in their own message.

Each message contains the extra merkle branch info needed to verify all the transactions in the message.  The more transactions sent in a single message, the less merkle info is required.  The encoding would be similar to the merkleblock encoding but modified so that branch info sent in previous messages doesn't need to be re-sent. 

It might be better to just include the entire branch, so that newblock messages can be verified without needing additional info (other than the block header).

Since the block is broken into pieces, the entire block doesn't need to be received before the node can start forwarding newblock messages to peers.  This cuts down on latency. 

A peer can sends a new chaintip message to inform peers how many transactions it has received for the new block.  Peers would not forward newblock messages for transactions that it already has.

The chaintip message could be used to indicate that it wants no more newblock messages from a particular peer by sending a chaintip with the transaction count sent to all ones.  It would still receive newblock messages if another block was found.

Unless a node sends at least one chaintip message, it would never receive newblock messages.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
1511421754
Hero Member
*
Offline Offline

Posts: 1511421754

View Profile Personal Message (Offline)

Ignore
1511421754
Reply with quote  #2

1511421754
Report to moderator
1511421754
Hero Member
*
Offline Offline

Posts: 1511421754

View Profile Personal Message (Offline)

Ignore
1511421754
Reply with quote  #2

1511421754
Report to moderator
1511421754
Hero Member
*
Offline Offline

Posts: 1511421754

View Profile Personal Message (Offline)

Ignore
1511421754
Reply with quote  #2

1511421754
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
gmaxwell
Moderator
Legendary
*
qt
Offline Offline

Activity: 2338



View Profile
March 18, 2015, 11:59:15 AM
 #2

An unvalidated getblock was implemented by Luke-JR previously. It didn't meaningfully improve performance. Latency in the system doesn't come from verification because practically all the data is already verified.

The 'transaction index' that you're describing sounds like it would have have more overhead just to relay one chunk than Matt's relaynetwork protocol typically needs to relay a whole block.

Block verification is not needed a DOS protection, indeed, but it's arguably important that the verifying network censor invalid blocks to avoid exposing SPV clients to them who will not be able to verify them in order to maintain strong incentives against producing invalid blocks.

At the other end of the spectrum there are ideas that can give basically perfect parallelism and perfect efficiency relative to already transmitted data, but they're certainly more complex.

Bitcoin will not be compromised
TierNolan
Legendary
*
Offline Offline

Activity: 1120


View Profile
March 18, 2015, 01:21:04 PM
 #3

The 'transaction index' that you're describing sounds like it would have have more overhead just to relay one chunk than Matt's relaynetwork protocol typically needs to relay a whole block.

Clients wouldn't confirm/update the chaintip after every transaction.  It is mainly just a way to prevent wasting bandwidth due to receiving the newblock messages from multiple peers.

The main idea is to send partial (unverified) blocks.  I think the relaynetwork protocol doesn't do block validation either?  

It remembers what transactions have already been sent and either sends a reference or the full transaction depending.  The assumption being

p2p --> bitcoind <-> relaynode <-> relaynode <-> bitcoind <--- p2p

Each relaynode has a bitcoind doing border routing?

Inherently, under that system, the entire block must be received before it can be relayed to peers.  With smaller messages, they can be forwarded, even if the rest of the block has not been received.

For larger blocks, especially if the 1MB limit is lifted, that latency would be more significant.

Quote
Block verification is not needed a DOS protection, indeed, but it's arguably important that the verifying network censor invalid blocks to avoid exposing SPV clients to them who will not be able to verify them in order to maintain strong incentives against producing invalid blocks.

SPV clients would still have to make sure that there are sufficient confirms.  This is just a way to distribute blocks without having to receive the entire block first.

Quote
At the other end of the spectrum there are ideas that can give basically perfect parallelism and perfect efficiency relative to already transmitted data, but they're certainly more complex.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Sergio_Demian_Lerner
Hero Member
*****
expert
Offline Offline

Activity: 539


View Profile WWW
March 19, 2015, 07:09:24 PM
 #4

I proposed something similar long ago and we implemented it in the NimbleCoinJ library (you can get it from github).
Basically we have a "newblock" command which sends only the header. And a "blockhashes" command which sends a list of hashes (partial hashes can also be sent). Nodes spread the header as fast as they can. Then they spread the hash list as fast as they can. Finally they validate block. Miners work on unverified blocks for a fixed amount of time, and then roll-back if they were unable to reconstruct the block. This works well if: the subsidy is high (so that creating empty blocks is no problem) or the fees are averaged (so even if you create an empty block you still get some fees) or if the block rate is so high that trying to withhold block transactions only reduce your chances of your block being accepted, and then there is no incentive to do so.

We implemented header-only propagation to achieve a 6 seconds block interval and an orphan rate similar to Bitcoin. We tested and it really worked well. Verifying 100x Bitcoin transaction volume in real-time was possible. It uses some additional magic, such as the DECOR+ protocol, and a local route-optimization protocol. NimbleCoin will probably be a Bitcoin side-chain. We're waiting for Blockstream to do their first step.

Regards


Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!