I took the $5000 Goldman Challenge

360 views
Skip to first unread message

Patrick Craig

unread,
Apr 16, 2001, 6:47:12 AM4/16/01
to
Read all about it:

http://www.geocities.com/patchnpuki/other/compression.htm

Patrick

--
Posted from IDENT:ro...@ns.nag-j.co.jp [211.0.18.242]
via Mailgate.ORG Server - http://www.Mailgate.ORG

Willem-Jan Monsuwe

unread,
Apr 16, 2001, 9:04:37 AM4/16/01
to
) Read all about it:
)
) http://www.geocities.com/patchnpuki/other/compression.htm
)
) Patrick

We warned Mike that his challenge wasn't worded carefully enough and that
something like this could happen. In fact your approach was rather timid.
There've been numerous ideas floating about the last week about how to meet
the challenge by using the loopholes in there.

I personally feel Mike shouldn't have put up such a loosely worded challenge
with a $5000 prize. As stated, the challenge is _not_ mathematically
impossible, as there are more (decompressor, data) tuples of total length N
than there are data files of length N. And allowing multiple data files
only increases that.

Mike, you fouled up. Be a man and admit it. Good form, Patrick!


SaSW,
--
Willem (at stack dot nl)
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Joshua Schmier

unread,
Apr 16, 2001, 10:32:58 AM4/16/01
to
I actually disagree, as I'm sure many will on this subject. Mike was going
by the guidelines within the FAQ. The FAQ clearly outlines that filesystem
exploits are not true compression. I think it may have been short-sighted of
Goldman to allow multiple 'compressed' files, however, having the challenge
worded so loosely makes things interesting. :)

And yes, very good show Patrick.


"Willem-Jan Monsuwe" <wil...@toad.stack.nl> wrote in message
news:slrn9dlrge...@toad.stack.nl...

s...@nospam.unt.edu

unread,
Apr 16, 2001, 12:28:15 PM4/16/01
to
Joshua Schmier <jsch...@bellsouth.net> wrote:

> I actually disagree, as I'm sure many will on this subject. Mike was going
> by the guidelines within the FAQ. The FAQ clearly outlines that filesystem
> exploits are not true compression. I think it may have been short-sighted of
> Goldman to allow multiple 'compressed' files, however, having the challenge
> worded so loosely makes things interesting. :)

I agree with this. To show compression, you need to show space
savings, which has not been done here. In fact, the disk space
required for the "compressed" data is substantially larger than the
disk space for the original data, since many more inodes/directory
entries are required. It all goes back to "hiding information" in
the file length, which has been discussed here over and over.

That said, as soon as I saw the request that multiple "compressed
files" be allowed, it was pretty obvious what game was going to be
played. Unfortunately, Mike didn't see it coming, and didn't object
to the "multiple files" requirement (in fact in an earlier posting
here, I pointed out that you should require the decompressor and data
to be bundled together in one file, and the size of that piece should
determine the "compressed size").

--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |

Dale King

unread,
Apr 16, 2001, 12:46:54 PM4/16/01
to
"Willem-Jan Monsuwe" <wil...@toad.stack.nl> wrote in message
news:slrn9dlrge...@toad.stack.nl...
> ) Read all about it:
> )
> ) http://www.geocities.com/patchnpuki/other/compression.htm
> )
> ) Patrick
>
> We warned Mike that his challenge wasn't worded carefully enough and that
> something like this could happen. In fact your approach was rather timid.
> There've been numerous ideas floating about the last week about how to
meet
> the challenge by using the loopholes in there.
>
> I personally feel Mike shouldn't have put up such a loosely worded
challenge
> with a $5000 prize. As stated, the challenge is _not_ mathematically
> impossible, as there are more (decompressor, data) tuples of total length
N
> than there are data files of length N. And allowing multiple data files
> only increases that.
>
> Mike, you fouled up. Be a man and admit it. Good form, Patrick!

I'm afraid I have to agree with Mike here the wording from the challenge
was, "Last, the contestant will send me a decompressor and a compressed
file". He said *A* compressed file. 218 files is not the same as a file. I
agree that Mike's challenge is not impossible, but in this case the
contestant did not meet the challenge as specified.

I see where Patrick said, "The restated challenge is to reconstruct the
original file using a decompressor and several compressed files whose total
file size is less than the original file size." The problem is that Mike
never restated the challenge in such a way. Nowhere in the thread of emails
he posted did Mike allow for anything but *a* compressed file and a *a* file
for the decompressor. That is even being generous as he allows you to rely
on the file length information in the header.

This is one of the reasons that I object so vigorously to David Scott's
claims of increasing compression ratio by relying on the file header. It is
the same fallacy that Patrick tried to exploit. Following Patrick's logic I
can easily meet this challenge for about any file. Let's say I have an n bit
file. All I do is create n files that have no data in any of them. I store
one data bit for each file in the archive bit (assuming Windoze) and the
last file is marked by setting it's read only bit. According to Patrick's
logic the files consume zero space because they have no data in them. So the
only space I am taking up is for the program.
--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 12:46:03 PM4/16/01
to
s...@nospam.unt.edu wrote in <9bf6iv$5p5$1...@hermes.acs.unt.edu>:

>That said, as soon as I saw the request that multiple "compressed
>files" be allowed, it was pretty obvious what game was going to be
>played. Unfortunately, Mike didn't see it coming, and didn't object
>to the "multiple files" requirement (in fact in an earlier posting
>here, I pointed out that you should require the decompressor and data
>to be bundled together in one file, and the size of that piece should
>determine the "compressed size").
>

So what is the bottom line in your view. Besides the fact Mike was
stupid and so eager for the 100 dollars that he allowed the multiple
files. I agree that he should have required one program which internally
must contain all info so that it expands to one file. But he did not.
So in your view should he pay the 5g's or not??
The rules that both men agreed to was a series of files. The total
length being less that the random files. I think that means Mike lost.
Are people here going to vote. I would like to know what Gutman and
Matt have to say after they read the rules the two men agreed to in
there correspondse. Which explicitly allowed for many files.

I already expect King to say Mike won since it obvous to him that the
length of a file is not the length but some number added to the length.


David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***

s...@nospam.unt.edu

unread,
Apr 16, 2001, 2:42:10 PM4/16/01
to
SCOTT19U.ZIP_GUY <david_...@emailv.com> wrote:
> s...@nospam.unt.edu wrote in <9bf6iv$5p5$1...@hermes.acs.unt.edu>:

>>That said, as soon as I saw the request that multiple "compressed
>>files" be allowed, it was pretty obvious what game was going to be
>>played. Unfortunately, Mike didn't see it coming, and didn't object
>>to the "multiple files" requirement (in fact in an earlier posting
>>here, I pointed out that you should require the decompressor and data
>>to be bundled together in one file, and the size of that piece should
>>determine the "compressed size").

> So what is the bottom line in your view. Besides the fact Mike was
> stupid and so eager for the 100 dollars that he allowed the multiple
> files. I agree that he should have required one program which internally
> must contain all info so that it expands to one file. But he did not.
> So in your view should he pay the 5g's or not??

That's not such an easy question -- the letter of Mike's challenge was
met (since he agreed to the multiple file modification), but clearly
the spirit was violated. Of course, the challenger knew full well
that he was violating the spirit of the contest and purposely modified
the rules of the contest to allow his specific "cheat". I'm just
sorry that Mike didn't see that when he should have....

Frankly, I'd like to see it be called a "draw" -- have Mike send back
the $100 and acknowledge that the challenger (Patrick?) found a way to
bend the rules in such a way as to technically meet the modified
challenge...

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 12:58:55 PM4/16/01
to
jsch...@bellsouth.net (Joshua Schmier) wrote in
<QoDC6.107$xZ3....@news1.mco>:

>I actually disagree, as I'm sure many will on this subject. Mike was
>going by the guidelines within the FAQ. The FAQ clearly outlines that
>filesystem exploits are not true compression. I think it may have been
>short-sighted of Goldman to allow multiple 'compressed' files, however,
>having the challenge worded so loosely makes things interesting. :)
>

Mike thought he was going by the FAQ becasue he thought he had a lock
and a free 100 dollars. But his allowing multiple files and not
clarifying that for any file length of N he would automaticlly add some
magic number for the "true length" shows Mike did not fully understand
the problem. The challenger and Mike are not really held to the FAQ
since they both agreed to go om the sum of the file length. The bet
was on there wording of letters. And it should be clear to any one
that MIKE lost.


