6 ms·

Paradoxical Compression with VDF

im3w1l 5y ago
Very neat, but my preference would be for it to very rarely expand the file, instead of very rarely rarely decompressing wrong. Then you could actually use it in practice. It would be pretty straightforward to change it as far as I can tell. Edit: If c+1 would wrap around, you could fallback on encoding as C0(x) || enc(0) || Mac(C0(x) || enc(0)).
- assbuttbuttass 5y ago
  Isn't it just a normal compression algorithm then?
  - im3w1l 5y ago
    No, a normal compression algorithm will often (as opposed to very rarely) expand the output when given a random input.
    - assbuttbuttass 5y ago
      I don't think you could expect this to do any better, though. Apparently this algorithm uses DEFLATE under the hood
  - goldenkey 5y ago
    Most compression algos have a simple flag to indicate an embedded file for cases where compression is not workable. All the same principles still apply, it's just that the compression algo is now meta of sorts.
- labawi 5y ago
  If the MAC and construction is solid, then wrong decompression is achievable, both theoretically, practically and by design, in many different ways except the one you mention - the rare collision. There likely won't be enough computation, ever, to trigger an accidental collision, even if was a galactic bitcoin equivalent. I'd only be worried about deliberate collisions, if the construction isn't sufficiently hard.
unnouinceput 5y ago
Quote: "A lossless compression algorithm that can actually reduce the size of at least one input file must also necessarily expand the size of at least one other possible input file. This is a direct application of the pigeonhole principle. A compression algorithm that claims to never increase the size of any input, while at the same time reducing the size of at least some inputs (it's not the trivial do-nothing compression that, by definition, preserves the length of the input), is called paradoxical compression." This paradoxical compression, as stated above is incomplete. You can achieve all input files to be compressed without having to expand any other file but you would expand time instead. Let me explain it: - Any set of data can be expressed using mathematical functions/algorithms that can be saved as one file, very small in data compared with original data, but to do so you'll need to invest a lot of time to find those functions/algorithms. One practical example would be a mission to Alpha Centauri which might want to have Earth's internet on board but no physical space for all that data. Let's say it takes 10 years to prepare the mission which in that case you'd also use this 10 years to compress, for argument sake, Google's big index, (or NSA Utah center if you like that one) and you'll have on board, on a single thumb stick, Internet version from 10 years before launch. Edit: Since some people have problems understanding this extreme compression, I am trying to clarify this further. This method is unique to that set of data. And it can be applied to only that data, only one time and that's it. Not a general set of algorithms so you can compress anything else. It will fail if not applied to that data. It is not a classic compression, it is more, if you like the term, a data generator. It will run a program that at the end of its run will generate that Internet version you started with 10 years ago. But to do that you'll need to research how to do that data generating, hence the extreme time it takes to achieve. In practice I'll envision a lot of people getting their slice of data and do one function. And the program will run those functions one after another, generating the data.
- anonymoushn 5y ago
  This is incorrect. If you would like to encode every string that's 10 gigabytes long to a string that's at least 1 byte shorter, then you don't have enough strings that are at least 1 byte shorter. There are fewer of them by a factor of about 256, and each one of them can decode to only one 10-gigabyte-long string. This is explained in the article.
willvarfar 5y ago
Off the top of my head, how about: Compression: gzip the file and tacking a crypto hash on the end. Discard if not shorter and store the original instead. Decompression: if has gzip header and the crypto hash at the end matches, unzip. Else return source as is. Have I just paradoxically compressed something?
- im3w1l 5y ago
  Well let's analyze it using the game from the paper. An attacker could do the following I believe: 1. Take something compressible like x0=AAAA... 2. Compress to get y0. 3. Take x1=y0. Compress to get y1. Now most likely y0=y1 meaning that decompressing y1 doesn't give x1, so you lost. But if y1 != y0, then 4. Take x{i+1} = y{i} and compress. Eventually there will be a collision. Preventing this is why the author's scheme is so complex.
