Been following Gavin's proposal for O(1) block propagation times.
Maybe I'm missing something really big here, but why can't blocks simply be propagated to peers asynchronously? Once a block header that has a valid hash is received (80 bytes) start to propagate the entire block contents to one's peers rather than waiting for all transactions to arrive. The block's eventual validity still would depend on the correctness of the comprised transactions.
You can't update the UTXO set and start building on the new block until you see all the transactions (because you don't know which transactions in your memory pool are spent).
So propagating asynchronously doesn't help.
Maybe I'm missing something again but how would other peers have the coinbase transaction in their memory pool?
@pgrigor You mean in my proposal? The coinbase transaction isn't in the mempool, it is redundantly error-correcting-encoded in the IBLT and is recovered by the IBLT decoding process.
So your proposal then isn't so much targeted toward propagation times, but rather is in place to allow miners to start working on the next block? The async solution would solve the propagation time problem.
Propagation times are tied intimately to getting miners to work on the next block. You cannot separate the two.
Generally speaking, nodes have already seen transactions that have been broadcast on the network. You do not want to send that data across the network a second time. You need the block header, the coinbase transaction, and some way to arrive at the correct list of transactions for that block.
I've explained it a bit better in this reddit post: http://www.reddit.com/r/Bitcoin/comments/2d98by/o1_block_propagation_using_asynchronous_block/
Full nodes verify before propagating.
Yes, they verify the entire block. This is unnecessary. They only need to verify the header then can start to forward the block (all of the block) immediately.
An invalid header would result in no propagation. A valid header would entail all the proof of work necessary, so miners would have a big incentive to forward the transactions after starting to forward the header.
Of course all nodes still would verify the entire block before accepting it, but the receipt of the header would act as a "placeholder" for the winning block. In this way a 10GB block would "win" over a 10K block as long as its header was received first. This makes propagation times irrelevant and removes the incentive to mine smaller blocks.
So your objection is that miners will spend their resources creating valid block headers for which they'll never get paid?
Remember, the block isn't confirmed until the full block is received. I'm separating confirmation from propagation. It's the propagation time that's O(n) now and provides an incentive for miners to mine smaller blocks. Blocks would be selected based on propagation, and accepted based on confirmation.
Bitcoin is a trustless system. You don't mine on blocks unless you have proven through validation that you trust them. Your distinction is without difference.
A block still wouldn't be mined until it was fully validated. The async forwarding of blocks simply starts propagating blocks upon receipt of a valid block header rather than waiting for the full block to be received.
There's absolutely no difference from what's being done now, except that the valid header serves as a "go-ahead" to start propagating the information received rather than waiting for the full block to arrive.
If the block hash is good enough to secure blocks, surely it's good enough to act as a signal that what's currently being received can be propagated.
EDIT: And I'm not talking at all about miners beginning to mine the next block. I'm talking about O(1) propagation time for blocks they've already mined. Mining the next block can't be done until the full block is received, but this is separate from how quickly the block propagates the network in the first place; it's also separate from how efficiently we can communicate a block's information (which is what Gavin's proposal does)
@pgrigor is correct here. This is the same idea I tried to implement about a year ago.
The local node won't accept the new block itself until verification completes, but it should be capable of doing the relay in realtime to reduce the overall propagation time.
I believe #3195 covered this topic pretty accurately, including your proposed "First seen header wins" rule.
I proposed an idea to the dev list which is basically the same as this. The subject was "cut-through propagation of blocks". Essentially it follows the same principle that routers/switches do, by beginning to forward a packet after receiving only the header, rather than the slower store-and-forward approach. As @pgrigor said, the change is compatible and complimentary to the IBLT work.
However, this change can be done as a low-level optimisation to networking code, without needing to change the chain selection rule. I.e. only count the block as "seen" once it is fully received and validated. This way you get the benefits of the streaming propagation, without having to worry about the implications of changing the chain selection rule to consider partial blocks. A far less controversial change.
Also worth noting: I believe that implementing this change would require an enhancement to the p2p protocol to support multiplexing of messages. Otherwise, someone can send a valid header but stall or slow the sending of the rest of the block in order to "jam" many of the connections in the network. Multiplexing would allow for one block to stream slowly while other faster blocks can overtake it.
As discussed on the mailing list though, another option is to implement this as a separate project. It could be an external process that connects locally to bitcoind using the p2p protocol, and acts as a bridge to send blocks to an alternative network which is designed for fast propagation. Possibly the alternate network could use a different topology than a random mesh broadcast network, to speed things up even more.
@ashleyholman Someone currently only needs to send an inv matching a block to significantly stall propagation of a block. I've been banging on about this for ages, that a 2 minute timeout is way too long. @pgrigor Maximum block size is 1MB, so your 10GB block example is not really applicable to bitcoin.
I think this can be closed in light of Compact, xthin and suchlike.