>And yes, very good show Patrick.


Bottom line your reply not clear. Should mike pay the money or not?
Is the other guy out the 100 dollars or not?

David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***

Dale King

unread,
Apr 16, 2001, 4:01:52 PM4/16/01
to
<s...@nospam.unt.edu> wrote in message
news:9bfee2$5rn$1...@hermes.acs.unt.edu...

> SCOTT19U.ZIP_GUY <david_...@emailv.com> wrote:
> > s...@nospam.unt.edu wrote in <9bf6iv$5p5$1...@hermes.acs.unt.edu>:
>
> >>That said, as soon as I saw the request that multiple "compressed
> >>files" be allowed, it was pretty obvious what game was going to be
> >>played. Unfortunately, Mike didn't see it coming, and didn't object
> >>to the "multiple files" requirement (in fact in an earlier posting
> >>here, I pointed out that you should require the decompressor and data
> >>to be bundled together in one file, and the size of that piece should
> >>determine the "compressed size").
>
> > So what is the bottom line in your view. Besides the fact Mike was
> > stupid and so eager for the 100 dollars that he allowed the multiple
> > files. I agree that he should have required one program which internally
> > must contain all info so that it expands to one file. But he did not.
> > So in your view should he pay the 5g's or not??
>
> That's not such an easy question -- the letter of Mike's challenge was
> met (since he agreed to the multiple file modification), but clearly
> the spirit was violated. Of course, the challenger knew full well
> that he was violating the spirit of the contest and purposely modified
> the rules of the contest to allow his specific "cheat". I'm just
> sorry that Mike didn't see that when he should have....
>
> Frankly, I'd like to see it be called a "draw" -- have Mike send back
> the $100 and acknowledge that the challenger (Patrick?) found a way to
> bend the rules in such a way as to technically meet the modified
> challenge...

Looking back over the page I see where the miscommunication occurred:

-------------
> I meant can I send you a compressor and several compressed files whose
> total file size is less than the original uncompressed file and from
> which I can regenerate the original uncompressed file
>
> Patrick

Sure -- but you send me a *decompressor*, I don't need the compressor.
-------------

Patrick was trying to relax the rules to allow the compressed file to be
broken into many files and rely on information in the file header (the
lengths) for storing some information. I am certain that Mike did not feel
the rules has changed as nowhere does he talk about compressed files plural
and talks repeatedly about a compressed file or the compressed file.
Including saying right after the original was sent,"In order to meet the
challenge you must provide to me a compressed file and a decompressor."

Whether the challenge changed by the above statements is a legal question.

The challenge as originally stated was not met. Patrick thinks that he got
the original terms of the challeng changed, and I don't believe Mike things
the terms changed.

If the supposed new definition were allowed, I have already shown how it can
be done by using the archive and readonly flags from a large number of
files.

--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 1:13:05 PM4/16/01
to
Ki...@TCE.com (Dale King) wrote in <3adb...@news.tce.com>:

I knew you would not be able to read the email and be able to figure
out what each man said. The the challene as agreed to was for several
files. Did you even bother to read it. How can one be so blind.

True Mark referred to sending a compressed file later in the series of
messages. Only because his narrow view of things like your narrow view
of things. He did not think that more than one would be sent. But it is
clear that he allowed multiply files. It was only after he lost that
he decied to change the rules and not allow for muliply files.

>
>I see where Patrick said, "The restated challenge is to reconstruct the
>original file using a decompressor and several compressed files whose
>total file size is less than the original file size." The problem is
>that Mike never restated the challenge in such a way. Nowhere in the
>thread of emails he posted did Mike allow for anything but *a*
>compressed file and a *a* file for the decompressor. That is even being
>generous as he allows you to rely on the file length information in the
>header.

Actually he did. When he stated the ruless where OK excepet that
the wanted the "decompressor" and not the "compressor". He stated rest of
rules ok. He even left that part of messages in the previous copy
part so it was clear to both men what the rules were. However I can
see from other posts that this simple logic is to hard for you to
follow.

>
>This is one of the reasons that I object so vigorously to David Scott's
>claims of increasing compression ratio by relying on the file header. It
>is the same fallacy that Patrick tried to exploit. Following Patrick's


Actaully the fallacy is in your mind. Patrick exploited the loop
hole given him. You probelm is understand what is and is not
availage to Patrick. If the agreement was more carefully worded
then such a loop hole would not exist. Problem is that the so called
loop hole was agreed to by both men. Just becasue in your mind you
don't think the loop hole should have been allowed does not change the
simple facts that it was allowed.


David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***

Dale King

unread,
Apr 16, 2001, 4:55:10 PM4/16/01
to
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:9085767C9H110W...@207.36.190.226...

> Ki...@TCE.com (Dale King) wrote in <3adb...@news.tce.com>:
>
> >I'm afraid I have to agree with Mike here the wording from the challenge
> >was, "Last, the contestant will send me a decompressor and a compressed
> >file". He said *A* compressed file. 218 files is not the same as a file.
> >I agree that Mike's challenge is not impossible, but in this case the
> >contestant did not meet the challenge as specified.
>
> I knew you would not be able to read the email and be able to figure
> out what each man said. The the challene as agreed to was for several
> files. Did you even bother to read it. How can one be so blind.
>
> True Mark referred to sending a compressed file later in the series of
> messages. Only because his narrow view of things like your narrow view
> of things. He did not think that more than one would be sent. But it is
> clear that he allowed multiply files. It was only after he lost that
> he decied to change the rules and not allow for muliply files.

Note, I did later point out where the idea of allowing multiple files
slipped in. I'm not sure if Mike actually thought he had changed the rules
to allow multiple files given the fact that he always said a compressed
file.

The original challenge was not met. Patrick wanted the challenge changed to
allow him to take advantage of storage of the file lenght in the header. If
one allows an arbitrary number of files and the file header is not counted
against it, it is trivial to compress an n-bit file into n files of zero
length using the archive and read-only bits for storage. But of course, no
compression has actually taken place.

> >I see where Patrick said, "The restated challenge is to reconstruct the
> >original file using a decompressor and several compressed files whose
> >total file size is less than the original file size." The problem is
> >that Mike never restated the challenge in such a way. Nowhere in the
> >thread of emails he posted did Mike allow for anything but *a*
> >compressed file and a *a* file for the decompressor. That is even being
> >generous as he allows you to rely on the file length information in the
> >header.
>
> Actually he did. When he stated the ruless where OK excepet that
> the wanted the "decompressor" and not the "compressor". He stated rest of
> rules ok. He even left that part of messages in the previous copy
> part so it was clear to both men what the rules were.

I acknowledged that later as I said. I think it was a miscommunication, but
that is beside the point.

> >This is one of the reasons that I object so vigorously to David Scott's
> >claims of increasing compression ratio by relying on the file header. It
> >is the same fallacy that Patrick tried to exploit. Following Patrick's
>
> Actaully the fallacy is in your mind. Patrick exploited the loop
> hole given him. You probelm is understand what is and is not
> availage to Patrick. If the agreement was more carefully worded
> then such a loop hole would not exist. Problem is that the so called
> loop hole was agreed to by both men. Just becasue in your mind you
> don't think the loop hole should have been allowed does not change the
> simple facts that it was allowed.

I agree that Mike should have been more careful wording it.

I'm not talking about the contest in that last paragraph. I am relating it
to your claims where you essentially rely on the fallacy that the length
information does not count and actually claim that is an increase in
compression ratio. The question is did Patrick actually compress anything?
The total of the data portions of all his files is less than the original,
so doesn't that count as compression.

The answer is no for the same reason that I have argued against your claim
that relying on the file length in the header is not increasing the
compression ratio. He is relying on the extra storage provided for the file
length in the file header. And he is doing that over enough files to get
enough extra storage to offset the size of the program.

--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 4:10:29 PM4/16/01
to
s...@nospam.unt.edu wrote in <9bfee2$5rn$1...@hermes.acs.unt.edu>:

>SCOTT19U.ZIP_GUY <david_...@emailv.com> wrote:

