{"thread":{"id":"20498","subject":"Hash algorithm choice","startedAt":"2009-08-09T16:17:01Z","lastAt":"2009-08-09T18:44:53Z","messageCount":8,"participants":["Jerome Baum","Linus Torvalds","Johannes Schindelin","Junio C Hamano","Sverre Rabbelier","Matthieu Moy"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"120059","messageId":"f448a46a0908090917s102b4c83pbad6f298a8e127cc@mail.gmail.com","threadId":"20498","inReplyTo":"f448a46a0908090907v68542e4dw1f1c4f610cb46ca2@mail.gmail.com","subject":"Hash algorithm choice","fromName":"Jerome Baum","fromEmail":"jerome@jeromebaum.com","sentAt":"2009-08-09T16:17:01Z","receivedAt":"2009-08-09T16:17:01Z","isPatch":false,"sender":{"key":"jerome@jeromebaum.com","avatar":null},"body":"Hi all,\n\n\nI just had an idea regarding git and hashing. Couldn't find any\nprevious discussion on the subject so here's what I'm thinking of:\n\nHow difficult would it be to allow users to choose a hash function\nduring git-init which is then globally used in the repo? Are there\nmany changes needed or are changes in git-hash-object and git-init\nsufficient?\n\nI'm not trying to undermine the decision to use SHA-1 or anything, but\nI would guess it builds for the future and adds flexibility to the\nsystem. So when SHA-1 is no longer sufficient, it would be easy to\nswitch to RIPEMD-160 with a simple \"git-init --hash=ripemd160\"\n\nWould be happy for any comments on this.\n\n\nRegards,\n\n\nJerome Baum\nHugo-Junkers-Str. 2\nD-37083 Göttingen\nGermany\nTel.: +49 551 2008782\nWeb: www.JeromeBaum.com\n"},{"id":"120063","messageId":"alpine.LFD.2.01.0908091038300.3288@localhost.localdomain","threadId":"20498","inReplyTo":"f448a46a0908090917s102b4c83pbad6f298a8e127cc@mail.gmail.com","subject":"Re: Hash algorithm choice","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-09T17:46:25Z","receivedAt":"2009-08-09T17:46:25Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 9 Aug 2009, Jerome Baum wrote:\n> \n> How difficult would it be to allow users to choose a hash function\n> during git-init which is then globally used in the repo? Are there\n> many changes needed or are changes in git-hash-object and git-init\n> sufficient?\n\nIf youlimit the hash size to 20 bytes, there are almost no changes \nnecessary.\n\nYou'd need to hijack the 'SHA1_Init/SHA1_Update/SHA1_Final' functions, of \ncourse, and you'd likely want to rename them (and eventually a lot of \nother functions too), but that renaming is mechanical and isn't even \nneeded for proper working.\n\nNow, if you would ever want to extend the _size_ of the hash, that's a \nmuch much bigger problem, but if you're ok with just changing the hash and \nthen truncating the result to 20 bytes (ie kind of like sha-512-160), or \nyou're ok with limiting yourself to 20-byte hashes like REIPMD-160, the \nsize of the changes should be minimal.\n\n\t\t\tLinus\n"},{"id":"120064","messageId":"alpine.DEB.1.00.0908091949090.8306@pacific.mpi-cbg.de","threadId":"20498","inReplyTo":"f448a46a0908090917s102b4c83pbad6f298a8e127cc@mail.gmail.com","subject":"Re: Hash algorithm choice","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-08-09T17:49:46Z","receivedAt":"2009-08-09T17:49:46Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 9 Aug 2009, Jerome Baum wrote:\n\n> I just had an idea regarding git and hashing. Couldn't find any previous \n> discussion on the subject so here's what I'm thinking of:\n> \n> How difficult would it be to allow users to choose a hash function \n> during git-init which is then globally used in the repo? Are there many \n> changes needed or are changes in git-hash-object and git-init \n> sufficient?\n\nA quick search revealed this:\n\nhttp://thread.gmane.org/gmane.comp.version-control.git/25632/focus=25735\n\nHth,\nDscho\n"},{"id":"120065","messageId":"7vljls986b.fsf@alter.siamese.dyndns.org","threadId":"20498","inReplyTo":"alpine.LFD.2.01.0908091038300.3288@localhost.localdomain","subject":"Re: Hash algorithm choice","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-08-09T18:03:08Z","receivedAt":"2009-08-09T18:03:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> If youlimit the hash size to 20 bytes, there are almost no changes \n> necessary.\n>\n> You'd need to hijack the 'SHA1_Init/SHA1_Update/SHA1_Final' functions, of \n> course, and you'd likely want to rename them (and eventually a lot of \n> other functions too), but that renaming is mechanical and isn't even \n> needed for proper working.\n>\n> Now, if you would ever want to extend the _size_ of the hash, that's a \n> much much bigger problem, but if you're ok with just changing the hash and \n> then truncating the result to 20 bytes (ie kind of like sha-512-160), or \n> you're ok with limiting yourself to 20-byte hashes like REIPMD-160, the \n> size of the changes should be minimal.\n\nJust in case Jerome really wants to go further, \"almost no changes\" and\n\"minimal\" refers to the fact that we have a few hard-coded hash values\nknown to the code, such as the object name for an empty blob and an empty\ntree.\n"},{"id":"120066","messageId":"fabb9a1e0908091116y6012caa7j6865d5fcd5d9888c@mail.gmail.com","threadId":"20498","inReplyTo":"7vljls986b.fsf@alter.siamese.dyndns.org","subject":"Re: Hash algorithm choice","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-08-09T18:16:31Z","receivedAt":"2009-08-09T18:16:31Z","isPatch":false,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Aug 9, 2009 at 11:03, Junio C Hamano wrote:\n> Just in case Jerome really wants to go further, \"almost no changes\" and\n> \"minimal\" refers to the fact that we have a few hard-coded hash values\n> known to the code, such as the object name for an empty blob and an empty\n> tree.\n\nWouldn't the transport code also have to be modified? I assume git's\nintegrity checking would yell at if you gave it commits with\nnon-sha1-hashes and have no way to tell it that that hash was\ncalculated with a non-sha1-hash at clone time?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"120069","messageId":"alpine.LFD.2.01.0908091116340.3288@localhost.localdomain","threadId":"20498","inReplyTo":"7vljls986b.fsf@alter.siamese.dyndns.org","subject":"Re: Hash algorithm choice","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-09T18:33:18Z","receivedAt":"2009-08-09T18:33:18Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 9 Aug 2009, Junio C Hamano wrote:\n> \n> Just in case Jerome really wants to go further, \"almost no changes\" and\n> \"minimal\" refers to the fact that we have a few hard-coded hash values\n> known to the code, such as the object name for an empty blob and an empty\n> tree.\n\nOnce nice thing about git is also that in many ways git doesn't even \n_care_ about the actual hash algorithm, because read-only git will \ngenerally (always?) just use the hashes as pointers.\n\nSo you could actually create a very limited sort of git that doesn't have \nany hash algorithm at all - and it would still be able to do a lot of \nregular git operations.\n\nGit strictly speaking needs to hash things only when\n\n - validating the index (ie if the index and stat data do not match). Git \n also checks the SHA1 hash at teh end of the index file every time it \n loads it.\n\n - creating new objects (ie commit)\n\n - git-fsck\n\n - probably some situation I didn't think about.\n\nbut during normal operations git doesn't strictly _need_ to hash anything.\n\nFor example, I literally just checked what happens when you break our hash \nalgorithm on purpose, and while any index operation is unhappy and \ncomplains about index corruption:\n\n\t[torvalds@nehalem git]$ ./git diff\n\terror: bad index file sha1 signature\n\tfatal: index file corrupt\n\nthat's really largely a sanity check. You can literally do things like \n\"git log -p\" without ever generating a single hash at all - because all \ngit will do is to look up objects based on the hashes it finds.\n\nNow, what's nice about this is that it means that \n\n (a) Hash performance only really matters for \"git add\" and \"git fsck\" \n (well, as long as it's not _totally_ sucky. As mentioned above, we do \n check the integrity of the index file more often, but that could be a \n different hash than the _object_ hashes - so even if you change the \n object hashes to be something else than SHA1, you wouldn't \n necessarily have to change the index checksum)\n\n (b) You could actually afford to have git auto-detect the hashes from \n existing objects\n\n (c) it's not even entirely unreasonable to mix different hashes in the \n same repository (ie \"old objects use old hash, new objects use new \n hash\".\n\n Aliasing (same object with different hashes) will hurt disk-space, \n and will make some operations (like merges and 'git diff') much more \n expensive when they hit a \"hash boundary\", but other than that you'd \n never even notice.\n\nOf course, the downside to the above is that git may not notice some kinds \nof corruption until you actually do things like \"git fsck\" (or native git \ntransfers like \"git pull\", which always check the result very carefully). \n\nFor disk corruption issues, there are things like zlib Adler checksums \n(and xdelta crc's) etc that we always check when unpacking objects, but \nthe hash itself only gets recomputed for fairly special events.\n\n\t\t\tLinus\n"},{"id":"120070","messageId":"alpine.LFD.2.01.0908091133420.3288@localhost.localdomain","threadId":"20498","inReplyTo":"fabb9a1e0908091116y6012caa7j6865d5fcd5d9888c@mail.gmail.com","subject":"Re: Hash algorithm choice","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2009-08-09T18:35:01Z","receivedAt":"2009-08-09T18:35:01Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 9 Aug 2009, Sverre Rabbelier wrote:\n>\n> Wouldn't the transport code also have to be modified? I assume git's\n> integrity checking would yell at if you gave it commits with\n> non-sha1-hashes and have no way to tell it that that hash was\n> calculated with a non-sha1-hash at clone time?\n\nWell, if you start introducing new hashes, the assumption is that all \ngit's that access it would have to be updated.\n\nYou certainly could never pull/push between git versions that don't know \nabout each others hashes. But you _can_ autodetect the hash mechanism \n(simple: just try them all on the first object you encounter)\n\n\t\tLinus\n"},{"id":"120073","messageId":"vpq1vnkddy2.fsf@bauges.imag.fr","threadId":"20498","inReplyTo":"f448a46a0908090917s102b4c83pbad6f298a8e127cc@mail.gmail.com","subject":"Re: Hash algorithm choice","fromName":"Matthieu Moy","fromEmail":"matthieu.moy@imag.fr","sentAt":"2009-08-09T18:44:53Z","receivedAt":"2009-08-09T18:44:53Z","isPatch":false,"sender":{"key":"git@matthieu-moy.fr","avatar":"https://avatars.githubusercontent.com/u/14709?v=4"},"body":"Jerome Baum writes:\n\n> How difficult would it be to allow users to choose a hash function\n> during git-init which is then globally used in the repo?\n\nThere's at least one really difficult thing: how do you merge two\nprojects using two different hash functions? The Git repository, for\nexample, has several (I don't remember how many) root repository, and\nwas originally made of several projects (git, gitk, git gui, ...). If\nthese projects had started using different hash functions, then,\neither:\n\n* Git would have needed to learn how to merge, and record the merge\n history, of projects using different hash functions.\n\n* One of the projects would have been forced to be converted to\n another hash function, which means changing all its identifiers (so,\n for example, finding a message on gmane telling that commit 1ab23cde\n fixes your problem wouldn't help much anymore ...).\n\n-- \nMatthieu\n"}]}