12 ms·

Updating the Git protocol for SHA-256

217 points by chmaynard 6y ago

chmaynard 6y ago
This article by John Coggeshall is an example of great technical writing. I look forward to reading more of his work. The more I learn about Git, the more it blows my mind. Torvalds must have designed Git in his head during the time he was using BitKeeper. When he decided to implement Git, he went to work and in a few weeks he had it working well enough to use for Linux kernel source control. Torvalds is either a genius or merely a superstar computer scientist and software engineer. Choose any two.
- langitbiru 6y ago
  10x engineer? :)
- nujabe 6y ago
  I'm almost certain if it weren't Torvalds, it would be someone else who creates something like Git. He just had the need and skills to create it. Like Bill Gates he was just a competent person, at the right place and time.
  - nordsieck 6y ago
    > I'm almost certain if it weren't Torvalds, it would be someone else who creates something like Git. He just had the need and skills to create it. Like Bill Gates he was just a competent person, at the right place and time. I think it's fair to point out that Torvalds didn't come up with Git on his own - he was influenced by a good amount of prior art, not the least of which was Bitkeeper. However, I think calling him a "competent person, at the right place and time" undersells him to a substantial degree. 1. He's a world class software developer. 2. He's a world class tech lead (There are certainly criticisms about his communication style, which I don't think are unfair. Here, I am judging him by the artifacts created under his leadership). 3. He was the write lock for an extremely large distributed team for more than a decade. It is not surprising to me that the 2nd most famous distributed source control tool - Mercurial - was also initially created by a Linux kernel developer.
    - deleted 6y ago
      [deleted]
    - bch 6y ago
      > It is not surprising to me that the 2nd most famous distributed source control tool - Mercurial - was also initially created by a Linux kernel developer. Because Linux was in a crisis and hot off an excellent experience w bitkeeper? Or something more profound?
      - edoceo 6y ago
        Maybe their extensive experience with both big-system code and distributed team problems?
      - nordsieck 6y ago
        > Because Linux was in a crisis and hot off an excellent experience w bitkeeper? Or something more profound? I'm sure the crisis was part of it. But also, the way Linux development is organized is very weird compared to how code is developed in most places. "Distributed" is not quite right, but it's the best word I've got. A source control tool like Perforce just wouldn't fit linux development very well, whereas large companies at the time were perfectly happy with it.
        quicklime 6y ago
        “Decentralized”? I agree with you that Linux development is weird compared to most places. Most places have a designated central repo that acts as the source of truth, whereas the Linux developers don’t really have this. This is possibly an unpopular opinion, but I think that when there is an official main repo, git is far more complicated than it needs to be. It’s confusing to a lot of developers because of all this unnecessary complexity. Most teams could probably be served better by a simpler system.
        Koromix 6y ago
        I share this opinion as well. For centralized-repo style, which is what most teams need, the Git model has three problems: - It is hard to use. There's a reason most teams have a single or two Git "experts" to help everyone else resolve repository / merge / pull / whatever problems that happen regularly. The onboarding experience for developers unfamilir with Git is very bad, and many of them end up never able to use it. If you have non-developers (e.g. artists), it is even worse. - Binary files. Yes, there is Git LFS, but there are many small integration problems when you try to use it, and the simple fact that Git needs something special to manage binary files is a problem. And no, storing binary files outside the repository is NOT a good solution. In games for example, the binary files and the engine usually evole together and if you want to checkout an old version, the code and the assets need to stay in sync. You want to version the game, not just the engine. - Partial (subtree) clones and permissions. There's a reason monorepos are popular: they're much simpler to manage. Unfortunaly, because Git barely does partial clones and cannot manage permissions (inside a repository) at all, monorepos are much more limited than in SVN or P4. That's why many projects end up divided in multiple repos, but this brings all sorts of problems and a large administrative overhead for all developers.
  - kohtatsu 6y ago
    I'd love to see an in-depth comparison of the contributions to technology from Jobs, Gates, and Torvalds.
    - nix23 6y ago
      I dont think there is much: -Jobs was management -Gates made basic and management -Torvald made a VCS a Kernel a Divecomputer-programm and a new way to develop software
  - riquito 6y ago
    > "He just had the need and skills to create it" Yeah, lucky Linus /sarcasm A bit undeserving, don't you think?
  - Dylan16807 6y ago
    If? Is Mercurial not like Git?
    - addicted 6y ago
      Yes, and according to Wikipedia their initial releases were only 2 weeks apart. Further, you also had Bazaar whose initial release was a month earlier and was itself based on another tool that was released a year before. For whatever reason, creating distributed alternatives to SVN was a very popular thing to do at the time.
      - Volt 6y ago
        They were really meant to be FLOSS alternatives to BitKeeper, not SVN.
  - rumanator 6y ago
    > he was just a competent person, at the right place and time. If you honestly have that pov then it must be very hard to explain how no one else in the whole history of the world has ever managed to pull anything similar to Git. It's one thing to point out we all stand on the shoulders of giants, but it's an entirely different thing to claim any random person with average skills pulls this off. I mean where's your Git?
    - deleted 6y ago
      [deleted]
  - sradman 6y ago
    > ... he was just a competent person, at the right place and time. Right skill set, right place, right time. The decentralized team workflow of Open Source projects demanded a decentralized version control system (DVCS). A number of DVCS systems emerged with varying trade-offs. It is interesting, but non obvious, which set of trade-offs gain greater adoption. Git versus Mercurial is a case study of this process.
- magnio 6y ago
  Reading the first Git version, i.e. its initial commit, makes learning git easier for me. Albeit very simple and barebone, its ideas are pretty fundamental to Git and differentiate it from many other VCSs.
- beagle3 6y ago
  Everyone is forgetting “monotone”, a DVCS developed by Graydon Hoare (who later went to create Rust) of which the Git model is essentially a simplification (and much much less related to BitKeeper) There was a lot of experimentation with VCSes at the time: arch -> tla -> baz ; bzr ; monotone ; cdv ; mercurial ; git ; even sun was finally getting merge tracking. Monotone had the best structure but a slow and clunky implementation. It was adopted and simplified (in different ways) by git and hg; eventually git won by virtue of being way faster and demonstrably effective for a project the size of the Linux kernel (and Linus’ celebrity status didn’t hurt either) But graydon hoare deserves a lot more credit than he received - Linus did credit him at the time, but no one seems to remember.
  - nix23 6y ago
    >Everyone is forgetting “monotone” I miss monotone! What a beautiful single-file (sqlite) VCS if it would be still maintained i would use it for small projects, but nowadays i use fossil and bitkeeper...and yeah git if i have to ;)
    - SQLite 6y ago
      Author of SQLite and Fossil here - I have not forgotten monotone! Indeed, Fossil itself is inspired by monotone documentation (though not the implementation). This is credited at https://fossil-scm.org/fossil/doc/trunk/www/history.md https://fossil-scm.org/fossil/doc/trunk/www/history.md
      - nix23 6y ago
        Thank you very much for that great piece's of Software!! Both Fossil and SQLite.
      - dschulz 6y ago
        Dr. Richard Hipp? Thanks for all your work. The world is a significantly better place thanks to you.
    - the_pwner224 6y ago