>> So what is the bottom line in your view. Besides the fact Mike was
>> stupid and so eager for the 100 dollars that he allowed the multiple
>> files. I agree that he should have required one program which internally
>> must contain all info so that it expands to one file. But he did not.
>> So in your view should he pay the 5g's or not??
>
>That's not such an easy question -- the letter of Mike's challenge was
>met (since he agreed to the multiple file modification), but clearly
>the spirit was violated. Of course, the challenger knew full well
>that he was violating the spirit of the contest and purposely modified
>the rules of the contest to allow his specific "cheat". I'm just
>sorry that Mike didn't see that when he should have....
>

Yes the letter of Mikes challenge was meet. But don't forget the
guy paid the CASH before he even saw the file that was to be compressed
so it was stil a challenage. I don't aggree that the challenger thought
he was violating the rules. He asked questions and got anwsers. I
doubt you would have called it a draw if the challenger failed to actaully
do what he requested. It only after the fact Mike was wrong and
lost that people are screaming foul.

>Frankly, I'd like to see it be called a "draw" -- have Mike send back
>the $100 and acknowledge that the challenger (Patrick?) found a way to
>bend the rules in such a way as to technically meet the modified
>challenge...
>

If mike is a man of honor and I get the impression there are not
many men of honor who reply here he should pay the money and be a
little bit wiser for it.

Dror Baron

unread,
Apr 16, 2001, 8:58:16 PM4/16/01
to
It's quite obvious that Mike made a huge blunder.
He agreed to the "multiple file" issue.

Technically, this serves a nice legal lesson.

Theoretically, note as pointed by others that the
total memory consumed by the file system did not
go down. I believe even David will agree ;-)

Mike and Patrick - have a good laugh over a beer
sometime...

Dror

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 7:59:24 PM4/16/01
to
Ki...@TCE.com (Dale King) wrote in <3adb...@news.tce.com>:

>
>


>Looking back over the page I see where the miscommunication occurred:
>
>-------------
>> I meant can I send you a compressor and several compressed files whose
>> total file size is less than the original uncompressed file and from
>> which I can regenerate the original uncompressed file
>>
>> Patrick
>
>Sure -- but you send me a *decompressor*, I don't need the compressor.
>-------------
>
>Patrick was trying to relax the rules to allow the compressed file to be
>broken into many files and rely on information in the file header (the
>lengths) for storing some information. I am certain that Mike did not
>feel the rules has changed as nowhere does he talk about compressed
>files plural and talks repeatedly about a compressed file or the
>compressed file. Including saying right after the original was sent,"In
>order to meet the challenge you must provide to me a compressed file and
>a decompressor."

I am certain having dealt with many bar room bets. Mike didn't
give a dam due to being smug about his winning. If anything he thought
Patrick was a bigger fool than he first thought. A common thing
in bar room bets. Mike knew he lost when Patrick sent him the files.
From that point on the emails were Mike trying to weasel out of the bet.
He know He lost them pretended to not understand by saying he checked
the 2 files and that Patrick failed. He knew he lost but tried to
change the rules after the action was over. Much like the deomcrats
in Florida.

>
>Whether the challenge changed by the above statements is a legal
>question.
>

No question about. In most state betting like this is illegal.
Mike has perfects rights to be nonhonerable and not pay. I am sure
Clinton would do the same thing and not pay up. Mike could just
laugh and keep the 100 dollars. However I would never like to
do business with Mike since I think honesty is still a valuble
thing. The facts are black and white Mike lost. But I can see
you being unable to comprehend this. You have not seen many
bar room fights.


>The challenge as originally stated was not met. Patrick thinks that he
>got the original terms of the challeng changed, and I don't believe Mike
>things the terms changed.

The rules changed and there is a written trail to prove it.

>
>If the supposed new definition were allowed, I have already shown how it
>can be done by using the archive and readonly flags from a large number
>of files.


Actully it can be done with other than those unfair tactics that
you seem so found of. Maybe your just pissed you didn't get the 5k
your self so you wish no one to get it.

>
>--
> Dale King

Joshua Schmier

unread,
Apr 16, 2001, 11:44:59 PM4/16/01
to
Scott, is it not clear to you what the definition of compression really is?
You complately ignore the definition that the FAQ describes for the sake of
your arguement. Please reconsider these parts of the FAQ before making
insults:

Part 9.2
Paragraph 9

This assumes of course that the information available to the decompressor is
only the bit sequence of the compressed data. If external information such
as a file name, a number of iterations, or a bit length is necessary to
decompress the data, the bits necessary to provide the extra information
must be included in the bit count of the compressed data. Otherwise, it
would be sufficient to consider any input data as a number, use this as the
file name, iteration count or bit length, and pretend that the compressed
size is zero. For an example of storing information in the file name, see
the program lmfjyh in the 1993 International Obfuscated C Code Contest,
available on all comp.sources.misc archives (Volume 39, Issue 104).

Part 10
Paragraph 1

Some programs claimed to achieve incredible compression ratios are
completely fake: they do not compress at all but just stored the
uncompressed data in hidden files on the hard disk or keep it in unused
clusters. Needless to say, such programs are dangerous and should never be
used because there is a significant risk of losing all the data.

I'm sorry for having to post actual excerpts from the FAQ itself, but to me
(and everyone else I imagine) Patrick clearly did not compress any
information whatsoever. Only a fool would conceed when the challenge was
obviously not met as such. I'm actually sorry for Mike, as he truely
believed someone was actually going to try to compress the data. Patrick, in
this case, did not even try. Keep the hundred dollars Goldman, you deserve
it for all your trouble.

"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message

news:9085B58E8H110W...@207.36.190.226...

Matt Timmermans

unread,
Apr 17, 2001, 12:10:15 AM4/17/01
to
Yes, this is essentially a bar bet.

I think it's pretty clear that Mike thought he could make a few bucks and
get a laugh, both at the expense of some sucker who thought he could
compress random data.

Mike was then out-suckered.

Well, turnabout is fair play. Patrick gets the laugh. He couldn't have
gotten the $5000 without a lawyer, which would cost him more than that
anyway (You're lucky he didn't have a lawyer uncle, Mike!), so he took the
moral high ground and forgave the bet. Even if he had a lawyer in the
family, he probably would have taken pity on Mike for his inexperience
(never give 50:1 odds on a sucker bet, Mike!), and forgiven the debt anyway.

Either way, Patrick wins this one. If this was an even-money bet, I would
say Mike should pay. At 50:1, I'm glad Patrick didn't force the issue -- In
a bar, you usually do this sort of thing for 20s, and you wouldn't try to
bleed your buddy for $1000 just because he tried to put one over on you.
Its best just to make him sweat a little before letting him off the hook,
which is exactly what Patrick did.

As others have said... very good form.


Joshua Schmier

unread,
Apr 17, 2001, 12:33:20 AM4/17/01
to
No, in this case Patrick bluffed and wasted all of our time in the process.
He never intended to actually COMPRESS the data, and lost a hundred dollars
over a rather well executed con. It may be true that he actually did provide
an example of file system exploitation which vaguely met the challenge
requirements, but no COMPRESSION took really place.

Bah. :)

"Matt Timmermans" <ma...@timmermans.nospam-remove.org> wrote in message
news:HmPC6.595981$f36.17...@news20.bellglobal.com...

Matt Timmermans

unread,
Apr 17, 2001, 1:41:51 AM4/17/01
to
It may have been called a "compression" challenge, but, as Patrick
demonstrated, the rules did not require compression. Mike defined an
acceptance test, which Patrick met. It's not his fault that the test was
defined poorly.

And what do you mean he wasted all of our time? What were you reading the
thread for? We know that you can't compress random data, Mike knows it, and
Patrick knows it. Nobody was expecting a miracle, so what were you hoping
for that you didn't get here?


"Joshua Schmier" <jsch...@bellsouth.net> wrote in message
news:zIPC6.203$xZ3....@news1.mco...

SCOTT19U.ZIP_GUY

unread,
Apr 16, 2001, 9:17:27 PM4/16/01
to
dba...@chopin.ifp.uiuc.edu (Dror Baron) wrote in
<Pine.GSO.4.21.01041...@chopin.ifp.uiuc.edu>:

>It's quite obvious that Mike made a huge blunder.
>He agreed to the "multiple file" issue.
>
>Technically, this serves a nice legal lesson.
>
>Theoretically, note as pointed by others that the
>total memory consumed by the file system did not
>go down. I believe even David will agree ;-)

Yes I agree Mike blundered and should pay up


