Why SHA are 40 bytes? (aka looking for flames)

Well, why to store always the full length SHA?

I know that looking at the code it is better then asking, but indeed asking is better then guessing and in my case looking at the scary sha low level code is almost like (bad) guessing.

We use 40 bytes to disambiguate two unlucky revisions or it is due to UI concerns?

In case it is the former does this apply?

40bytes-sha1 + 40bytes-sha2 == 7**bytes-sha1 + 7bytes-sha2 + "a way to disambiguate the two"*

(*) as example calculating on the fly the full length sha in the unlikely event it is needed, or storing complete 40bytes sha when needed.

(**) 7 is my lucky number ;-)

If in the packed tree truncated sha are stored, togheter of course with corresponding revision data, does it is enough to keep the *same* information of a complete pack?

For performance reasons, probably the inflating should be done only when necessary, it means all git code should use shrinked sha-s, leaving inflating as a remote and unlikely event. What are the real walls about using small length sha everywhere in git code?

Ok. It's enough for collecting a long list of very bad answers. I think I've done my day now!

Thanks for your *kind* reply Marco

On Saturday 2007, April 21, Marco Costalba wrote:

Well apart from being easier than working out the optimum size for every single object write, one really good reason would be that there is no way to predict that an object in the future won't have a conflicting SHA - every object /has/ to be stored with its full hash, because you are preventing conflicts with everything object now, in the past and all possible futures.

Wow - git is like a time machine.

Andy

On 2007-04-21 16:08:01 +0100, Andy Parkins wrote:

