13 ms·

The $5000 Compression Challenge

323 points by vq 12y ago

jheriko 12y ago
yeah, he should have been smart enough to spot what was coming when he was asked about multiple files... or at least asked some more directed questions than 'what do you think you have that will solve this problem'
- gruntled 12y ago
  Or insisted it was a single file, tar files allowed.
  - jheriko 12y ago
    true. maybe he was smuggly thinking 'if he thinks using multiple files will help, he must be really dumb' :)
  - SeoxyS 12y ago
    Tar files have a decent amount of overhead. Source: I wrote a streaming untarring library in C for a streaming video product. You would definitely add WAY more than 1 byte of overhead per file, which is what is required for this trick to work.
    - gruntled 12y ago
      But it rules out other kinds of tricks like storing info in file names. If all the metadata is counted in the length of the tar file, these tricks don't stand a chance. There's way more than 1 byte of overhead per file in the file system and Mike needed a rule that counts all of them.
bdcs 12y ago
I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than setting up FTPs with personal IP addresses. The bet is promptly won by Patrick. Ah, how things have changed in 14 years
- qopp 12y ago
  They could have used an escrow service 15 years ago and the challenge terms could have been defined as a Python program since Python is 24 years old.
  - nadaviv 12y ago
    Getting someone with domain expertise on the matter to provide escrow is non-trivial. Escrow trust accounts are heavily regulated in most parts of the world, and require licensing, bonds and lawyers. I highly doubt they would find someone willing to go through all this. The cost for (legally) operating an escrow is probably higher than the entire bet... (he could also do this without licensing, and take on the legal risk, I guess. this might go under the radar for small things like that, but doesn't really work at scale.) Bitcoin improves on that by not requiring a trust account - their trusted third party would simply hold one key in a 2-of-3 multi-signature scheme, giving him the authority to resolve disputes and adjudicate between them, but without holding any funds under his full control. I find the legal implications of Bitcoin smart contracts very exciting - this significantly lowers the entry barriers for providing many kinds of financial services and opens up these markets for competition in a way that was simply impossible before. There's lots of room for innovation and disruption with that. Disclaimer: standard IANAL/TINLA apply, but I'm the founder at a startup that facilitates exactly that (https://www.bitrated.com/ https://www.bitrated.com/) and received extensive legal guidance on the matter.
    - leereeves 12y ago
      Bitcoin makes the technical process easier but doesn't help with the hard problem (as you said): finding a third party with domain expertise, whom they both trust, who is willing to adjudicate at very low cost. It sounds like your startup is trying to solve that and create a "Trust Marketplace". Godspeed. Establishing trust between strangers is a very hard problem. And while you may find a way to innovate around existing laws, new laws will be written.
      - nadaviv 12y ago
softbuilder 12y ago
>It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file. Even without a filesystem - just sending data over the wire - you have to be able to delimit files in some way, and there's going to be overhead associated with that. Another way to think of this is that any particular volume could be viewed as a single big file. How much space in that big file is he taking up?
- ThrustVectoring 12y ago
  That just invites more ways of implicitly sharing and hiding data. Like, have each of 230 hosts have one part of the file. Instructions for running the program are "Go to %part1url. Download the file as `foo.1`. Go to %part2url. Download the file as `foo.2`." and so forth. That's exploiting the fact that the instructions for running the program aren't counted as part of the program size.
im3w1l 12y ago
I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.
- ac29 12y ago
  From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
  - bagels 12y ago
    The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.
    - davmre 12y ago
      Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)
ac29 12y ago
See also section [9] of the comp.compression FAQ for more on the history of compression of random data: http://www.faqs.org/faqs/compression-faq/part1/ http://www.faqs.org/faqs/compression-faq/part1/
cpks 12y ago
Mike Goldman is now immortalized on the internet as someone who welches on bets...
- GhotiFish 12y ago
  It's not so clear cut, The filesystem really was acting as a "table" of index values on where to replace the characters that were removed.
hurin 12y ago
(2001) tag?
BenderV 12y ago
"I still think I compressed the data in the original file. It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file." I don't really agree with that, given the fact that he used the information about the size of the files.
nothrabannosir 12y ago
Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common sequences, split the file on those sequences recursively and then reassemble it by joining in reverse. Gzip, bzip2, &c, &c, it's all the same thing. Split the file by a common sequence and reassemble it by that. Patrick just created a customized compressor that went only 1 level deep. Normally you'd need a delimiter to separate those chunks, a delimiter that doesn't occur in the chunks e.g. through padding or escaping. That, in turn, increases the filesize, and now you're in trouble. What Patrick did was to use EOF as a new fresh "delimiter" that doesn't occur anywhere, and at a cost of zero bytes, no less. Cheating, or inventive.
- Dylan16807 12y ago
  I wonder how you got a downvote for that, it's quite accurate. A version of simplistic token replacement even has a wikipedia page http://en.wikipedia.org/wiki/Byte_pair_encoding http://en.wikipedia.org/wiki/Byte_pair_encoding
- barrkel 12y ago
  The EOF is not at a cost of zero bytes; it costs as much as storing the length of each constituent file. The extra space used is in the file system accounting.
  - Dylan16807 12y ago
    It's at a cost of 0 competition score bytes. Mike screwed up by allowing an alphabet of 257 symbols and then only counting 256 of them. Pretty much any compression or repacking algorithm could have been used at that point.
    - cnvogel 12y ago
      Dylan16807, that's a very concise way to put it, thanks for making that comment.
yk 12y ago
Previous discussions: https://news.ycombinator.com/item?id=5025211 https://news.ycombinator.com/item?id=5025211 https://news.ycombinator.com/item?id=4616704 https://news.ycombinator.com/item?id=4616704
kennywinker 12y ago
My money is on Hooli winning this one.
flockonus 12y ago
http://www.piedpiper.com/ http://www.piedpiper.com/
deleted 12y ago
[deleted]
- chambo622 12y ago
  Did you skip the part where Mike agreed to new terms that would allow multiple files?
kazinator 12y ago
Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes added together. Goldman should accept that he foolishly rushed into a careless amendment of his original challenge and pay the money. That said, it obviously is cheating to have the archive format or file system hide the representation of where the removed bytes are! If a single file is produced, it has to include a table of where to insert the bytes that were taken out. If multiple files are produced, the archive format or file system stores that information for you at considerable expense. If both people are wrong, the contest should be declared invalid and Goldman should return the $100. If only Goldman is wrong, he should pay $5000. Under no interpretation is Goldman strictly right and the contestant strictly wrong. So he is wrong to keep the $100 in any case.
- scintill76 12y ago
  > He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up. It casts doubt on whether he would pay if somebody won by the original rules with some luck. Maybe he has an implicit allowance, that merely two files can't "encode" a big enough advantage, but again, then it's his fault for not addressing that in the new rules.
  - thret 12y ago
    It's effectively a prop bet. If you're a world class table tennis champion and you bet someone you can beat them at table tennis on the proviso that they get to pick the bats, you can't really complain if you find out later that they have spent six months practicing with frying pans. You just have to pay up. If you don't see the loophole before you agree, you pay. Actually there's a great little bit about this in the movie Guys And Dolls (1955), and what to do if someone bets you that he can make a jack of spades squirt cider in your ear.