>
>Mike and Patrick - have a good laugh over a beer
>sometime...
>

German or Japenese Sappro draft was good when I
was in Japan

>Dror

Tim Tyler

unread,
Apr 17, 2001, 6:21:56 AM4/17/01
to
Patrick Craig <pat...@nag-j.co.jp> wrote:

: http://www.geocities.com/patchnpuki/other/compression.htm

Pat: ``can I send you a compressor and several compressed files whose


total file size is less than the original uncompressed file and

from which I can regenerate the original uncompressed file''

Mike:``Sure''

It's almost a shame things have settled down and none of the mentioned
legal action for fraud is taking place ;-)
--
__________
|im |yler Try my latest game - it rockz - http://rockz.co.uk/

Joshua Schmier

unread,
Apr 17, 2001, 7:02:34 AM4/17/01
to
Main Entry: 1sev·er·al
Pronunciation: 'sev-r&l, 'se-v&-
Function: adjective
Etymology: Middle English, from Anglo-French, from Medieval Latin separalis,
from Latin separ separate, back-formation from separare to separate
Date: 15th century
1 a : separate or distinct from one another <federal union of the several
states> b (1) : individually owned or controlled : EXCLUSIVE <a several
fishery> -- compare COMMON (2) : of or relating separately to each
individual involved <a several judgment> c : being separate and distinctive
: RESPECTIVE <specialists in their several fields>
2 a : more than one <several pleas> b : more than two but fewer than many
<moved several inches> c chiefly dialect : being a great many

Would you consider 218 files many? I would.

"Tim Tyler" <t...@cryogen.com> wrote in message news:GBxM4...@bath.ac.uk...

Joshua Schmier

unread,
Apr 17, 2001, 7:05:27 AM4/17/01
to
I was expecting someone to TRY to compress a file. I was expecting a bunch
of e-mails talking about schemes never before thought of (I don't care if
they worked or not). I was not, however, expecting someone to exploit
something that anyone in this newsgroup could have done.

Do you truely believe Patrick's intent was to COMPRESS the data? No, he
intended to bluff his way to a five thousand dollar prize. It's very vague
in their correpondance whether or not Goldman agreed to the multiple file
scheme. And I believe he did not agree to such.

I honestly don't know how you think the rules didn't require compression.
Patrick didn't meet the rules. However, he did trick his way around a bit
until he got to the last step. So because of that Goldman should pay up? I
seriously don't think so.

It's Patrick's fault for entering the challenge knowing full and well his
intent was to exploit a file system, NOT compress data.

What was I hoping for that didn't get here? I was hoping the challenge was
met with sincerity. I was hoping the challenged was truely attempting to
hack out the random data until he gave up.

"Matt Timmermans" <ma...@timmermans.nospam-remove.org> wrote in message

news:zIQC6.596667$f36.17...@news20.bellglobal.com...

Phil Norman

unread,
Apr 17, 2001, 7:30:49 AM4/17/01
to
On Tue, 17 Apr 2001 04:05:27 -0700,
Joshua Schmier <jsch...@bellsouth.net> wrote:
>
>Do you truely believe Patrick's intent was to COMPRESS the data? No, he
>intended to bluff his way to a five thousand dollar prize.

I don't believe he had a purely financial intent in mind. Note
the two quotes from the discussion after the decompressor had been
sent:

"Obviously I would like you to send me the $5000 as promised,
but I never really expected you to."

... and a little later...

"I will withdraw my claim to the $5000 and allow you to...."

The way I read it, it's fairly clear that Patrick's main reason
for accepting the challenge was to show Mike how dangerous it can
be to make carelessly-worded challenges. If this really is his
reason for his acceptance of the challenge, I consider all those
comments which have appeared in this thread that his action is
immoral or otherwise distasteful to be quite ridiculous. In my
opinion, it used a very clever information hiding algorithm to
quite clearly make a very valid point.

Mathematics states that the counting theorem is truth.
Mathematics, however, requires careful wording in order that its
meaning cannot be confused.

Cheers,
Phil

Joshua Schmier

unread,
Apr 17, 2001, 7:44:24 AM4/17/01
to
He did use some bit of trickery to get there, though. Goldman should have
had some rest, he probably wouldn't have slipped up if he had. Trickery is
distasteful regardless of the context. :)

You must admit that this is the first time anyone has accepted the
challenge. I, for one, don't expect the challenger to execute everything
perfectly. The wording is absolutely fine. No one can send him _a_ file and
_a_ decompressor and still compress the file. It's that plain and simple.
The wording is absolutely 100% fine.

So, Patrick essentially proved that someone can be tricked. Nice.

"Phil Norman" <Phil....@genedata.com> wrote in message
news:slrn9doab9.6g...@jalua.ch.genedata.com...

Remzi Seker

unread,
Apr 17, 2001, 10:44:31 AM4/17/01
to
You can not compress a pure random data. However, even the randon number
generators have some statistical underlying dependence, so one may achieve
some compression, depending on how bad the randon number generator is.
Remzi

"Patrick Craig" <pat...@nag-j.co.jp> wrote in message
news:3ADACD0D...@nag-j.co.jp...

s...@nospam.unt.edu

unread,
Apr 17, 2001, 11:13:09 AM4/17/01
to
Joshua Schmier <jsch...@bellsouth.net> wrote:

> He did use some bit of trickery to get there, though. Goldman should have
> had some rest, he probably wouldn't have slipped up if he had. Trickery is
> distasteful regardless of the context. :)

Oh come on. Who was trying to trick who? Wasn't Mike trying to trick
some naive person into accepting a challenge that couldn't be met? So
Patrick out-tricked the tricker.... that's the thing that great tales
are made of.

Personally, I think it's a great story, and both people (Mike and
Patrick) seem to view it that way instead of as a serious/legal
matter. It wouldn't be amusing at all if lawyers got involved, and I
commend both of them for a mature approach to this incident (a few of
the whiners around here could certainly learn something from them).

SCOTT19U.ZIP_GUY

unread,
Apr 17, 2001, 12:07:31 PM4/17/01
to
jsch...@bellsouth.net (Joshua Schmier) wrote in
<N0WC6.152$yL1....@news4.mco>:

>He did use some bit of trickery to get there, though. Goldman should
>have had some rest, he probably wouldn't have slipped up if he had.
>Trickery is distasteful regardless of the context. :)

Then you live in a anal retentive world. The world does not
conform to your rules. The bet was over file length period.
If it was otherwise when Mike sent the file of the desired length
he would have had to say for the contest to be as in the FAQ I am
sending a file of X data bits but I am also adding a number equal
to base two of the bits or byte length to account for the extra
information in the file. He did not. He and Pat both strictly used
the data length as length. Mike should pay up. At the very least
if Patricj gives Mike a break he should pay the 100 dollars back
plus 100 hunred dollars for the leason Mike should have learned.

>

>You must admit that this is the first time anyone has accepted the
>challenge. I, for one, don't expect the challenger to execute everything
>perfectly. The wording is absolutely fine. No one can send him _a_ file
>and _a_ decompressor and still compress the file. It's that plain and
>simple. The wording is absolutely 100% fine.
>

Then You can't read and exaimine what the true facts the emails show.

Dror Baron

unread,
Apr 17, 2001, 3:06:47 PM4/17/01
to
> Oh come on. Who was trying to trick who? Wasn't Mike trying to trick
> some naive person into accepting a challenge that couldn't be met? So
> Patrick out-tricked the tricker.... that's the thing that great tales
> are made of.
>
> Personally, I think it's a great story, and both people (Mike and
> Patrick) seem to view it that way instead of as a serious/legal
> matter. It wouldn't be amusing at all if lawyers got involved, and I
> commend both of them for a mature approach to this incident (a few of
> the whiners around here could certainly learn something from them).

Precisely my previous point.
Mike and Patrick now have something to laugh over
when having their beers :)

Dror

Dror Baron

unread,
Apr 17, 2001, 3:09:07 PM4/17/01
to

