{"thread":{"id":"5962","subject":"Re: VCS comparison table","startedAt":"2006-10-20T08:43:18Z","lastAt":"2006-10-20T08:43:18Z","messageCount":1,"participants":["linux@horizon.com"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"29304","messageId":"20061020084318.9705.qmail@science.horizon.com","threadId":"5962","inReplyTo":null,"subject":"Re: VCS comparison table","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-10-20T08:43:18Z","receivedAt":"2006-10-20T08:43:18Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> I've been following the git-vs-bzr discussion, and I'd like to ask a\n> question (being new to both bzr and git). How does git disambiguate SHA1\n> hash collisions? I think git has an alternative way to name revisions\n> (can someone please explain it in more detail, I've seen <ref>~<n>\n> mentioned only in passing in this thread). It seems to me collisions are\n> a good argument in favour of having two independent naming schemes, so\n> that you're not solely relying on hashes being unique.\n> \n> A strong argument is that a global namespace based on hashes of data is\n> ideal because the names are generated from the data being named, and\n> therefore are immutable. Same data => same name for that data, always\n> and forever, which is desirable when merging named data from many\n> sources. But the converse isn't true: one name does not necessarily map\n> to only that data. Have I misunderstood? Is this a problem?\n\nGit avoids the problem by using a very large gryptographic hash.\nWhile recent cryptographic advances mean that it will soon be barely\npossible to deliberately construct two files with the same SHA hash,\nabsent massivecomputational investment, it can be considered a truly\nrandom hash function.\n\nThat means that, given N objects in the repository, there are N * (N-1)\n/ 2 pairs, each of which is a chance to collide.  The probability of\nhaving a collision is thus roughly N * (N-1) / 2^161.  Which doesn't\nreach 1/2 until N == 2^80.\n\nSuppose a git repository has 100 objects added per second, continuously,\nuntil the Sun turns into a red giant and swallows the Earth in 5-6\nbillion years' time (thus halting development).\n\nThat will generate 2^64 objects in the repository, and the probability\nof there being a collison at that time is 2^128/2^161 = 2^-33, or 1 in\n8 billion, small enough to be negligible.\n\nFor slightly more plausible repository sizes, the odds of having a\nproblem are even more miniscule.\n\nAnd the benefits gained from having a completely deterministic\ndata => name mapping are considerable, well worth running such\na minisule risk of major problems.\n\n(There is a road map for conversion to the even larger SHA-256 if\nthat ever proves necessary, but it's not likely to.)\n\n\n\nAs for the <ref>~<n> syntax, see \"man git-rev-parse\".  The parent of <rev>\nis <rev>^.  If it has multiple parents, the othersare <rev>^2, <rev>^3, etc.\n\n<rev>^^^^ is the great-great-grandparent of the named rev, and may also\nbe written <rev>~4.\n"}]}