Re: Yo dawg, I heard you like trees...

From: Jeff King <peff@peff.net>
Date: Dec 7, 2011, 22:12 UTC
Message-ID: <20111207221202.GB21596@sigill.intra.peff.net>
In-Reply-To: <20111207155411.GB2003@thinkpad>

On Wed, Dec 07, 2011 at 04:54:11PM +0100, Sebastian Morr wrote:

Show 5 quoted lines

> > Git uses a DAG. The A stands for "acyclic". Loops are not allowed.
> 
> I'm aware of that. It's acyclic by design, but is this actually enforced
> by the code? Or does it simply trust that no loops will ever occur,
> because it's so improbable?

The latter. And not just "improbable", but "so improbable that trying to do it on purpose should still take billions of years".

Assuming sha1 isn't totally broken, of course.

> After Andrew's response I investigated a bit, and it seems I
> overvalued the attempts to "break" SHA-1. Wikipedia quotes a 2008
> attack, that can create a collision with 2^51 hash function calls.

According to wikipedia, it _may_ produce collisions in 2^51 to 2^57.

Worrisome numbers, certainly, but 2^51 is probably within our ability to compute if a big project is undertaken. Yet to my knowledge nobody has actually created such a collision. So the attack is still theoretical at this point, and there's no good way to create a loop within the git DAG (or within a tree).

-Peff