{"thread":{"id":"5328","subject":"Re: [RFC] adding support for md5","startedAt":"2006-08-19T03:19:31Z","lastAt":"2006-08-19T22:30:27Z","messageCount":2,"participants":["linux@horizon.com","Petr Baudis"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25598","messageId":"20060819031931.486.qmail@science.horizon.com","threadId":"5328","inReplyTo":null,"subject":"Re: [RFC] adding support for md5","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-08-19T03:19:31Z","receivedAt":"2006-08-19T03:19:31Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"This is a Very Dumb Idea.\n\nI normally try to be polite, but this concept is particularly\ndeserving of scorn.\n\nThe idea that more choice is a good thing is sometimes seductive, but when\nit comes to standards, that's not a good idea.  It's like the famous joke\ntold about the dumb inhabitants of your favorite ethnic region: they're\ngoing to try driving on the other side of the road.  Starting next month,\nall the cars will drive on the other side.  If that goes well, the month\nafter they'll add trucks and buses.\n\nIf some disaster arose that required Git to change hash functions,\nit would be possible to build a conversion utility, although all the\nsignatures in tag objects would break; you'd have to regenerate them, too.\n\nBut this is an all-or-nothing change.  Trying to support *multiple*\nsimultaneous hash functions is a mess.\n\nGit depends very fundamentally on identical objects having identical\nhashes.  The in-memory merge depends on it.  The network protocol\ndepends on it.  Various kludges can be imagined to handle blob objects\nwith multiple names, but tree objects quickly become unworkable.\n\n\nLet's break down the solutions.  There are basically four classes,\ndepending on \n1) whether objects are stored in the database indexed by both hashes,\n   or just one, and\n2) Whether pointers to objects include both hashes, or just one.\n\nIf you include both hashes everywhere, then you've just built\na larger hash function that's the concatenation of SHA-1 and MD5,\nand while it works sanely, it just makes the object IDs even\nbigger, and there are obviously no speed benefts.  But this is\nthe most reasonable alternative.\n\nIf pointers include both hashes, but objects are indexed by only one,\nthen to find an object by pointer requires two lookups, and you still\nneed to hash every blob twice when committing get the values to\nput in the tree objects.  So obviosuly no faster than the first option.\n\nOkay, so pointers are only one hash.  If they were always the same hash,\nthe second hash would be utterly pointless, so we're assuming the\ndatabase contains a mix.\n\nIf objects are indexed by both hashes, then you can hash new blobs once\nto check to see if they're already in the database, but if they're not,\nyou have to hash again with the another algorithm.\n\nOn the other hand, if you index by only one, then every object being\nchecked to see if it's already in the database needs to be hashed twice\nso it can be looked up twice.  What were the claimed speed gains?\n\nBut more to the point, any system which stores one arbitrary hash as\na pointer makes the the tree object created to describe a directory no\nlonger unique, which results in its hash being fundamentally non-unique,\nwhich cascades all the way up to the commit object.\n\nSo you can get silly things like the need for a merge commit to\nrecord the merge of trees that are actually identical.\n\n\nJust a big mess.\n"},{"id":"25631","messageId":"20060819223027.GA23891@pasky.or.cz","threadId":"5328","inReplyTo":"20060819031931.486.qmail@science.horizon.com","subject":"Re: [RFC] adding support for md5","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-08-19T22:30:27Z","receivedAt":"2006-08-19T22:30:27Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Pre Scriptum: I do not advocate supporting many hashing functions just\nfor the heck of it, but I don't like the \"full sweep\" approach _when_\n(not \"in case\") we _need_ to change the hash function. After all,\ncurrently we have to operate with the fact that the next one will likely\nfall victim of attacks in time as well and this is going to be\nperiodical operation.\n\nDear diary, on Sat, Aug 19, 2006 at 05:19:31AM CEST, I got a letter\nwhere linux@horizon.com said that...\n> So you can get silly things like the need for a merge commit to\n> record the merge of trees that are actually identical.\n\nYou can create an ordering of hashes based on their strength and then\nrehash your objects to max() of hash types used in the operation. So, if\nyou're about to merge md5(x) and sha1(y), you first recompute the first\nid as sha1(x). Of course \"recomputing\" needs to be a wee bit more\ncomplex: you need to first substitute tree id for a common hash as well\n(and recursively do the same in the trees); slow, yes, but you can\ncache it.\n\nIt gets worse when you are about to recompute ancestry, so you need to\nset up the hash usage transition so that you don't ever have to\n- such an event is sufficiently rare that each branch keeper can declare\na flag day \"before now I merged only md5 commits and from now on I\nwill merge only sha1 commits\". The tool can help to enforce this.\nThis strategy will not help in 100% of the cases (md5git-based tool\ntakes sha1git-created commit and re-creates it based on a snapshot and\nthe precise same metadata) but I guess it's good enough.\n\nIt's good that this is just theory so far, though. I'd say let it be for\nnow (at least from the \"emergency hash switch\" standpoint) and do it\nwhen it's needed; you will have to have people upgrade their Git at that\npoint anyway and the code would bitrot just sitting there and adding\nso-far unnecessary complexity. We have worse problems at our hands right\nnow anyway.\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nSnow falling on Perl. White noise covering line noise.\nHides all the bugs too. -- J. Putnam\n"}]}