bugmonotone - Bugs: bug #12900, Hash collision handling

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #12900: Hash collision handling

Submitted by:  Jozef Behran <jojoworks>
Submitted on:  Fri 29 Apr 2005 11:30:52 AM UTC  
 
Category: storage systemSeverity: 3 - Normal
Item Group: incorrect behaviorStatus: Invalid
Privacy: PublicAssigned to: None
Open/Closed: Closed
mtn version --full: 

Fri 29 Apr 2005 07:50:44 PM UTC, comment #2:

I'm sorry for not taking the monotone's distributed nature into my considerations when suggesting the fix. Now I see that it is really unfeasible to assign these IDs when the development is being distributed.

So I would like to ask a simple question only: What will monotone do if it is faced to a true hash collision (when both colliding data chunks are on the local machine)? Disrupts the database silently or aborts with an error so the user is warned that he is hitting the odd corner of the hashing probability?

If the former is the case, updating the monotone's behavior to the latter case would increase reliability without losing all the properties. All that needs to be done is when writing something that is hashed into the database and the hash is already stored in the database, check if the thing in the database is really the same as the thing being stored and if not, issue an error and abort. This can be done no matter how the things to be written have been obtained. This will not catch ALL collisions, because that would break the netsync (when one of the colliding things is on one host and the other on another; netsync simply assumes that such things are already the same and will not try to sync them) but will catch those collisions which happen on the same machine (and which could distrupt the commit being done on the local machine for example).

If the latter is the case, then this bug is really invalid. However in that case there should be a notice in the documentation that monotone tries to avoid all such avoidable collisions and how it tries to avoid them. For example http://article.gmane.org/gmane.comp.version-control.monotone.devel/2920 presents some points about this issue which are worth adding into the "Hash integrity" chapter of the manual so at least the people which read manuals first (I'm among them) get it right.

And another stupid question: Is it possible to collide for example a file content with a revision, for example? I suppose, that the answer is "no", because the files, the changesets, the revisions and the merkle nodes can be stored in different pools of the database preventing them from colliding.

Jozef Behran <jojoworks>
Fri 29 Apr 2005 06:28:24 PM UTC, comment #1:

I'm afraid this proposal won't work for a number of reasons. It actually won't work even for things like file ids, because of monotone's distributed nature -- since if the colliding files were generated on different machines, they would probably both end up with the same serial number as well; you could use random nonces instead of serial numbers, but then you're back to relying on probability, and this whole discussion assumes that we don't believe in probability.

Worse than that, though, is the many places in which monotone exactly depends on the algorithmic properties of hashing to do things that are otherwise impossible. Netsync can synchronize two dozens of megabyte databases in just a handful of bytes of network traffic, without keeping any state ahead of time. This is too important a property to give up because of unsupported worries about hash collisions, and it is not possible to achieve this without using hashes.

http://article.gmane.org/gmane.comp.version-control.monotone.devel/2920
has a more full discussion of the issues, and a description of a more workable method to protect against collisions. If you're worried about this case, then helping re-implement 'vcheck's as described there would be a good way to help.

Nathaniel Smith <njs>
Project Member
Fri 29 Apr 2005 11:30:52 AM UTC, original submission:

I'm somewhat concerned about the hash collision handling. Though extremely unprobable, it can cause serious failure leading to undetectable data corruption if it occurs. From the manual and the design of the content identifiers I deducted that you are trusting the hash blindly to make no collisions on the "normal inputs" instead of preparing the code for the possible eventuality of the hash clash. I didn't read your sources but I suppose that in the case of a hash clash these things can occur:

1. The clashing content of the file is overwritten in the database. This leads to corruption of the content of the other files which is different but has the same hash value as the one being written. I guess this is the thing that will happen since it is too easy to compute the hash first and compare the content only when the hashes are different.

2. The clashing content of the file is not overwritten. This means that the changes of the offending file are lost.

3. The commit is aborted with some sort of internal error.

The idea to solve this issue is very simple. Extend the content identifier to contain some sort of serial number (the identifier should have the form of <HASH><SERIALNO>, not <SERIALNO><HASH> as most if not all <SERIALNO> values will be the same). When writing the content of the database compute the hash first. Then search the database for the hash. If no such hash is there, set the serialno to zero and write the content into the database. If the hash is there, search the contents that are already stored for that hash value. If the content being stored is among them, take the serialno of the content and you have the ID for the content being stored. If it is not there, pick an unused serialno (for example set the serialno to the count of the datachunks with the same hash already present in the database) and store the content using the hash and picked serialno.

This way you are 100% safe from any database corruptions from hash clashes. Another important thing is that this way the monotone can be used as a check of the secure hash power (by simply letting the system to run for a while and then asking users to tell their monotone installations to search the databases for collisions).

Jozef Behran <jojoworks>

 

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

Do you think this task is very important?
If so, you can click here to add your encouragement to it.
This task has 0 encouragements so far.

Only logged-in users can vote.

 

Please enter the title of George Orwell's famous dystopian book (it's a date):

 

 

Follow 2 latest changes.

Date Changed By Updated Field Previous Value => Replaced By
Fri 29 Apr 2005 06:28:24 PM UTCnjsStatusNone=>Invalid
  Open/ClosedOpen=>Closed

Back to the top


Powered by Savane 3.1-cleanup1