On 17 Apr 2001, SCOTT19U.ZIP_GUY wrote:
> >He did use some bit of trickery to get there, though. Goldman should
> >have had some rest, he probably wouldn't have slipped up if he had.
> >Trickery is distasteful regardless of the context. :)
>
> Then you live in a anal retentive world. The world does not
> conform to your rules. The bet was over file length period.
> If it was otherwise when Mike sent the file of the desired length
> he would have had to say for the contest to be as in the FAQ I am
> sending a file of X data bits but I am also adding a number equal
> to base two of the bits or byte length to account for the extra
> information in the file. He did not. He and Pat both strictly used
> the data length as length. Mike should pay up. At the very least
> if Patricj gives Mike a break he should pay the 100 dollars back
> plus 100 hunred dollars for the leason Mike should have learned.

I for one wouldn't be surprised if Patrick is
one of David's paid agents...

Probably the trick he used can be formulated as
a bijection, which is clearly the best compression
and/or cryptographic method ever devised by man :)

Dror

Dale King

unread,
Apr 17, 2001, 3:40:23 PM4/17/01
to
"Tim Tyler" <t...@cryogen.com> wrote in message news:GBxM4...@bath.ac.uk...
> Patrick Craig <pat...@nag-j.co.jp> wrote:
>
> : http://www.geocities.com/patchnpuki/other/compression.htm
>
> Pat: ``can I send you a compressor and several compressed files whose
> total file size is less than the original uncompressed file and
> from which I can regenerate the original uncompressed file''
>
> Mike:``Sure''

In addition to Joshua's pointing out the ambiguity of the word several,
there is also the question of the definition of "total file size". That
could easily be construed to also take into account the file header
information. One could also construe that to include the unused portion of
the last sector of the file, since that is part of the size of the file.

Quoting the FAQ, "If external information such as a file name, a number of


iterations, or a bit length is necessary to decompress the data, the bits
necessary to provide the extra information must be included in the bit count

of the compressed data." Since the file lengths for all of the 218 files is


necessary to decompress the data, the bits necessary to provide the extra

information must be included in the bit count of the compressed data. That
is the common, accepted method for computing compression ratio (except for
David), that was given in the FAQ where Patrick read about the challenge. I
see no place where Patrick asked that this be changed.
--
Dale King

Joshua Schmier

unread,
Apr 17, 2001, 4:15:52 PM4/17/01
to
Hey, I did say in previous threads that Pratrick gave us a good show. I was
just defending the legal standpoint the others ridiculously proposed. I
totally agree, this is a great story, but if anyone was expecting anything
real out of it, they're more deluded than anyone who honestly accepts the
challenge (see: those who believe Goldman should pay up).

History was made. Nothing was done or ever intended to be done. I'm both
elated and disappointed.

<s...@nospam.unt.edu> wrote in message
news:9bhmi5$7q5$1...@hermes.acs.unt.edu...

Joshua Schmier

unread,
Apr 17, 2001, 4:24:10 PM4/17/01
to
Pfft, you don't think Patrick tricked Goldman into accepting guidelines that
were unlike the original challenge? It seems like you're the one attempting
to conform the world to your rules. The challenge and bet were completely
different creatures, Patrick got to where he did merely by trickery (I'm not
defending that Goldmans bet was not a trick in itself). If you can't see
that then you're more deluded than I before thought.

I saw the e-mails. I saw the word compression in there many times. However,
no compression took place. The wording for the challenge is fine. The
loosely defined correspondence is where the mix up occured. (Intentionally
or no? I personally believe Patrick wanted the money and thought $100 was a
nice gamble since his rules were predefined and accepted, IMHO.)

"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message

news:908662A4AH110W...@207.36.190.226...

SCOTT19U.ZIP_GUY

unread,
Apr 17, 2001, 5:12:13 PM4/17/01
to
jsch...@bellsouth.net (Joshua Schmier) wrote in
<3E1D6.167$yL1....@news4.mco>:


>I saw the e-mails. I saw the word compression in there many times.
>However, no compression took place. The wording for the challenge is
>fine. The loosely defined correspondence is where the mix up occured.
>(Intentionally or no? I personally believe Patrick wanted the money and
>thought $100 was a nice gamble since his rules were predefined and
>accepted, IMHO.)

No there was no mix up in the emails. The emails was to clarify
the actaully rules. IN the emails mike allowed for nore files.


The bet was for string files sizes period. Besides just what do
you call compression. Since there are no real compressors for
gerneral files. Each one can only do some shuffling of file sizes.
No compressor really exist. So what the hell is your deination of
compressor. Do you know of any general compressors that can actaully
be count to make general files smaller no. The best they can do is
break even if there fully bijective that is.

Dale King

unread,
Apr 17, 2001, 5:53:42 PM4/17/01
to
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:908696BC5H110W...@207.36.190.226...

> jsch...@bellsouth.net (Joshua Schmier) wrote in
> <3E1D6.167$yL1....@news4.mco>:
>
> No compressor really exist. So what the hell is your deination of
> compressor. Do you know of any general compressors that can actaully
> be count to make general files smaller no.

I can't believe I have to explain this basic information to you.

No compressor can make all bit sequences smaller, which I am sure you agree
with.

A compressor can make a certain subset of all possible bit sequences
smaller. If certain sequences are known or presumed to be more likely to
occur then those can be targeted to be smaller. When one factors in the
probability of these being more likely then one can achieve compression
averaged over all files if they occur with those probabilities.

> The best they can do is
> break even if there fully bijective that is.

Sorry, but your permutation does not break even (unless one let you get away
with ignoring the file length). You can only break even (assuming all
sequences are equally likely) if you make no sequences smaller. By the
counting theorem, "if a lossless compression program compresses some files,
it must expand others"
--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 17, 2001, 6:34:44 PM4/17/01
to
Ki...@TCE.com (Dale King) wrote in <3adc...@news.tce.com>:

>No compressor can make all bit sequences smaller, which I am sure you
>agree with.

Yes you are honest about this one point.

>
>A compressor can make a certain subset of all possible bit sequences
>smaller. If certain sequences are known or presumed to be more likely to
>occur then those can be targeted to be smaller. When one factors in the
>probability of these being more likely then one can achieve compression
>averaged over all files if they occur with those probabilities.
>
>> The best they can do is
>> break even if there fully bijective that is.

Let me reword this in way you can understand. It can't break
even unless its bijective. I hope you had enough real logic
courses to understand this. But I doubt it.

>
>Sorry, but your permutation does not break even (unless one let you get
>away with ignoring the file length). You can only break even (assuming
>all sequences are equally likely) if you make no sequences smaller. By
>the counting theorem, "if a lossless compression program compresses some
>files, it must expand others"

Again as with bijective compression. Break even does not mean it makes
all files smaller maybe it does to you though. Suppose I have a program
that maps ever file to itself exceept file A and B. File A gets mapped
to file B and file A get mapped to file B. I would say the compression
discribed by the transform is a break even thing. You may not.


Yes if a lossless compression program compresses some files
if must expand others. ( assuming we are talking about general
file compressors) However if its your kind of compressor since it
fails to make full use of the file space it must expand even more
files than a simalar nonbijective compressor. Becasue of the gaps
introduced by your wasteful file compression that fails to use all
the data space the way normal files use it.

Tom Gutman

unread,
Apr 17, 2001, 7:28:00 PM4/17/01
to
"SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote in message
news:908561603H110W...@207.36.190.226...
> s...@nospam.unt.edu wrote in <9bf6iv$5p5$1...@hermes.acs.unt.edu>:
>
> >That said, as soon as I saw the request that multiple "compressed
> >files" be allowed, it was pretty obvious what game was going to
be
> >played. Unfortunately, Mike didn't see it coming, and didn't
object
> >to the "multiple files" requirement (in fact in an earlier
posting
> >here, I pointed out that you should require the decompressor and
data
> >to be bundled together in one file, and the size of that piece
should
> >determine the "compressed size").

> >
>
> So what is the bottom line in your view. Besides the fact Mike
was
> stupid and so eager for the 100 dollars that he allowed the
multiple
> files. I agree that he should have required one program which
internally
> must contain all info so that it expands to one file. But he did
not.
> So in your view should he pay the 5g's or not??
> The rules that both men agreed to was a series of files. The
total
> length being less that the random files. I think that means Mike
lost.
> Are people here going to vote. I would like to know what Gutman
and
> Matt have to say after they read the rules the two men agreed to
in
> there correspondse. Which explicitly allowed for many files.
>
> I already expect King to say Mike won since it obvous to him
that the
> length of a file is not the length but some number added to the
length.
>
>
As long as my name is mentioned here, although mostly it's all been
already said.