- alblue 6y ago
  I wrote a series of blog posts covering how the intervals of git works; I posted a summary here for reference: https://alblue.bandlem.com/2011/12/git-tip-of-week-finale.html https://alblue.bandlem.com/2011/12/git-tip-of-week-finale.ht... If you’re interested in how commits, trees and objects are represented then it could be interesting for you.
- chmaynard 6y ago
  “The thing that differentiates scientists is purely an artistic ability to discern what is a good idea, what is a beautiful idea, what is worth spending time on, and most importantly, what is a problem that is sufficiently interesting, yet sufficiently difficult, that it hasn't yet been solved, but the time for solving it has come now.” -- Savas Dimopoulos
sargun 6y ago
I wonder why SHA-256, and not BLAKE2(b/s) or BLAKE3. BLAKE3 is significantly faster.
- altmind 6y ago
  because the speed is not the only concern. also, sha2 is already hardware accelerated, and may still be faster than the rest of the hashes.
- bawolff 6y ago
  Does performance matter in this context? Git isn't exactly hashing terabytes of data.
  - JoshTriplett 6y ago
    It does; I've encountered some cases (ingesting large amounts of data into git) where the limiting factor on performance is a combination of SHA-1 and DEFLATE.
  - hobofan 6y ago
    You don't think that GitHub has to hash petabytes of their users data?
