# Yo dawg, I heard you like trees... 4 messages from 2011-12-05 to 2011-12-07. Participants: Sebastian Morr, Andrew Ardill, Jeff King. Thread: https://gitlist.dev/t/29089 ## Sebastian Morr, 2011-12-05 23:57 Subject: Yo dawg, I heard you like trees... Message-ID: <20111205235740.GB27318@thinkpad> URL: https://gitlist.dev/e/20111205235740.GB27318%40thinkpad ``` Just out of curiosity: Do you know of any attempts to construct a tree object that contains itself, that is, references it's own SHA-1? Sebastian ``` ## Andrew Ardill, 2011-12-06 00:04 Subject: Re: Yo dawg, I heard you like trees... Message-ID: URL: https://gitlist.dev/e/CAH5451nfXe_W7QA-WFP-_-q7OryMzNgSrO4EWpqaP97YrspyKQ%40mail.gmail.com In-Reply-To: <20111205235740.GB27318@thinkpad> ``` The difficulty in doing this is essentially the same as breaking SHA-1, so I doubt anyone has seriously tried to do it. Regards, Andrew Ardill On 6 December 2011 10:57, Sebastian Morr wrote: > Just out of curiosity: Do you know of any attempts to construct a tree > object that contains itself, that is, references it's own SHA-1? > > Sebastian > -- > To unsubscribe from this list: send the line "unsubscribe git" in > the body of a message to majordomo@vger.kernel.org > More majordomo info at  http://vger.kernel.org/majordomo-info.html > ``` ## Sebastian Morr, 2011-12-07 15:54 Subject: Re: Yo dawg, I heard you like trees... Message-ID: <20111207155411.GB2003@thinkpad> URL: https://gitlist.dev/e/20111207155411.GB2003%40thinkpad In-Reply-To: ``` > 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? 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. Which, of course, is still way to much. Good for you! :-) ``` ## Jeff King, 2011-12-07 22:12 Subject: Re: Yo dawg, I heard you like trees... Message-ID: <20111207221202.GB21596@sigill.intra.peff.net> URL: https://gitlist.dev/e/20111207221202.GB21596%40sigill.intra.peff.net In-Reply-To: <20111207155411.GB2003@thinkpad> ``` On Wed, Dec 07, 2011 at 04:54:11PM +0100, Sebastian Morr wrote: > > 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 ```