The analysis in the original thread still stands. The original
challenge remains unmet. It still has the weakness of allowing two
files (and therefor some additional information) but it is unlikely
that a combination of a sufficiently short decompressor and a
sufficiently long (but still practical) file can be found.

Mike got snookered into accepting a change in the rules. Why he did
not see the implications of multiple files is quite beyond me, but
that is what happened. But that's the heart of the situation --
once multiple files are allowed, there is no way to identify or
isolate the length information.

Patrick was clearly (beyond his statement) not interested in
actually collecting the money. He was quite conservative in
implementing his scheme. His scheme as implemented allows for
removing a byte in every 256 bytes -- about 12,000 bytes in a 3MB
file. He only did 200 bytes. Carried to an extreme, splitting the
file into segments could yield close to one extra bit per byte (but
the average file length would then be around two -- that means a
*LOT* of files). If he wanted to, he could have hidden the
underlying method by adding some fluff -- perhaps a MTF followed by
adaptive Huffman (which would do minimal expansion for
non-compressible files) would make to difficult to identify the
actual source of the compression (if the split were complete, the
Huffman coding could actually save a bit, as the segments then use
only 255 symbols).

As to who owes whom what, Patrick already relinquished claims to the
$5000, and even to the $100 fee. So nothing is legally or morally
owed. A gentlemen would return the $100, along with a case of wine
(or maybe just a case of very good wine).


I notice further down some nut nattering about bijections. I don't
see where bijections come into this and since the poster did not
explicate it seems completely nonsensical.


--
Tom Gutman

Tom Gutman

unread,
Apr 17, 2001, 7:35:47 PM4/17/01
to
"Dale King" <Ki...@TCE.com> wrote in message
news:3adb...@news.tce.com...
[snip]

>
> If the supposed new definition were allowed, I have already shown
how it can
> be done by using the archive and readonly flags from a large
number of
> files.
>
I would reject that, since the resulting files would not be normal
files and would not withstand the normal vicissitudes of file
maintenance. The archive bits disappear at the next backup, and the
read only bits do not survive copying to CD-ROM medium.

If you really want some extra information from the file system, I
would recommend the last modified date. That provides considerably
more bits, is generally kept intact by file maintenance routines,
has no functional implications, and is already used in some cases to
store extra information (such as Windows version).

However any of this puts you in the context of a specific file
system with whatever its specific facilities and quirks. The scheme
actually used requires nothing more than the standard abstraction of
a file -- a finite sequence of bytes.


--
Tom Gutman

Tom Gutman

unread,
Apr 17, 2001, 7:41:40 PM4/17/01
to
"Dale King" <Ki...@TCE.com> wrote in message
news:3adc...@news.tce.com...
I would like to point out that the files used came with only byte
lengths, not bit lengths. There is a reason why the FAQ
specifically specifies "bit length" and not just "length".


--
Tom Gutman

Phil Norman

unread,
Apr 18, 2001, 3:35:54 AM4/18/01
to
On Tue, 17 Apr 2001 13:24:10 -0700,
Joshua Schmier <jsch...@bellsouth.net> wrote:
>
>I saw the word compression in there many times. However, no
>compression took place.

The word 'compression' is a poorly chosen one anyway. It implies
that a so-say 'compressor' will make information take up less
storage space. This is not, in general, the case.

It is, in fact, possible to devise a storage medium in which
multiple files take up no extra storage space. For example, if my
filesystem stores 9 bits per byte, and sets the high bit to '1'
only when this byte is the start of a new file. Unlikely, yes,
and not a particularly useful storage system, but in this case
such a compressor, using multiple files, would be a good way to
pack the information.

Anyway, that's not the point at all. It was a good joke - I
enjoyed it a lot.


>The wording for the challenge is fine.

Wrong. The wording of the challenge allows for two files, a
decompressor and a file containing compressed data. That
'expansion' of one file to two in itself ignores the principle of
per-file overhead within the filesystem. Yes, with a large file
(and considering the size of the smallest piece of code possible
for reassembly - see Patrick's aforementioned URL for examples)
this expansion of filesystem overhead (and its inherent ability to
store information about the length of files without adding to the
perceived file length) is irrelevant. However, the principle was
not mentioned.


>loosely defined correspondence is where the mix up occured. (Intentionally
>or no? I personally believe Patrick wanted the money and thought $100 was a
>nice gamble since his rules were predefined and accepted, IMHO.)

Did you read the web page which Patrick posted? I won't bother
requoting it; see my previous post on the subject.

Cheers,
Phil

Mikael Lundqvist

unread,
Apr 18, 2001, 4:36:53 AM4/18/01
to
>===== Original Message From "Matt Timmermans"
<ma...@timmermans.nospam-remove.org> =====

>And what do you mean he wasted all of our time? What were you reading the
>thread for? We know that you can't compress random data, Mike knows it, and
>Patrick knows it. Nobody was expecting a miracle, so what were you hoping
>for that you didn't get here?
>
One might just wonder why some individuals are so inclined to return to
these
so utterly hopeless issues.
I suppose solving real problems like how to make PPM faster/better/more
efficient is too much of a challenge...

Regards,

Mikael Lundqvist
mailto:mikael.l...@spray.se
http://hem.spray.se/mikael.lundqvist/
Occum's Razor:
"The simplest solution is probably the correct one."

Mikael Lundqvist

unread,
Apr 18, 2001, 4:48:28 AM4/18/01
to
>===== Original Message From Dror Baron <dba...@chopin.ifp.uiuc.edu> =====
> ...

>I for one wouldn't be surprised if Patrick is
>one of David's paid agents...
>
Extremely funny!

>Probably the trick he used can be formulated as
>a bijection, which is clearly the best compression
>and/or cryptographic method ever devised by man :)
>

Data security problems (not just cryptography) are part of Computer Science
because they ARE a problem (unlike compressing random data). Viruses,
hackers,
fire ... the list continue.
The greatness in David's ideas may be debatable but even the slightest
improvement is still an improvement, isn't it?

Keep an open mind,

Phil Norman

unread,
Apr 18, 2001, 4:52:46 AM4/18/01
to
On Wed, 18 Apr 2001 01:00:46 -0700,
Joshua Schmier <jsch...@bellsouth.net> wrote:
>
>Give me an example where two files can be exploited to hide data in a
>current filesystem. If you can do that then I will conceed the argument that
>the wording itself is flawed.

Have you read the web page mentioned at the start of this thread?
It describes exactly how one can hide information in the file
length entry of a filesystem. The example given splits one file
into roughly 250 parts, but the principle holds for splitting into
2 parts.

Cheers,
Phil

Joshua Schmier

unread,
Apr 18, 2001, 6:11:07 AM4/18/01
to
How can that be? You still need space to store the decompression script. The
probablity of finding a sequence of bytes within a file that matches the
last bytes of the file is near zero. It would require a huge file to
compress the data in this fasion. So huge in fact, I do not think current
hard drives or file systems could hold it.

"Phil Norman" <Phil....@genedata.com> wrote in message

news:slrn9dqleu.hi...@jalua.ch.genedata.com...

Phil Norman

unread,
Apr 18, 2001, 6:31:39 AM4/18/01
to
On Wed, 18 Apr 2001 03:11:07 -0700,

Joshua Schmier <jsch...@bellsouth.net> wrote:
>"Phil Norman" <Phil....@genedata.com> wrote in message
>news:slrn9dqleu.hi...@jalua.ch.genedata.com...
>> On Wed, 18 Apr 2001 01:00:46 -0700,
>> Joshua Schmier <jsch...@bellsouth.net> wrote:
>> >
>> >Give me an example where two files can be exploited to hide
>> >data in a current filesystem. If you can do that then I will
>> >conceed the argument that the wording itself is flawed.
>>
>> Have you read the web page mentioned at the start of this thread?
>> It describes exactly how one can hide information in the file
>> length entry of a filesystem. The example given splits one file
>> into roughly 250 parts, but the principle holds for splitting into
>> 2 parts.
>How can that be? You still need space to store the decompression script. The
>probablity of finding a sequence of bytes within a file that matches the
>last bytes of the file is near zero. It would require a huge file to
>compress the data in this fasion. So huge in fact, I do not think current
>hard drives or file systems could hold it.

