Tell me more ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 3 down vote favorite

I've been reading about git in Apress' "Pro Git" book. It mentions that SHA-1 is used to detect changes to commits and also to verify there is no corruption during pulls from the server. I am aware of the message digest detecting change, but how is it checking and presumably correcting for corruption ? The Wikipedia page for SHA-1 does not mention features like CRC.

Thanks,

Scott

share|improve this question

3 Answers

up vote 3 down vote

It's basically like CRC, only with a much wider result space so there's less chance of a collision. This is actually done pretty frequently with cryptographic hashing and open-source projects. I'll often see a download site that says "here's the link, and here's a MD5 hash and here's a SHA hash, so you can verify the download's integrity.

share|improve this answer
Ok, I understand that the hash is a (hopefully) unique and not collided signature for the file that can notify if modifications have been made, but does it contain information that can be used to fix corruption, like CRC ? – Scott Davies Mar 15 '11 at 16:43
1  
@Scott: I've never heard of CRC containing error-correcting information, and the Wikipedia article on it doesn't say anything about that either. AFAIK CRC, like stronger hashing, is only useful for detecting errors. They can then be corrected by requesting a new copy, assuming of course that the original is still correct. – Mason Wheeler Mar 15 '11 at 16:49
up vote 0 down vote

Basically, every time you get a cryptographic hash (message digest) from the same set of bytes it will always be the same result. The important aspect is that if one bit is off, the message digest will be very different.

When GIT performs a data transfer it also passes the message digest for the affected files along with the files themselves. The client runs the cryptographic hash again and compares it's calculation with the one provided by the server. If they don't match, it asks for the content again.

share|improve this answer
So it only detects corruption and does not contain the correcting code to fix it ? I would guess that in this case it pulls the ENTIRE file again, instead of being able to fix the problem ? – Scott Davies Mar 15 '11 at 16:44
That is correct. In this case the cost to retransmit the changes is fairly low compared with adding in extra parity bits ala CRC. – Berin Loritsch Mar 15 '11 at 16:45
up vote 0 down vote

I am not certain about the specific technology you are using but this concept may aide in your understanding. (Though you may already understand this)

Key Concept: The same source put into a hash (SHA-1) will always get out the same result.

So before the transfer the source is put through the SHA-1 and the result is sent over. When the receiver gets the source and its SHA-1 result, the received source is put through SHA-1 and the result is checked with the received result. If they differ then a change, error has occurred and steps can be taken to remedy it.

AFAIK the only efficient way to remedy (correct) the corruption it is to request the information again.

share|improve this answer
Ah, ok. Requesting again seems inefficient compared to the CRC from years back (like CRC32, etc. with xmodem, xmodem, kermit, etc.). – Scott Davies Mar 15 '11 at 16:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.