Well, any hash is "incomplete" or "not long enough" inasmuch as it's theoretically possible to find collisions. The choice of the full 160 bits (note: this is 20 bytes, not 40) is arbitrary -- it's just "long enough". 128 bits would have been enough to prevent any naturally occurring collisions, too (maybe even 96 bits would be enough, I'm too lazy to do the math). The only reason to go as high as 160 is to prevent any possible collision created by a malicious adversary, too, so that it's possible to e.g. sign just a commit and be able to trust everything it points to. The SHA1 designers felt that 160 bits was a good compromise between size and robustness, and we just trust that their (and the cryptographic community's) guess is good enough.

On 4/21/07, Karl Hasselström <kha@treskal.com> wrote:

Yes ;-) Of course. Sorry!!

On 4/21/07, Andy Parkins <andyparkins@gmail.com> wrote:

Well, this is true also with 40 bytes sha, also if less probable.

Apart from this, when, in the future you are going to add an object that conflicts with an existing one you will handle that situation for the *new* object, as example storing with longer sha, without touching the existing one anymore.

Well I admit I don't know exacting what I'm saying, but sometimes ingenuity (a kind word to say ignorance) could lead to some surprises.

Marco

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:

When Shawn gets done with full compression the SHAs would get stored in the packfile once and then be replaced with a token generated from the compression algorithm. Compression tokens are designed to use the minimal number of bits depending on frequency of occurrence.

This doesn't happen with the current compression code since it doesn't have a global dictionary.

There are many other things that would benefit from a global dictionary. For example when working on the Mozilla repository the Mozilla license has gone through four major revisions. Each of these licenses is in the repository thousands of times. Making a copy of each license to a global dictionary and then replacing them with a token would yield megabytes of savings in the pack.

I would think that it is better to wait for a general compression solution rather than do a specific one for SHAs.

On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:

Currently in Lunux tree there are about 445.424 objects (git count-objects -v), if each object has his 40 bytes name it is about 20MB to store sha *once*, probably with no real disambiguate need to be that much.

Marco

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:

You have to store the full SHAs at least once since they are the signature against data corruption.

On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:

This is interesting.

So until know I learnt 3 uses of sha:

- Reference an object
- Check against object data corruption
- Prevent any possible collision among objects

Karl says that we need 160 bits to prevent collisions:

Probably we don't need 160bits to reference an object. I really don't know how many bit we need to be robust against data corruption.

Someone more versed then me in SHA1 could tell the probablity to find a corrupted object calculating his hash and checking against his stored 160bits known good signature and *FAIL* to find as corrupt *the same object* calculating his hash and checking against a truncated sha to say 20bits.

I would say this probability is veery veery low in random case (not a malicious attack of course, but I think this is not the case with git repository as it was with SHA1 designers).

Marco

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:

The SHA is also a security signature against tampering. All commits having an SHA. These SHAs are repeated into a check-in entry, which then gets an SHA. Releases are identified by publishing an SHA.

You take the release SHA and use it to find/verify the commit record. Opening the commit record gives you the SHA of all of the pieces of the commit. (I simplified this by ignoring trees).

This stops some one from altering a file in a git repo as a way of inserting malicious code. If you alter a file all of the SHAs that depend on it will change. It is very, very difficult to figure out how to patch a file and not change the SHA for it.

This is a real problem and people have tried to secretly insert code into the Linux kernel in the past.

Marco Costalba wrote:

The probability of finding a collision when only 20 bits are used is 1 in 1048575. In other words, repositories would already be exhibiting collisions with only 20 bits of hash, even with a perfect dispersion.

I believe the KDE repo is the biggest one in git today, with its several hundred thousand revisions (and thus most likely several million objects).

The reason it's not much use to cut down the hash-size is that it already reflects a very small percentage of the total size of the repo, and since using the full hash allows git to handle up to 1461501637330902918203684832716283019655932542976 objects without encountering conflicts (it doesn't really, but that's 2 to the power of 160), this works as a nice size for a hash to be.

If the hash is reduced to 80 bits, the maximum number of unique hashes shrinks to 1208925819614629174706176 (less than 1% of 160 bits) while only saving 10 bytes of storage per object. Using a more efficient compression algorithm for the objects themselves (bzip2, anyone?) will most likely reduce storage size an order of magnitude more than reducing the size of the hash, although at the expense of CPU-efficiency.

One must also factor in the code-changes necessary to support abbreviated hashes and ask oneself "is it worth it?". Since using a smaller portion of the hash doesn't only have upsides, I'd say "no, definitely not".

On Tue, 24 Apr 2007, Andreas Ericsson wrote:

An order of magnitude I really doubt it. Maybe 20% could be a really optimistic prediction. But if bzip2 could reduce the repo by 20%, it will slow runtime usage of that repo by maybe 100%. That is not worth it.

This is also the reason why we changed the default zlib compression level from "best" to "default".

Nicolas

Nicolas Pitre wrote:

... order of magnitude *more than reducing the size of the hash*.

On Tue, 24 Apr 2007, Andreas Ericsson wrote:

Ah, sorry.  Still I wanted to advise against it nevertheless.

Anyway, if you compare packing with repack.usedeltabaseoffset set to true, then to false, you'll have a pretty good approximation of the SHA1 storage cost. With most objects as deltas, in the first case the reference to the base object is stored as an offset in the pack while in the second case the full SHA1 is used. You can deduce from the size difference that the SHA1 doesn't constitute a terrible storage cost indeed.

Nicolas

On Sat, 21 Apr 2007, Marco Costalba wrote:

Object names aren't 40 bytes.  They are 20 bytes.

It  is their hex representation that takes 40 bytes.

Nicolas

Nicolas Pitre wrote:

Sure, but that's the way they're stored in *most* git objects, in particular in commit objects.

	-hpa

"H. Peter Anvin" <hpa@zytor.com> wrote:

But OBJ_TREE occurs more often, and its 20 bytes binary for a SHA-1 in those. They are only ASCII hex in OBJ_COMMIT and OBJ_TAG.

If Nico and I ever get pack v4 done, all SHA-1s drop to 24 bytes worst case, or 20 + (4 * n_references) best case. Typically we found that n_references was large enough, frequently enough, that we shaved 5% or so off linux-2.6.git. And I don't think that's including the 20 * n_objects saved out of the .idx files...

On Mon, 23 Apr 2007, H. Peter Anvin wrote:

Commit objects aren't *most* objects. They usually are blob and tree objects, and for the later the SHA1 references are stored as 20 byte binary.

Nicolas