Hello? Read the web page with which this thread began! Read also
my posting two times ago (which you followed up to), where I
specifically mention that the saving which can be had by splitting
a file into just two parts would not offset the size of the
decompression script. Wake up, drink some coffee, whatever, just
please read and try to understand before reiterating what I've
already said, or claiming that the idea behind the *working
implementation* that started this thread could not possibly work.
I'm out of patience; if you continue talking rubbish I'll just
ignore your postings.

Cheers,
Phil

Patrick Craig

unread,
Apr 18, 2001, 7:27:30 AM4/18/01
to

> >===== Original Message From "Matt Timmermans"
> <ma...@timmermans.nospam-remove.org> =====
> >And what do you mean he wasted all of our time? What were you reading the
> >thread for? We know that you can't compress random data, Mike knows it, and
> >Patrick knows it. Nobody was expecting a miracle, so what were you hoping
> >for that you didn't get here?
> >
> One might just wonder why some individuals are so inclined to return to
> these
> so utterly hopeless issues.
> I suppose solving real problems like how to make PPM faster/better/more
> efficient is too much of a challenge...

What's the prize money for solving these problems?

Mikael Lundqvist

unread,
Apr 18, 2001, 8:14:37 AM4/18/01
to
>===== Original Message From pat...@nag-j.co.jp (Patrick Craig) =====

>> >===== Original Message From "Matt Timmermans"
>> <ma...@timmermans.nospam-remove.org> =====
>> >And what do you mean he wasted all of our time? What were you reading the
>> >thread for? We know that you can't compress random data, Mike knows it,
and
>> >Patrick knows it. Nobody was expecting a miracle, so what were you hoping
>> >for that you didn't get here?
>> >
>> One might just wonder why some individuals are so inclined to return to
>> these
>> so utterly hopeless issues.
>> I suppose solving real problems like how to make PPM faster/better/more
>> efficient is too much of a challenge...
>
>What's the prize money for solving these problems?
>
If your solution is good, better than most, I'm sure some will pay money for
using your software.
But making computing better should be reason enough. (just ask the
scientists)
What is the use in discussing something we all know is a waste of time?
Random data can't be compressed!!! This should be reason enough to end this
discussion.

Regards,

George Johnson

unread,
Apr 18, 2001, 9:58:56 AM4/18/01
to
"Remzi Seker" <re...@norm.dpo.uab.edu> wrote in message
news:9bhkj2$eio$1...@SonOfMaze.dpo.uab.edu...

| You can not compress a pure random data. However, even the randon number
| generators have some statistical underlying dependence, so one may achieve
| some compression, depending on how bad the randon number generator is.
| Remzi

Actually, I disagree. A pure random data compressor that works efficiently
on ONLY random data should be able to exist. The downside is that it would be
entirely worthless for non-random data and probably rather slow on the Kilobyte
per minute rate. It also wouldn't compress near-random data very well (like
the kind found in ordered compression files).

There should always be an inverse to any function.

Patrick BROSSET

unread,
Apr 18, 2001, 10:11:46 AM4/18/01
to
hi

i agree !

Patrick

"George Johnson" <matr...@voyager.net> wrote in message
news:3add9f23$0$18890$272e...@news.execpc.com...

SCOTT19U.ZIP_GUY

unread,
Apr 18, 2001, 10:21:07 AM4/18/01
to
mika...@MailAndNews.com (Mikael Lundqvist) wrote in
<3AE5...@MailAndNews.com>:

>>===== Original Message From pat...@nag-j.co.jp (Patrick Craig) =====
>>> >===== Original Message From "Matt Timmermans"
>>> <ma...@timmermans.nospam-remove.org> =====
>>> >And what do you mean he wasted all of our time? What were you
>>> >reading the thread for? We know that you can't compress random
>>> >data, Mike knows it,
>and
>>> >Patrick knows it. Nobody was expecting a miracle, so what were you
>>> >hoping for that you didn't get here?
>>> >
>>> One might just wonder why some individuals are so inclined to return
>>> to these
>>> so utterly hopeless issues.
>>> I suppose solving real problems like how to make PPM
>>> faster/better/more efficient is too much of a challenge...
>>
>>What's the prize money for solving these problems?
>>
>If your solution is good, better than most, I'm sure some will pay money
>for using your software.

Don't count on the money, Just like with Mike you most likely
would never see a penny. First of all IBM would use there over
paid lawyers saying you infringed on an existing patent. Of course
it would be a lie but money is what counts in this game not honesty
as you are already leraning.

>But making computing better should be reason enough. (just ask the
>scientists)

This is a good reason but don't expect your name to go down in
history since odds are some one else will get credit for the idea.
But for ones on satisfacation go ahead.

>What is the use in discussing something we all know is a waste of time?
>Random data can't be compressed!!! This should be reason enough to end
>this discussion.

Actually this is a good discussion why should the thread end
I think some may actually learn something.

Dale King

unread,
Apr 18, 2001, 10:31:45 AM4/18/01
to
"Tom Gutman" <Tom_G...@compuserve.com> wrote in message
news:9bijtb$os4$1...@sshuraaa-i-1.production.compuserve.com...

> "Dale King" <Ki...@TCE.com> wrote in message
> news:3adb...@news.tce.com...
> [snip]
> >
> > If the supposed new definition were allowed, I have already shown
> how it can
> > be done by using the archive and readonly flags from a large
> number of
> > files.
> >
> I would reject that, since the resulting files would not be normal
> files and would not withstand the normal vicissitudes of file
> maintenance. The archive bits disappear at the next backup, and the
> read only bits do not survive copying to CD-ROM medium.
>
> If you really want some extra information from the file system, I
> would recommend the last modified date. That provides considerably
> more bits, is generally kept intact by file maintenance routines,
> has no functional implications, and is already used in some cases to
> store extra information (such as Windows version).

Good point! But my general point was that if you are allowed to make use of
information in the file header it is trivial to simply produce a gazillion
files all of which have zero "length". According to David's logic if I
shrink a file down to zero length it has no information and therefore I
don't have to count it.

> However any of this puts you in the context of a specific file
> system with whatever its specific facilities and quirks. The scheme
> actually used requires nothing more than the standard abstraction of
> a file -- a finite sequence of bytes.

I make no distinction between the file length or any part of the header. If
it is outside of the data portion of the file and it is necessary for
decompressing you have to count it. That is what I keep trying to get David
to understand.
--
Dale King

Dale King

unread,
Apr 18, 2001, 10:35:57 AM4/18/01
to
"Tom Gutman" <Tom_G...@compuserve.com> wrote in message
news:9bik8c$qqs$1...@sshuraac-i-1.production.compuserve.com...

>
> I would like to point out that the files used came with only byte
> lengths, not bit lengths. There is a reason why the FAQ
> specifically specifies "bit length" and not just "length".

No, a file length IS a bit length! Multiply by 8 and you have the bit length
of the file.

The reason the FAQ says bit length is that it covers both lengths with bit
resolution or those with only byte resolution.
--
Dale King

Dale King

unread,
Apr 18, 2001, 10:48:33 AM4/18/01
to
"Tim Tyler" <t...@cryogen.com> wrote in message news:GBz9B...@bath.ac.uk...
> Dale King <Ki...@tce.com> wrote:
> : "SCOTT19U.ZIP_GUY" <david_...@emailv.com> wrote:
>
> :> The best they can do is break even if there fully bijective that is.

>
> : Sorry, but your permutation does not break even (unless one let you get
away
> : with ignoring the file length). You can only break even (assuming all
> : sequences are equally likely) if you make no sequences smaller. By the
> : counting theorem, "if a lossless compression program compresses some
files,
> : it must expand others"
>
> I'd say a compressor that produced no average change in the length of
> files of any specified size was "breaking even".
>
> What makes you think "you can only break even ... if you make no
> sequences smaller"...?

First off let's not use the word files. And forgive me for not being
precise. What I really should have said was smaller than the entropy of the
data source. If you encode any sequence in less bits than the entropy of the
source you will have to expand others. The amount of expansion will be
larger than the amount saved, so you will actually increase the average
compressed length. The only way to break even is to map all sequences to a
sequence equal in length to the entropy of the source. You cannot do any
better than that when averaging over all sequences that can be generated by
the source. See the FAQ and the counting theorem.

As I said above though that assumes that all sequences are equally likely.
That is not usually the case.

