BIP: Increasing the Network Hashing Power by reducing block propagation time

[Sergio_Demian_Lerner]

Hi!
I'm sending this BIP for the community to discuss. I hope I get good feedback so I can proceed to implementing it, publish it in the BIPs wiki, and make it into the protocol.

BIP: <unassigned number>
Title: Increasing the Network Hashing Power by reducing block propagation time
Author: Sergio Demian Lerner
Status: Draft (incomplete)
Created 19-Feb-2013

Abstract

When a block get orphaned, it means that some of the available network hashing power has been wasted. This wasted hashing power does not benefit anyone in the Bitcoin network.
Orphan blocks are created mostly because of the network propagation time of new blocks. A 1 Mbyte block, sent over a 50 Kbytes/sec connection, takes 20 seconds. Assuming an average network graph diameter of 4 hops, it takes more than 1 minute for such a block to propagate throughout the network. Current block average size is 150 Kbytes, so this is not an issue today. As we expect the Bitcoin network to grow upto its maximum capacity, it's reasonable to expect a 13% waste in network hashing power in the near future because of orphaned blocks.

One of the ways to reduce block propagation time is by sending only the block header and transactions hashes in a first command payload ("header"), and then sending the remaining data (the transactions) in a second command payload ("block"). Since the coinbase transaction cannot be sent to peers without the block enclosure, the "header" command must also send this special transaction.

Specification

"header" command format is:

- Block header
- transactions hash list
- Coinbase transaction (maximum 10 Kbytes in size)

An average "header" command size (for an 1 Mbyte block, considering an average 400 bytes tx) is 80 kbytes, that takes 1.5 seconds per hop.

The "header" command should only be sent for newly created blocks and not for historical ones.

Semantics

Just after the first command "header" is received, a node should:

1. Verify that the block parent is known. If it's not, then discard the command.
2. Verify that the block is the last block of a chain (by the time field)
3. Compute the PoW and check if it's similar to the parent block PoW (+/- the possible expected variation). If it's not, then the command is ignored and the sender is blacklisted (DoS prevention).
4. Resent the "header" command to all peers.
5. Check if transaction hashes contained in the "header" command are already in the Tx pool.
6a. If all hashes are in the pool, reconstruct the block referred by the "header" and announce to peers.
6b. If very few are not in the pool, then the missing txs can be requested from peers.
6c. If almost all of them are not, ignore the "header" command and request the block from the peer having sent the "header" command by using "getblocks".
7. After the complete block X is reconstructed/received, proceed as normal (announce the block by "inv" to peers and forward when requested)

Miners should, after doing the previous steps 1-6, do:

1. Wait until the full block is reconstructed or received (while mining as normal without interruption)
2a. If the block X is received before our own block is solved, start over trying to solve a block whose parent is X.
2b. If a block is solved locally before the complete block X is reconstructed, discard X and try to win the block chain race against X.

This BIP does not require any soft-fork or hard-fork and is 100% backward compatible because it only involves changes in the p2p communication protocol. Peers that do not understand the "header" command will process the "block" command instead.

Reference Implementation

<not yet implemented>

Further related improvements

With a maximum 10 seconds propagation time, a 2 minute block confirmation interval should be stable, so it might be possible in the future (with the community acceptance) to reduce the block interval to 2 minutes or less with a hardfork (reducing also the fees and the block size proportionally to keep the same economic properties of Bitcoin intact and keep the contract with the community).

Who benefits from this BIP?

Miners: miners that implement this protocol (even if privately between them) get a 10% advantage over the remaining ones.

Users: They get 10% additional security for almost no extra cost (overhead should be negligible). Also if blocks are reconstructed using existent transaction in the pool, and not sent, bandwidth usage is reduced to a half.

This is a win-win situation.

Best regards,
 Sergio.

[gmaxwell]

I'm not sure where you're getting 10% from— but orphaning rates are not that high, even extrapolating on block size. Your analysis is also ignoring RTT, and changing the data size transmitted doesn't change the contribution to latency from the speed of light.

P2Pool already implements basically the protocol you're describing. Works reasonably well.  I don't know that it's especially interesting except for miners, however. Objectively, it doesn't seem that miners care that much since they haven't all switched to p2pool.

1. Verify that the block parent is known. If it's not, then discard the command.

The parent must be fetched or the network will not converge.

2. Verify that the block is the last block of a chain (by the time field)