thomasahle 12y ago
AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original. So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win. The correct price for this game is probably closer to 200$.
- Dylan16807 12y ago
  The problem is that even the most trivial linux-compatible decompressor will add a few bytes, and there's almost no chance of saving that many bytes. But sure it wouldn't hurt to require it be 100+ bytes smaller.
TillE 12y ago
In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes. It's just a shame that the heat death of the universe will probably occur before your program finishes.
- piannucci 12y ago
  Sorry, but no. There are far more files with a given hash than just the one, if the file is longer than the hash. And having multiple hashes doesn't help until the hashes exceed the length of the file.
  - compbio 12y ago
    Chances of getting a collision is higher than getting a good solution, but having multiple hashes does help in increasing the chance at a good solution. With a hash 1 bit less than the length of the file, we put two pigeons inside one hole, and have a 50% chance at picking the right pigeon. The fewer/smaller hashes, the more we get "sorry, but no".
    - m_mueller 12y ago
      Also, I guess the hash algorithm could be specifically tested to work for this particular solution, couldn't it (although only after having spent the $100 of course)?. The problem I guess is to have a script that takes up less space than for the hash to still work without a collision for the particular data. Even with the smallest possible program or script, this probably isn't going to work then.
    - Someone 12y ago
      It's easier to just drop the final F bits from the N-bit input stream and, at decompression time, guess what they are than to go through this exercise of generating hashes that have N-F bits in total and hunt for bit streams having those hashes.
- dvirsky 12y ago
skatenerd 12y ago
Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge. Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
- mappu 12y ago
  How do you determine whether the file is kolmogorov-random? The only approach is to try a perfect kolmogorov compressor, which doesn't exist (well, excepting brute force over the space of possible turing machines).
  - skatenerd 12y ago
    I bet that with longer strings, the odds of drawing a kolmogorov-random string are high enough that he's guaranteed to make money from his Challenge
- darkmighty 12y ago
  Read the article, this is a circumvention rather than compression, although if you define Komogorov-randomness appropriately, such a definition would work. But modern OS's have non-determinism available: take a Kolmogorov-random file of size n which can be generated by a program n+1. Then, replace a certain part of the program (totaling k bits, and delete 2 extra bits) with a function drawing k+2 random bits from the OS. Then with probability 2^-(k+2), you win.
hyperpallium 12y ago
The file ordering contains information (done with filenames, comp.$i, but could use other file metadata). Mike can escape his unthinking agreement to multiple files by the rules forbidding information in filenames.
compbio 12y ago
A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914 http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair. A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ http://prize.hutter1.net/ up to 50.000$ prize money, but severe restrictions on memory and running time. You can not beat Goldman's troll-ish challenge (certainly if the rules are retro-actively clarified in favor of the organizer). You could however try to put the challenge in limbo by creating a decompressor which bruteforces a solution, 'till some hashes match or the final heat death of the universe or the halting problem is solved, whichever comes first. Goldman will not be able to ever verify your solution, and when he does (theoretically it is not impossible), it means you win. Or, instead of above Schrödinger's Compressor you can send a good random number generator back as your solution. If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Why does he want to do a diff between two random files, is he perhaps looking for order where there is none? But that's the same foolishness he accuses his participants of.
- function_seven 12y ago
  > If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Maybe because the file was XOR'd with a secret one time pad?
  - compbio 12y ago
    Blast! That would require our solution to break all known encryption. Then it would be easier to just target Goldman's setup. A file with output from AES-256("sekrit") would not be random to Goldman. It would appear random to us, until we crack it with a plausible password. Key to randomness is unpredictability. The moment Goldman saves some atmospheric noise on his computer and makes a short pointer to it on his filesystem, is the moment this file loses its claimed unpredictability. Goldman knows this file deeply: He himself has compressed meaningless random data into predictable information that has meaning and purpose, a feat he set out to prove impossible. By simply entering the challenge with real meaningless randomness you make Goldman solve it for you.
snowwrestler 12y ago
The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't understand their area of expertise as well as they do. They get angry and offended at naive questions, and seek to punish the idiots. This is a great way to take an interesting subject and ruin it for everyone. One of the best aspects of the HN culture is that experts here tend to incline more toward teaching and less toward chastising. It's a nice change from Usenet.
- x0x0 12y ago
  Why do you think that rather than Mike is genuinely interested in novel compression methodologies, and willing to pay some money to make interested people attempt to discover them?
  - zik 12y ago
    Because information theory says it's impossible.
  - DanBC 12y ago
    There was a problem in comp.compression (or whatever Usenet newsgroup) of arrogant challengers announcing their brilliant new compression algorithm. This bet is a way of demonstrating at least the pigeon hole problem to other people.
  - seanc722 12y ago
    I would say the update he posted to the news group rules this out.
  - pgaddict 12y ago
    Because that's pretty much what he says in his post to comp.compression, where he announces that someone accepted the challenge. Let me quote: > Before naming the individual and giving additional details of our > correspondence, I would like to give him some time to analyze the > data I will be sending him. It would be very easy to point out to > him the impossibility of his task, but far more interesting to see > how long he will struggle with the problem before realizing it for > himself. > > I am supposing that one of his fellow co-workers probably referred > him to my challenge, as I cannot fathom that someone would read the > comp.compression faq first and then want to participate after > understanding the futility of the effort. On the other hand, some > people just don't understand information theory too well. > > I'll try to give him a complete explanation of his error after a > week or so, I guess. :) So Mike is just smug about how clever he is, how stupid the other person is, not even suspecting there might be a loophole in the challenge. I see no sign of interest in learning what the other person is up to, or even admitting that there might be something to learn.
phkahler 12y ago
Here's a more risky solution. Chose an arbitrary large file size. Have the decompressor search the local file system for a file of that specific size and make a copy of it as output. This presumes he's going to have the uncompressed file on the system to verify the output of the decompressor. That may turn out to be a false assumption, but what if...
- log_n 12y ago
  Or just have the decompressor log onto a server and download the original file. Only risk then is internet connection.
mrfusion 12y ago
I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.
- robzyb 12y ago
  GZIP would not apply very much compression, at all, to purely random data. So the compressed data + gzip decompressor would very likely be a greater size than the original data.
- btown 12y ago
  If you're given perfectly random data, gzipping it will (almost) never reduce the size so much that you could fit the gunzip binary in the reduced space. In the extremely rare occurrence that the generated random data has, say, a repeated string longer than the gunzip binary, the challenger could be on guard for that and just regenerate random data until that's not the case. To be more formal, the challenger is finding what he believes to be a string that is Kolmogorov-random, and betting (quite safely) that the challenged party can't prove him wrong. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
  - function_seven 12y ago
    > that you could fit the gunzip binary in the reduced space What's funny is that Patrick (the challenger) asked if a bash script consisting solely of a call to gunzip would suffice as the decompressor. In other words, all he had to do was compress the file by more than the amount of the script. Mike allowed it, knowing that even a tiny "decompressor" that really just called out to the real thing, would still be larger than the compression achievable on a well-crafted random blob.
