CODEWITHSUNDEEP
git
Eric
Eric

Reputation: 97661

Can a commit be its own ancestor in git?

Is it possible to construct a cyclic git history like in the following ascii-art?

A (root)
|  H<-G
| /    \
VL      \
C        F
 \      /
  \    /
   D->E

Where C is a merge commit of A and H, but H itself is a descendant of C

Upvotes: 4

Views: 710

Answers (3)

jthill
jthill

Reputation: 60547

As Henning Makholm points out above, commits include SHA1 hash codes for their parent(s), and there are known techniques for producing two documents with identical SHA1 hashes that only need multiple high-end-cpu years to work.

What that doesn't take into account is that those techniques depend on controlled document modifications: given two current documents (with their specific hash codes), you can calculate modifications that will make the resulting pair of hash codes "closer" to each other by some metric. But, from Finding Collisions in the Full SHA-1, "Note that message modification should keep all the message conditions".

That means calculating specific bit modifications in those specific documents, and that you can't do with git commits because any modification also randomizes 160 other bits. There's no such thing as a predictable modification to interdependent git commit hashes, and the known techniques all but literally can't get out of the starting gate.

Even that doesn't describe how dicey the specific task you're asking for really is: it isn't a search for two documents with identical hash codes, it's a search for two documents each containing the other's hash code, (which would also be their own, if you manage to make them identical) at a specific place. So far as I've ever heard there has been no research at all on this problem.

So I think the real answer is "no one has ever even tried, let alone has the least clue how, to make this happen by anything less than brute chance".

Upvotes: 2

hmakholm left over Monica
hmakholm left over Monica

Reputation: 23342

Each commit ID is a SHA-1 hash of something that includes the commit IDs of its immediate ancestors, so ordinarily you'll need to know the IDs of the ancestors before you can find an ID that can be their descendant. Thus there's nowhere to start constructing a cycle.

Being able to construct a short cycle structure (where "short" means something like less than 2^64 commits in the cycle) would constitute a break of the hash function being used.

SHA-1 is known to be broken with regard to collision resistance, and it is conceivable that the techniques behind this break could adapted to construct a cycle. But it is not clear how to do this, and it is certainly not just a matter of plugging some off-the-shelf cryptanalytic components together.

Upvotes: 5

Abizern
Abizern

Reputation: 150715

Nope.

Git forms a Directed Acyclic Graph, so you can't have cycles.

Upvotes: 0

Related Questions