- svara 5y ago
  That doesn't work, since there's no way to distinguish a compressed file from an uncompressed file that just happens to have the same contents. The hash doesn't help with that since that has collisions, it's the same pigeon hole issue. Most files in the space of all possible files will be essentially random and not compress, and adding a header will make them larger.
  - willvarfar 5y ago
    A compressed file is distinguished by being a valid gzip file with a valid hash. Such a file won’t compress a second time, so the length will remain unchanged. Then, decompressing twice will also generate the same output.
    - comex 5y ago
      Then what happens if the user starts with a file that happens to be a valid gzip file with a valid hash, compresses it twice, and decompresses it twice?
  - nuccy 5y ago
emilfihlman 5y ago
>Of course I am slightly cheating here, but the cheat is conceptually interesting (and fun). The idea is that paradoxical compression might have only a small density of problematic cases (inputs where the algorithm misbehaves, e.g. by expanding the length or not decompressing to the original input) and tools from the field of cryptography can be used to "push away" these cases so that they mathematically exist but nobody can find one with nonnegligible probability. In essence, this is transforming the question from "is it mathematically possible?" to "can I claim to do it and not being detected as a fraud?". This change of model makes paradoxical compression possible. Isn't this trivially wrong? If you have a bitstring s and you compress it to c, where the length of s is larger than length of c, compressing c again produces an issue. For example, if you compress a bitstring to just 1, how do you compress 1? To 0? And how do you compress 0 then? We can use this principle to find uncompressable bitstrings of any length anywhere for any algorithm. An idea pops into my head regarding this, though: in signal analysis there's a concept called noise shaping (which matches OPs ideas to a great degree), the idea is to push any noise out from some band and into another, it's super neat actually. Could this idea be expanded such that there is some singular monster string that expands to an absurd size, while others stay the same or are smaller? How about multiple but still small in density? My intuition sadly says no because of what I started this comment with. It's trivial to find strings that aren't compressible. Please let me know if and where my ideas on this go wrong!
madars 5y ago
Very nice! A tl;dr with spoilers -- for a typical compression algorithm C(x), applying it over and over again C(x), C(C(x)), C(C(C(x))), ... we would quickly arrive at an input for which the compressed length increases. Here the author proposes C(x) which either equals x (no compression), or encodes a normal compression (e.g. gzip) plus a MAC'd counter. Applying C(x) on the latter case again would simply increment the counter, so an adversary who only issues a bounded number of compression requests gets "stuck" on a chain that contains no contradiction. (The attacker could try to get to y = C(x) with a large counter value without compressor's help but that requires predicting the MAC which is infeasible.) The requirement for C and D to share a secret (here, a MAC key) can be removed by replacing MAC with a VDF proof that you spent O(counter) sequential time producing the compressed output, so a computationally bounded attacker can't overflow the counter (in practice, 128 bit counter requiring ~2^128 time) and disprove the paradox.
Arkanosis 5y ago
Another implementation of paradoxical compression, which, applied recursively also allows for infinite compression (ie. down to 0 byte) of any file: https://cs.fit.edu/~mmahoney/compression/barf.html https://cs.fit.edu/~mmahoney/compression/barf.html Of course, there's a catch.
- messe 5y ago
  Given that barf is already using the filename to indicate the compression, why not just move the final byte of the file into the filename instead? Something like, head -c -1 "$file" > "$file$(tail -c1 "$file")" EDIT: Obviously this has the corner case of null bytes
  - Arkanosis 5y ago
    That's actually pretty much what BARF is doing already; that's the catch.
    - messe 5y ago
      Haha, you're right. I should really read the source before speculating next time.
- chrisseaton 5y ago
  Is he just moving bytes from the file into the file name? He should count the increased size of the file name in the size of the compressed file otherwise he’s not counting all of the essential data you need for the decompression. You can decompress a gzip file without the file name (think about tar using a pipe.)
  - karmanyaahm 5y ago
    I'm pretty sure barf is a joke?
    - chrisseaton 5y ago
