1 Subject: Transition plan for git to move to a new hash function
6 We run multiple object name subnamespaces in parallel, one for each
7 hash function. Each object lives in exactly one subnamespace.
8 Objects with identical content in the different object stores, named
9 by different hash functions, are different objects.
11 Objects may refer to objects living in different subnamespaces (ie,
12 named by a different hash function) to their own.
14 Packfiles need to be extended to be able to contain objects named by
15 new hash functions. Blob objects with identical contents but living
16 in different subnamespaces would ideally share storage.
18 Every program that invokes git or speaks git protocols will need to
19 understand the extended object name syntax.
21 Safety catches preferent accidental incorporation into a project of
22 incompatibly-new objects, or additional deprecatedly-old objects.
23 This allows for incremental deployment.
28 The object name textual syntax is extended as follows:
30 We declare that the object name syntax is henceforth
31 [A-Z]+[0-9a-z]+ | [0-9a-f]+
32 and that names [A-Z].* are deprecated as ref name components.
36 Full backwards compatibility is impossible, because the hash
37 function needs to be evident in the name, so the new names
38 must be disjoint from all old SHA-1 names.
40 We want a short but extensible syntax. The syntax should impose
41 minimal extra requirements on existing git users. In most
42 contexts where existing git users use hashes, ASCII alphanumeric
43 object names will fit. Use of punctuation such as : or even _
44 may give trouble to existing users, who are already using
45 such things as delimiters.
47 In existing deployments, refnames that differ only in case are
48 generally avoided (because they are troublesome on
49 case-insensitive filesystems). And conventionally refnames are
50 lower case. So names starting with an upper case letter will be
51 disjoint from most existing ref name components.
53 Even though we probably want to keep using hex, it is a good
54 idea to reserve the flexibility to use a more compact encoding,
55 while not excessively widening the existing permissible
58 Object names using SHA-1 are represented, in text, as at present.
60 Object names starting with uppercase ASCII letters H or later refer to
61 new hash functions. Programs that use `g<objectname>' should ideally
62 be changed to show `H<hash>' for hash function `H' rather than
67 Object names starting with A-F might look like hex. G is
68 reserved because of the way that many programs write
71 This gives us 19 new hash function values until we have to
72 starting using two-letter hash function prefixes, or decide to
75 (Truncated object names work as they do at the moment.)
77 Initially we define and assign one new hash function (and textual
78 object name encoding):
80 H<hex> where <hex> is the BLAKE2b hash of the object
83 We also reserve the following syntax for private experiments:
85 We declare that public releases of git will never accept such
88 Everywhere in the git object formats and git protocols, a new object
89 name (with hash function indicator) is permitted where an old object
92 A single object may refer to other objects by its own hash functon, or
93 by other hash functions. Ie, object references cross subnamespaces.
94 During all git operations, subnamespace boundaries in the object graph
97 Two additional restrictions: a tree object may be referenced only by
98 objects in the same subnamespace; and, a tree object may reference
99 blobs in its own subnamespace.
101 In binary protocols, where a SHA-1 object name in binary form was
102 previously used, a new codepoint must be allocated in a containing
103 structure (eg a new typecode). Usually, the new-format binary object
104 will have a new typecode and also an additional name hash indicator,
105 and it will also need a length field (as new hashes may be of
108 Whenever a new hash function textual syntax is defined, corresponding
109 binary format codepoint(s) are assigned. (Implementation details such
110 as the binary format specification is outside the scope of this
116 Hash functions are partially ordered, from `older' to `newer'.
118 The ordering is configurable. The default, with the two hash
119 functions defined here, is the obvious ordering
120 SHA1 ([0-9a-f]*) < BLAKE2b (H*)
123 CHOICE OF SUBNAMESPACE
125 Whenever objects are created, it is necessary to choose the
126 subnamespace to use (ie, the hash function).
128 Each ref may also have a subnamespace hint associated with it.
133 A commit is made (by default) as new as the newest of
134 (i) each of its parents
135 (ii) if applicable, the subnamespace hint for the ref to which the
136 new commit is to be written
138 Implicitly this normally means that if HEAD refers to a new commit,
139 further new commits will be generated on top of it.
141 The subnamespace of an origin commit is controlled by the hint left in
142 .git by git checkout --orphan or git init.
144 At boundaries between old and new history, new commit(s) will refer to
150 A tag is created (by default) in the same subnamespace as the object
156 Trees are only referenced by objects in their own subnamespace.
158 To satisfy this rule, occasionally a tree object from one subnamespace
159 must be recursively rewritten into another subnamespace.
161 When a tree refers to a commit, it may refer to one in a different
164 Rationale: we want to avoid new commits and tags relying on weak
165 hashes. But we must avoid demanding that commits be rewritten.
170 Blobs are normally referred to by trees. Trees always refer to blobs
171 in the same subnamespace.
173 Where a blob is created in other circumstances, the caller should
174 specify the subnamespace.
179 As noted above, each ref may also have a subnamespace hint associated
182 The subnamespace hint is (by default) copied, when the ref value is
183 copied. So for exmple if `git checkout foo' makes refs/heads/foo out
184 of refs/remotes/origin/foo, it will copy the subnamespace hint (or
185 lack of one) from refs/remotes/origin/foo.
187 Likewise, the subnamespace hint is conveyed by `git fetch' (by
188 default) and can be updated with `git push' (though this is not done
191 The ref subnamespace hint may be set explicitly. That is how an
192 individual branch is upgraded. git checkout --orphan sets it to the
193 subnamespace (or hint) of the previous HEAD.
195 When a commit is made and stored in a ref, the subnamespace hint for
196 that ref is removed iff the commit's subnamespace and the hint's
197 subnamespace are the same.
200 OBJECT STORE BEHAVIOUR
202 The object store has configuration to specify which hash functions are
203 enabled. Each hash function H has a combination of the following
204 behaviours, according to configuration:
206 * Collision behaviour:
208 What to do if we encounter an object we already have (eg as part of
209 a pack, or with hash-object) but with different contents.
211 (a) fail: print a scary message and abort operation (on the
212 basis that the source of the colliding object probably intended
213 the preimage that they provided, or is conducting an attack).
215 (b) tolerate: prefer our own data; print a message, but treat
216 the reference as referring to our version of the object.
218 In both cases we keep a copy of the second preimage in our .git, for
221 This is used as part of a gradual desupport strategy. Existing
222 history in all existing object stores is safe and cannot be
223 corrupted or modified by receiving colliding objects.
225 New trees which receive their initial data from a trustworthy sender
226 over a trustworthy channel will receive correct data. Bad object
227 stores or untrustworthy channels could exploit collisions, but not
228 in new regions of the history which are presumably using new names.
229 So the collisons can only affect archaeology.
231 Merging previously-unrelated histories does introduce a collision
232 hazard, but the collision would have had to have been introduced
233 while the colliding hash function was still a live hash function
234 in at least one of the two projects.
237 * Hash function enablement:
239 (a) enabled: this hash function is good and available for use
241 (b) deprecated (in favour of H2): this hash function is
242 available for use, but newly created objects will use another
243 hash function instead (specifically, when creating an object,
244 this has function is not considered as a candidate; if as a
245 result there are no candidate hash functions, we use the
246 specified replacement H2). Existing refs referring to objects
247 with this hash, with no ref hint, are treated as having a ref
248 hint specifying H2. If no H2 is specified, the newest hash
251 (c) disabled: existing objects using this hash function can be
252 accessed, but no such objects can be created or received.
253 (again, a replacement may be specified). This is used both
254 initially to prevent unintended upgrade, and later to block the
255 introduction of vulnerable data generated by badly configured
258 (d) forgotten: such objects are not stored. References to such
259 objects return dummy objects of the right shape: the empty blob;
260 the empty tree; a root commit with an empty tree and dummy
261 metadata. This allows us to finally retire a hash function
262 entirely. We effectively throw away all the history which uses
265 During transfer protocols, the receiver will say which hashes it
266 thinks are forgotten, and the sender will not follow such references
267 when computing the set of objects to send. So receivers will not
268 receive the forgotten objects.
273 During the negotation, a receiver needs to specify what hashes it
274 understands, and whether it is prepared to see only a partial view.
276 When the sender is listing its refs, refs naming objects the receiver
277 cannot understand are either elided (if the receiver is content with a
278 parial view), or cause an error.
283 Note that semantically identical trees may (now) have different tree
284 objects because those tree objects might use (and be named by)
285 different hashes. So (in some contexts at least) tree comparison
286 cannot any longer be done by comparing names; rather an invocation of
287 git diff is needed, or explicit generation of a tree object with the
293 Y0: Implement all of the above. Test it.
295 Default configuration:
297 SHA-512 is disabled in trees without working trees
298 SHA-512 is enabled in trees with working trees
302 Existing projects will not switch to SHA-512 willy-nilly.
303 New projects will still use SHA-1.
305 Incompatible new-style commits cannot be pushed without server
306 admin effort (or until future upgrade).
308 So all old git clients still work.
310 Y4: SHA-512 by default for new projects.
311 Conversion enabled for existing projects.
312 Old git software is now pretty firmly deprecated.
314 Default configuration change:
316 When creating a new bare tree, a configuration dropping is left
317 (in `config') which specifies that SHA-1 is OBSOLESCENT
319 Default status for SHA-512 is FORBIDDEN if SHA-1 is ENABLED,
320 or ENABLED if SHA-1 is OBSOLESCENT.
322 default HEAD hash is newest ENABLED hash.
326 When creating a new working tree, it starts using SHA-512.
327 A new server tree will accept SHA-512.
329 Existing server trees do not yet accept SHA-512. They publish
330 their SHA-1 hashes, so clients make commits with SHA-1.
332 To convert a project, an administrator would set SHA-1 to
333 OBSOLESCENT on the server. All clones after that will have HEAD
334 with a SHA-512 name. Fetches and pulls will update to SHA-512
337 will , and push one SHA-512 commit to
342 Default configuration change:
346 When creating a new tree with working tree with git init (ie, no
347 HEAD), the default HEAD hash is set to SHA-512 (because SHA-1 is
348 OBSOLESCENT in a new tree and therefore SHA-512 is the only
349 ENABLED hash and is the default).
351 Newly minted server trees accept SHA-512.
354 start using SHA-512 by default.
356 Y6: Existing projects start being converted infectiously.
357 It is hard to stop this happening.
358 Old git software is firmly stuffed.
360 Default configuration change:
362 (default for SHA-512, and HEAD hash, computed as in Y4)
364 Result is that by default all software
366 (Projects which do not want to convert need to set SHA-1 to
367 ENABLED, explicitly, on their
369 Y6: Existing projects start using SHA-512.
371 Default configuration change:
374 (default default HEAD hash is already SHA-512)
376 In existing repositories where no special action
380 Ian Jackson <ijackson@chiark.greenend.org.uk> These opinions are my own.
382 If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
383 a private address which bypasses my fierce spamfilter.