- slavik81 6y ago
  SHA-256 is faster when hardware accelerated, and was judged to be a more conservative choice. You can find their evaluation here: https://public-inbox.org/git/20180609224913.GC38834@genre.crustytoothpaste.net/ https://public-inbox.org/git/20180609224913.GC38834@genre.cr...
  - JoshTriplett 6y ago
    That post was made in mid 2018, and BLAKE3 wasn't published until late 2019; I don't think it was considered. SHA256 with hardware acceleration might be competitive with BLAKE2, but not with BLAKE3 (performance graph at https://raw.githubusercontent.com/BLAKE3-team/BLAKE3/master/media/speed.svg?sanitize=true https://raw.githubusercontent.com/BLAKE3-team/BLAKE3/master/... ). BLAKE3 is also capable of being heavily parallelized without changing its output, as well as quickly updated without rehashing entire objects (if you keep some partial hashes around). Overall, it'd be quite desirable. Hopefully all the work to abstract the choice of hash algorithm will make it relatively straightforward to prototype the use of other hashes.
qwename 6y ago
Other than using a stronger hashing algorithm that produces longer hashes, would there be any advantage in storing two or more separate hashes of an object? The extra hashes could be from a different hash function, or a hash of the reversed bits/bytes. I wonder about the difficulty of producing collisions for a single 256-bit hash function versus two 128-bit hash functions, four 64-bit hash functions and so on.
- TicklishTiger 6y ago
  That reminds me of my phone. It is kinda special. Instead of an eleven digit number, I have eleven one digit phone numbers. When I write them down, I usually just writen them all in one row. So the written version of my eleven phone numbers look just like a normal eleven digit phone number.
  - SftwreEngnr 6y ago
    What?
    - sophiebits 6y ago
      A function that concatenates the results of two 64-bit hash functions _is_ a 128-bit hash function. Just as a string of individual digits makes a larger number.
      - hobofan 6y ago
        I mean, technically yes, but it it would be a 128-bit hash function with the security properties of a 64-bit hash function, so it offers little advantage over just using a 64bit hash (which I think was also the point you were trying to make, I think?). However, that doesn't really address the original question on how much harder cracking 2x64bit hash would be than cracking a single 128bit hash would be. My best guess there would be that it's really quantify as you start opening up more dimensions besides the number of bits. The gain would mostly come from protection against other properties from one of the algorithms like a potentially hidden backdoor or a undiscovered mathematical weakness. So as long as the strength of the individual hash function holds up, it probably makes sense to diversify between hash functions. E.g. SHA3-256 + BLAKE3-256, probably offers better long-term security properties than using SHA3-512.
IshKebab 6y ago
This is going to be such a pain for clients to support. Especially because there's not really a good specification for git - the official implementation is the specification. For my client I think I will just have to wait until this is officially enabled before implementating it. Guess it has to be done though. I don't understand the bit about distinguishing hashes by length only. If you're going to change it why not add an identifier prefix? Then the logic can be "if length == 128 { its sha-1 } else { read first byte to determine hash algorithm }".
kelnos 6y ago
One of the comments mentioned that there was a suggestion (presumably rejected) to "rotate" the first character of the hex string for the SHA256 hashes by 16 characters, so 0 becomes g, 1 becomes h, etc. (that way the SHA256 hashes would be unambiguously not SHA1 hashes, even when abbreviated). This made me think... why are we using long, unwieldy base-16 hex strings at all? Why not use an alphabetic (non-numeric) base-46 string: 20 lowercase letters ([g-z]), 26 capital letters ([A-Z])? Then the new SHA256 hash strings end up being shorter than the old SHA1 strings, and there is no overlap with the [0-9a-f] range of the base-16 strings. If you wanted to even it out to 64 characters, you could create a "modified base-64" that doesn't use [0-9a-f] and instead uses more special characters (though for convenience you'd want to choose characters that are shell-safe and possibly even URL-safe, which might make this not work). Alternatively you could use a subset for a base-32 representation. The downside -- perhaps a significant one? -- is that you can't use standard tools like `sha256sum` or the representation conversion functions into the stdlib of many languages to generate these hashes; it would require custom code. Not sure if that's a concern, though.
- supakeen 6y ago
  What is unwieldy about hex strings? If you'd want to solve this perhaps a prefix would be easier?
  - richbradshaw 6y ago
    If you store them as strings instead of binary (which I'm guessing 99% of hashes are), they take up more DB space currently, and passing them round is slower, e.g. as etags etc.
    - speedgoose 6y ago
      I would guess that once compressed, binary represented as hex strings don't take much more space than base64 strings. Probably still a bit more than the compressed binary though.
      - 6y ago
cletus 6y ago
I've never seen an adequate answer to this but it boggles my mind that this problem wasn't foreseen. When Git came out we'd already seen a move from MD5 hashes to SHA-1 because MD5 was no longer deemed secure. Of course this was going to happen again. So why wasn't the protocol and the repository designed to have multiple (hash algorithm, hash) pairs? At this point it becomes a client and server issue if you support a given protocol or not so you have this handshake to agree on what you're using (eg a server may reject SHA-1), much like we have with SSH. This seems like it would've been trivial to allow for in the beginning. Or am I missing something?
- masklinn 6y ago
  > So why wasn't the protocol and the repository designed to have multiple (hash algorithm, hash) pairs? yagni? The design without a real use case could well have been unsuitable, and git has managed to live for 15 years before this issue became a real concern. That’s a pretty good run.
- corty 6y ago
  It would have been possible to include the ability to change algorithms in a handshake (agility). But general current consensus in the cryptography and security community (which I don't agree with) is: "Agility is bad, hmkay". The reasoning is largely because there have been plenty of attacks based on downgrading protocols like TLS to broken crypto by an attacker. Also, the handshake mechanism necessarily enlarges the attack surface of your software, usually in a pre-auth part which is very problematic. The counter-argument is of course that a lack of agility leads to lots of pain later on, when you need agility because your one chosen algorithm is broken. There is also the added argument for not using SHA-1 in git: SHA-1 was already starting to "smell" when git was first implemented. Picking something else back then would at least have moved the current problems farther into the future, when SHA-2 might start to be problematic.
  - hannob 6y ago
    There are good reasons why agility is bad. It never works the way people imagine. The fantasy is people think "in case of a sudden algorithm break we can quickly switch to a better algorithm". This is wrong because: a) there are no sudden algorithm breaks. You always know way in advance before something is broken. (In the case of SHA-1 there was more than a decade between early warnings and the first attack.) In the case of Git the warnings about SHA-1 are older than Git itself. The problem wasn't lack of agility, the problem was choosing an algorithm that was already known to be bad. b) if you have agility it means people will continue supporting bad algorithms and use agility as an excuse. b) happened exactly in TLS. Padding oracles were known, but people chose to ignore it. In TLS 1.2 they included better algorithms (GCM), but chose to keep the bad ones (CBC/HMAC). Then more padding oracle attacks happened. Then people said "oh we have agility, we can disable CBC and ... well nobody supports GCM yet... let's use this other broken thing we have called RC4". Then attacks on RC4 came in. If by the time people designed TLS 1.2 they would've said "we know RC4 is weak, we know CBC/HMAC (as used in TLS) is weak, we will just support GCM" none of that mess would've happened.
rurban 6y ago
So brian finally got closer? Waiting for a long time
kzrdude 6y ago
When browsing lwn in firefox, "unable to connect" errors are relatively common. Is this just the server being aggressive with prioritizing which requests to serve?
miohtama 6y ago
I remebember during DVCS wars, an argument was raised for Bazaar/Mercurial that they supported pluggable hash algorithms. Git was hard coded to SHA. Now this design decisions is harder to get changed.
bluesign 6y ago
maybe some naive question but why not hash content with SHA256 then hash the result with SHA1?
- umvi 6y ago
  That's like saying "why not choose a 20 character password and just use the first 8 characters of it?"
austincheney 6y ago
I couldn’t see in the article, but why settle on SHA2-256? Why not something bigger or newer such as SHA2-512 or SHA3-256? Or why not a variable length hash like SHAKE256?
- chmaynard 6y ago
  I believe this is discussed in https://lwn.net/Articles/811068/ https://lwn.net/Articles/811068/
rudolph9 6y ago
Perhaps I missed it but what are we doing to future proof the hash algorithm to when we need to transition away from sha256? Seems like we’re going to just have the same problem in another decade if we don’t address this now?
- matt_kantor 6y ago
  > In closing, it is worth noting that one of the reasons this transition has been so hard is that the original Git implementation was not designed to swap out hashing algorithms. Much of the work put in to the SHA-256 implementation has been walking back this initial design flaw. With these changes almost complete, it not only provides an alternative to SHA-1, but also makes Git fundamentally indifferent to the hashing algorithm used. This should make Git more adaptable in the future should the need to replace SHA-256 with something stronger arise. That's the last paragraph of the article.
dec0dedab0de 6y ago
Wouldnt an easier solution be to keep the sha-1 to work exactly as is, but add additional hashes to verify the files havent been maliciously modified to keep the same hash. It seems almost impossible to craft a file that has different hashing algorithms equal the same thing. Assuming older versions dont explode when new data is added, it should stay backwards compatible. The sha-1 and short hashes would be the name that is displayed and used for checking out commits, but not relied upon for security.
rudolph9 6y ago
I wish more people would adopt (and better formalize) multihash and related projects https://github.com/multiformats/multihash https://github.com/multiformats/multihash It’s a really simple good idea that has developed in the ipfs world.
kazinator 6y ago
Is there a way to opt out of this other than pinning your git executables to an old version or forking? I want to make sure all my git repos are forever readable by the original git they were produced with, even if newer git versions are used for producing commits. The article makes some troubling comments like: > countless repositories need to be transitioned from SHA-1 to SHA-256. Absolutely never doing this.
gentleman11 6y ago
I am working on a game and version control in the gaming world is definitely weird to somebody coming from web dev. Almost nobody in this world uses git, they all use perforce, svn, and plastic. Apparently got doesn’t deal with binary assets well; even with lfs, it’s hard to find hosting for your 100-500GB repositories that also supports file locking (another binary-specific feature needed for games that many hosts don’t seem to support for some reason). I wanted to try lfs, but where do you actually go to find cheap hosting for a 100-150GB repo?

217 points by chmaynard 6y ago

This article by John Coggeshall is an example of great technical writing. I look forward to reading more of his work. The more I learn about Git, the more it blows my mind. Torvalds must have designed Git in his head during the time he was using BitKeeper. When he decided to implement Git, he went to work and in a few weeks he had it working well enough to use for Linux kernel source control. Torvalds is either a genius or merely a superstar computer scientist and software engineer. Choose any two.

langitbiru 6y ago
10x engineer? :)
nujabe 6y ago
I'm almost certain if it weren't Torvalds, it would be someone else who creates something like Git. He just had the need and skills to create it. Like Bill Gates he was just a competent person, at the right place and time.
- nordsieck 6y ago
  > I'm almost certain if it weren't Torvalds, it would be someone else who creates something like Git. He just had the need and skills to create it. Like Bill Gates he was just a competent person, at the right place and time. I think it's fair to point out that Torvalds didn't come up with Git on his own - he was influenced by a good amount of prior art, not the least of which was Bitkeeper. However, I think calling him a "competent person, at the right place and time" undersells him to a substantial degree. 1. He's a world class software developer. 2. He's a world class tech lead (There are certainly criticisms about his communication style, which I don't think are unfair. Here, I am judging him by the artifacts created under his leadership). 3. He was the write lock for an extremely large distributed team for more than a decade. It is not surprising to me that the 2nd most famous distributed source control tool - Mercurial - was also initially created by a Linux kernel developer.
  - deleted 6y ago
    [deleted]
  - bch 6y ago
    > It is not surprising to me that the 2nd most famous distributed source control tool - Mercurial - was also initially created by a Linux kernel developer. Because Linux was in a crisis and hot off an excellent experience w bitkeeper? Or something more profound?
    - edoceo 6y ago
      Maybe their extensive experience with both big-system code and distributed team problems?
    - nordsieck 6y ago
      > Because Linux was in a crisis and hot off an excellent experience w bitkeeper? Or something more profound? I'm sure the crisis was part of it. But also, the way Linux development is organized is very weird compared to how code is developed in most places. "Distributed" is not quite right, but it's the best word I've got. A source control tool like Perforce just wouldn't fit linux development very well, whereas large companies at the time were perfectly happy with it.
      - quicklime 6y ago
        “Decentralized”? I agree with you that Linux development is weird compared to most places. Most places have a designated central repo that acts as the source of truth, whereas the Linux developers don’t really have this. This is possibly an unpopular opinion, but I think that when there is an official main repo, git is far more complicated than it needs to be. It’s confusing to a lot of developers because of all this unnecessary complexity. Most teams could probably be served better by a simpler system.
        Koromix 6y ago
        I share this opinion as well. For centralized-repo style, which is what most teams need, the Git model has three problems: - It is hard to use. There's a reason most teams have a single or two Git "experts" to help everyone else resolve repository / merge / pull / whatever problems that happen regularly. The onboarding experience for developers unfamilir with Git is very bad, and many of them end up never able to use it. If you have non-developers (e.g. artists), it is even worse. - Binary files. Yes, there is Git LFS, but there are many small integration problems when you try to use it, and the simple fact that Git needs something special to manage binary files is a problem. And no, storing binary files outside the repository is NOT a good solution. In games for example, the binary files and the engine usually evole together and if you want to checkout an old version, the code and the assets need to stay in sync. You want to version the game, not just the engine. - Partial (subtree) clones and permissions. There's a reason monorepos are popular: they're much simpler to manage. Unfortunaly, because Git barely does partial clones and cannot manage permissions (inside a repository) at all, monorepos are much more limited than in SVN or P4. That's why many projects end up divided in multiple repos, but this brings all sorts of problems and a large administrative overhead for all developers.
- kohtatsu 6y ago
  I'd love to see an in-depth comparison of the contributions to technology from Jobs, Gates, and Torvalds.
  - nix23 6y ago
    I dont think there is much: -Jobs was management -Gates made basic and management -Torvald made a VCS a Kernel a Divecomputer-programm and a new way to develop software
- riquito 6y ago
  > "He just had the need and skills to create it" Yeah, lucky Linus /sarcasm A bit undeserving, don't you think?
- Dylan16807 6y ago
  If? Is Mercurial not like Git?
  - addicted 6y ago
    Yes, and according to Wikipedia their initial releases were only 2 weeks apart. Further, you also had Bazaar whose initial release was a month earlier and was itself based on another tool that was released a year before. For whatever reason, creating distributed alternatives to SVN was a very popular thing to do at the time.
    - Volt 6y ago
      They were really meant to be FLOSS alternatives to BitKeeper, not SVN.
- rumanator 6y ago
  > he was just a competent person, at the right place and time. If you honestly have that pov then it must be very hard to explain how no one else in the whole history of the world has ever managed to pull anything similar to Git. It's one thing to point out we all stand on the shoulders of giants, but it's an entirely different thing to claim any random person with average skills pulls this off. I mean where's your Git?
  - deleted 6y ago
    [deleted]
- sradman 6y ago
  > ... he was just a competent person, at the right place and time. Right skill set, right place, right time. The decentralized team workflow of Open Source projects demanded a decentralized version control system (DVCS). A number of DVCS systems emerged with varying trade-offs. It is interesting, but non obvious, which set of trade-offs gain greater adoption. Git versus Mercurial is a case study of this process.
magnio 6y ago
Reading the first Git version, i.e. its initial commit, makes learning git easier for me. Albeit very simple and barebone, its ideas are pretty fundamental to Git and differentiate it from many other VCSs.
beagle3 6y ago
Everyone is forgetting “monotone”, a DVCS developed by Graydon Hoare (who later went to create Rust) of which the Git model is essentially a simplification (and much much less related to BitKeeper) There was a lot of experimentation with VCSes at the time: arch -> tla -> baz ; bzr ; monotone ; cdv ; mercurial ; git ; even sun was finally getting merge tracking. Monotone had the best structure but a slow and clunky implementation. It was adopted and simplified (in different ways) by git and hg; eventually git won by virtue of being way faster and demonstrably effective for a project the size of the Linux kernel (and Linus’ celebrity status didn’t hurt either) But graydon hoare deserves a lot more credit than he received - Linus did credit him at the time, but no one seems to remember.
- nix23 6y ago
  >Everyone is forgetting “monotone” I miss monotone! What a beautiful single-file (sqlite) VCS if it would be still maintained i would use it for small projects, but nowadays i use fossil and bitkeeper...and yeah git if i have to ;)
  - SQLite 6y ago
    Author of SQLite and Fossil here - I have not forgotten monotone! Indeed, Fossil itself is inspired by monotone documentation (though not the implementation). This is credited at https://fossil-scm.org/fossil/doc/trunk/www/history.md https://fossil-scm.org/fossil/doc/trunk/www/history.md
    - nix23 6y ago
      Thank you very much for that great piece's of Software!! Both Fossil and SQLite.
    - dschulz 6y ago
      Dr. Richard Hipp? Thanks for all your work. The world is a significantly better place thanks to you.
  - the_pwner224 6y ago