Intermernet 12y ago
Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net? There are grey areas here. Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size? I know this was written 14 years ago, but we had the net then, and shared libraries aren't exactly a new thing. Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way? I'd say that using the filesystem to "hide" bytes is the least of the possible loop-holes with this challenge, if you were being pedantic about the rules.
- function_seven 12y ago
  > Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net? The judge can disconnect his computer from the Internet, attempt to run the submitted decompressor and file, and declare failure when it doesn't work. Nothing in the challenge guarantees Internet connectivity on the machine. > Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size? Nope. In the email exchange, Mike said that just a script that called out to gunzip would be fine, and that he'd only count the size of the script as the decompressor size > Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way? Yup, as long as the dependency is already on the machine I suppose. That's what's so enlightening about this challenge. Even a tiny, tiny script that calls to other programs still can't compress a "pathologically" random file by more than a few bytes.
  - Intermernet 12y ago
    >Yup, as long as the dependency is already on the machine I suppose. That's exactly what I was getting at. If gzip was allowed, then any common decompression utility should be allowed. If that's the case, and said utility relies on an external library, should that library be included as part of the size of the decompression utility? It's arguable that the "fabric" over which the data is delivered shouldn't matter. If shouldn't really matter if the linked library comes from the same SSD as the executable, or from a server on the other side of the world. We currently define "the machine" as the internals of a box. Would this count if you were running the executable from a removable drive? If not, why does "network storage" trigger the disqualification, and not "USB storage"? I understand the original premise of Mike's challenge, but considering a loophole is being discussed here, I'd like to know where people see that the boundaries of similar loopholes lie.
thezilch 12y ago
By Patricks thinking, I could just store the last N bytes of each file in the filename! Clearly he can see this isn't compression?
dvirsky 12y ago
You should re-read this and imagine Goldman's messages being read in Vizzini's voice.
progrn 12y ago
Can someone explain why this is not possible? I understand why sending a decompressor beforehand is not possible for all inputs. I don't understand this formulation of the problem, where it only needs to work for one input that you get before you need to create the decompressor.
- raverbashing 12y ago
  Some simple explanation Compression exploits redundancy in a data stream (basically). You basically get "all symbols" (and how you define this varies according to your compression method: you could do all letters in the case of text, or even text snippets that repeat, etc) and reassemble them in a way that the ones that repeat the most take less space (and you also need to start from a basic dictionary known by all uncompressors or ship it with your compressed file) One simple analogy is writing with abbreviations, but if you write e.g. the reader has to know what "e.g." means or you have to put in the beginning "e.g. = example" (and this also takes space) Now, a randomly generated file ideally has all symbols repeating with the same frequency, (we say all symbols have the same entropy - I'm not sure about this exact wording), hence you can't take a symbol that repeats more or less and make it take less space in your compressed file
  - s369610 12y ago
    what if instead of using your own dictionary, you use an index into an existing dictionary? such as an index into a subsequence of pi. Couldn't you then find a sequence of bytes in the file in which the index into pi takes less bytes and then replace them all with the index? If you couldn't find any in pi use e or another such number? What am I missing
    - raverbashing 12y ago
      In this case your dictionary either doesn't have everything or to adequately point to it you take as much space as not using it. While Pi has all pairs of 2 digits, your index would take more space than storing the pairs itself (because you might need to go beyond position 99) For one situation you might "get lucky" and find a coincidence, but this won't scale generically
paulsecwhatt 12y ago
I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it. If you then complain that THAT is cheating, you're a pedantic idiot - one of those annoying kids in middle school who loses a bet and then tries every possible way to weasel himself out. To add fuel to the fire, his obnoxious replies such as "I tried running the first two files and it didn't work", make my blood boil, as it's a clear attempt to try and belittle the contestant.
- sjwright 12y ago
  > If you design an impossible game, the only possible thing for anyone to do is to break it. Which is the Kobayashi Maru in a nutshell. In that fictional case, Kirk was disqualified but also received a commendation.
  - qbrass 12y ago
    https://en.wikipedia.org/wiki/The_Kobayashi_Maru_%28Star_Trek_novel%29 https://en.wikipedia.org/wiki/The_Kobayashi_Maru_%28Star_Tre... I don't know if the novel is canon, but it ought to be. Kirk beat it by cheating, Scotty beat it legitimately, then proved that what he did only worked in the simulation.
- emn13 12y ago
  Mike's responses could have been better, but in the correspondence I see no guarantee that the files will be presented in order, or with the same file names, or in an otherwise empty directory. That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising that this limitation isn't mentioned), and the subsequent alteration to the rules was initiated by Patrick, who intentionally tried to inject a loophole, but failed to specify the need to keep the files in order. His rules; he should have to live by them. Also, I suspect that if Patrick had mentioned the need to leave the file names unaltered or in order, there's a good chance that Mike would have smelled a rat. After all, it is precisely in that side-channel where the information gain is to be had.
prettyrandom100 12y ago
I didn't see anything that mentions run-time in the challenge. I think a good compression challenge should mention about run-time. Theoretically, it would be possible to hash parts of the file and then brute force the hash in the decompressor. This would take a lot of time but would work.
- cplease 12y ago
  No it wouldn't work! Hashes do not defy information theory, they lose information. Such brute forcing would only find hash collisions and "decompress" to a different text than the original.
- jholman 12y ago
  I endorse the creativity in your approach, but you are mistaken; this will not (deterministically) work. Given a hash function that hashes an input I (of size N, comprised of N arbitrary bytes) to a digest D (of size M), then assuming that M is a fixed value, then for each output digest D_0, there will be 2^(N-M) values that hash to that D_0. How will you tell which is the "right" one?
- zaroth 12y ago
  There are an unbounded number of inputs which may result in the same hash digest. Saving just the hashes (digests) and then finding the preimages would not guarantee the same result. You would find collisions but not necessarily the right collision. In fact, as the data being hashed increases in size, the amount of data required to identify which preimage is the correct preimage must be greater than or equal to the difference in size between the digest and the preimage. For example, let's say you are using a perfect hash function, with a 64-bit digest. If you feed data into the hash function in 64 bits chucks, and then try to brute-force the results, each preimage you find will be the right one, and you can assemble the original file, but you have exactly as many bytes as when you started! Now lets say you feed in 65 bits to the perfect hash function, saving 1/65 space in the resulting list of digests. But unfortunately, there are two 65-bit preimages which will result in each of your stored digests, so you need a bit to decide which one is correct. And so on...