--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 18, 2001, 10:53:17 AM4/18/01
to
I am one to pay off barroom bets. And this whole thread has my
interest so I am willing to step in and offer 50 american dollars
to Patrick if he can met my challenge by end of May. At that time
any one else is elgible to win by end of June. If no one solves
it. It may mean that the only solution is no solution.

Here is my contest. I have not checked what what you sent so
you may already be a winner. If your a winner its OK becasue it
proves that random.org is generating long strings thare are not
very complex according to K ( i can't spell or pronounce it anyway)
theory. It also implies that the random data my be a front for
groups such as the NSA.

take the "current random file that was used in last contest"
Use my code to add the number "zero". This just tacks a long
value of zero to file 32 bits of zero. Than run DSC to meld
the length to the previously given random file. It will change
the original file by a few bytes. It could even get shorter.
Take this new length call it X. However it will get no longer
than 4 more than the oringal file.

The goal is to archive the files you used together to a single
file and see if this resulting file is less than X bytes long.
data can't be hidden in file name flags all data used must be
in the file. However that archive is only data no file names are
in it except in your script.

First step in build archive. This is a First in Last out type
of archive. So just like the original data file to the program
add a long zero than run DSC. The output file is the archive
at this point. Next take the first data file you use add it to
the acrhive by appending the archive file to the end of the
data file. Then write a long to end of file and run DSC again
to get new archive.
Repeat for each addition data as stated here.
Append the archive to the current data file add long
value to end of current file. Then run DSC to creat new
archive file.
At this point you should have a 8-bit byte type of file that sort of
contains the complexity of the orginal file. If this resulting
file can be made shorter than X you win.

First let me say DSC bijectively combines a number to a file
the number is in range of 0 to N-1 where N is number of bytes
in the file. For the pusposes of archiving. Any 8-bit binary
file can be thought of as a file of N bytes with a pointer of
0 to N-1 attached. Therefor one can consider any file an acrhive
file. If the pointer is zero in value then there is only one
file in the archive. If not zero then the first N bytes can
be thought of as first file out of archive and UNDSC takes
number from the file leaving at end as a long. You then have
to remove the long from end of file to check for more files
to be removed.


Any questions or thoughts that need to be cleared up?

Dale King

unread,
Apr 18, 2001, 10:58:52 AM4/18/01
to
"Mikael Lundqvist" <mika...@MailAndNews.com> wrote in message
news:3AE2...@MailAndNews.com...

> Data security problems (not just cryptography) are part of Computer
Science
> because they ARE a problem (unlike compressing random data). Viruses,
> hackers,
> fire ... the list continue.
> The greatness in David's ideas may be debatable but even the slightest
> improvement is still an improvement, isn't it?
>
> Keep an open mind,

Unfortunately one must make sure that any attempt at improvement is grounded
in correct science and mathematics. In computer science that is information
theory and computational theory. It is wrong to let someone ignore the
basics of those using a sleight of hand to disprove what has already been
established to be fact. The counting theorem for instance is proven. It
can't be disproved. That is why it is a theorem. Note the difference between
a theorem and a theory. Theorems are proven facts, theories are hypotheses.

I think I've lost what my point was.

Note I have explained the encryption benefits that David gets in a way that
does not rely on a permutation compressor. The key is simply don't compress
the length information with the data.

--
Dale King

SCOTT19U.ZIP_GUY

unread,
Apr 18, 2001, 11:03:10 AM4/18/01
to
Ki...@TCE.com (Dale King) wrote in <3add...@news.tce.com>:

>Good point! But my general point was that if you are allowed to make use
>of information in the file header it is trivial to simply produce a
>gazillion files all of which have zero "length". According to David's
>logic if I shrink a file down to zero length it has no information and
>therefore I don't have to count it.

Actually for my BIJECTIONS I don't include the NULL file.
However I don't think the contest was structured so that they
were rulled out. I think Patrick could have used Empty files
if he wished to. In My challenge of today empty files are
ruled out.

>I make no distinction between the file length or any part of the header.
>If it is outside of the data portion of the file and it is necessary for
>decompressing you have to count it. That is what I keep trying to get
>David to understand.

Even DOS text files don't have the length in the data protion
of file. Why on earth would one force a compressed file to include
such data that other files don't have, Especailly since the goal
of the compressor is to make the file shorter. You seem to be
forgetting what compression of files is meant to be or not to be.

SCOTT19U.ZIP_GUY

unread,
Apr 18, 2001, 11:14:50 AM4/18/01
to
Ki...@TCE.com (Dale King) wrote in <3add...@news.tce.com>:

>"Tom Gutman" <Tom_G...@compuserve.com> wrote in message

Actually the FAQ does not go far enough. It really should have
only one basis for the length. A good base where all files of
any byte sizes of 1 to n bits. Is the distance to the last "one"
bit used in the infinitely finite odd file. One could easly
take an input file and find the distance to last one after
it is converted to a infinite file that is finitely odd as well
as one could take the distance of converted compressed file to
find the distance to last one bit in this converted format.
Multiply a byte file by 8 to get the number of bits. Does not
really compare to a sting of that many bits since there are
string of bits that are not multiplies of 8. Come on King use
your mind.

Dror Baron

unread,
Apr 18, 2001, 1:43:59 PM4/18/01
to
On Wed, 18 Apr 2001, George Johnson wrote:

> Actually, I disagree. A pure random data compressor that works efficiently
> on ONLY random data should be able to exist. The downside is that it would be
> entirely worthless for non-random data and probably rather slow on the Kilobyte
> per minute rate. It also wouldn't compress near-random data very well (like
> the kind found in ordered compression files).
>
> There should always be an inverse to any function.

That data was generated by hardware measurements and then
unbiased. If you guys sincerely think that "function" has
an inverse, you need to consult medical and not scientific
people.

Dror

Mikael Lundqvist

unread,
Apr 18, 2001, 1:58:35 PM4/18/01
to
>===== Original Message From "Dale King" =====
> ...

>Unfortunately one must make sure that any attempt at improvement is grounded
>in correct science and mathematics. In computer science that is information
>theory and computational theory. It is wrong to let someone ignore the
>basics of those using a sleight of hand to disprove what has already been
>established to be fact. The counting theorem for instance is proven. It
>can't be disproved. That is why it is a theorem. Note the difference between
>a theorem and a theory. Theorems are proven facts, theories are hypotheses.
>
You're correct of course!

>I think I've lost what my point was.
>

Maybe it's time to move on?

>Note I have explained the encryption benefits that David gets in a way that
>does not rely on a permutation compressor. The key is simply don't compress
>the length information with the data.
>

You and Mr Scott should have a beer or two together
some day and have a great laugh about it.
You two seem to have a lot in common.

Peace,

Dror Baron

unread,
Apr 18, 2001, 2:04:37 PM4/18/01
to
On Wed, 18 Apr 2001, Patrick Craig wrote:

> > One might just wonder why some individuals are so inclined to return to
> > these
> > so utterly hopeless issues.
> > I suppose solving real problems like how to make PPM faster/better/more
> > efficient is too much of a challenge...
>
> What's the prize money for solving these problems?

If you want to play "hide the information in the
header" preschool games, the payoff will be small.

If you have serious contributions:
1. Compression superior to PPM / BWT with LZ-like
complexity in software.
2. Compression similar to PPM / BWT in hardware.
In these cases the payoff could be nice.

Mikael wants us to stop playing games and start
coming up with real ideas.

Dror

Dale King

unread,
Apr 18, 2001, 2:25:29 PM4/18/01
to
"George Johnson" <matr...@voyager.net> wrote in message
news:3add9f23$0$18890$272e...@news.execpc.com...

I agree with what you meant, but your terminology and understanding of
information theory is a bit wrong. There really isn't such a thing as random
and non-random data. There are random and non-random data sources. It is
impossible to compress all data from a random source. What presumably you
are talking about is data that has no patterns to it. In other words all
symbols appear with equal frequency and sequences of symbols do not repeat,
etc. If you had a source that emitted sequences that were always or even
usually like this then you can compress that because the entropy is lower
than the size of the messages. You are saying that it will never generate a
sequence consisting of all the same symbol or at least its likelihood is
much lower than that of any other sequence. That is not however a random
source. A random source generates all seuences with equally likelihood.

> There should always be an inverse to any function.

All functions have inverse relationships, but that inverse relationship may
not be a function. Many functions do not have an inverse function: f(x) =
x^2; g(x) = 0; ceil(x); abs(x); signum(x) to