alblue 6y ago
I wrote a series of blog posts covering how the intervals of git works; I posted a summary here for reference: https://alblue.bandlem.com/2011/12/git-tip-of-week-finale.html https://alblue.bandlem.com/2011/12/git-tip-of-week-finale.ht... If you’re interested in how commits, trees and objects are represented then it could be interesting for you.
chmaynard 6y ago
“The thing that differentiates scientists is purely an artistic ability to discern what is a good idea, what is a beautiful idea, what is worth spending time on, and most importantly, what is a problem that is sufficiently interesting, yet sufficiently difficult, that it hasn't yet been solved, but the time for solving it has come now.” -- Savas Dimopoulos

sargun 6y ago

I wonder why SHA-256, and not BLAKE2(b/s) or BLAKE3. BLAKE3 is significantly faster.

altmind 6y ago
because the speed is not the only concern. also, sha2 is already hardware accelerated, and may still be faster than the rest of the hashes.
bawolff 6y ago
Does performance matter in this context? Git isn't exactly hashing terabytes of data.
- JoshTriplett 6y ago
  It does; I've encountered some cases (ingesting large amounts of data into git) where the limiting factor on performance is a combination of SHA-1 and DEFLATE.
- hobofan 6y ago
  You don't think that GitHub has to hash petabytes of their users data?