- brongondwana 12y ago
gayprogrammer 12y ago
If you printed the files each on a sheet of paper, it would 'use more trees' than printing the original file (paper being the 'filesystem'). I agree that it shouldn't matter what the filesystem does to store it, if the rules state that file size is determined by a specific command to count all the inodes, then he lost. If the command is 'du' or 'wc', then he won.
fishnchips 12y ago
I am actually surprised that Patrick did not compress the original data to 0 bytes by keeping all the data in filenames. That would be the ultimate troll ;)
- xorcist 12y ago
  I disagree. You could legitimately say he just stored the data in the metadata fields. But files have a size, even as a stream, completely regardless of metadata. I think this is a more clever hack.
  - fishnchips 12y ago
    Maybe, I don't know. One way or another you're storing some data (chunk ordering in Patrick's case, all data in my case) in file names.
yummybear 12y ago
I remember a "fractal compression" hoax one time. It would compress a file ridiculously (like 1 1mb file down to 100 bytes), and decompress it flawlessly. Of course it just moved the file to some other place on the harddrive and created a "compressed file" full of junk and restored the file on decompress. Good one...
Bentota 12y ago
Why wouldn't binary run length encoding work here? E.g. "compressing" 11100110 to 30020 for example?
- tehwalrus 12y ago
  How are you storing that 3 in 1s and 0s? ;)
- DanBC 12y ago
  Compression relies on entropy. There's not enough entropy in the random file your your run-length encoding to work. I think the data is available so you can always try to beat the bet.
  - et1337 12y ago
    I may be completely misinformed, but I think you meant to say there's too much entropy. A binary string of all ones followed by all zeroes has very low entropy, while a purely random binary string has high entropy. (I think. I'm skimming the Wikipedia article on entropy now)
    - DanBC 12y ago
      Yes, sorry!!
