From mboxrd@z Thu Jan  1 00:00:00 1970
Message-ID: <843c8d7c852ad56be010ea390aed5cf1@quanstro.net>
To: 9fans@cse.psu.edu
Subject: [9fans] thoughs about venti+fossil
From: erik quanstrom <quanstro@quanstro.net>
Date: Wed,  5 Mar 2008 09:03:58 -0500
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Topicbox-Message-UUID: 6f55eb3c-ead3-11e9-9d60-3106f5b1d025

> >> http://www.nmt.edu/~val/review/hash/index.html
> >>
> >> Not that this analysis is without flaws, though.
> >
> > have you invented the 9fans.net effect?
>=20
> Meaning? I guess the reference went over my head.

the link was inaccessable when i tried to access it.
i figured the combined traffic of 9fans brought it down. ;-).

> > this link may or may not be similar.  but it is on point:
> > http://www.valhenson.org/review/hash.pdf
>=20
> I believe it to be exactly the same paper.
>=20
> > do you care to elaborate on the flaws of this analysis?
>=20
> I tend to agree with counter arguments published here:
>     http://monotone.ca/docs/Hash-Integrity.html
> I'm not an expert in this field (although I dabbled
> in cryptograhy somewhat given my math background) and
> thus I would love if somebody can show that the
> counter arguments don't stand.
>=20

the analysis in =C2=A74.1 is just wrong.  pedanticly, i can't get
past the fact that the paper talkes about "sha-1(1)" and
"sha-1(x), x>0".  i'm not sure what that means since sha-1
operates on blocks not integers.  but the real problem is
that the author doesn't appear to understand
"cryptograpically strong".  the invented function may have
the same probability of collision as sha-1, but it is not
cryptographically strong.

also, i think the author doesn't fully appreciate the
power of really big numbers.  you'd need 10^(12+3.2)/2
tb hard drives *full of data* to have a reasonable chance
of a hash collision with 8k blocks.  at $250 each, this
would cost 2.48e17 dollars.

i'm pretty sure that there are other limits in venti that
kick in before 9000 yottabytes.  that's not in standard
si form because yotta is the biggest si prefix i can find.

i think that venti has a different problem.  indexing by
sha-1 hash trades time and index lookups for space.
but disk space is cheep relative to our needs and table
lookup and fragmentation that venti implies results
in a lot of random i/o.  modern disks are at least 25x
faster doing sequential i/o.

- erik