slavik81 6y ago
SHA-256 is faster when hardware accelerated, and was judged to be a more conservative choice. You can find their evaluation here: https://public-inbox.org/git/20180609224913.GC38834@genre.crustytoothpaste.net/ https://public-inbox.org/git/20180609224913.GC38834@genre.cr...
- JoshTriplett 6y ago
  That post was made in mid 2018, and BLAKE3 wasn't published until late 2019; I don't think it was considered. SHA256 with hardware acceleration might be competitive with BLAKE2, but not with BLAKE3 (performance graph at https://raw.githubusercontent.com/BLAKE3-team/BLAKE3/master/media/speed.svg?sanitize=true https://raw.githubusercontent.com/BLAKE3-team/BLAKE3/master/... ). BLAKE3 is also capable of being heavily parallelized without changing its output, as well as quickly updated without rehashing entire objects (if you keep some partial hashes around). Overall, it'd be quite desirable. Hopefully all the work to abstract the choice of hash algorithm will make it relatively straightforward to prototype the use of other hashes.

qwename 6y ago

Other than using a stronger hashing algorithm that produces longer hashes, would there be any advantage in storing two or more separate hashes of an object? The extra hashes could be from a different hash function, or a hash of the reversed bits/bytes. I wonder about the difficulty of producing collisions for a single 256-bit hash function versus two 128-bit hash functions, four 64-bit hash functions and so on.

TicklishTiger 6y ago
That reminds me of my phone. It is kinda special. Instead of an eleven digit number, I have eleven one digit phone numbers. When I write them down, I usually just writen them all in one row. So the written version of my eleven phone numbers look just like a normal eleven digit phone number.
- SftwreEngnr 6y ago
  What?
  - sophiebits 6y ago
    A function that concatenates the results of two 64-bit hash functions _is_ a 128-bit hash function. Just as a string of individual digits makes a larger number.
    - hobofan 6y ago
      I mean, technically yes, but it it would be a 128-bit hash function with the security properties of a 64-bit hash function, so it offers little advantage over just using a 64bit hash (which I think was also the point you were trying to make, I think?). However, that doesn't really address the original question on how much harder cracking 2x64bit hash would be than cracking a single 128bit hash would be. My best guess there would be that it's really quantify as you start opening up more dimensions besides the number of bits. The gain would mostly come from protection against other properties from one of the algorithms like a potentially hidden backdoor or a undiscovered mathematical weakness. So as long as the strength of the individual hash function holds up, it probably makes sense to diversify between hash functions. E.g. SHA3-256 + BLAKE3-256, probably offers better long-term security properties than using SHA3-512.

IshKebab 6y ago

This is going to be such a pain for clients to support. Especially because there's not really a good specification for git - the official implementation is the specification. For my client I think I will just have to wait until this is officially enabled before implementating it. Guess it has to be done though. I don't understand the bit about distinguishing hashes by length only. If you're going to change it why not add an identifier prefix? Then the logic can be "if length == 128 { its sha-1 } else { read first byte to determine hash algorithm }".

kelnos 6y ago

One of the comments mentioned that there was a suggestion (presumably rejected) to "rotate" the first character of the hex string for the SHA256 hashes by 16 characters, so 0 becomes g, 1 becomes h, etc. (that way the SHA256 hashes would be unambiguously not SHA1 hashes, even when abbreviated). This made me think... why are we using long, unwieldy base-16 hex strings at all? Why not use an alphabetic (non-numeric) base-46 string: 20 lowercase letters ([g-z]), 26 capital letters ([A-Z])? Then the new SHA256 hash strings end up being shorter than the old SHA1 strings, and there is no overlap with the [0-9a-f] range of the base-16 strings. If you wanted to even it out to 64 characters, you could create a "modified base-64" that doesn't use [0-9a-f] and instead uses more special characters (though for convenience you'd want to choose characters that are shell-safe and possibly even URL-safe, which might make this not work). Alternatively you could use a subset for a base-32 representation. The downside -- perhaps a significant one? -- is that you can't use standard tools like `sha256sum` or the representation conversion functions into the stdlib of many languages to generate these hashes; it would require custom code. Not sure if that's a concern, though.

