📅 Original date posted:2015-12-02
📝 Original message:My issue is more that its additional complexity and attack surface, and
for a very minor gain which should disappear with further optimization
elsewhere and less that we absolutely shouldn't add compression because
we're definitely gonna have issues.
On 12/02/15 20:16, Peter Tschipper via bitcoin-dev wrote:
> Building a compressor from scratch may yeild some better compression
> ratios, or not, but having trust and faith in whether it will stand up
> against attack vectors another matter. LZO has been around for 20 years
> with very few problems and no current issues. Maybe something better
> can be built, but when and how much testing will need to be done before
> it can be trusted? Right now there is something that provides a benefit
> and in the future if something better is found it's not that difficult
> to add it. We could easily support multiple compression libraries.
>
>
> On 02/12/2015 10:57 AM, Emin Gün Sirer wrote:
>> 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.
>>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
Matt Corallo [ARCHIVE] /
npub1e4…jxmcu
2023-06-07 17:45:24
in reply to nevent1q…rn6g
Author Public Key
npub1e46n428mcyfwznl7nlsf6d3s7rhlwm9x3cmkuqzt3emmdpadmkaqqjxmcuPublished at
2023-06-07 17:45:24Event JSON
{
"id": "660c06c1cb75e4cfd264f4ebce6e0d236d3daa690cfb6084d2473758430e30e5",
"pubkey": "cd753aa8fbc112e14ffe9fe09d3630f0eff76ca68e376e004b8e77b687adddba",
"created_at": 1686159924,
"kind": 1,
"tags": [
[
"e",
"66e2fed0b01e52e71a1dd6b42fe6a9fda1f0a599c3d79a1ed608f15fbb8c1ad3",
"",
"root"
],
[
"e",
"08bb08831a2071a4282aaf4c38c6038f4ee7df85815d27804a1ee0da728a4eec",
"",
"reply"
],
[
"p",
"ac0cba4c14f9ee9637c44e3773a1d205d62c63ca6095fc39aae39e6fffee6f48"
]
],
"content": "📅 Original date posted:2015-12-02\n📝 Original message:My issue is more that its additional complexity and attack surface, and \nfor a very minor gain which should disappear with further optimization \nelsewhere and less that we absolutely shouldn't add compression because \nwe're definitely gonna have issues.\n\nOn 12/02/15 20:16, Peter Tschipper via bitcoin-dev wrote:\n\u003e Building a compressor from scratch may yeild some better compression\n\u003e ratios, or not, but having trust and faith in whether it will stand up\n\u003e against attack vectors another matter. LZO has been around for 20 years\n\u003e with very few problems and no current issues. Maybe something better\n\u003e can be built, but when and how much testing will need to be done before\n\u003e it can be trusted? Right now there is something that provides a benefit\n\u003e and in the future if something better is found it's not that difficult\n\u003e to add it. We could easily support multiple compression libraries.\n\u003e\n\u003e\n\u003e On 02/12/2015 10:57 AM, Emin Gün Sirer wrote:\n\u003e\u003e Thanks Peter for the careful, quantitative work.\n\u003e\u003e\n\u003e\u003e I want to bring one additional issue to everyone's consideration,\n\u003e\u003e related to the choice of the Lempel-Ziv family of compressors.\n\u003e\u003e\n\u003e\u003e While I'm not familiar with every single compression engine tested,\n\u003e\u003e the Lempel-Ziv family of compressors are generally based on\n\u003e\u003e \"compression tables.\" Essentially, they assign a short unique number\n\u003e\u003e to every new subsequence they encounter, and when they re-encounter a\n\u003e\u003e sequence like \"ab\" in \"abcdfdcdabcdfabcdf\" they replace it with that\n\u003e\u003e short integer (say, in this case, 9-bit constant 256). So this example\n\u003e\u003e sequence may turn into \"abcdfd\u003c258 for cd\u003e\u003c256 for ab\u003e\u003c258 for\n\u003e\u003e cd\u003ef\u003c261 for abc\u003e\u003c259 for df\u003e\" which is slightly shorter than the\n\u003e\u003e original (I'm doing this off the top of my head so the counts may be\n\u003e\u003e off, but it's meant to be illustrative). Note that the sequence \"abc\"\n\u003e\u003e got added into the table only after it was encountered twice in the\n\u003e\u003e input.\n\u003e\u003e\n\u003e\u003e This is nice and generic and works well for English text where certain\n\u003e\u003e letter sequences (e.g. \"it\" \"th\" \"the\" \"this\" \"are\" \"there\" etc) are\n\u003e\u003e repeated often, but it is nowhere as compact as it could possibly be\n\u003e\u003e for mostly binary data -- there are opportunities for much better\n\u003e\u003e compression, made possible by the structured reuse of certain byte\n\u003e\u003e sequences in the Bitcoin wire protocol.\n\u003e\u003e\n\u003e\u003e On a Bitcoin wire connection, we might see several related\n\u003e\u003e transactions reorganizing cash in a set of addresses, and therefore,\n\u003e\u003e several reuses of a 20-byte address. Or we might see a 200-byte\n\u003e\u003e transaction get transmitted, followed by the same transaction,\n\u003e\u003e repeated in a block. Ideally, we'd learn the sequence that may be\n\u003e\u003e repeated later on, all at once (e.g. a Bitcoin address or a\n\u003e\u003e transaction), and replace it with a short number, referring back to\n\u003e\u003e the long sequence. In the example above, if we knew that \"abcdf\" was a\n\u003e\u003e UNIT that would likely be repeated, we would put it into the\n\u003e\u003e compression table as a whole, instead of relying on repetition to get\n\u003e\u003e it into the table one extra byte at a time. That may let us compress\n\u003e\u003e the original sequence down to \"abcdfd\u003c257 for cd\u003e\u003c256 for abcdf\u003e\u003c256\n\u003e\u003e for abcdf\u003e\" from the get go.\n\u003e\u003e\n\u003e\u003e Yet the LZ variants I know of will need to see a 200-byte sequence\n\u003e\u003e repeated **199 times** in order to develop a single, reusable,\n\u003e\u003e 200-byte long subsequence in the compression table.\n\u003e\u003e\n\u003e\u003e So, a Bitcoin-specific compressor can perhaps do significantly better,\n\u003e\u003e but is it a good idea? Let's argue both sides.\n\u003e\u003e\n\u003e\u003e Cons:\n\u003e\u003e\n\u003e\u003e On the one hand, Bitcoin-specific compressors will be closely tied to\n\u003e\u003e the contents of messages, which might make it difficult to change the\n\u003e\u003e wire format later on -- changes to the wire format may need\n\u003e\u003e corresponding changes to the compressor. If the compressor cannot be\n\u003e\u003e implemented cleanly, then the protocol-agnostic, off-the-shelf\n\u003e\u003e compressors have a maintainability edge, which comes at the expense of\n\u003e\u003e the compression ratio.\n\u003e\u003e\n\u003e\u003e Another argument is that compression algorithms of any kind should be\n\u003e\u003e tested thoroughly before inclusion, and brand new code may lack the\n\u003e\u003e maturity required. While this argument has some merit, all outputs are\n\u003e\u003e verified separately later on during processing, so\n\u003e\u003e compression/decompression errors can potentially be detected. If the\n\u003e\u003e compressor/decompressor can be structured in a way that isolates\n\u003e\u003e bitcoind from failure (e.g. as a separate process for starters), this\n\u003e\u003e concern can be remedied.\n\u003e\u003e\n\u003e\u003e Pros:\n\u003e\u003e\n\u003e\u003e The nature of LZ compressors leads me to believe that much higher\n\u003e\u003e compression ratios are possible by building a custom, Bitcoin-aware\n\u003e\u003e compressor. If I had to guess, I would venture that compression ratios\n\u003e\u003e of 2X or more are possible in some cases. In some sense, the \"O(1)\n\u003e\u003e block propagation\" idea that Gavin proposed a while ago can be seen as\n\u003e\u003e extreme example of a Bitcoin-specific compressor, albeit one that\n\u003e\u003e constrains the order of transactions in a block.\n\u003e\u003e\n\u003e\u003e Compression can buy us some additional throughput at zero cost, modulo\n\u003e\u003e code complexity.\n\u003e\u003e Given the amount of acrimonious debate over the block size we have all\n\u003e\u003e had to endure, it seems\n\u003e\u003e criminal to leave potentially free improvements on the table. Even if\n\u003e\u003e the resulting code is\n\u003e\u003e deemed too complex to include in the production client right now, it\n\u003e\u003e would be good to understand\n\u003e\u003e the potential for improvement.\n\u003e\u003e\n\u003e\u003e How to Do It\n\u003e\u003e\n\u003e\u003e If we want to compress Bitcoin, a programming challenge/contest would\n\u003e\u003e be one of the best ways to find the best possible, Bitcoin-specific\n\u003e\u003e compressor. This is the kind of self-contained exercise that bright\n\u003e\u003e young hackers love to tackle. It'd bring in new programmers into the\n\u003e\u003e ecosystem, and many of us would love to discover the limits of\n\u003e\u003e compressibility for Bitcoin bits on a wire. And the results would be\n\u003e\u003e interesting even if the final compression engine is not enabled by\n\u003e\u003e default, or not even merged.\n\u003e\u003e\n\u003e\n\u003e\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e",
"sig": "040154e6417d2e35c06f2ea9878074f7642a7813cc91611717bc578a1786d7239ce893b67fc6bda2efb3eea0539cdd50edfca28d288a0f48356831171237ffa9"
}