Re: [Monotone-devel] Hash collisions resiliency

[William Uther]

Hi,
  I'm a little confused here.  People are saying that hash collisions 
are hard to detect - that you'd have to do a full-text check of all the 
files.  That doesn't seem right.  Couldn't you just have a table of 
hashes in the database.  When you add a new hash, you add it to the 
table.  If it is already there, *THEN* you do a full-text check of the 
two files with the matching hashes.  If the two files actually are the 
same, then you're ok.  If the two files are different, you have a 
problem, *and* you have detected it.

  The inverse problem, having two of the same file that have different 
hashes, is the one that would require full text checking, right?  And 
that is impossible with a deterministic hash algorithm.

  Of course, you might have a distributed hash collision - two 
machines, each of which with a distinct file, but the files have the 
same hash.  This would not be detected until the data was sent between 
the machines, but it could be trivially detected at that point.

  I must admit I'm new to monotone, so I might be misunderstanding 
something here...

Cheers,

Will        :-}

--
Dr William Uther                           National ICT Australia
Phone: +61 2 9385 6357               Computer Science and Engineering
Email: address@hidden          University of New South Wales
Web: http://www.cse.unsw.edu.au/~willu/     Sydney, Australia