DemocracyFTW 5y ago
> Paradoxical compression is mathematically impossible. This repository contains a description of how to nonetheless achieve it, as well as a demo implementation. That's AWESOME show me! > Of course I am slightly cheating here mkay... :-(
slaymaker1907 5y ago
Paradoxical compression really isn't that bad of a problem in practice since you can just dedicate a single bit at the start of the data to indicate whether a file is compressed or not. This guarantees that a file is no more than 1 byte larger than it would be "uncompressed" (since in this case we just add on a byte to indicate we have not used our regular compression algorithm).
- anderskaseorg 5y ago
  It sounds like you misunderstand what “paridoxical compression” means. It does not refer to the problem where compression sometimes increases the size. A (purported) paridoxical compression algorithm is one that sometimes decreases and never increases the size.
  - IncRnd 5y ago
    This is not purely paradoxical compression, and cheats in this area. You might want to read the gh page that was linked as the article.
a1369209993 5y ago
> "infinite compression", in which it is claimed that every possible input can be reduced in size. It's computationally intractable (in fact, I'm pretty sure it's computational-intractability-complete), but if you live in a deterministic universe, it actually is possible to compress any input to at most a psuedo-constant number of bits. Just run every possible program in some Turing-complete language in parallel, and pick the shortest program that outputs your input. In the worst case, this will be a program that simulates the entire history of your universe up to the point where you were provided with the input and then reads out the simulated input. No matter how large the input is, this will only take (U+logXYZT) bits, where U is the number of bits to describe the laws of physics and initial state of the universe, and logXYZT is the number of bits to describe your position in space and time (among other things, it's logarithmic in the current age of the universe). (Caution: there may be elditch abominations in your universal prior[0], but as long as you stick to programs that output a fixed input and don't try to fiddle with them to decompress more data than you originally put in, they probably can't hurt you.) 0: https://ordinaryideas.wordpress.com/2016/11/30/what-does-the-universal-prior-actually-look-like/ https://ordinaryideas.wordpress.com/2016/11/30/what-does-the...
- AndrewDucker 5y ago
  That assumes an infinite univerise, which means your coordinates are also theoretically infinite, which means that they aren't a fixed number of bits.
  - deleted 5y ago
    [deleted]
  - a1369209993 5y ago
    Uh, no? It assumes a effectively finite universe (perhaps with something like the speed-of-light limit rather than strictly finite, but effectively). It can be infinite in time if you're okay with your compressed data potentially being somewhat larger the later you compress it, but that's not strictly necessary.

Very neat, but my preference would be for it to very rarely expand the file, instead of very rarely rarely decompressing wrong. Then you could actually use it in practice. It would be pretty straightforward to change it as far as I can tell. Edit: If c+1 would wrap around, you could fallback on encoding as C0(x) || enc(0) || Mac(C0(x) || enc(0)).

assbuttbuttass 5y ago
Isn't it just a normal compression algorithm then?
- im3w1l 5y ago
  No, a normal compression algorithm will often (as opposed to very rarely) expand the output when given a random input.
  - assbuttbuttass 5y ago
    I don't think you could expect this to do any better, though. Apparently this algorithm uses DEFLATE under the hood
- goldenkey 5y ago
  Most compression algos have a simple flag to indicate an embedded file for cases where compression is not workable. All the same principles still apply, it's just that the compression algo is now meta of sorts.
labawi 5y ago
If the MAC and construction is solid, then wrong decompression is achievable, both theoretically, practically and by design, in many different ways except the one you mention - the rare collision. There likely won't be enough computation, ever, to trigger an accidental collision, even if was a galactic bitcoin equivalent. I'd only be worried about deliberate collisions, if the construction isn't sufficiently hard.

unnouinceput 5y ago