logicallee 12y ago
In terms of behavior, we know Mike acted in bad faith: before he saw the approach, he had agreed that the challenger could use multiple files. But once the challenger had posted them, he proceeded to download only a single file to verify its functionality, not touching the others. It shows bad faith on the part of Mike when he chose to ignore the other files. By the way in a theoretical sense Mike lost when he said he would allow multiple files and count their sizes: this is because [] is not the same as [[][][]], but consists of 3 empty sets. You can theoretically encode a file into just a bunch of 0-byte files, without using the order of the files or their names. He shouldn't have agreed to count only their sizes. For the theoretical encoding into 0-sized files, you can simply interpret the input file as a binary number, and then create that many empty files. This is not a practical solution of course - you can only compress two bytes down to 0-byte files this way, as 2^16-1 is already up to 65535 empty files. For three bytes it's up to 16,777,215 files. If you wanted to store 9 bytes in unary as the number of empty files, you would need 2^72-1 = 4.7 sextillion (million quadrillion) files. Obviously that is not actually possible. But even 9 bytes is hardly enough to interpret the files as binary again. (Unless you can somehow get Mike to agree to the invocation - since the decompression program itself doesn't need to store any information and theoretically could be 0, 1 or 2 bytes.) But theoretically you don't need anything other than what Mike foolishly agreed to: allowing multiple output files counting their sizes. 2. There is also another theoretical way to make money off of Mike, but it is not practical. (It doesn't work.) If we were not limited to bytes but could use bits, you could shave up to 5 bits off of every input file, if you figured out a way to decompress it by always prepending the bits 00000. (Theoretically there is only 1 pigeonhole to decompression, so you do not need to store any information in the decompression algorithm and it has no minimum size). If Mike is using a random source for the files, this would result in a correct decompression in 1/32 of cases. But Mike is giving 49:1 odds (risk $100, get $5000), which is better than 31:1. So you could simply repeat the game with Mike thousands of times, always using the same decompression algorithm, until you have all of Mike's money. This works better if Mike is a computer, of course. And it doesn't work at all on any actual systems, as a nibble is less than a byte and would not count as savings even if you could encode the decompression algorithm into a 0-byte (or up to 3 bit) invocation.
hackhat 12y ago
He also doesn't state that the output should be right at first decompression try. By using this you could encode multiple bits and then generate various wrong archives, knowing that after 1000000 tries he would get a correct decompressed file.
brownbat 12y ago
If you want to hear some stories from the master of proposition bets, there's an old autobiographical article in SI by Titanic Thompson: http://www.si.com/vault/1972/10/09/618832/soundings-from-titanic http://www.si.com/vault/1972/10/09/618832/soundings-from-tit... (The risk being that half of it is made up, but he definitely had a reputation for this sort of thing.) "You might wonder why, if I was the best golfer in the world, like I say I was, I didn't turn pro and win all the championships? Well, you were liable to win a golf bag if you won a tournament in those days. A top pro wouldn't win as much in a year as I would in a week as a hustler. People would get to know a pro, and I wanted to keep my skill a secret as far as possible. I didn't care about championships. I wanted the cash."

323 points by vq 12y ago

yeah, he should have been smart enough to spot what was coming when he was asked about multiple files... or at least asked some more directed questions than 'what do you think you have that will solve this problem'

gruntled 12y ago
Or insisted it was a single file, tar files allowed.
- jheriko 12y ago
  true. maybe he was smuggly thinking 'if he thinks using multiple files will help, he must be really dumb' :)
- SeoxyS 12y ago
  Tar files have a decent amount of overhead. Source: I wrote a streaming untarring library in C for a streaming video product. You would definitely add WAY more than 1 byte of overhead per file, which is what is required for this trick to work.
  - gruntled 12y ago
    But it rules out other kinds of tricks like storing info in file names. If all the metadata is counted in the length of the tar file, these tricks don't stand a chance. There's way more than 1 byte of overhead per file in the file system and Mike needed a rule that counts all of them.

bdcs 12y ago

I think Patrick sums it up quite well. Perhaps the interesting thing is imagining how this would go down 15 years later in 2015: Patrick asks if the bet is available; it is. They enter into a 2-of-3 bitcoin transaction with 3rd-party escrow. Patrick and Mike sign the terms (probably written in pseudocode or python) using their sending bitcoin addresses (or GPG keys). Filesharing is an order-of-magnitude easier than setting up FTPs with personal IP addresses. The bet is promptly won by Patrick. Ah, how things have changed in 14 years

qopp 12y ago
They could have used an escrow service 15 years ago and the challenge terms could have been defined as a Python program since Python is 24 years old.
- nadaviv 12y ago
  Getting someone with domain expertise on the matter to provide escrow is non-trivial. Escrow trust accounts are heavily regulated in most parts of the world, and require licensing, bonds and lawyers. I highly doubt they would find someone willing to go through all this. The cost for (legally) operating an escrow is probably higher than the entire bet... (he could also do this without licensing, and take on the legal risk, I guess. this might go under the radar for small things like that, but doesn't really work at scale.) Bitcoin improves on that by not requiring a trust account - their trusted third party would simply hold one key in a 2-of-3 multi-signature scheme, giving him the authority to resolve disputes and adjudicate between them, but without holding any funds under his full control. I find the legal implications of Bitcoin smart contracts very exciting - this significantly lowers the entry barriers for providing many kinds of financial services and opens up these markets for competition in a way that was simply impossible before. There's lots of room for innovation and disruption with that. Disclaimer: standard IANAL/TINLA apply, but I'm the founder at a startup that facilitates exactly that (https://www.bitrated.com/ https://www.bitrated.com/) and received extensive legal guidance on the matter.
  - leereeves 12y ago
    Bitcoin makes the technical process easier but doesn't help with the hard problem (as you said): finding a third party with domain expertise, whom they both trust, who is willing to adjudicate at very low cost. It sounds like your startup is trying to solve that and create a "Trust Marketplace". Godspeed. Establishing trust between strangers is a very hard problem. And while you may find a way to innovate around existing laws, new laws will be written.
    - nadaviv 12y ago

softbuilder 12y ago

>It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file. Even without a filesystem - just sending data over the wire - you have to be able to delimit files in some way, and there's going to be overhead associated with that. Another way to think of this is that any particular volume could be viewed as a single big file. How much space in that big file is he taking up?

ThrustVectoring 12y ago
That just invites more ways of implicitly sharing and hiding data. Like, have each of 230 hosts have one part of the file. Instructions for running the program are "Go to %part1url. Download the file as `foo.1`. Go to %part2url. Download the file as `foo.2`." and so forth. That's exploiting the fact that the instructions for running the program aren't counted as part of the program size.

im3w1l 12y ago

I don't think it is 100% foolproof, even if no filesystem trickery is used. The random number generator used is likely not perfect and so the data should be compressible. I mean it would probably be quite difficult, but maybe possible.

ac29 12y ago
From the link I posted in my other comment, a thought experiment... Yes, some random files can be compressed by a given program, but not all random files. The proof is fairly simple, once you think it through: Theorem: No program can compress without loss all files of size >= N bits, for any given integer N >= 0. Proof: Assume that the program can compress without loss all files of size >= N bits. Compress with this program all the 2^N files which have exactly N bits. All compressed files have at most N-1 bits, so there are at most (2^N)-1 different compressed files [2^(N-1) files of size N-1, 2^(N-2) of size N-2, and so on, down to 1 file of size 0]. So at least two different input files must compress to the same output file. Hence the compression program cannot be lossless.
- bagels 12y ago
  The challenge was to provide a decompressor for one file, not any or all files. This proof of the impossibility of a compressor that can compress any file has been known for decades.
  - davmre 12y ago
    Yes, but you don't get to see the file until after you've sent in the $100. So in order for this to be a good bet, you'd need a method that can compress a random file with at least 2% ($100/5000) probability. That's still quite difficult. An example of an algorithm that does compress 2% (actually 1/32 ~= 3%) of random files: just drop the initial five bits of the file, and replace them with zeros upon decompression. There's a 1/32 chance they were all zeros, in which case you win. The difficult part is encoding the decompression procedure into a program of less than five bits. :-)

ac29 12y ago

See also section [9] of the comp.compression FAQ for more on the history of compression of random data: http://www.faqs.org/faqs/compression-faq/part1/ http://www.faqs.org/faqs/compression-faq/part1/

cpks 12y ago

Mike Goldman is now immortalized on the internet as someone who welches on bets...

GhotiFish 12y ago
It's not so clear cut, The filesystem really was acting as a "table" of index values on where to replace the characters that were removed.

hurin 12y ago

(2001) tag?

BenderV 12y ago

"I still think I compressed the data in the original file. It's not my fault that a file system uses up more space storing the same amount of data in two files rather than a single file." I don't really agree with that, given the fact that he used the information about the size of the files.

nothrabannosir 12y ago

Quote from Mike: > Rather, you simply split the file into 218 parts ending with the > character "5" and then stripped that final character from each part. Thus the > "decompressor" is nothing more than a reassembler, > concatenating the parts and reappending > the character "5" after each. Well, that's exactly the definition of lossless compression. Look at e.g. how js crunch works: you create a dictionary of common sequences, split the file on those sequences recursively and then reassemble it by joining in reverse. Gzip, bzip2, &c, &c, it's all the same thing. Split the file by a common sequence and reassemble it by that. Patrick just created a customized compressor that went only 1 level deep. Normally you'd need a delimiter to separate those chunks, a delimiter that doesn't occur in the chunks e.g. through padding or escaping. That, in turn, increases the filesize, and now you're in trouble. What Patrick did was to use EOF as a new fresh "delimiter" that doesn't occur anywhere, and at a cost of zero bytes, no less. Cheating, or inventive.

Dylan16807 12y ago
I wonder how you got a downvote for that, it's quite accurate. A version of simplistic token replacement even has a wikipedia page http://en.wikipedia.org/wiki/Byte_pair_encoding http://en.wikipedia.org/wiki/Byte_pair_encoding
barrkel 12y ago
The EOF is not at a cost of zero bytes; it costs as much as storing the length of each constituent file. The extra space used is in the file system accounting.
- Dylan16807 12y ago
  It's at a cost of 0 competition score bytes. Mike screwed up by allowing an alphabet of 257 symbols and then only counting 256 of them. Pretty much any compression or repacking algorithm could have been used at that point.
  - cnvogel 12y ago
    Dylan16807, that's a very concise way to put it, thanks for making that comment.

yk 12y ago

Previous discussions: https://news.ycombinator.com/item?id=5025211 https://news.ycombinator.com/item?id=5025211 https://news.ycombinator.com/item?id=4616704 https://news.ycombinator.com/item?id=4616704

kennywinker 12y ago

My money is on Hooli winning this one.

flockonus 12y ago

http://www.piedpiper.com/ http://www.piedpiper.com/

deleted 12y ago

[deleted]

chambo622 12y ago
Did you skip the part where Mike agreed to new terms that would allow multiple files?

kazinator 12y ago

Mike Goldman originally wrote the challenge such that it calls for one file and one decompressor. However, when subsequently asked whether there can be multiple files, he agreed; thereby he was arguably duped. He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. This means that the original formula for adding the size of the solution applies: just the file sizes added together. Goldman should accept that he foolishly rushed into a careless amendment of his original challenge and pay the money. That said, it obviously is cheating to have the archive format or file system hide the representation of where the removed bytes are! If a single file is produced, it has to include a table of where to insert the bytes that were taken out. If multiple files are produced, the archive format or file system stores that information for you at considerable expense. If both people are wrong, the contest should be declared invalid and Goldman should return the $100. If only Goldman is wrong, he should pay $5000. Under no interpretation is Goldman strictly right and the contestant strictly wrong. So he is wrong to keep the $100 in any case.

scintill76 12y ago
> He didn't say "okay, but there will be a 256 byte size penalty per additional file", he just plainly agreed. Exactly. IMO the challenge-setter is the one being more unfair here, since his metadata-based reason to reject the solution applies to submissions made under the original rules too. He accepted an amendment without counter-amending to cover that loophole, so if he stands by his word, he has to pay up. It casts doubt on whether he would pay if somebody won by the original rules with some luck. Maybe he has an implicit allowance, that merely two files can't "encode" a big enough advantage, but again, then it's his fault for not addressing that in the new rules.
- thret 12y ago
  It's effectively a prop bet. If you're a world class table tennis champion and you bet someone you can beat them at table tennis on the proviso that they get to pick the bats, you can't really complain if you find out later that they have spent six months practicing with frying pans. You just have to pay up. If you don't see the loophole before you agree, you pay. Actually there's a great little bit about this in the movie Guys And Dolls (1955), and what to do if someone bets you that he can make a jack of spades squirt cider in your ear.

thomasahle 12y ago

AFAIK, information theory requires the _Expected_ size of a 'compressed' file be at least as large as the original. So we could create an encoding that compressed N/50 of the strings with lg(N/50)=lg(N)-lg(50) bits. That would save us lg(50) > 5 bits with 2% chance. In this game we have 50 tries (5000$/100$) so we'd be pretty sure to win. The correct price for this game is probably closer to 200$.

Dylan16807 12y ago
The problem is that even the most trivial linux-compatible decompressor will add a few bytes, and there's almost no chance of saving that many bytes. But sure it wouldn't hurt to require it be 100+ bytes smaller.

TillE 12y ago

In theory, I quite like the solution mentioned in the earlier threads: request a file that's a few kilobytes, then get two or three different hashes of the file, and write a "decompressor" that generates random files and checks the hashes. It's just a shame that the heat death of the universe will probably occur before your program finishes.

piannucci 12y ago
Sorry, but no. There are far more files with a given hash than just the one, if the file is longer than the hash. And having multiple hashes doesn't help until the hashes exceed the length of the file.
- compbio 12y ago
  Chances of getting a collision is higher than getting a good solution, but having multiple hashes does help in increasing the chance at a good solution. With a hash 1 bit less than the length of the file, we put two pigeons inside one hole, and have a 50% chance at picking the right pigeon. The fewer/smaller hashes, the more we get "sorry, but no".
  - m_mueller 12y ago
    Also, I guess the hash algorithm could be specifically tested to work for this particular solution, couldn't it (although only after having spent the $100 of course)?. The problem I guess is to have a script that takes up less space than for the hash to still work without a collision for the particular data. Even with the smallest possible program or script, this probably isn't going to work then.
  - Someone 12y ago
    It's easier to just drop the final F bits from the N-bit input stream and, at decompression time, guess what they are than to go through this exercise of generating hashes that have N-F bits in total and hunt for bit streams having those hashes.
dvirsky 12y ago

skatenerd 12y ago

Can't he just send you a Kolmogorov-random file? The definition of randomness (in Kolmogorov sense) basically corresponds directly to his challenge. Also, Kolmogorov-random sequences vastly outnumber non-random sequences in general, so with a long-enough file, I wonder how certain he can be that he has generated such a file. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...

mappu 12y ago
How do you determine whether the file is kolmogorov-random? The only approach is to try a perfect kolmogorov compressor, which doesn't exist (well, excepting brute force over the space of possible turing machines).
- skatenerd 12y ago
  I bet that with longer strings, the odds of drawing a kolmogorov-random string are high enough that he's guaranteed to make money from his Challenge
darkmighty 12y ago
Read the article, this is a circumvention rather than compression, although if you define Komogorov-randomness appropriately, such a definition would work. But modern OS's have non-determinism available: take a Kolmogorov-random file of size n which can be generated by a program n+1. Then, replace a certain part of the program (totaling k bits, and delete 2 extra bits) with a function drawing k+2 random bits from the OS. Then with probability 2^-(k+2), you win.

hyperpallium 12y ago

The file ordering contains information (done with filenames, comp.$i, but could use other file metadata). Mike can escape his unthinking agreement to multiple files by the rules forbidding information in filenames.

compbio 12y ago

A trick similar to the recursive Barf compressor (add information to the filename). http://mattmahoney.net/dc/barf.html http://mattmahoney.net/dc/barf.html A longer running challenge is http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914 http://www.drdobbs.com/architecture-and-design/the-enduring-... No entry fee, $100 prize, and just as unfair. A completely serious compression challenge with serious consequences for AI and NLP: http://prize.hutter1.net/ http://prize.hutter1.net/ up to 50.000$ prize money, but severe restrictions on memory and running time. You can not beat Goldman's troll-ish challenge (certainly if the rules are retro-actively clarified in favor of the organizer). You could however try to put the challenge in limbo by creating a decompressor which bruteforces a solution, 'till some hashes match or the final heat death of the universe or the halting problem is solved, whichever comes first. Goldman will not be able to ever verify your solution, and when he does (theoretically it is not impossible), it means you win. Or, instead of above Schrödinger's Compressor you can send a good random number generator back as your solution. If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Why does he want to do a diff between two random files, is he perhaps looking for order where there is none? But that's the same foolishness he accuses his participants of.

function_seven 12y ago
> If Goldman wants his file to be random, any random file should do. Why does he want exactly his own random file? Maybe because the file was XOR'd with a secret one time pad?
- compbio 12y ago
  Blast! That would require our solution to break all known encryption. Then it would be easier to just target Goldman's setup. A file with output from AES-256("sekrit") would not be random to Goldman. It would appear random to us, until we crack it with a plausible password. Key to randomness is unpredictability. The moment Goldman saves some atmospheric noise on his computer and makes a short pointer to it on his filesystem, is the moment this file loses its claimed unpredictability. Goldman knows this file deeply: He himself has compressed meaningless random data into predictable information that has meaning and purpose, a feat he set out to prove impossible. By simply entering the challenge with real meaningless randomness you make Goldman solve it for you.

snowwrestler 12y ago

The point of the challenge was to tempt people who do not understand compression as well as Mike into putting themselves into a position for Mike to mock and/or shame them. From that respect, it seems to me like it was a trick. In my experience, people who set up such tricks do not usually respond well when the tables are turned. There are some people in the world who take it personally when other people don't understand their area of expertise as well as they do. They get angry and offended at naive questions, and seek to punish the idiots. This is a great way to take an interesting subject and ruin it for everyone. One of the best aspects of the HN culture is that experts here tend to incline more toward teaching and less toward chastising. It's a nice change from Usenet.

x0x0 12y ago
Why do you think that rather than Mike is genuinely interested in novel compression methodologies, and willing to pay some money to make interested people attempt to discover them?
- zik 12y ago
  Because information theory says it's impossible.
- DanBC 12y ago
  There was a problem in comp.compression (or whatever Usenet newsgroup) of arrogant challengers announcing their brilliant new compression algorithm. This bet is a way of demonstrating at least the pigeon hole problem to other people.
- seanc722 12y ago
  I would say the update he posted to the news group rules this out.
- pgaddict 12y ago
  Because that's pretty much what he says in his post to comp.compression, where he announces that someone accepted the challenge. Let me quote: > Before naming the individual and giving additional details of our > correspondence, I would like to give him some time to analyze the > data I will be sending him. It would be very easy to point out to > him the impossibility of his task, but far more interesting to see > how long he will struggle with the problem before realizing it for > himself. > > I am supposing that one of his fellow co-workers probably referred > him to my challenge, as I cannot fathom that someone would read the > comp.compression faq first and then want to participate after > understanding the futility of the effort. On the other hand, some > people just don't understand information theory too well. > > I'll try to give him a complete explanation of his error after a > week or so, I guess. :) So Mike is just smug about how clever he is, how stupid the other person is, not even suspecting there might be a loophole in the challenge. I see no sign of interest in learning what the other person is up to, or even admitting that there might be something to learn.

phkahler 12y ago

Here's a more risky solution. Chose an arbitrary large file size. Have the decompressor search the local file system for a file of that specific size and make a copy of it as output. This presumes he's going to have the uncompressed file on the system to verify the output of the decompressor. That may turn out to be a false assumption, but what if...

log_n 12y ago
Or just have the decompressor log onto a server and download the original file. Only risk then is internet connection.

mrfusion 12y ago

I'm confused about the challenge. Why wouldn't simply using gzip work? I must be missing something obvious.

robzyb 12y ago
GZIP would not apply very much compression, at all, to purely random data. So the compressed data + gzip decompressor would very likely be a greater size than the original data.
btown 12y ago
If you're given perfectly random data, gzipping it will (almost) never reduce the size so much that you could fit the gunzip binary in the reduced space. In the extremely rare occurrence that the generated random data has, say, a repeated string longer than the gunzip binary, the challenger could be on guard for that and just regenerate random data until that's not the case. To be more formal, the challenger is finding what he believes to be a string that is Kolmogorov-random, and betting (quite safely) that the challenged party can't prove him wrong. http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogoro...
- function_seven 12y ago
  > that you could fit the gunzip binary in the reduced space What's funny is that Patrick (the challenger) asked if a bash script consisting solely of a call to gunzip would suffice as the decompressor. In other words, all he had to do was compress the file by more than the amount of the script. Mike allowed it, knowing that even a tiny "decompressor" that really just called out to the real thing, would still be larger than the compression achievable on a well-crafted random blob.

Intermernet 12y ago

Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net? There are grey areas here. Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size? I know this was written 14 years ago, but we had the net then, and shared libraries aren't exactly a new thing. Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way? I'd say that using the filesystem to "hide" bytes is the least of the possible loop-holes with this challenge, if you were being pedantic about the rules.

function_seven 12y ago
> Does the decompressor have to be wholly hosted locally? Could it just be a shim that pulls a more complex program from the net? The judge can disconnect his computer from the Internet, attempt to run the submitted decompressor and file, and declare failure when it doesn't work. Nothing in the challenge guarantees Internet connectivity on the machine. > Does a decompressor that depends on linked libraries count? Do things like libc count towards the total decompressor size? Nope. In the email exchange, Mike said that just a script that called out to gunzip would be fine, and that he'd only count the size of the script as the decompressor size > Where do you draw the line? Can any decompression code call an external dependency and not be disqualified in the same way? Yup, as long as the dependency is already on the machine I suppose. That's what's so enlightening about this challenge. Even a tiny, tiny script that calls to other programs still can't compress a "pathologically" random file by more than a few bytes.
- Intermernet 12y ago
  >Yup, as long as the dependency is already on the machine I suppose. That's exactly what I was getting at. If gzip was allowed, then any common decompression utility should be allowed. If that's the case, and said utility relies on an external library, should that library be included as part of the size of the decompression utility? It's arguable that the "fabric" over which the data is delivered shouldn't matter. If shouldn't really matter if the linked library comes from the same SSD as the executable, or from a server on the other side of the world. We currently define "the machine" as the internals of a box. Would this count if you were running the executable from a removable drive? If not, why does "network storage" trigger the disqualification, and not "USB storage"? I understand the original premise of Mike's challenge, but considering a loophole is being discussed here, I'd like to know where people see that the boundaries of similar loopholes lie.

thezilch 12y ago

By Patricks thinking, I could just store the last N bytes of each file in the filename! Clearly he can see this isn't compression?

dvirsky 12y ago

You should re-read this and imagine Goldman's messages being read in Vizzini's voice.

progrn 12y ago

Can someone explain why this is not possible? I understand why sending a decompressor beforehand is not possible for all inputs. I don't understand this formulation of the problem, where it only needs to work for one input that you get before you need to create the decompressor.

raverbashing 12y ago
Some simple explanation Compression exploits redundancy in a data stream (basically). You basically get "all symbols" (and how you define this varies according to your compression method: you could do all letters in the case of text, or even text snippets that repeat, etc) and reassemble them in a way that the ones that repeat the most take less space (and you also need to start from a basic dictionary known by all uncompressors or ship it with your compressed file) One simple analogy is writing with abbreviations, but if you write e.g. the reader has to know what "e.g." means or you have to put in the beginning "e.g. = example" (and this also takes space) Now, a randomly generated file ideally has all symbols repeating with the same frequency, (we say all symbols have the same entropy - I'm not sure about this exact wording), hence you can't take a symbol that repeats more or less and make it take less space in your compressed file
- s369610 12y ago
  what if instead of using your own dictionary, you use an index into an existing dictionary? such as an index into a subsequence of pi. Couldn't you then find a sequence of bytes in the file in which the index into pi takes less bytes and then replace them all with the index? If you couldn't find any in pi use e or another such number? What am I missing
  - raverbashing 12y ago
    In this case your dictionary either doesn't have everything or to adequately point to it you take as much space as not using it. While Pi has all pairs of 2 digits, your index would take more space than storing the pairs itself (because you might need to go beyond position 99) For one situation you might "get lucky" and find a coincidence, but this won't scale generically

paulsecwhatt 12y ago

I absolutely believe Mike should have paid Patrick. On the simple premise that since Mike was hosting a bet that he KNEW was impossible (i.e. under no circumstance, ever, would he have to pay the 5000$), then literally the only point of the game is to find any loopholes. Otherwise it's just Mike preying on unsuspecting victims. If you design an impossible game, the only possible thing for anyone to do is to break it. If you then complain that THAT is cheating, you're a pedantic idiot - one of those annoying kids in middle school who loses a bet and then tries every possible way to weasel himself out. To add fuel to the fire, his obnoxious replies such as "I tried running the first two files and it didn't work", make my blood boil, as it's a clear attempt to try and belittle the contestant.

sjwright 12y ago
> If you design an impossible game, the only possible thing for anyone to do is to break it. Which is the Kobayashi Maru in a nutshell. In that fictional case, Kirk was disqualified but also received a commendation.
- qbrass 12y ago
  https://en.wikipedia.org/wiki/The_Kobayashi_Maru_%28Star_Trek_novel%29 https://en.wikipedia.org/wiki/The_Kobayashi_Maru_%28Star_Tre... I don't know if the novel is canon, but it ought to be. Kirk beat it by cheating, Scotty beat it legitimately, then proved that what he did only worked in the simulation.
emn13 12y ago
Mike's responses could have been better, but in the correspondence I see no guarantee that the files will be presented in order, or with the same file names, or in an otherwise empty directory. That sounds close to cheating, but I think it's exactly in the spirit of both the original challenge by Mike and the response by Patrick. After all, the original challenge didn't mention multiple files (so it's not surprising that this limitation isn't mentioned), and the subsequent alteration to the rules was initiated by Patrick, who intentionally tried to inject a loophole, but failed to specify the need to keep the files in order. His rules; he should have to live by them. Also, I suspect that if Patrick had mentioned the need to leave the file names unaltered or in order, there's a good chance that Mike would have smelled a rat. After all, it is precisely in that side-channel where the information gain is to be had.

prettyrandom100 12y ago

I didn't see anything that mentions run-time in the challenge. I think a good compression challenge should mention about run-time. Theoretically, it would be possible to hash parts of the file and then brute force the hash in the decompressor. This would take a lot of time but would work.

cplease 12y ago
No it wouldn't work! Hashes do not defy information theory, they lose information. Such brute forcing would only find hash collisions and "decompress" to a different text than the original.
jholman 12y ago
I endorse the creativity in your approach, but you are mistaken; this will not (deterministically) work. Given a hash function that hashes an input I (of size N, comprised of N arbitrary bytes) to a digest D (of size M), then assuming that M is a fixed value, then for each output digest D_0, there will be 2^(N-M) values that hash to that D_0. How will you tell which is the "right" one?
zaroth 12y ago
There are an unbounded number of inputs which may result in the same hash digest. Saving just the hashes (digests) and then finding the preimages would not guarantee the same result. You would find collisions but not necessarily the right collision. In fact, as the data being hashed increases in size, the amount of data required to identify which preimage is the correct preimage must be greater than or equal to the difference in size between the digest and the preimage. For example, let's say you are using a perfect hash function, with a 64-bit digest. If you feed data into the hash function in 64 bits chucks, and then try to brute-force the results, each preimage you find will be the right one, and you can assemble the original file, but you have exactly as many bytes as when you started! Now lets say you feed in 65 bits to the perfect hash function, saving 1/65 space in the resulting list of digests. But unfortunately, there are two 65-bit preimages which will result in each of your stored digests, so you need a bit to decide which one is correct. And so on...
brongondwana 12y ago

gayprogrammer 12y ago

If you printed the files each on a sheet of paper, it would 'use more trees' than printing the original file (paper being the 'filesystem'). I agree that it shouldn't matter what the filesystem does to store it, if the rules state that file size is determined by a specific command to count all the inodes, then he lost. If the command is 'du' or 'wc', then he won.

fishnchips 12y ago

I am actually surprised that Patrick did not compress the original data to 0 bytes by keeping all the data in filenames. That would be the ultimate troll ;)

xorcist 12y ago
I disagree. You could legitimately say he just stored the data in the metadata fields. But files have a size, even as a stream, completely regardless of metadata. I think this is a more clever hack.
- fishnchips 12y ago
  Maybe, I don't know. One way or another you're storing some data (chunk ordering in Patrick's case, all data in my case) in file names.

yummybear 12y ago

I remember a "fractal compression" hoax one time. It would compress a file ridiculously (like 1 1mb file down to 100 bytes), and decompress it flawlessly. Of course it just moved the file to some other place on the harddrive and created a "compressed file" full of junk and restored the file on decompress. Good one...

Bentota 12y ago

Why wouldn't binary run length encoding work here? E.g. "compressing" 11100110 to 30020 for example?

tehwalrus 12y ago
How are you storing that 3 in 1s and 0s? ;)
DanBC 12y ago
Compression relies on entropy. There's not enough entropy in the random file your your run-length encoding to work. I think the data is available so you can always try to beat the bet.
- et1337 12y ago
  I may be completely misinformed, but I think you meant to say there's too much entropy. A binary string of all ones followed by all zeroes has very low entropy, while a purely random binary string has high entropy. (I think. I'm skimming the Wikipedia article on entropy now)
  - DanBC 12y ago
    Yes, sorry!!

logicallee 12y ago

In terms of behavior, we know Mike acted in bad faith: before he saw the approach, he had agreed that the challenger could use multiple files. But once the challenger had posted them, he proceeded to download only a single file to verify its functionality, not touching the others. It shows bad faith on the part of Mike when he chose to ignore the other files. By the way in a theoretical sense Mike lost when he said he would allow multiple files and count their sizes: this is because [] is not the same as [[][][]], but consists of 3 empty sets. You can theoretically encode a file into just a bunch of 0-byte files, without using the order of the files or their names. He shouldn't have agreed to count only their sizes. For the theoretical encoding into 0-sized files, you can simply interpret the input file as a binary number, and then create that many empty files. This is not a practical solution of course - you can only compress two bytes down to 0-byte files this way, as 2^16-1 is already up to 65535 empty files. For three bytes it's up to 16,777,215 files. If you wanted to store 9 bytes in unary as the number of empty files, you would need 2^72-1 = 4.7 sextillion (million quadrillion) files. Obviously that is not actually possible. But even 9 bytes is hardly enough to interpret the files as binary again. (Unless you can somehow get Mike to agree to the invocation - since the decompression program itself doesn't need to store any information and theoretically could be 0, 1 or 2 bytes.) But theoretically you don't need anything other than what Mike foolishly agreed to: allowing multiple output files counting their sizes. 2. There is also another theoretical way to make money off of Mike, but it is not practical. (It doesn't work.) If we were not limited to bytes but could use bits, you could shave up to 5 bits off of every input file, if you figured out a way to decompress it by always prepending the bits 00000. (Theoretically there is only 1 pigeonhole to decompression, so you do not need to store any information in the decompression algorithm and it has no minimum size). If Mike is using a random source for the files, this would result in a correct decompression in 1/32 of cases. But Mike is giving 49:1 odds (risk $100, get $5000), which is better than 31:1. So you could simply repeat the game with Mike thousands of times, always using the same decompression algorithm, until you have all of Mike's money. This works better if Mike is a computer, of course. And it doesn't work at all on any actual systems, as a nibble is less than a byte and would not count as savings even if you could encode the decompression algorithm into a 0-byte (or up to 3 bit) invocation.

hackhat 12y ago

He also doesn't state that the output should be right at first decompression try. By using this you could encode multiple bits and then generate various wrong archives, knowing that after 1000000 tries he would get a correct decompressed file.

brownbat 12y ago

If you want to hear some stories from the master of proposition bets, there's an old autobiographical article in SI by Titanic Thompson: http://www.si.com/vault/1972/10/09/618832/soundings-from-titanic http://www.si.com/vault/1972/10/09/618832/soundings-from-tit... (The risk being that half of it is made up, but he definitely had a reputation for this sort of thing.) "You might wonder why, if I was the best golfer in the world, like I say I was, I didn't turn pro and win all the championships? Well, you were liable to win a golf bag if you won a tournament in those days. A top pro wouldn't win as much in a year as I would in a week as a hustler. People would get to know a pro, and I wanted to keep my skill a secret as far as possible. I didn't care about championships. I wanted the cash."