4 ms·

Completely agree. > Which in case of Git is that it's a DAG And one step beyond that, that it's a Merkel tree. It's key to understanding stuff like "if I chan

Completely agree. > Which in case of Git is that it's a DAG And one step beyond that, that it's a Merkel tree. It's key to understanding stuff like "if I change a commit, it changes all commit after that" or "if I move (cherry pick, rebase) this commit, I'm creating a new one, not really moving".

ilammy 7y ago
> And one step beyond that, that it's a Merkel tree. Not really, not every block chain is a Merkle tree. Since Git history is not linear, you can’t order the commits in any canonical way. You definitely can order them in some way (like "git log" does) and then construct a tree for that list of hashes, but this is not really useful computation. Git repo integrity is verified simply by HEAD commit hash because you normally clone the entire repository anyway.
- TeMPOraL 7y ago
  Is git even a Merkle tree? Git history forms a DAG, not a tree. But I'm not 100% sure about how the hashes are computed - whether they work on the DAG, or on some local subtree.
  - ilammy 7y ago
    No, it’s not. Commit hashes are exactly what it says on the tin: hash sums of commit objects, which are basically text files that include hash sums of tree objects (directory tree state), hash sums of parent commits, your commit message and other metadata. You can see it with "git cat-file": $ git cat-file -p d8defd0bb0062ed541de173a2aec834b64d6adbe tree cbdb56fe9bb1766d8fc2b2e53c9c934efbacbf1c parent a8a1049c06d100a3f926a82414e6addb9b9af5e8 author ilammy <alexei@cossacklabs.com> 1581533224 +0200 committer ilammy <alexei@cossacklabs.com> 1581533224 +0200 fixup! Avoid unsigned overflow in length computations And compute the commit hash manually to verify that: $ sha=d8defd0bb0062ed541de173a2aec834b64d6adbe $ cat <(echo -ne "$(git cat-file -t $sha) $(git cat-file -s $sha)\0") \ <(git cat-file -p $sha) | sha1sum d8defd0bb0062ed541de173a2aec834b64d6adbe - Git prefixes object content with object type ("commit" in case of commits), its size in bytes (textual, decimal), terminated by a null byte. And hashes all of that get the commit hash.

ilammy 7y ago

> And one step beyond that, that it's a Merkel tree. Not really, not every block chain is a Merkle tree. Since Git history is not linear, you can’t order the commits in any canonical way. You definitely can order them in some way (like "git log" does) and then construct a tree for that list of hashes, but this is not really useful computation. Git repo integrity is verified simply by HEAD commit hash because you normally clone the entire repository anyway.

TeMPOraL 7y ago
Is git even a Merkle tree? Git history forms a DAG, not a tree. But I'm not 100% sure about how the hashes are computed - whether they work on the DAG, or on some local subtree.
- ilammy 7y ago
  No, it’s not. Commit hashes are exactly what it says on the tin: hash sums of commit objects, which are basically text files that include hash sums of tree objects (directory tree state), hash sums of parent commits, your commit message and other metadata. You can see it with "git cat-file": $ git cat-file -p d8defd0bb0062ed541de173a2aec834b64d6adbe tree cbdb56fe9bb1766d8fc2b2e53c9c934efbacbf1c parent a8a1049c06d100a3f926a82414e6addb9b9af5e8 author ilammy <alexei@cossacklabs.com> 1581533224 +0200 committer ilammy <alexei@cossacklabs.com> 1581533224 +0200 fixup! Avoid unsigned overflow in length computations And compute the commit hash manually to verify that: $ sha=d8defd0bb0062ed541de173a2aec834b64d6adbe $ cat <(echo -ne "$(git cat-file -t $sha) $(git cat-file -s $sha)\0") \ <(git cat-file -p $sha) | sha1sum d8defd0bb0062ed541de173a2aec834b64d6adbe - Git prefixes object content with object type ("commit" in case of commits), its size in bytes (textual, decimal), terminated by a null byte. And hashes all of that get the commit hash.