Quote: "A lossless compression algorithm that can actually reduce the size of at least one input file must also necessarily expand the size of at least one other possible input file. This is a direct application of the pigeonhole principle. A compression algorithm that claims to never increase the size of any input, while at the same time reducing the size of at least some inputs (it's not the trivial do-nothing compression that, by definition, preserves the length of the input), is called paradoxical compression." This paradoxical compression, as stated above is incomplete. You can achieve all input files to be compressed without having to expand any other file but you would expand time instead. Let me explain it: - Any set of data can be expressed using mathematical functions/algorithms that can be saved as one file, very small in data compared with original data, but to do so you'll need to invest a lot of time to find those functions/algorithms. One practical example would be a mission to Alpha Centauri which might want to have Earth's internet on board but no physical space for all that data. Let's say it takes 10 years to prepare the mission which in that case you'd also use this 10 years to compress, for argument sake, Google's big index, (or NSA Utah center if you like that one) and you'll have on board, on a single thumb stick, Internet version from 10 years before launch. Edit: Since some people have problems understanding this extreme compression, I am trying to clarify this further. This method is unique to that set of data. And it can be applied to only that data, only one time and that's it. Not a general set of algorithms so you can compress anything else. It will fail if not applied to that data. It is not a classic compression, it is more, if you like the term, a data generator. It will run a program that at the end of its run will generate that Internet version you started with 10 years ago. But to do that you'll need to research how to do that data generating, hence the extreme time it takes to achieve. In practice I'll envision a lot of people getting their slice of data and do one function. And the program will run those functions one after another, generating the data.

anonymoushn 5y ago
This is incorrect. If you would like to encode every string that's 10 gigabytes long to a string that's at least 1 byte shorter, then you don't have enough strings that are at least 1 byte shorter. There are fewer of them by a factor of about 256, and each one of them can decode to only one 10-gigabyte-long string. This is explained in the article.

willvarfar 5y ago

Off the top of my head, how about: Compression: gzip the file and tacking a crypto hash on the end. Discard if not shorter and store the original instead. Decompression: if has gzip header and the crypto hash at the end matches, unzip. Else return source as is. Have I just paradoxically compressed something?

im3w1l 5y ago
Well let's analyze it using the game from the paper. An attacker could do the following I believe: 1. Take something compressible like x0=AAAA... 2. Compress to get y0. 3. Take x1=y0. Compress to get y1. Now most likely y0=y1 meaning that decompressing y1 doesn't give x1, so you lost. But if y1 != y0, then 4. Take x{i+1} = y{i} and compress. Eventually there will be a collision. Preventing this is why the author's scheme is so complex.
svara 5y ago
That doesn't work, since there's no way to distinguish a compressed file from an uncompressed file that just happens to have the same contents. The hash doesn't help with that since that has collisions, it's the same pigeon hole issue. Most files in the space of all possible files will be essentially random and not compress, and adding a header will make them larger.
- willvarfar 5y ago
  A compressed file is distinguished by being a valid gzip file with a valid hash. Such a file won’t compress a second time, so the length will remain unchanged. Then, decompressing twice will also generate the same output.
  - comex 5y ago
    Then what happens if the user starts with a file that happens to be a valid gzip file with a valid hash, compresses it twice, and decompresses it twice?
- nuccy 5y ago

emilfihlman 5y ago

>Of course I am slightly cheating here, but the cheat is conceptually interesting (and fun). The idea is that paradoxical compression might have only a small density of problematic cases (inputs where the algorithm misbehaves, e.g. by expanding the length or not decompressing to the original input) and tools from the field of cryptography can be used to "push away" these cases so that they mathematically exist but nobody can find one with nonnegligible probability. In essence, this is transforming the question from "is it mathematically possible?" to "can I claim to do it and not being detected as a fraud?". This change of model makes paradoxical compression possible. Isn't this trivially wrong? If you have a bitstring s and you compress it to c, where the length of s is larger than length of c, compressing c again produces an issue. For example, if you compress a bitstring to just 1, how do you compress 1? To 0? And how do you compress 0 then? We can use this principle to find uncompressable bitstrings of any length anywhere for any algorithm. An idea pops into my head regarding this, though: in signal analysis there's a concept called noise shaping (which matches OPs ideas to a great degree), the idea is to push any noise out from some band and into another, it's super neat actually. Could this idea be expanded such that there is some singular monster string that expands to an absurd size, while others stay the same or are smaller? How about multiple but still small in density? My intuition sadly says no because of what I started this comment with. It's trivial to find strings that aren't compressible. Please let me know if and where my ideas on this go wrong!

madars 5y ago