The time does not tell you this, its not monotonic (and can't be monotonic without creating minor vulnerabilities.)

3. Compute the PoW and check if it's similar to the parent block PoW (+/- the possible expected variation). If it's not, then the command is ignored and the sender is blacklisted (DoS prevention).

The amount of work assigned to a header is a strict function of the prior chain. There is no permitted variation _at all_

An average "header" command size (for an 1 Mbyte block, considering an average 400 bytes tx) is 80 kbytes, that takes 1.5 seconds per hop.

If you're going to go crazy with compression you could actually transmit only half the transaction IDs (16 bytes rather than 32) and half that, I suppose.

[Peter Todd]

"header" command format is:

- Block header
- transactions hash list
- Coinbase transaction (maximum 10 Kbytes in size)

An average "header" command size (for an 1 Mbyte block, considering an average 400 bytes tx) is 80 kbytes, that takes 1.5 seconds per hop.

You have to be careful with transmitting transaction hash lists rather than the transactions themselves. While it definitely makes propagation faster in the average case, it also means that the worst-case, a block entirely composed of transactions that have not been previous broadcast on the network, is significantly worse. For the purpose of just reducing orphans, as is done by P2Pool as gmaxwell pointed out, the worst case isn't a problem, but don't make assumptions that have security implications. In particular by the mechanism I pointed out here you'll actually create a market for large hashpower miners where they can offer lower fees, paid for by the lower effective competition, provided the sender promises not to send the transaction to any other miner. I can't see such markets developing for 1MiB blocks, but they might develop for much larger block sizes.

P2Pool is interesting because miners on it have an incentive for any P2Pool block to be propagated to the network as a whole as fast as possible. In addition the perverse propagation incentives for shares within P2Pool are probably less of an issue given that the higher the hash power of P2Pool as a whole, the lower the variance for any individual miner - miners on P2Pool aren't playing a zero-sum game. P2Pool miners also have very little control over propagation because P2Pool shares are all identical.

[gmaxwell]

You have to be careful with transmitting transaction hash lists rather than the transactions themselves. While it definitely makes propagation faster in the average case, it also means that the worst-case, a block entirely composed of transactions that have not been previous broadcast on the network, is significantly worse.

The obvious thing to do in that case is to have the sender choose whatever representation it believes will be more efficient based on what it knows from the peer. (e.g. transactions it has previously offered the peer, or the peer has offered it).

In the p2pool case for p2pool shares p2pool miners are incentive to pre-forward what the transactions they are mining by the fact that their shares are punished (nodes attempt to build off their parent instead of the share). Though I don't think that really usefully applies to the Bitcoin network.

[Mike Hearn]

Writing BIPs like this is better done after the pullreq to go with it. Matt already prototyped this optimization some time ago but didn't finish it, there were some details that needed addressing to handle cases where the exchange stops half way through and so on.

When somebody has implemented a patch to send blocks as hashes and it's passed code review, that's the time to write a BIP. For instance, you talk about a headers command, but that already exists and is used for something else (a response to getheaders).

[gmaxwell]

Writing BIPs like this is better done after the pullreq to go with it.

Doesn't even have to be a pull request. It could also be an alternative protocol and a little gateway daemon. Both as a proof of concept and as a rapid deployment tool.  We really could use some diversity in the P2P transports. As noted by Sergio Demian Lerner and others there are a lot of harry DOS attack corner cases... we can't have really any diversity in the Blockchain stuff, but we absolutely can and should have more in the node to node transport.

[Peter Todd]

Two pull requests I would like to see, ones that make prototyping this stuff easier, would be "getrawblock/sendrawblock" RPC commands, and a "notifytransaction" mechanism.

The latter lets you find new incoming transactions that have been accepted to the mempool so you can inject them into your alternate distribution mechanism, later added to the client mempool with sendrawtransaction (a flag that disables re-broadcasting would be nice) The latter has already been attempted; I seem to remember there were some issues with locking that needed to be solved, but they looked tractable.

The former lets you do the same thing for entire blocks. (submitblock isn't quite what you want)

For instance a cool and potentially useful thing to do would be to operate a service that mulicasts the blockchain via Amazon's Simple Messaging Service. You'd sign up, and get a blockchain feed for your EC2 node without having to actually connect to anyone else. EC2 bandwidth is fairly expensive, so costs would be significantly less, and it could scale to absolutely enormous numbers of clients. Of course, you are trusting the service, but for some applications it's not a big deal.

Another cool thing to do would be to implement multicast broadcasting of the blockchain and transactions. While not commonly available, multicast is available on a few networks, so there will be some people who can make use of it. Equally you could start up a satellite downlink service or radio service.

The point is, actually implementing those ideas will be much easier with those two pull requests.

[Milkshake]

Hmm, I have to say I don't really like this proposal. Orphaned blocks are not really wasted - if orphan rates were reduced, then the difficulty will be higher because more blocks will be solved, and that really doesn't change anything.

[Mike Hearn]

Is anything new required to find transacations accepted into the mempool? Any accepted transaction is announced via an inv. You can just connect to a local node you run yourself and then getdata any tx than is announced.

Matt probably has his half-finished code around somewhere. It'd be great to have it integrated into the core P2P protocol, even though I agree that there are lots of other protocols that might be useful ways to move data around. The one I'd want to do as a highest priority is a Bluetooth protocol for phones to swap transactions with each other, so if one is offline the other can broadcast the transaction for it. Perhaps even tunneling a real P2P connection via BT. We prototyped a very basic example of that at a Berlin hackathon using insecure Bluetooth (so there's no pairing UI overhead), it worked but wasn't robust enough to integrate.

[TierNolan]

Hmm, I have to say I don't really like this proposal. Orphaned blocks are not really wasted - if orphan rates were reduced, then the difficulty will be higher because more blocks will be solved, and that really doesn't change anything.

This means that the total proof of work increases, so the network is more secure.

The advantage is that it balances nodes that have slower propagation times.

However, it still means that mining a block that has a "hidden" transaction still gives the miner an edge.  Under the current system, they have to provide the entire transaction to get the network hashing power to switch.

There needs to be some way for people to confirm that transactions are known.  Maybe the protocol rule could be changed to not propagate the message if any txs are unknown. This creates an incentive to only mine against well known transactions.

I wonder if this could be combined with Bloom filtering from BIP-37 for notifying spent transaction outputs (TXOs).

Basically, with bloom filtering, each "object" sets a number of bits (say 4) based on a hash function.  Each TXO matching an input into the block would set 4 bits in the filter output.

Unless all 4 bits matching a TXO are set, you are guaranteed that TXO is not in the block.  However, false positives can occur.

If a block has 1000 transactions and each with an average of 3 inputs, then that is 3000 TXOs that are invalidated.  This means that on average 12000 bits would be set in the filtered output.  The filter length could be decided based on the number of TXOs and bits.

If the filter was 24000 long (so double the expected number of bits) and used 4 bits, then the odds of a false positive are (0.5) ^ 4 = 0.0625.

24000 bits is around 3kB.

However, Bloom filter length scales directly with the number to TXOs.

[Edit]

It is probably best to have a Bloom filter per tx.  That way individual txs can be checked.  With 4 bytes per filter, you get around a 6.25% chance of a false positive.

This allows nodes to verify individual txs.

[Sergio_Demian_Lerner]

3. Compute the PoW and check if it's similar to the parent block PoW (+/- the possible expected variation). If it's not, then the command is ignored and the sender is blacklisted (DoS prevention).

The amount of work assigned to a header is a strict function of the prior chain. There is no permitted variation _at all_

Ok, it's not clear. What I meant is that the parent block may have required a difficulty adjustment that should be taken into account.

1. Verify that the block parent is known. If it's not, then discard the command.

The parent must be fetched or the network will not converge.

No, that's not correct.

If the parent is known, then we keep propagating the "header" command. If it's unknown, then we just wait for the full "block" command to arrive.

A single decision is made whenever a new block X is advertised with "inv":

If I have a previous "header" description of block X, then evaluate if it's better to download the block or to download the transactions separately.
If you decide the former, keep as normal.
If you decide the later, then ignore this "inv" command forever, and store a remainder in a memory table to reconstruct the block when all txs are received.

(If I have no "header" of X, keep as normal. )

This simplifies the implementation a lot. There is no race condition, no unstable state. Convergence is guaranteed.

If you're going to go crazy with compression you could actually transmit only half the transaction IDs (16 bytes rather than 32) and half that, I suppose.

Yes, I had noticed that too.

[Peter Todd]

There needs to be some way for people to confirm that transactions are known.  Maybe the protocol rule could be changed to not propagate the message if any txs are unknown. This creates an incentive to only mine against well known transactions.

You need to be really careful with anything that discourages blocks. Any time a given rule for discouraging blocks is adopted by a minority, rather than a majority, the majority of hashing power that is not following that particular rule has an incentive to deliberately produce blocks that will be discouraged by the minority.

What you are proposing is a relay rule, so the issue is really what % of hashing power doesn't get the block because of the rule, but regardless if only 25% of the hashing power ignores the violating block, the other 75% should include an unknown TX in every block they mine. They'll have 25% less competition - an obvious advantage.

[TierNolan]

What you are proposing is a relay rule, so the issue is really what % of hashing power doesn't get the block because of the rule, but regardless if only 25% of the hashing power ignores the violating block, the other 75% should include an unknown TX in every block they mine. They'll have 25% less competition - an obvious advantage.

It depends on how many miners use the rule.

If 75% won't include the certain txs, then mining that tx type is a bad plan.

Also, even if only 25% refused to mine the txs, there is still a public goods problem for the majority coalition.  It might be in the interests of the coalition to include at least 1 discouraged tx, but it is still in the interests of each individual member to make his blocks acceptable to as many miners as possible.

Refusing to mine against certain blocks also won't cause a fork and the rule could be "soft" and only apply to the last block in the chain.

[Sergio_Demian_Lerner]

You have to be careful with transmitting transaction hash lists rather than the transactions themselves. While it definitely makes propagation faster in the average case, it also means that the worst-case, a block entirely composed of transactions that have not been previous broadcast on the network, is significantly worse.

I don't think so. Since only the missing transactions are transmitted, the worst case is just like it is today. Maybe a little worse in the limit case that the decision to request individual txs instead of the full block was not a good one (many requested are made instead of a single request).

[Peter Todd]

You have to be careful with transmitting transaction hash lists rather than the transactions themselves. While it definitely makes propagation faster in the average case, it also means that the worst-case, a block entirely composed of transactions that have not been previous broadcast on the network, is significantly worse.

I don't think so. Since only the missing transactions are transmitted, the worst case is just like it is today. Maybe a little worse in the limit case that the decision to request individual txs instead of the full block was not a good one (many requested are made instead of a single request).

I don't mean worse than today, I mean worse than the average case.

Just implementing your idea is fine and probably should be done; the issue purely in making assumptions, particularly security assumptions, about how fast blocks will propagate based on it.

[Sergio_Demian_Lerner]

Writing BIPs like this is better done after the pullreq to go with it. Matt already prototyped this optimization some time ago but didn't finish it, there were some details that needed addressing to handle cases where the exchange stops half way through and so on.

My proposal is almost stateless. There are no unknown or intermediate states. A single decision is made when a "inv" arrives containing a block hash.

When somebody has implemented a patch to send blocks as hashes and it's passed code review, that's the time to write a BIP. For instance, you talk about a headers command, but that already exists and is used for something else (a response to getheaders).

Why write code if you know nobody will be using it? I prefer to know in advance.

The existent command is "headers" not "header" 

[Mike Hearn]

I don't remember what the issue was with Matts code, just that there were some details that needed to be resolved in the code. It's one thing to say, another thing to do. But sure, it'd be a good improvement. Then we can tick it off the scalability page (it's listed there as a future improvement).

I hope you wouldn't submit a patch that adds a command only one letter different from an existing command?

[Mike Hearn]

By the way, one possible elaboration of this idea is to have nodes send only the minimally required prefixes of the hashes in order to disambiguate transactions that it knows the peer has seen. For most blocks of current size you'd only need one or two bytes to distinguish the transaction that is included. It's probably not worth the additional complexity though.

[TierNolan]

A further improvement on this system would be to have miners pre-send their transaction lists.

When a miner decides on which transactions to include in a block.  He sends a "pending" message.  This is a list of hashes.

hash(coinbase)
hash(transaction1)
...
...
hash(last transaction)

When a client receives a pending message, it checks that it knows about all the transactions listed (except the coinbase).

It will then ask for any missing transactions in the list.  When it has all the transactions, it will then forward the pending message.

it won't forward it if it contains unknown transactions.

The lookup table would map the merkle root to the transaction list.

Then when the miner solves the block he can send just the header.

When another client receives the header, it can pull the transaction list from the lookup table, using the merkle root as key.  It will also have asked for all missing transactions in advance.

This creates the incentive to propagate transactions before including them in blocks.  Otherwise your pending messages won't be forwarded.

Not sure how best to do spam protection.  One way to do it would be to include a proof of work.  Effectively, prove that some hashing power was thrown away to produce the message.

[TierNolan]

Not sure how best to do spam protection.  One way to do it would be to include a proof of work.  Effectively, prove that some hashing power was thrown away to produce the message.

After thinking about it, the same effect can be achieved by sending one of the messages in the OP.  If the POW is > 1/16 of the required POW and the message is otherwise valid, forward it to any node that you haven't sent a message with the same merkle root to.  This reduces spam, but still allows miners to propagate their preview.

The threshold could be tweaked, but if 1/16 is used, then 15 times out of every 16 times a miner wins a block, the miner will be able to send a preview of the transaction hashes in advance of actually solving the block.  1 time in 16, the first solution that is less than 16 times the target will also be less than the target.

The preview is 32 bytes per transaction.  If the average actual bytes per transaction is 350 bytes, then that is only a 10X improvement.

The short hashes idea would improve things.  If there are 100 million transactions in the memory pool, then you only need on average 26 bits, so 4 bytes.  A miner could reduce the size of his pending block by using short hashes.  The rule could be to not propagate the messages, unless all hashes in the message hash to exactly one transaction contained in memory.   The sub-hashes would increase with the log of the number of entries in the transaction memory pool.