supakeen 6y ago
What is unwieldy about hex strings? If you'd want to solve this perhaps a prefix would be easier?
- richbradshaw 6y ago
  If you store them as strings instead of binary (which I'm guessing 99% of hashes are), they take up more DB space currently, and passing them round is slower, e.g. as etags etc.
  - speedgoose 6y ago
    I would guess that once compressed, binary represented as hex strings don't take much more space than base64 strings. Probably still a bit more than the compressed binary though.
    - 6y ago

cletus 6y ago

I've never seen an adequate answer to this but it boggles my mind that this problem wasn't foreseen. When Git came out we'd already seen a move from MD5 hashes to SHA-1 because MD5 was no longer deemed secure. Of course this was going to happen again. So why wasn't the protocol and the repository designed to have multiple (hash algorithm, hash) pairs? At this point it becomes a client and server issue if you support a given protocol or not so you have this handshake to agree on what you're using (eg a server may reject SHA-1), much like we have with SSH. This seems like it would've been trivial to allow for in the beginning. Or am I missing something?

masklinn 6y ago
> So why wasn't the protocol and the repository designed to have multiple (hash algorithm, hash) pairs? yagni? The design without a real use case could well have been unsuitable, and git has managed to live for 15 years before this issue became a real concern. That’s a pretty good run.
corty 6y ago
It would have been possible to include the ability to change algorithms in a handshake (agility). But general current consensus in the cryptography and security community (which I don't agree with) is: "Agility is bad, hmkay". The reasoning is largely because there have been plenty of attacks based on downgrading protocols like TLS to broken crypto by an attacker. Also, the handshake mechanism necessarily enlarges the attack surface of your software, usually in a pre-auth part which is very problematic. The counter-argument is of course that a lack of agility leads to lots of pain later on, when you need agility because your one chosen algorithm is broken. There is also the added argument for not using SHA-1 in git: SHA-1 was already starting to "smell" when git was first implemented. Picking something else back then would at least have moved the current problems farther into the future, when SHA-2 might start to be problematic.
- hannob 6y ago
  There are good reasons why agility is bad. It never works the way people imagine. The fantasy is people think "in case of a sudden algorithm break we can quickly switch to a better algorithm". This is wrong because: a) there are no sudden algorithm breaks. You always know way in advance before something is broken. (In the case of SHA-1 there was more than a decade between early warnings and the first attack.) In the case of Git the warnings about SHA-1 are older than Git itself. The problem wasn't lack of agility, the problem was choosing an algorithm that was already known to be bad. b) if you have agility it means people will continue supporting bad algorithms and use agility as an excuse. b) happened exactly in TLS. Padding oracles were known, but people chose to ignore it. In TLS 1.2 they included better algorithms (GCM), but chose to keep the bad ones (CBC/HMAC). Then more padding oracle attacks happened. Then people said "oh we have agility, we can disable CBC and ... well nobody supports GCM yet... let's use this other broken thing we have called RC4". Then attacks on RC4 came in. If by the time people designed TLS 1.2 they would've said "we know RC4 is weak, we know CBC/HMAC (as used in TLS) is weak, we will just support GCM" none of that mess would've happened.

rurban 6y ago

So brian finally got closer? Waiting for a long time

kzrdude 6y ago

When browsing lwn in firefox, "unable to connect" errors are relatively common. Is this just the server being aggressive with prioritizing which requests to serve?

miohtama 6y ago

I remebember during DVCS wars, an argument was raised for Bazaar/Mercurial that they supported pluggable hash algorithms. Git was hard coded to SHA. Now this design decisions is harder to get changed.

bluesign 6y ago

maybe some naive question but why not hash content with SHA256 then hash the result with SHA1?

umvi 6y ago
That's like saying "why not choose a 20 character password and just use the first 8 characters of it?"

austincheney 6y ago

I couldn’t see in the article, but why settle on SHA2-256? Why not something bigger or newer such as SHA2-512 or SHA3-256? Or why not a variable length hash like SHAKE256?

chmaynard 6y ago
I believe this is discussed in https://lwn.net/Articles/811068/ https://lwn.net/Articles/811068/

rudolph9 6y ago

Perhaps I missed it but what are we doing to future proof the hash algorithm to when we need to transition away from sha256? Seems like we’re going to just have the same problem in another decade if we don’t address this now?

matt_kantor 6y ago
> In closing, it is worth noting that one of the reasons this transition has been so hard is that the original Git implementation was not designed to swap out hashing algorithms. Much of the work put in to the SHA-256 implementation has been walking back this initial design flaw. With these changes almost complete, it not only provides an alternative to SHA-1, but also makes Git fundamentally indifferent to the hashing algorithm used. This should make Git more adaptable in the future should the need to replace SHA-256 with something stronger arise. That's the last paragraph of the article.

dec0dedab0de 6y ago

Wouldnt an easier solution be to keep the sha-1 to work exactly as is, but add additional hashes to verify the files havent been maliciously modified to keep the same hash. It seems almost impossible to craft a file that has different hashing algorithms equal the same thing. Assuming older versions dont explode when new data is added, it should stay backwards compatible. The sha-1 and short hashes would be the name that is displayed and used for checking out commits, but not relied upon for security.

rudolph9 6y ago

I wish more people would adopt (and better formalize) multihash and related projects https://github.com/multiformats/multihash https://github.com/multiformats/multihash It’s a really simple good idea that has developed in the ipfs world.

kazinator 6y ago

Is there a way to opt out of this other than pinning your git executables to an old version or forking? I want to make sure all my git repos are forever readable by the original git they were produced with, even if newer git versions are used for producing commits. The article makes some troubling comments like: > countless repositories need to be transitioned from SHA-1 to SHA-256. Absolutely never doing this.

gentleman11 6y ago

I am working on a game and version control in the gaming world is definitely weird to somebody coming from web dev. Almost nobody in this world uses git, they all use perforce, svn, and plastic. Apparently got doesn’t deal with binary assets well; even with lfs, it’s hard to find hosting for your 100-500GB repositories that also supports file locking (another binary-specific feature needed for games that many hosts don’t seem to support for some reason). I wanted to try lfs, but where do you actually go to find cheap hosting for a 100-150GB repo?