1Git hash function transition 2============================ 3 4Objective 5--------- 6Migrate Git from SHA-1 to a stronger hash function. 7 8Background 9---------- 10At its core, the Git version control system is a content addressable 11filesystem. It uses the SHA-1 hash function to name content. For 12example, files, directories, and revisions are referred to by hash 13values unlike in other traditional version control systems where files 14or versions are referred to via sequential numbers. The use of a hash 15function to address its content delivers a few advantages: 16 17* Integrity checking is easy. Bit flips, for example, are easily 18 detected, as the hash of corrupted content does not match its name. 19* Lookup of objects is fast. 20 21Using a cryptographically secure hash function brings additional 22advantages: 23 24* Object names can be signed and third parties can trust the hash to 25 address the signed object and all objects it references. 26* Communication using Git protocol and out of band communication 27 methods have a short reliable string that can be used to reliably 28 address stored content. 29 30Over time some flaws in SHA-1 have been discovered by security 31researchers. https://shattered.io demonstrated a practical SHA-1 hash 32collision. As a result, SHA-1 cannot be considered cryptographically 33secure any more. This impacts the communication of hash values because 34we cannot trust that a given hash value represents the known good 35version of content that the speaker intended. 36 37SHA-1 still possesses the other properties such as fast object lookup 38and safe error checking, but other hash functions are equally suitable 39that are believed to be cryptographically secure. 40 41Goals 42----- 43Where NewHash is a strong 256-bit hash function to replace SHA-1 (see 44"Selection of a New Hash", below): 45 461. The transition to NewHash can be done one local repository at a time. 47 a. Requiring no action by any other party. 48 b. A NewHash repository can communicate with SHA-1 Git servers 49 (push/fetch). 50 c. Users can use SHA-1 and NewHash identifiers for objects 51 interchangeably (see "Object names on the command line", below). 52 d. New signed objects make use of a stronger hash function than 53 SHA-1 for their security guarantees. 542. Allow a complete transition away from SHA-1. 55 a. Local metadata for SHA-1 compatibility can be removed from a 56 repository if compatibility with SHA-1 is no longer needed. 573. Maintainability throughout the process. 58 a. The object format is kept simple and consistent. 59 b. Creation of a generalized repository conversion tool. 60 61Non-Goals 62--------- 631. Add NewHash support to Git protocol. This is valuable and the 64 logical next step but it is out of scope for this initial design. 652. Transparently improving the security of existing SHA-1 signed 66 objects. 673. Intermixing objects using multiple hash functions in a single 68 repository. 694. Taking the opportunity to fix other bugs in Git's formats and 70 protocols. 715. Shallow clones and fetches into a NewHash repository. (This will 72 change when we add NewHash support to Git protocol.) 736. Skip fetching some submodules of a project into a NewHash 74 repository. (This also depends on NewHash support in Git 75 protocol.) 76 77Overview 78-------- 79We introduce a new repository format extension. Repositories with this 80extension enabled use NewHash instead of SHA-1 to name their objects. 81This affects both object names and object content --- both the names 82of objects and all references to other objects within an object are 83switched to the new hash function. 84 85NewHash repositories cannot be read by older versions of Git. 86 87Alongside the packfile, a NewHash repository stores a bidirectional 88mapping between NewHash and SHA-1 object names. The mapping is generated 89locally and can be verified using "git fsck". Object lookups use this 90mapping to allow naming objects using either their SHA-1 and NewHash names 91interchangeably. 92 93"git cat-file" and "git hash-object" gain options to display an object 94in its sha1 form and write an object given its sha1 form. This 95requires all objects referenced by that object to be present in the 96object database so that they can be named using the appropriate name 97(using the bidirectional hash mapping). 98 99Fetches from a SHA-1 based server convert the fetched objects into 100NewHash form and record the mapping in the bidirectional mapping table 101(see below for details). Pushes to a SHA-1 based server convert the 102objects being pushed into sha1 form so the server does not have to be 103aware of the hash function the client is using. 104 105Detailed Design 106--------------- 107Repository format extension 108~~~~~~~~~~~~~~~~~~~~~~~~~~~ 109A NewHash repository uses repository format version `1` (see 110Documentation/technical/repository-version.txt) with extensions 111`objectFormat` and `compatObjectFormat`: 112 113 [core] 114 repositoryFormatVersion = 1 115 [extensions] 116 objectFormat = newhash 117 compatObjectFormat = sha1 118 119The combination of setting `core.repositoryFormatVersion=1` and 120populating `extensions.*` ensures that all versions of Git later than 121`v0.99.9l` will die instead of trying to operate on the NewHash 122repository, instead producing an error message. 123 124 # Between v0.99.9l and v2.7.0 125 $ git status 126 fatal: Expected git repo version <= 0, found 1 127 # After v2.7.0 128 $ git status 129 fatal: unknown repository extensions found: 130 objectformat 131 compatobjectformat 132 133See the "Transition plan" section below for more details on these 134repository extensions. 135 136Object names 137~~~~~~~~~~~~ 138Objects can be named by their 40 hexadecimal digit sha1-name or 64 139hexadecimal digit newhash-name, plus names derived from those (see 140gitrevisions(7)). 141 142The sha1-name of an object is the SHA-1 of the concatenation of its 143type, length, a nul byte, and the object's sha1-content. This is the 144traditional <sha1> used in Git to name objects. 145 146The newhash-name of an object is the NewHash of the concatenation of its 147type, length, a nul byte, and the object's newhash-content. 148 149Object format 150~~~~~~~~~~~~~ 151The content as a byte sequence of a tag, commit, or tree object named 152by sha1 and newhash differ because an object named by newhash-name refers to 153other objects by their newhash-names and an object named by sha1-name 154refers to other objects by their sha1-names. 155 156The newhash-content of an object is the same as its sha1-content, except 157that objects referenced by the object are named using their newhash-names 158instead of sha1-names. Because a blob object does not refer to any 159other object, its sha1-content and newhash-content are the same. 160 161The format allows round-trip conversion between newhash-content and 162sha1-content. 163 164Object storage 165~~~~~~~~~~~~~~ 166Loose objects use zlib compression and packed objects use the packed 167format described in Documentation/technical/pack-format.txt, just like 168today. The content that is compressed and stored uses newhash-content 169instead of sha1-content. 170 171Pack index 172~~~~~~~~~~ 173Pack index (.idx) files use a new v3 format that supports multiple 174hash functions. They have the following format (all integers are in 175network byte order): 176 177- A header appears at the beginning and consists of the following: 178 - The 4-byte pack index signature: '\377t0c' 179 - 4-byte version number: 3 180 - 4-byte length of the header section, including the signature and 181 version number 182 - 4-byte number of objects contained in the pack 183 - 4-byte number of object formats in this pack index: 2 184 - For each object format: 185 - 4-byte format identifier (e.g., 'sha1' for SHA-1) 186 - 4-byte length in bytes of shortened object names. This is the 187 shortest possible length needed to make names in the shortened 188 object name table unambiguous. 189 - 4-byte integer, recording where tables relating to this format 190 are stored in this index file, as an offset from the beginning. 191 - 4-byte offset to the trailer from the beginning of this file. 192 - Zero or more additional key/value pairs (4-byte key, 4-byte 193 value). Only one key is supported: 'PSRC'. See the "Loose objects 194 and unreachable objects" section for supported values and how this 195 is used. All other keys are reserved. Readers must ignore 196 unrecognized keys. 197- Zero or more NUL bytes. This can optionally be used to improve the 198 alignment of the full object name table below. 199- Tables for the first object format: 200 - A sorted table of shortened object names. These are prefixes of 201 the names of all objects in this pack file, packed together 202 without offset values to reduce the cache footprint of the binary 203 search for a specific object name. 204 205 - A table of full object names in pack order. This allows resolving 206 a reference to "the nth object in the pack file" (from a 207 reachability bitmap or from the next table of another object 208 format) to its object name. 209 210 - A table of 4-byte values mapping object name order to pack order. 211 For an object in the table of sorted shortened object names, the 212 value at the corresponding index in this table is the index in the 213 previous table for that same object. 214 215 This can be used to look up the object in reachability bitmaps or 216 to look up its name in another object format. 217 218 - A table of 4-byte CRC32 values of the packed object data, in the 219 order that the objects appear in the pack file. This is to allow 220 compressed data to be copied directly from pack to pack during 221 repacking without undetected data corruption. 222 223 - A table of 4-byte offset values. For an object in the table of 224 sorted shortened object names, the value at the corresponding 225 index in this table indicates where that object can be found in 226 the pack file. These are usually 31-bit pack file offsets, but 227 large offsets are encoded as an index into the next table with the 228 most significant bit set. 229 230 - A table of 8-byte offset entries (empty for pack files less than 231 2 GiB). Pack files are organized with heavily used objects toward 232 the front, so most object references should not need to refer to 233 this table. 234- Zero or more NUL bytes. 235- Tables for the second object format, with the same layout as above, 236 up to and not including the table of CRC32 values. 237- Zero or more NUL bytes. 238- The trailer consists of the following: 239 - A copy of the 20-byte NewHash checksum at the end of the 240 corresponding packfile. 241 242 - 20-byte NewHash checksum of all of the above. 243 244Loose object index 245~~~~~~~~~~~~~~~~~~ 246A new file $GIT_OBJECT_DIR/loose-object-idx contains information about 247all loose objects. Its format is 248 249 # loose-object-idx 250 (newhash-name SP sha1-name LF)* 251 252where the object names are in hexadecimal format. The file is not 253sorted. 254 255The loose object index is protected against concurrent writes by a 256lock file $GIT_OBJECT_DIR/loose-object-idx.lock. To add a new loose 257object: 258 2591. Write the loose object to a temporary file, like today. 2602. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the lock. 2613. Rename the loose object into place. 2624. Open loose-object-idx with O_APPEND and write the new object 2635. Unlink loose-object-idx.lock to release the lock. 264 265To remove entries (e.g. in "git pack-refs" or "git-prune"): 266 2671. Open loose-object-idx.lock with O_CREAT | O_EXCL to acquire the 268 lock. 2692. Write the new content to loose-object-idx.lock. 2703. Unlink any loose objects being removed. 2714. Rename to replace loose-object-idx, releasing the lock. 272 273Translation table 274~~~~~~~~~~~~~~~~~ 275The index files support a bidirectional mapping between sha1-names 276and newhash-names. The lookup proceeds similarly to ordinary object 277lookups. For example, to convert a sha1-name to a newhash-name: 278 279 1. Look for the object in idx files. If a match is present in the 280 idx's sorted list of truncated sha1-names, then: 281 a. Read the corresponding entry in the sha1-name order to pack 282 name order mapping. 283 b. Read the corresponding entry in the full sha1-name table to 284 verify we found the right object. If it is, then 285 c. Read the corresponding entry in the full newhash-name table. 286 That is the object's newhash-name. 287 2. Check for a loose object. Read lines from loose-object-idx until 288 we find a match. 289 290Step (1) takes the same amount of time as an ordinary object lookup: 291O(number of packs * log(objects per pack)). Step (2) takes O(number of 292loose objects) time. To maintain good performance it will be necessary 293to keep the number of loose objects low. See the "Loose objects and 294unreachable objects" section below for more details. 295 296Since all operations that make new objects (e.g., "git commit") add 297the new objects to the corresponding index, this mapping is possible 298for all objects in the object store. 299 300Reading an object's sha1-content 301~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 302The sha1-content of an object can be read by converting all newhash-names 303its newhash-content references to sha1-names using the translation table. 304 305Fetch 306~~~~~ 307Fetching from a SHA-1 based server requires translating between SHA-1 308and NewHash based representations on the fly. 309 310SHA-1s named in the ref advertisement that are present on the client 311can be translated to NewHash and looked up as local objects using the 312translation table. 313 314Negotiation proceeds as today. Any "have"s generated locally are 315converted to SHA-1 before being sent to the server, and SHA-1s 316mentioned by the server are converted to NewHash when looking them up 317locally. 318 319After negotiation, the server sends a packfile containing the 320requested objects. We convert the packfile to NewHash format using 321the following steps: 322 3231. index-pack: inflate each object in the packfile and compute its 324 SHA-1. Objects can contain deltas in OBJ_REF_DELTA format against 325 objects the client has locally. These objects can be looked up 326 using the translation table and their sha1-content read as 327 described above to resolve the deltas. 3282. topological sort: starting at the "want"s from the negotiation 329 phase, walk through objects in the pack and emit a list of them, 330 excluding blobs, in reverse topologically sorted order, with each 331 object coming later in the list than all objects it references. 332 (This list only contains objects reachable from the "wants". If the 333 pack from the server contained additional extraneous objects, then 334 they will be discarded.) 3353. convert to newhash: open a new (newhash) packfile. Read the topologically 336 sorted list just generated. For each object, inflate its 337 sha1-content, convert to newhash-content, and write it to the newhash 338 pack. Record the new sha1<->newhash mapping entry for use in the idx. 3394. sort: reorder entries in the new pack to match the order of objects 340 in the pack the server generated and include blobs. Write a newhash idx 341 file 3425. clean up: remove the SHA-1 based pack file, index, and 343 topologically sorted list obtained from the server in steps 1 344 and 2. 345 346Step 3 requires every object referenced by the new object to be in the 347translation table. This is why the topological sort step is necessary. 348 349As an optimization, step 1 could write a file describing what non-blob 350objects each object it has inflated from the packfile references. This 351makes the topological sort in step 2 possible without inflating the 352objects in the packfile for a second time. The objects need to be 353inflated again in step 3, for a total of two inflations. 354 355Step 4 is probably necessary for good read-time performance. "git 356pack-objects" on the server optimizes the pack file for good data 357locality (see Documentation/technical/pack-heuristics.txt). 358 359Details of this process are likely to change. It will take some 360experimenting to get this to perform well. 361 362Push 363~~~~ 364Push is simpler than fetch because the objects referenced by the 365pushed objects are already in the translation table. The sha1-content 366of each object being pushed can be read as described in the "Reading 367an object's sha1-content" section to generate the pack written by git 368send-pack. 369 370Signed Commits 371~~~~~~~~~~~~~~ 372We add a new field "gpgsig-newhash" to the commit object format to allow 373signing commits without relying on SHA-1. It is similar to the 374existing "gpgsig" field. Its signed payload is the newhash-content of the 375commit object with any "gpgsig" and "gpgsig-newhash" fields removed. 376 377This means commits can be signed 3781. using SHA-1 only, as in existing signed commit objects 3792. using both SHA-1 and NewHash, by using both gpgsig-newhash and gpgsig 380 fields. 3813. using only NewHash, by only using the gpgsig-newhash field. 382 383Old versions of "git verify-commit" can verify the gpgsig signature in 384cases (1) and (2) without modifications and view case (3) as an 385ordinary unsigned commit. 386 387Signed Tags 388~~~~~~~~~~~ 389We add a new field "gpgsig-newhash" to the tag object format to allow 390signing tags without relying on SHA-1. Its signed payload is the 391newhash-content of the tag with its gpgsig-newhash field and "-----BEGIN PGP 392SIGNATURE-----" delimited in-body signature removed. 393 394This means tags can be signed 3951. using SHA-1 only, as in existing signed tag objects 3962. using both SHA-1 and NewHash, by using gpgsig-newhash and an in-body 397 signature. 3983. using only NewHash, by only using the gpgsig-newhash field. 399 400Mergetag embedding 401~~~~~~~~~~~~~~~~~~ 402The mergetag field in the sha1-content of a commit contains the 403sha1-content of a tag that was merged by that commit. 404 405The mergetag field in the newhash-content of the same commit contains the 406newhash-content of the same tag. 407 408Submodules 409~~~~~~~~~~ 410To convert recorded submodule pointers, you need to have the converted 411submodule repository in place. The translation table of the submodule 412can be used to look up the new hash. 413 414Loose objects and unreachable objects 415~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 416Fast lookups in the loose-object-idx require that the number of loose 417objects not grow too high. 418 419"git gc --auto" currently waits for there to be 6700 loose objects 420present before consolidating them into a packfile. We will need to 421measure to find a more appropriate threshold for it to use. 422 423"git gc --auto" currently waits for there to be 50 packs present 424before combining packfiles. Packing loose objects more aggressively 425may cause the number of pack files to grow too quickly. This can be 426mitigated by using a strategy similar to Martin Fick's exponential 427rolling garbage collection script: 428https://gerrit-review.googlesource.com/c/gerrit/+/35215 429 430"git gc" currently expels any unreachable objects it encounters in 431pack files to loose objects in an attempt to prevent a race when 432pruning them (in case another process is simultaneously writing a new 433object that refers to the about-to-be-deleted object). This leads to 434an explosion in the number of loose objects present and disk space 435usage due to the objects in delta form being replaced with independent 436loose objects. Worse, the race is still present for loose objects. 437 438Instead, "git gc" will need to move unreachable objects to a new 439packfile marked as UNREACHABLE_GARBAGE (using the PSRC field; see 440below). To avoid the race when writing new objects referring to an 441about-to-be-deleted object, code paths that write new objects will 442need to copy any objects from UNREACHABLE_GARBAGE packs that they 443refer to to new, non-UNREACHABLE_GARBAGE packs (or loose objects). 444UNREACHABLE_GARBAGE are then safe to delete if their creation time (as 445indicated by the file's mtime) is long enough ago. 446 447To avoid a proliferation of UNREACHABLE_GARBAGE packs, they can be 448combined under certain circumstances. If "gc.garbageTtl" is set to 449greater than one day, then packs created within a single calendar day, 450UTC, can be coalesced together. The resulting packfile would have an 451mtime before midnight on that day, so this makes the effective maximum 452ttl the garbageTtl + 1 day. If "gc.garbageTtl" is less than one day, 453then we divide the calendar day into intervals one-third of that ttl 454in duration. Packs created within the same interval can be coalesced 455together. The resulting packfile would have an mtime before the end of 456the interval, so this makes the effective maximum ttl equal to the 457garbageTtl * 4/3. 458 459This rule comes from Thirumala Reddy Mutchukota's JGit change 460https://git.eclipse.org/r/90465. 461 462The UNREACHABLE_GARBAGE setting goes in the PSRC field of the pack 463index. More generally, that field indicates where a pack came from: 464 465 - 1 (PACK_SOURCE_RECEIVE) for a pack received over the network 466 - 2 (PACK_SOURCE_AUTO) for a pack created by a lightweight 467 "gc --auto" operation 468 - 3 (PACK_SOURCE_GC) for a pack created by a full gc 469 - 4 (PACK_SOURCE_UNREACHABLE_GARBAGE) for potential garbage 470 discovered by gc 471 - 5 (PACK_SOURCE_INSERT) for locally created objects that were 472 written directly to a pack file, e.g. from "git add ." 473 474This information can be useful for debugging and for "gc --auto" to 475make appropriate choices about which packs to coalesce. 476 477Caveats 478------- 479Invalid objects 480~~~~~~~~~~~~~~~ 481The conversion from sha1-content to newhash-content retains any 482brokenness in the original object (e.g., tree entry modes encoded with 483leading 0, tree objects whose paths are not sorted correctly, and 484commit objects without an author or committer). This is a deliberate 485feature of the design to allow the conversion to round-trip. 486 487More profoundly broken objects (e.g., a commit with a truncated "tree" 488header line) cannot be converted but were not usable by current Git 489anyway. 490 491Shallow clone and submodules 492~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 493Because it requires all referenced objects to be available in the 494locally generated translation table, this design does not support 495shallow clone or unfetched submodules. Protocol improvements might 496allow lifting this restriction. 497 498Alternates 499~~~~~~~~~~ 500For the same reason, a newhash repository cannot borrow objects from a 501sha1 repository using objects/info/alternates or 502$GIT_ALTERNATE_OBJECT_REPOSITORIES. 503 504git notes 505~~~~~~~~~ 506The "git notes" tool annotates objects using their sha1-name as key. 507This design does not describe a way to migrate notes trees to use 508newhash-names. That migration is expected to happen separately (for 509example using a file at the root of the notes tree to describe which 510hash it uses). 511 512Server-side cost 513~~~~~~~~~~~~~~~~ 514Until Git protocol gains NewHash support, using NewHash based storage 515on public-facing Git servers is strongly discouraged. Once Git 516protocol gains NewHash support, NewHash based servers are likely not 517to support SHA-1 compatibility, to avoid what may be a very expensive 518hash reencode during clone and to encourage peers to modernize. 519 520The design described here allows fetches by SHA-1 clients of a 521personal NewHash repository because it's not much more difficult than 522allowing pushes from that repository. This support needs to be guarded 523by a configuration option --- servers like git.kernel.org that serve a 524large number of clients would not be expected to bear that cost. 525 526Meaning of signatures 527~~~~~~~~~~~~~~~~~~~~~ 528The signed payload for signed commits and tags does not explicitly 529name the hash used to identify objects. If some day Git adopts a new 530hash function with the same length as the current SHA-1 (40 531hexadecimal digit) or NewHash (64 hexadecimal digit) objects then the 532intent behind the PGP signed payload in an object signature is 533unclear: 534 535 object e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7 536 type commit 537 tag v2.12.0 538 tagger Junio C Hamano <gitster@pobox.com> 1487962205 -0800 539 540 Git 2.12 541 542Does this mean Git v2.12.0 is the commit with sha1-name 543e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7 or the commit with 544new-40-digit-hash-name e7e07d5a4fcc2a203d9873968ad3e6bd4d7419d7? 545 546Fortunately NewHash and SHA-1 have different lengths. If Git starts 547using another hash with the same length to name objects, then it will 548need to change the format of signed payloads using that hash to 549address this issue. 550 551Object names on the command line 552~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 553To support the transition (see Transition plan below), this design 554supports four different modes of operation: 555 556 1. ("dark launch") Treat object names input by the user as SHA-1 and 557 convert any object names written to output to SHA-1, but store 558 objects using NewHash. This allows users to test the code with no 559 visible behavior change except for performance. This allows 560 allows running even tests that assume the SHA-1 hash function, to 561 sanity-check the behavior of the new mode. 562 563 2. ("early transition") Allow both SHA-1 and NewHash object names in 564 input. Any object names written to output use SHA-1. This allows 565 users to continue to make use of SHA-1 to communicate with peers 566 (e.g. by email) that have not migrated yet and prepares for mode 3. 567 568 3. ("late transition") Allow both SHA-1 and NewHash object names in 569 input. Any object names written to output use NewHash. In this 570 mode, users are using a more secure object naming method by 571 default. The disruption is minimal as long as most of their peers 572 are in mode 2 or mode 3. 573 574 4. ("post-transition") Treat object names input by the user as 575 NewHash and write output using NewHash. This is safer than mode 3 576 because there is less risk that input is incorrectly interpreted 577 using the wrong hash function. 578 579The mode is specified in configuration. 580 581The user can also explicitly specify which format to use for a 582particular revision specifier and for output, overriding the mode. For 583example: 584 585git --output-format=sha1 log abac87a^{sha1}..f787cac^{newhash} 586 587Selection of a New Hash 588----------------------- 589In early 2005, around the time that Git was written, Xiaoyun Wang, 590Yiqun Lisa Yin, and Hongbo Yu announced an attack finding SHA-1 591collisions in 2^69 operations. In August they published details. 592Luckily, no practical demonstrations of a collision in full SHA-1 were 593published until 10 years later, in 2017. 594 595The hash function NewHash to replace SHA-1 should be stronger than 596SHA-1 was: we would like it to be trustworthy and useful in practice 597for at least 10 years. 598 599Some other relevant properties: 600 6011. A 256-bit hash (long enough to match common security practice; not 602 excessively long to hurt performance and disk usage). 603 6042. High quality implementations should be widely available (e.g. in 605 OpenSSL). 606 6073. The hash function's properties should match Git's needs (e.g. Git 608 requires collision and 2nd preimage resistance and does not require 609 length extension resistance). 610 6114. As a tiebreaker, the hash should be fast to compute (fortunately 612 many contenders are faster than SHA-1). 613 614Some hashes under consideration are SHA-256, SHA-512/256, SHA-256x16, 615K12, and BLAKE2bp-256. 616 617Transition plan 618--------------- 619Some initial steps can be implemented independently of one another: 620- adding a hash function API (vtable) 621- teaching fsck to tolerate the gpgsig-newhash field 622- excluding gpgsig-* from the fields copied by "git commit --amend" 623- annotating tests that depend on SHA-1 values with a SHA1 test 624 prerequisite 625- using "struct object_id", GIT_MAX_RAWSZ, and GIT_MAX_HEXSZ 626 consistently instead of "unsigned char *" and the hardcoded 627 constants 20 and 40. 628- introducing index v3 629- adding support for the PSRC field and safer object pruning 630 631 632The first user-visible change is the introduction of the objectFormat 633extension (without compatObjectFormat). This requires: 634- implementing the loose-object-idx 635- teaching fsck about this mode of operation 636- using the hash function API (vtable) when computing object names 637- signing objects and verifying signatures 638- rejecting attempts to fetch from or push to an incompatible 639 repository 640 641Next comes introduction of compatObjectFormat: 642- translating object names between object formats 643- translating object content between object formats 644- generating and verifying signatures in the compat format 645- adding appropriate index entries when adding a new object to the 646 object store 647- --output-format option 648- ^{sha1} and ^{newhash} revision notation 649- configuration to specify default input and output format (see 650 "Object names on the command line" above) 651 652The next step is supporting fetches and pushes to SHA-1 repositories: 653- allow pushes to a repository using the compat format 654- generate a topologically sorted list of the SHA-1 names of fetched 655 objects 656- convert the fetched packfile to newhash format and generate an idx 657 file 658- re-sort to match the order of objects in the fetched packfile 659 660The infrastructure supporting fetch also allows converting an existing 661repository. In converted repositories and new clones, end users can 662gain support for the new hash function without any visible change in 663behavior (see "dark launch" in the "Object names on the command line" 664section). In particular this allows users to verify NewHash signatures 665on objects in the repository, and it should ensure the transition code 666is stable in production in preparation for using it more widely. 667 668Over time projects would encourage their users to adopt the "early 669transition" and then "late transition" modes to take advantage of the 670new, more futureproof NewHash object names. 671 672When objectFormat and compatObjectFormat are both set, commands 673generating signatures would generate both SHA-1 and NewHash signatures 674by default to support both new and old users. 675 676In projects using NewHash heavily, users could be encouraged to adopt 677the "post-transition" mode to avoid accidentally making implicit use 678of SHA-1 object names. 679 680Once a critical mass of users have upgraded to a version of Git that 681can verify NewHash signatures and have converted their existing 682repositories to support verifying them, we can add support for a 683setting to generate only NewHash signatures. This is expected to be at 684least a year later. 685 686That is also a good moment to advertise the ability to convert 687repositories to use NewHash only, stripping out all SHA-1 related 688metadata. This improves performance by eliminating translation 689overhead and security by avoiding the possibility of accidentally 690relying on the safety of SHA-1. 691 692Updating Git's protocols to allow a server to specify which hash 693functions it supports is also an important part of this transition. It 694is not discussed in detail in this document but this transition plan 695assumes it happens. :) 696 697Alternatives considered 698----------------------- 699Upgrading everyone working on a particular project on a flag day 700~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 701Projects like the Linux kernel are large and complex enough that 702flipping the switch for all projects based on the repository at once 703is infeasible. 704 705Not only would all developers and server operators supporting 706developers have to switch on the same flag day, but supporting tooling 707(continuous integration, code review, bug trackers, etc) would have to 708be adapted as well. This also makes it difficult to get early feedback 709from some project participants testing before it is time for mass 710adoption. 711 712Using hash functions in parallel 713~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 714(e.g. https://public-inbox.org/git/22708.8913.864049.452252@chiark.greenend.org.uk/ ) 715Objects newly created would be addressed by the new hash, but inside 716such an object (e.g. commit) it is still possible to address objects 717using the old hash function. 718* You cannot trust its history (needed for bisectability) in the 719 future without further work 720* Maintenance burden as the number of supported hash functions grows 721 (they will never go away, so they accumulate). In this proposal, by 722 comparison, converted objects lose all references to SHA-1. 723 724Signed objects with multiple hashes 725~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 726Instead of introducing the gpgsig-newhash field in commit and tag objects 727for newhash-content based signatures, an earlier version of this design 728added "hash newhash <newhash-name>" fields to strengthen the existing 729sha1-content based signatures. 730 731In other words, a single signature was used to attest to the object 732content using both hash functions. This had some advantages: 733* Using one signature instead of two speeds up the signing process. 734* Having one signed payload with both hashes allows the signer to 735 attest to the sha1-name and newhash-name referring to the same object. 736* All users consume the same signature. Broken signatures are likely 737 to be detected quickly using current versions of git. 738 739However, it also came with disadvantages: 740* Verifying a signed object requires access to the sha1-names of all 741 objects it references, even after the transition is complete and 742 translation table is no longer needed for anything else. To support 743 this, the design added fields such as "hash sha1 tree <sha1-name>" 744 and "hash sha1 parent <sha1-name>" to the newhash-content of a signed 745 commit, complicating the conversion process. 746* Allowing signed objects without a sha1 (for after the transition is 747 complete) complicated the design further, requiring a "nohash sha1" 748 field to suppress including "hash sha1" fields in the newhash-content 749 and signed payload. 750 751Lazily populated translation table 752~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 753Some of the work of building the translation table could be deferred to 754push time, but that would significantly complicate and slow down pushes. 755Calculating the sha1-name at object creation time at the same time it is 756being streamed to disk and having its newhash-name calculated should be 757an acceptable cost. 758 759Document History 760---------------- 761 7622017-03-03 763bmwill@google.com, jonathantanmy@google.com, jrnieder@gmail.com, 764sbeller@google.com 765 766Initial version sent to 767http://public-inbox.org/git/20170304011251.GA26789@aiede.mtv.corp.google.com 768 7692017-03-03 jrnieder@gmail.com 770Incorporated suggestions from jonathantanmy and sbeller: 771* describe purpose of signed objects with each hash type 772* redefine signed object verification using object content under the 773 first hash function 774 7752017-03-06 jrnieder@gmail.com 776* Use SHA3-256 instead of SHA2 (thanks, Linus and brian m. carlson).[1][2] 777* Make sha3-based signatures a separate field, avoiding the need for 778 "hash" and "nohash" fields (thanks to peff[3]). 779* Add a sorting phase to fetch (thanks to Junio for noticing the need 780 for this). 781* Omit blobs from the topological sort during fetch (thanks to peff). 782* Discuss alternates, git notes, and git servers in the caveats 783 section (thanks to Junio Hamano, brian m. carlson[4], and Shawn 784 Pearce). 785* Clarify language throughout (thanks to various commenters, 786 especially Junio). 787 7882017-09-27 jrnieder@gmail.com, sbeller@google.com 789* use placeholder NewHash instead of SHA3-256 790* describe criteria for picking a hash function. 791* include a transition plan (thanks especially to Brandon Williams 792 for fleshing these ideas out) 793* define the translation table (thanks, Shawn Pearce[5], Jonathan 794 Tan, and Masaya Suzuki) 795* avoid loose object overhead by packing more aggressively in 796 "git gc --auto" 797 798[1] http://public-inbox.org/git/CA+55aFzJtejiCjV0e43+9oR3QuJK2PiFiLQemytoLpyJWe6P9w@mail.gmail.com/ 799[2] http://public-inbox.org/git/CA+55aFz+gkAsDZ24zmePQuEs1XPS9BP_s8O7Q4wQ7LV7X5-oDA@mail.gmail.com/ 800[3] http://public-inbox.org/git/20170306084353.nrns455dvkdsfgo5@sigill.intra.peff.net/ 801[4] http://public-inbox.org/git/20170304224936.rqqtkdvfjgyezsht@genre.crustytoothpaste.net 802[5] https://public-inbox.org/git/CAJo=hJtoX9=AyLHHpUJS7fueV9ciZ_MNpnEPHUz8Whui6g9F0A@mail.gmail.com/