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

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

[Marco Costalba]

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

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

[Andy Parkins]

On Saturday 2007, April 21, Marco Costalba wrote:
> Well, why to store always the full length SHA?

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

-- 
Dr Andy Parkins, M Eng (hons), MIET
andyparkins@gmail.com

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

[Karl Hasselström]

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

> On Saturday 2007, April 21, Marco Costalba wrote:
>
> > Well, why to store always the full length SHA?
>
> 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.

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.

-- 
Karl Hasselström, kha@treskal.com
      www.treskal.com/kalle

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

[Marco Costalba]

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

> bits (note: this is 20 bytes, not 40)

Yes ;-) Of course. Sorry!!

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

[Marco Costalba]

On 4/21/07, Andy Parkins <andyparkins@gmail.com> wrote:
> On Saturday 2007, April 21, Marco Costalba wrote:
> > Well, why to store always the full length SHA?
>
> 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.
>

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

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

[Jon Smirl]

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> Well, why to store always the full length SHA?

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.

-- 
Jon Smirl
jonsmirl@gmail.com

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

[Marco Costalba]

On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:
> On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> > Well, why to store always the full length SHA?
>
> 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.
>

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

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

[Jon Smirl]

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:
> > On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> > > Well, why to store always the full length SHA?
> >
> > 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.
> >
>
> 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.

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

> Marco
>


-- 
Jon Smirl
jonsmirl@gmail.com

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

[Marco Costalba]

On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:
>
> You have to store the full SHAs at least once since they are the
> signature against data corruption.
>

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:

>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.

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

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

[Jon Smirl]

On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> 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).

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.

-- 
Jon Smirl
jonsmirl@gmail.com

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

[Andreas Ericsson]

Marco Costalba wrote:
> 
> 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.
> 

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 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).
> 

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".

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

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

[Nicolas Pitre]

On Tue, 24 Apr 2007, Andreas Ericsson wrote:

> 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.

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

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

[Andreas Ericsson]

Nicolas Pitre wrote:
> On Tue, 24 Apr 2007, Andreas Ericsson wrote:
> 
>> 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.
> 
> 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".
> 

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

-- 
Andreas Ericsson                   andreas.ericsson@op5.se
OP5 AB                             www.op5.se
Tel: +46 8-230225                  Fax: +46 8-230231

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

[Nicolas Pitre]

On Tue, 24 Apr 2007, Andreas Ericsson wrote:

> Nicolas Pitre wrote:
> > On Tue, 24 Apr 2007, Andreas Ericsson wrote:
> > 
> >> 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.
> > 
> > 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".
> > 
> 
> ... order of magnitude *more than reducing the size of the hash*.

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

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

[Nicolas Pitre]

On Sat, 21 Apr 2007, Marco Costalba wrote:

> On 4/21/07, Jon Smirl <jonsmirl@gmail.com> wrote:
> > On 4/21/07, Marco Costalba <mcostalba@gmail.com> wrote:
> > > Well, why to store always the full length SHA?
> > 
> > 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.
> > 
> 
> 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.

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

It  is their hex representation that takes 40 bytes.


Nicolas

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

[H. Peter Anvin]

Nicolas Pitre wrote:
> 
> Object names aren't 40 bytes.  They are 20 bytes.
> It  is their hex representation that takes 40 bytes.
> 

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

	-hpa

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

[Shawn O. Pearce]

"H. Peter Anvin" <hpa@zytor.com> wrote:
> Nicolas Pitre wrote:
> >
> >Object names aren't 40 bytes.  They are 20 bytes.
> >It  is their hex representation that takes 40 bytes.
> >
> 
> Sure, but that's the way they're stored in *most* git objects, in 
> particular in commit objects.

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...

-- 
Shawn.

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

[Nicolas Pitre]

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

> Nicolas Pitre wrote:
> > 
> > Object names aren't 40 bytes.  They are 20 bytes.
> > It  is their hex representation that takes 40 bytes.
> > 
> 
> Sure, but that's the way they're stored in *most* git objects, in particular
> in commit objects.

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