https://lwn.net/SubscriberLink/921787/949cf79f2599f734/ LWN.net Logo LWN .net News from the source LWN * Content + Weekly Edition + Archives + Search + Kernel + Security + Events calendar + Unread comments + ------------------------------------------------------------- + LWN FAQ + Write for us User: [ ] Password: [ ] [Log in] | [Subscribe] | [Register] Subscribe / Log in / New account Git archive generation meets Hyrum's law [LWN subscriber-only content] Welcome to LWN.net Free trial subscription The following subscription-only Try LWN for free for 1 content has been made available to month: no payment or you by an LWN subscriber. Thousands credit card required. of subscribers depend on LWN for Activate your trial the best news from the Linux and subscription now and see free software communities. If you why thousands of readers enjoy this article, please consider subscribe to LWN.net. accepting the trial offer on the right. Thank you for visiting LWN.net! By Jonathan Corbet February 2, 2023 On January 30, the GitHub blog carried a brief notice that the checksums of archives (such as tarballs) generated by the site had just changed. GitHub's engineers were seemingly unaware of the consequences of such a change -- consequences that were immediately evident to anybody familiar with either packaging systems or Hyrum's law. Those checksums were widely depended on by build systems, which immediately broke when the change went live; the resulting impact of jawbones hitting the floor was observed by seismographs worldwide. The change has been reverted for now, but it is worth looking at how GitHub managed to casually break vast numbers of build systems -- and why this sort of change will almost certainly happen again. One widely used GitHub feature is the ability to download an archive file of the state of the repository at an arbitrary commit; it is often used by build systems to obtain a specific release of a package of interest. Internally, this archive is created at request time by the git archive subcommand. Most build systems will compare the resulting archive against a separately stored checksum to be sure that the archive is as expected and has not been corrupted; if the checksum fails to match, the build will be aborted. So when the checksums of GitHub-generated tarballs abruptly changed, builds started failing. Unsurprisingly, people started to complain. The initial response from GitHub employee (and major Git contributor) brian m. carlson was less than fully understanding: I'm saying that policy has never been correct and we've never guaranteed stable checksums for archives, just like Git has never guaranteed that. I apologize that things are broken here and that there hasn't been clearer communication in the past on this, but our policy hasn't changed in over 4 years. This answer, it might be said, was not received well. Wyatt Anderson, for example, said: The collective amount of human effort it will take to break glass, recover broken build systems that are impacted by this change, and republish artifacts across entire software ecosystems could probably cure cancer. Please consider reverting this change as soon as possible. The outcry grew louder, and it took about two hours for Matt Cooper (another GitHub employee) to announce that the change was being reverted -- for now: "`we're reverting the change, and we'll communicate better about such changes in the future (including timelines)'". Builds resumed working, and peace reigned once again. The source of the problem The developers at GitHub did not wake up one morning and hatch a scheme to break large numbers of build systems; instead, all they did was upgrade the version of Git used internally. In June 2022, Rene Schedar changed git archive to use an internal implementation of the gzip compression algorithm rather than invoking the gzip program separately. This change, which found its way into the Git 2.38 release, allowed Git to drop the gzip dependency, more easily support compression across operating systems, and compress the data with less CPU time. It also caused git archive to compress files differently. While the uncompressed data is identical, the compressed form differs, so the checksum of the compressed data differs as well. Once this change landed on GitHub's production systems, the checksums for tarballs generated on the fly abruptly changed. GitHub backed out the change, either by reverting to an older Git or by explicitly configuring the use of the standalone gzip program, and the immediate problem went away. The resulting discussion on the Git mailing list has been relatively muted so far. Eli Schwartz started things off with a suggestion that Git should change its default back to using the external gzip program for now, then implement a "`v2 archive format'" using the internal compressor. Using a heuristic, git archive would always default to the older format for commits before some sort of cutoff date. That would ensure ongoing compatibility for older archives, but the idea of wiring that sort of heuristic into Git was not generally popular. AEvar Arnfjord Bjarmason, instead, suggested that the default could be changed to use the external gzip, retaining the internal implementation as an option or as a fallback should the external program not be found. The responsibility for output compatibility could then be shifted to the compression program: anybody who wants to ensure that their generated archive files do not change will have to ensure that their gzip does not change. Since the Git developers do not control that program, they cannot guarantee its forward compatibility in any case. Carlson, though, argued for avoiding stability guarantees -- especially implicit guarantees -- if possible: I made a change some years back to the archive format to fix the permissions on pax headers when extracted as files, and kernel.org was relying on that and broke. Linus yelled at me because of that. Since then, I've been very opposed to us guaranteeing output format consistency without explicitly doing so. I had sent some patches before that I don't think ever got picked up that documented this explicitly. I very much don't want people to come to rely on our behaviour unless we explicitly guarantee it. He went on to suggest that Git could guarantee the stability of the archive format in uncompressed form. That format would have to be versioned, though, since the SHA-256 transition, if and when it happens, will force changes in that format anyway (a claim that Bjarmason questioned). In general, carlson concluded, it may well become necessary for anybody who wants consistent results to decompress archive files before checking checksums. He later reiterated that, in his opinion, implementing a stable tar format is feasible, but adding compression is not: "`I personally feel that's too hard to get right and am not planning on working on it'". Konstantin Ryabitsev said that, while he understands carlson's desire to avoid committing to an output format, "`I also think it's one of those things that happen despite your best efforts to prevent it'". He suggested adding a --stable option to git archive that was guaranteed to not change. What next? As of this writing, the Git community has not decided whether to make any changes as the result of this episode. Bjarmason argued that the Git community should accommodate the needs of its users, even if they came to depend on a feature that was never advertised as being stable: That's unfortunate, and those people probably shouldn't have done that, but that's water under the bridge. I think it would be irresponsible to change the output willy-nilly at this point, especially when it seems rather easy to find some compromise everyone will be happy with. He has since posted a patch set restoring the old behavior, but also documenting that this behavior could change in the future. Committing to stability of this type is never a thing to be done lightly, though; such stability can be hard to maintain (especially when dealing with file formats defined by others) and can block other types of progress. For example, replacing gzip can yield better compression that can be performed more efficiently; an inability to move beyond that algorithm would prevent Git from obtaining those benefits. Even if Git restores the use of an external gzip program by default, that program might, itself, change, or downstream users like GitHub may decide that they no longer want to support that format. It would thus be unsurprising if this problem were to refuse to go away. The Git project is reluctant to add a stability guarantee to its maintenance load, and the same is true of its downstream users; GitHub has said that it would give some warning before a checksum change returns, but has not said that such a change would not happen. The developers and users of build systems may want to be rethinking their reliance on the specific compression format used by one proprietary service on the Internet. The next time problems turn up, they will not be able to say they haven't been warned. [Send a free link] Did you like this article? Please accept our trial subscription offer to be able to see more content like it and to participate in the discussion. ----------------------------------------- (Log in to post comments) Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:18 UTC (Thu) by dskoll (subscriber, #1630) [ Link] Couldn't the checksum be based on the uncompressed data? Kernel release signatures are based on the uncompressed data, for example. Sure, it would be a little annoying to have to uncompress to verify the archive integrity, but that would free up developers to tweak the compression to their hearts' content. It also means build processes that rely on checksums would need to be adjusted, but that would be a one-time adjustment. I suppose there's the risk of a compression bomb that could DoS build systems, but those would be relatively easy to detect... along with the checksum, store the size of the uncompressed data you expect and abort if it starts uncompressing to a larger size. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:19 UTC (Thu) by dskoll (subscriber, #1630) [ Link] Ah, just noticed this was mentioned in the article. Missed it first time around. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:25 UTC (Thu) by alonz (subscriber, #815) [Link] Why not do the opposite - instead of stabilizing the checksum, make it so that every single download will have a different checksum (by including some hidden field that is always randomized)? This way the "checksum is not a guarantee" becomes a real thing, and Hyrum gets a rest. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:44 UTC (Thu) by zdzichu (subscriber, #17118) [ Link] While interesting as a mental exercise, what would be the point of that? Checksums are used for specific purposes (e.g. checking for potential corruption or making sure you get exactly what you expect, not something with the same filename but different content) . Those purposes do not disappear when you make checksums useless. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:52 UTC (Thu) by geert (subscriber, #98403) [ Link] Relying on the checksums of the compressed archives sounds like a bad idea, as those archives don't exist on the server, but are generated on the fly, using an external program. Imagine you want to download the same archive in 10 years, what do you do when checksum verification fails? Download again? Go to a different server? What uniquely specifies the contents are the git commit ID (which is still sha1). And perhaps the checksum of the uncompressed archive (assumed git can keep that stable, and doesn't have to change it due to e.g. a security bug). [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 17:48 UTC (Thu) by mathstuf (subscriber, #69389) [ Link] `export-subst` and `export-ignore` can pull metadata from the commit in question and bake it into the archive (or exclude the file completely). What should have happened is that the creation of a release has an option to permalink the "Source code" links Github provides. Note that this is not suitable for projects using things like autoconf (as it would lack `configure`) or having submodules (as `git archive` just ignores them). [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 16:58 UTC (Thu) by farnz (subscriber, #17727) [ Link] The point is that the output of git archive when compressed is not stable. By making it unstable, so that each run of git archive requested compressed output of a given git commit has a different checksum, you stop people assuming that they can run git archive and get a fixed result - they know, instead, that each time you run git archive, you get a different answer. Once you've built the archive, you can checksum it and keep it as a stable artefact long into the future. You just don't have a guarantee that you can regenerate the archive from the source and get the same checksum - if you need to validate that a given artefact matches the source, you need to do a deeper dive of some form. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:47 UTC (Thu) by flussence (subscriber, #85566) [Link] Then the party publishing the stable checksum in this situation (i.e. not GitHub, it has never done so for these download links) can simply provide a corresponding stable tarball. [Reply to this comment] Was it github's fault? Posted Feb 2, 2023 16:35 UTC (Thu) by Wol (subscriber, #4433) [Link] And can we get the git archive request to add a flag to identify the chosen compression algorithm? It seems that it was actually a change to git. Yes it could have been a github employee who made that change (was it?), but it wasn't github's systems per se that caused the grief. Adding an (optional) flag means that we don't break existing systems, but by adding the flag I guess downstreams would get the benefit of faster downloads etc. And then, as I think someone suggested, if you start tagging your repository, if the default depends on the date of the tag being downloaded then github, gitlab, whoever can move to upgraded compression algorithms without breaking pre-existing stored checksums. In fact, could you store the compression algorithm of choice with the tag? Cheers, Wol [Reply to this comment] Was it github's fault? Posted Feb 2, 2023 17:56 UTC (Thu) by mathstuf (subscriber, #69389) [ Link] > In fact, could you store the compression algorithm of choice with the tag? This isn't about compression algorithm choice, but implementation. How would I record what `gzip` I used to make a source archive as part of the tag? What do I do for bz2, xz, zip, or any other compression format that I don't make on that day? Would I not be allowed to use a hypothetical SuperSqueeze algorithm on a tag of last year because it didn't exist then? [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 17:16 UTC (Thu) by ballombe (subscriber, #9523) [ Link] There is no reason the internal gzip implementation cannot produce the same output as the external one, really. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 18:06 UTC (Thu) by epa (subscriber, #39769) [Link] I think we need a 'canonical compressed form' for zlib / gzip / zip compressed data. It would correspond roughly to gzip -9. I mean the compression heuristics like how far to look in the sliding window for a match, and possibly fixing some choices in the Huffman coding (like if two sequences are equally probable, which codes to assign). With today's processing power, the tradeoff between compression speed and compressed size doesn't really matter. Nor does squeezing out the last few bytes. You just pick a fixed set of parameters that's easy to implement. For cryptographic applications you could, on decompressing, do an additional check that the data was indeed in canonical compressed format (just re-compress it and check). That way you have a one-to-one mapping between input data and compressed output, not one-to-many as now. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:31 UTC (Thu) by kilobyte (subscriber, #108024) [Link] For example, the gzip behaviour precludes any parallelization. Computers hardly get any faster single-threaded, there are MASSIVE improvements in core counts, vectorization, etc. Thus even if we stick with the ancient gzip format, we should go with pigz instead. But even that would break the holy github [tar]balls. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 18:33 UTC (Thu) by mathstuf (subscriber, #69389) [ Link] Sure. But what does that mean for Git reimplementations (JGit, gitoxide, etc.)? But if everything is going to pin things to GNU gzip behavior...that should be documented (and probably ported to the BSD utils and other such implementations which may exist). And that doesn't help bzip2, xz, or zstd at all. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:26 UTC (Thu) by ballombe (subscriber, #9523) [ Link] All I am saying is that that you can use an internal gzip without breaking checksum, so this a false dichotomy. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 17:56 UTC (Thu) by agateau (subscriber, #57569) [ Link] It seems to me the idea of generating the archives on the fly is wrong. GitHub (and other git forges) should generate the archive once, store the result and then always serve the same file. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 18:50 UTC (Thu) by sionescu (subscriber, #59410) [ Link] This is the right answer. Command line utilities generally don't have the expectation of producing a stable output, but the web pretty much has that expectation. Github should store an archive the first time a release tarball is fetched, and serve that forever. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:03 UTC (Thu) by NYKevin (subscriber, #129325) [ Link] I imagine they do have some degree of caching already - it would be very expensive to generate an archive every single time anyone in the world requests it. You are effectively proposing to keep things in the cache for eternity, but what is the benefit of doing that, compared to a more conventional cache invalidation strategy? It has multiple drawbacks: * Your cache uses an ever-growing amount of storage, which you would otherwise be using to host repositories, so now repository hosting gets more expensive. * After you have been doing this for a few years or so, the vast majority of your cache is holding data that nobody is ever going to look at again, so now you need to implement a hierarchical cache (i.e. push all the low-traffic files out to tape to cut down on costs). * But retrieving a file from tape probably takes *longer* than just generating a fresh archive, so your cache isn't a cache anymore, it's a bottleneck. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:30 UTC (Thu) by bnewbold (subscriber, #72587) [ Link] This was my response as well. Or at least, once an archive has been requested (downloaded), store that. It occurs to me that I've been assuming that the original issue was with "release" archives (aka, git tag'd commits resulting in tarballs). If the issue has been with pulling archives of arbitrary git commits, i'm less sympathetic to the assumption of stability, as it does seem reasonable to generate those on-the-fly and not persist the result. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 18:01 UTC (Thu) by walters (subscriber, #7396) [ Link] Personally I still think something along the lines of https:// github.com/cgwalters/git-evtag/ is the right solution. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 19:16 UTC (Thu) by flussence (subscriber, #85566) [Link] One thing I've not seen mention of anywhere: anything depending on these archives to be stable was *already* broken! They *already* change silently without rhyme or reason! It's enough of a problem that Gentoo has standing QA rules for _years_ now forbidding use of those tarballs. It's only getting attention now because someone, somewhere, saw an opportunity to go outrage-farming for clicks over it. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 22:05 UTC (Thu) by mjg59 (subscriber, #23239) [ Link] The tarballs in question do *not* change silently without rhyme or reason - this would have been noticed well before now. Github had previously asserted that these would remain stable. Are you confusing this situation with tarballs pointing at specific commits rather than tags? [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 22:32 UTC (Thu) by vivo (subscriber, #48315) [Link ] this! Github has releases which does exactly that provide an unchanging archive [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 22:36 UTC (Thu) by vivo (subscriber, #48315) [Link ] mjg59 already fixed my reasoning - they really broke releases [Reply to this comment] Outrage farming Posted Feb 2, 2023 22:36 UTC (Thu) by corbet (editor, #1) [Link] I'm curious as to where this "outrage farming" happened? Hopefully you're not referring to this article? The discussions I found were mostly in issue trackers and such - projects reacting to their builds failing. Not the best venue if one is hoping to accomplish some "outrage farming". [Reply to this comment] Would CHECKSUMS files help? Posted Feb 2, 2023 20:28 UTC (Thu) by akkornel (subscriber, #75292) [ Link] I wonder if one partial solution might be to produce CHECKSUMS files. For tags and releases, in addition to the existing downloads, have a CHECKSUMS file. Maybe call it CHECKSUMS.sha256 to say which algorithm was being used. The file would contain the checksums for the release artifacts (like installers), and also the auto-generated .zip and .tar.gz fles. Instead of having to cache .zip and .tar.gz files, GitHub would only have to cache the (presumably smaller) CHECKSUMS file. GitHub could make the convention that, instead of storing a static checksum in your CI, you store the URL to the CHECKSUMS file. When a back-end change is made that could affect the checksums, GitHub would delete the CHECKSUMS file from their local cache. When an un-cached CHECKSUMS file is requested, GitHub would regenerate it, returning an HTTP 503 Service Unavailable error if needed, possibly with a Retry-After header. This solution would not work for all downloads. For example, if you go a repo's main page, you can download the repo as a .zip file. That kind of download would not be covered by this. [Reply to this comment] Would CHECKSUMS files help? Posted Feb 2, 2023 20:35 UTC (Thu) by mathstuf (subscriber, #69389) [ Link] How does this solve the "need to be able to redo a build from 3 years ago that baked in hashes" problem? You can't go and rewrite all software that does this verification in the past. What should have been provided all this time is a button to do "add source archives as artifacts" button in releases to pin them at that point. Still can. They can even go and hit it via an internal script on every (public?) release in the system just to ensure that there's a better URL than the `/archive/` endpoint from today forward. [Reply to this comment] Would CHECKSUMS files help? Posted Feb 2, 2023 21:05 UTC (Thu) by ceplm (subscriber, #41334) [ Link] If you are not caching those tarballs, your system is already broken. To quote my former colleague, GCC developer: "We are sorry that our compiler processed this turd which pretends to be a syntactically correct C program and generated assembly from it. It will never happen again." [Reply to this comment] Would CHECKSUMS files help? Posted Feb 2, 2023 21:51 UTC (Thu) by mathstuf (subscriber, #69389) [ Link] Sure, but the other approach is like the Linux kernel's approach to stability: whoops, but we're stuck with it, please revert. Given how much stuff broke with this... FWIW, I agree that these links *should not* have been relied upon. Alas, they have been... It also seems to break every 3-5 years (2010 and 2017 at least). It's just that the amount of validation of these things today is...way more. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 20:36 UTC (Thu) by cesarb (subscriber, #6266) [ Link] Part of the reason why this could happen is that the standalone gzip program (as well as its underlying zlib library) has essentially fossilized: AFAIK, other than security fixes, its compression code hasn't changed much in decades. Contrast with zstd, which often changes its compression code for better compression or performance (or both); a new version of zstd will usually have a different output than an older version, at the same compression level. This can be felt when using delta RPMs for instance on Fedora: since Fedora currently uses zstd for its RPM packages, whenever they update the zstd library, the reconstruction of the full RPM from the delta RPM starts to fail (and it has to go back and download the full RPM) for a while, until both sides are again using the same zstd release. [Reply to this comment] Git archive generation meets Hyrum's law Posted Feb 2, 2023 21:15 UTC (Thu) by NYKevin (subscriber, #129325) [ Link] Why would you delta your compressed files? Wouldn't it be more efficient (and robust) to delta the uncompressed files, and then compress the deltas? [Reply to this comment] xkcd 1172 (Workflow) Posted Feb 2, 2023 20:43 UTC (Thu) by david.a.wheeler (subscriber, # 72896) [Link] Obligatory reference: https://xkcd.com/1172/ [Reply to this comment] Copyright (c) 2023, Eklektix, Inc. Comments and public postings are copyrighted by their creators. Linux is a registered trademark of Linus Torvalds