Very nice! A tl;dr with spoilers -- for a typical compression algorithm C(x), applying it over and over again C(x), C(C(x)), C(C(C(x))), ... we would quickly arrive at an input for which the compressed length increases. Here the author proposes C(x) which either equals x (no compression), or encodes a normal compression (e.g. gzip) plus a MAC'd counter. Applying C(x) on the latter case again would simply increment the counter, so an adversary who only issues a bounded number of compression requests gets "stuck" on a chain that contains no contradiction. (The attacker could try to get to y = C(x) with a large counter value without compressor's help but that requires predicting the MAC which is infeasible.) The requirement for C and D to share a secret (here, a MAC key) can be removed by replacing MAC with a VDF proof that you spent O(counter) sequential time producing the compressed output, so a computationally bounded attacker can't overflow the counter (in practice, 128 bit counter requiring ~2^128 time) and disprove the paradox.

Arkanosis 5y ago

Another implementation of paradoxical compression, which, applied recursively also allows for infinite compression (ie. down to 0 byte) of any file: https://cs.fit.edu/~mmahoney/compression/barf.html https://cs.fit.edu/~mmahoney/compression/barf.html Of course, there's a catch.

messe 5y ago
Given that barf is already using the filename to indicate the compression, why not just move the final byte of the file into the filename instead? Something like, head -c -1 "$file" > "$file$(tail -c1 "$file")" EDIT: Obviously this has the corner case of null bytes
- Arkanosis 5y ago
  That's actually pretty much what BARF is doing already; that's the catch.
  - messe 5y ago
    Haha, you're right. I should really read the source before speculating next time.
chrisseaton 5y ago
Is he just moving bytes from the file into the file name? He should count the increased size of the file name in the size of the compressed file otherwise he’s not counting all of the essential data you need for the decompression. You can decompress a gzip file without the file name (think about tar using a pipe.)
- karmanyaahm 5y ago
  I'm pretty sure barf is a joke?
  - chrisseaton 5y ago

DemocracyFTW 5y ago

> Paradoxical compression is mathematically impossible. This repository contains a description of how to nonetheless achieve it, as well as a demo implementation. That's AWESOME show me! > Of course I am slightly cheating here mkay... :-(

slaymaker1907 5y ago

Paradoxical compression really isn't that bad of a problem in practice since you can just dedicate a single bit at the start of the data to indicate whether a file is compressed or not. This guarantees that a file is no more than 1 byte larger than it would be "uncompressed" (since in this case we just add on a byte to indicate we have not used our regular compression algorithm).

anderskaseorg 5y ago
It sounds like you misunderstand what “paridoxical compression” means. It does not refer to the problem where compression sometimes increases the size. A (purported) paridoxical compression algorithm is one that sometimes decreases and never increases the size.
- IncRnd 5y ago
  This is not purely paradoxical compression, and cheats in this area. You might want to read the gh page that was linked as the article.

a1369209993 5y ago

> "infinite compression", in which it is claimed that every possible input can be reduced in size. It's computationally intractable (in fact, I'm pretty sure it's computational-intractability-complete), but if you live in a deterministic universe, it actually is possible to compress any input to at most a psuedo-constant number of bits. Just run every possible program in some Turing-complete language in parallel, and pick the shortest program that outputs your input. In the worst case, this will be a program that simulates the entire history of your universe up to the point where you were provided with the input and then reads out the simulated input. No matter how large the input is, this will only take (U+logXYZT) bits, where U is the number of bits to describe the laws of physics and initial state of the universe, and logXYZT is the number of bits to describe your position in space and time (among other things, it's logarithmic in the current age of the universe). (Caution: there may be elditch abominations in your universal prior[0], but as long as you stick to programs that output a fixed input and don't try to fiddle with them to decompress more data than you originally put in, they probably can't hurt you.) 0: https://ordinaryideas.wordpress.com/2016/11/30/what-does-the-universal-prior-actually-look-like/ https://ordinaryideas.wordpress.com/2016/11/30/what-does-the...

AndrewDucker 5y ago
That assumes an infinite univerise, which means your coordinates are also theoretically infinite, which means that they aren't a fixed number of bits.
- deleted 5y ago
  [deleted]
- a1369209993 5y ago
  Uh, no? It assumes a effectively finite universe (perhaps with something like the speed-of-light limit rather than strictly finite, but effectively). It can be infinite in time if you're okay with your compressed data potentially being somewhat larger the later you compress it, but that's not strictly necessary.