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 always referenced by objects in their own subnamespace.
158 Occasionally, a tree object from one subnamespace must be recursively
159 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
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.
182 The object store knows which hash functions are enabled. Each hash
183 function H has one of the following statuses, which are configured by
188 As far as the user is concerned every object in the object store is
189 accessible using H. Objects which use H names can be received and
192 This is actually two states, depending on whether any objects exist
193 in the store which use these names. If no such objects exist yet,
194 we say that the hash function is `ENABLED PROSPECTIVE'. The H names
195 for the objects have not yet been calculated.
197 When the first object which names another object using H is received
198 (or, on demand), the object store calculates the H names for all
199 existing objects and notes that this hash function is now
202 If a hash collision is detected, we crash immediately.
204 * OBSOLESCENT: Every object in the object store has its hash
205 calculated using H. However, H is known to possibly have collisions
206 which we try to tolerate. When a collision occurs, the object text
207 which is currently in the object store is preferred and the "new"
208 object is thrown away.
210 Local creation of new objects with references using H is
211 discouraged. Specifically, if another hash function is ENABLED, we
212 will use that instead.
214 This is used as part of a gradual desupport strategy. When the hash
215 function is in this stage, existing history in all existing object
216 stores is safe and cannot be corrupted or modified by receiving
219 New object stores which receive their data from a trustworthy sender
220 over a trustworthy channel will receive correct data. Bad object
221 stores or untrustworthy channels could exploit collisions, but not
222 in new regions of the history which are presumably using new names.
223 So the collisons can only affect archaeology.
225 Merging previously-unrelated histories does introduce a collision
226 hazard, but the collision would have had to have been introduced
227 while H was still a "live" hash function in at least one of the two
230 * FORBIDDEN: Objects do not have their hashes calculated using this
231 hash function. Attempts to reference an object by such a name
232 fail. Optionally the user may specify a tolerant mode where:
233 a commit which refers to parents by obsolete names is taken to
234 simply not have those parents; a commit which refers to a tree by
235 an obsolete name is taken to have an empty tree.
237 This is used for two purposes:
239 - On a server, we use this to restrict the propagation of
240 new hashes so as to enforce our compatibility intentions.
241 Ie, hashes which we are "not ready for" are forbidden.
243 - Everywhere, we use this to get rid of old hash functions.
244 It makes access to old history possible but difficult.
246 * FORGOTTEN: Objects do not have their hashes calculated using this
247 hash function. References to objects by all such names return dummy
248 objects of the right shape: the empty blob; the empty tree; a root
249 commit with an empty tree and dummy metadata.
251 This allows us to finally retire a hash function entirely. We
252 effectively throw away all the history which uses H.
254 During transfer protocols, the receiver will say which hashes it
255 thinks are obsolete or forgotten, and the sender will not follow such
256 references when computing the set of objects to send. So receivers
257 will not receive the objects which were named only by obsolete or
261 Naming in newly-generated objects, queries, etc.
263 There is a `default' hash function, which is that which HEAD uses.
264 (That is, HEAD refers to an object by some name. The default hash
265 function is that name's hash function.)
267 git tools produce always output object names in the default hash
268 function. (Including git-hash-object.)
270 As a consequence, newly generated objects will contain object
271 references using the `default' hash function.
273 When HEAD is empty, there is a separate record of the default hash
274 function. This comes from a configured default in a new tree. In an
275 existing tree, using git checkout --orphan remembers the default hash
276 function that HEAD had.
278 When HEAD is updated to a new commit, the name stored in HEAD uses the
279 newer of the previous HEAD hash function and of the hash function used
280 in the commit being stored. ("Newer" is a built-in preference order,
281 overrideable by configuration.)
283 This (together with the `forbidden' state, above) ensures that
284 switching a project to use a new hash function is a deliberate
285 decision: the default hash function needs to be changed to make the
286 first commit with the new hash function. After that, provided
287 the server accepts it, it's infectious.
290 Naming of refs other than HEAD
292 A ref refers to an object by one of its names. However, operations
293 like git-show-ref convert that name to the default format (see above).
295 git-gc rewrites ref names to the default format iff that is newer.
300 During the negotation, a receiver needs to specify what hashes it
303 When the sender is listing its refs, the names are converted to a
304 hash understood by the client if necessary. If this is not necessary,
305 they are left unchanged.
307 When a receiver is updating refs, it should by follow the sender's
308 idea of a hash change iff it's an upgrade (and the new function is
309 ENABLED). That is, if the sender sends name H2 for some ref, and the
310 receiver has H1, but these refer to the same object, then the receiver
311 should update its own ref name from H1 to H2 iff H2 uses a newer hash
317 All software which tests for equality of git objects by checking
318 whether their object names are equal needs to obtain a canonical name
321 This is going to be quite annoying.
323 We should provide a convenient utility which tests whether two object
324 names refer to the same object.
326 Note that semantically identical trees may (now) have different tree
327 objects because those tree objects might contain different object
328 names. So (in some contexts at least) tree comparison cannot any
329 longer be done by comparing names; rather an invocation of git diff is
330 needed, or explicit generation of a tree object with the right name.
335 Y0: Implement all of the above. Test it.
337 Default configuration:
339 SHA-512 is FORBIDDEN in bare repos
340 SHA-512 is ENABLED in trees with working trees
341 default HEAD hash is SHA-1
345 Existing projects will not switch to SHA-512 willy-nilly.
346 New projects will still use SHA-1.
348 Incompatible new-style commits cannot be pushed without server
349 admin effort (or until future upgrade).
351 So all old git clients still work.
353 Y4: SHA-512 by default for new projects.
354 Conversion enabled for existing projects.
355 Old git software is now pretty firmly deprecated.
357 Default configuration change:
359 When creating a new bare tree, a configuration dropping is left
360 (in `config') which specifies that SHA-1 is OBSOLESCENT
362 Default status for SHA-512 is FORBIDDEN if SHA-1 is ENABLED,
363 or ENABLED if SHA-1 is OBSOLESCENT.
365 default HEAD hash is newest ENABLED hash.
369 When creating a new working tree, it starts using SHA-512.
370 A new server tree will accept SHA-512.
372 Existing server trees do not yet accept SHA-512. They publish
373 their SHA-1 hashes, so clients make commits with SHA-1.
375 To convert a project, an administrator would set SHA-1 to
376 OBSOLESCENT on the server. All clones after that will have HEAD
377 with a SHA-512 name. Fetches and pulls will update to SHA-512
380 will , and push one SHA-512 commit to
385 Default configuration change:
389 When creating a new tree with working tree with git init (ie, no
390 HEAD), the default HEAD hash is set to SHA-512 (because SHA-1 is
391 OBSOLESCENT in a new tree and therefore SHA-512 is the only
392 ENABLED hash and is the default).
394 Newly minted server trees accept SHA-512.
397 start using SHA-512 by default.
399 Y6: Existing projects start being converted infectiously.
400 It is hard to stop this happening.
401 Old git software is firmly stuffed.
403 Default configuration change:
405 (default for SHA-512, and HEAD hash, computed as in Y4)
407 Result is that by default all software
409 (Projects which do not want to convert need to set SHA-1 to
410 ENABLED, explicitly, on their
412 Y6: Existing projects start using SHA-512.
414 Default configuration change:
417 (default default HEAD hash is already SHA-512)
419 In existing repositories where no special action
423 Ian Jackson <ijackson@chiark.greenend.org.uk> These opinions are my own.
425 If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
426 a private address which bypasses my fierce spamfilter.