Thanks Peter for the careful, quantitative work.

I want to bring one additional issue to everyone's consideration, related to the choice of the Lempel-Ziv family of compressors. 

While I'm not familiar with every single compression engine tested, the Lempel-Ziv family of compressors are generally based on "compression tables." Essentially, they assign a short unique number to every new subsequence they encounter, and when they re-encounter a sequence like "ab" in "abcdfdcdabcdfabcdf" they replace it with that short integer (say, in this case, 9-bit constant 256). So this example sequence may turn into "abcdfd<258 for cd><256 for ab><258 for cd>f<261 for abc><259 for df>" which is slightly shorter than the original (I'm doing this off the top of my head so the counts may be off, but it's meant to be illustrative). Note that the sequence "abc" got added into the table only after it was encountered twice in the input. 

This is nice and generic and works well for English text where certain letter sequences (e.g. "it" "th" "the" "this" "are" "there" etc) are repeated often, but it is nowhere as compact as it could possibly be for mostly binary data -- there are opportunities for much better compression, made possible by the structured reuse of certain byte sequences in the Bitcoin wire protocol.

On a Bitcoin wire connection, we might see several related transactions reorganizing cash in a set of addresses, and therefore, several reuses of a 20-byte address. Or we might see a 200-byte transaction get transmitted, followed by the same transaction, repeated in a block. Ideally, we'd learn the sequence that may be repeated later on, all at once (e.g. a Bitcoin address or a transaction), and replace it with a short number, referring back to the long sequence. In the example above, if we knew that "abcdf" was a UNIT that would likely be repeated, we would put it into the compression table as a whole, instead of relying on repetition to get it into the table one extra byte at a time. That may let us compress the original sequence down to "abcdfd<257 for cd><256 for abcdf><256 for abcdf>" from the get go.

Yet the LZ variants I know of will need to see a 200-byte sequence repeated **199 times** in order to develop a single, reusable, 200-byte long subsequence in the compression table. 

So, a Bitcoin-specific compressor can perhaps do significantly better, but is it a good idea? Let's argue both sides.

Cons:

On the one hand, Bitcoin-specific compressors will be closely tied to the contents of messages, which might make it difficult to change the wire format later on -- changes to the wire format may need corresponding changes to the compressor.  If the compressor cannot be implemented cleanly, then the protocol-agnostic, off-the-shelf compressors have a maintainability edge, which comes at the expense of the compression ratio. 

Another argument is that compression algorithms of any kind should be tested thoroughly before inclusion, and brand new code may lack the maturity required. While this argument has some merit, all outputs are verified separately later on during processing, so compression/decompression errors can potentially be detected. If the compressor/decompressor can be structured in a way that isolates bitcoind from failure (e.g. as a separate process for starters), this concern can be remedied.

Pros:

The nature of LZ compressors leads me to believe that much higher compression ratios are possible by building a custom, Bitcoin-aware compressor. If I had to guess, I would venture that compression ratios of 2X or more are possible in some cases. In some sense, the "O(1) block propagation" idea that Gavin proposed a while ago can be seen as extreme example of a Bitcoin-specific compressor, albeit one that constrains the order of transactions in a block.

Compression can buy us some additional throughput at zero cost, modulo code complexity. 
Given the amount of acrimonious debate over the block size we have all had to endure, it seems 
criminal to leave potentially free improvements on the table. Even if the resulting code is
deemed too complex to include in the production client right now, it would be good to understand
the potential for improvement.

How to Do It

If we want to compress Bitcoin, a programming challenge/contest would be one of the best ways to find the best possible, Bitcoin-specific compressor. This is the kind of self-contained exercise that bright young hackers love to tackle. It'd bring in new programmers into the ecosystem, and many of us would love to discover the limits of compressibility for Bitcoin bits on a wire. And the results would be interesting even if the final compression engine is not enabled by default, or not even merged.