I don't like this 75% full idea because the miners would virtually be REQUIRED to pad out blocks with trivial transactions if they don't have enough on their own. To not do so would leave hashing power idle.

A simpler solution would be to require that blocks are always 1 MB (or whatever) in size, and that they must be padded out with 0xDEADBEEF or whatever if the block can't be filled with transactions. This way all blocks will take the same amount of time to transmit, and there's no incentive not to include a transaction of any fee if what it's replacing would just be bad data.

I'm not saying I'm in favor of this proposal necessarily, but it works better.

I don't think there would be reason to, except in protest perhaps. 750Kb size block is 750Kb no matter what transactions make up the block; whos transactions go into a block wouldn't change propagation time. Miners would rather take other peoples' transactions if forced to take transactions at all. That way they get the fees.

I suppose that's true. Trying to fix that would basically put you in the third case - you need everyone to be working on the same transactions, which are the most significant (greatest transaction fees).

The entire purpose of mining is to enable global consensus.

It's not possible to ensure that all miners are operating on the same transaction set.

I think Andresen's O(1) block propagation proposal[0] requires exactly that. I'm not sure if he has worked out the details though.

[0]:https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2

Gavin relies on the transactions miners are working on being close to the same, but not exactly.

An easy way to understand the proposal is to think about it in terms of forward error correction.

The design is an improvement over the existing relay network to compactly encode transactions which are not yet fully relayed.

In practice the improvement is very small.

Information on the existing relay network is available here http://bitcoinrelaynetwork.org/