plan.txt

   1 From: Ian Jackson <ijackson@chiark.greenend.org.uk>
   2 To: ijackson@chiark.greenend.org.uk
   3 Subject: Transition plan for git to move to a new hash function
   4 Date: Thu, 20 Oct 2016 19:26:44 +0100
   5
   6
   7 Basic principle: Every object will have two (or more) names,
   8 corresponding to different hash functions.  It may be named by any of
   9 its names, in every context.
  10
  11 Every program that invokes git or speaks git protocols will need to
  12 understand the extended object name syntax, and understand that
  13 objects have multiple names.
  14
  15 Safety catches preferent accidental incorporation into a project of
  16 objects which contain references by incompatibly-new or
  17 deprecatedly-old names.  This allows for incremental deployment.
  18
  19
  20 Syntax:
  21
  22 The object name syntax is extended as follows: object names using sha1
  23 are as current.  Object names starting with lowercase ASCII letters h
  24 or later refer to new hash functions.  (`g' is reserved because of the
  25 way that many programs write `g<objectname>'.  Programs that use
  26 `g<objectname>' should be changed to show `h<hash>' for hash function
  27 `h' rather than `gh<hash>'.)
  28
  29 Object names h<hex> are SHA-512 hashes.  Remaining letters are
  30 reserved.  `x' `y' `z' are reserved for private experiments; we
  31 declare that public releases of git will never accept such names.
  32
  33 Everywhere in the git object formats and git protocols, a new object
  34 name (with hash function indicator) is permitted where an old object
  35 name is permitted.  A single object refers to all the objects it
  36 references by the same hash function; in general this might be a
  37 different hash function to the hash function by which this particular
  38 object was itself referenced or obtained.
  39
  40 As an exception, it is forbidden to refer to a tree object by a name
  41 other than the hash function it uses to name its subtrees.  If this
  42 seems necessary, the tree object must be recursively rewritten instead
  43 to use the desired object name.
  44
  45 In binary protocols, where a SHA-1 object name in binary form was
  46 previously used, a new codepoint must be allocated in a containing
  47 structure (eg a new typecode).  Usually, the new-format binary object
  48 will have a new typecode and also an additional name hash indicator.
  49 15 of the hash indicator values correspond to the lowercase letters
  50 reserved above.
  51
  52
  53 Object store:
  54
  55 The object store knows which hash functions are enabled.  Each hash
  56 function H has one of the following statuses, which are configured by
  57 the user:
  58
  59 * ENABLED:
  60
  61   As far as the user is concerned every object in the object store is
  62   accessible using H.  Objects which use H names can be received and
  63   stored.
  64
  65   This is actually two states, depending on whether any objects exist
  66   in the store which use these names.  If no such objects exist yet,
  67   we say that the hash function is `ENABLED PROSPECTIVE'.  The H names
  68   for the objects have not yet been calculated.
  69
  70   When the first object which names another object using H is received
  71   (or, on demand), the object store calculates the H names for all
  72   existing objects and notes that this hash function is now
  73   `ENABLED PRESENT'.
  74
  75   If a hash collision is detected, we crash immediately.
  76
  77 * OBSOLESCENT: Every object in the object store has its hash
  78   calculated using H.  However, H is known to possibly have collisions
  79   which we try to tolerate.  When a collision occurs, the object text
  80   which is currently in the object store is preferred and the "new"
  81   object is thrown away.
  82
  83   Local creation of new objects with references using H is
  84   discouraged.  Specifically, if another hash function is ENABLED, we
  85   will use that instead.
  86
  87   This is used as part of a gradual desupport strategy.  When the hash
  88   function is in this stage, existing history in all existing object
  89   stores is safe and cannot be corrupted or modified by receiving
  90   colliding objects.
  91
  92   New object stores which receive their data from a trustworthy sender
  93   over a trustworthy channel will receive correct data.  Bad object
  94   stores or untrustworthy channels could exploit collisions, but not
  95   in new regions of the history which are presumably using new names.
  96   So the collisons can only affect archaeology.
  97
  98   Merging previously-unrelated histories does introduce a collision
  99   hazard, but the collision would have had to have been introduced
 100   while H was still a "live" hash function in at least one of the two
 101   projects.
 102
 103 * FORBIDDEN: Objects do not have their hashes calculated using this
 104   hash function.  Attempts to reference an object by such a name
 105   fail.  Optionally the user may specify a tolerant mode where:
 106   a commit which refers to parents by obsolete names is taken to
 107   simply not have those parents; a commit which refers to a tree by
 108   an obsolete name is taken to have an empty tree.
 109
 110   This is used for two purposes:
 111
 112     - On a server, we use this to restrict the propagation of
 113       new hashes so as to enforce our compatibility intentions.
 114       Ie, hashes which we are "not ready for" are forbidden.
 115
 116     - Everywhere, we use this to get rid of old hash functions.
 117       It makes access to old history possible but difficult.
 118
 119 * FORGOTTEN: Objects do not have their hashes calculated using this
 120   hash function.  References to objects by all such names return dummy
 121   objects of the right shape: the empty blob; the empty tree; a root
 122   commit with an empty tree and dummy metadata.
 123
 124   This allows us to finally retire a hash function entirely.  We
 125   effectively throw away all the history which uses H.
 126
 127 During transfer protocols, the receiver will say which hashes it
 128 thinks are obsolete or forgotten, and the sender will not follow such
 129 references when computing the set of objects to send.  So receivers
 130 will not receive the objects which were named only by obsolete or
 131 forgotten names.
 132
 133
 134 Naming in newly-generated objects, queries, etc.
 135
 136 There is a `default' hash function, which is that which HEAD uses.
 137 (That is, HEAD refers to an object by some name.  The default hash
 138 function is that name's hash function.)
 139
 140 git tools produce always output object names in the default hash
 141 function.  (Including git-hash-object.)
 142
 143 As a consequence, newly generated objects will contain object
 144 references using the `default' hash function.
 145
 146 When HEAD is empty, there is a separate record of the default hash
 147 function.  This comes from a configured default in a new tree.  In an
 148 existing tree, using git checkout --orphan remembers the default hash
 149 function that HEAD had.
 150
 151 When HEAD is updated to a new commit, the name stored in HEAD uses the
 152 newer of the previous HEAD hash function and of the hash function used
 153 in the commit being stored.  ("Newer" is a built-in preference order,
 154 overrideable by configuration.)
 155
 156 This (together with the `forbidden' state, above) ensures that
 157 switching a project to use a new hash function is a deliberate
 158 decision: the default hash function needs to be changed to make the
 159 first commit with the new hash function.  After that, provided
 160 the server accepts it, it's infectious.
 161
 162
 163 Naming of refs other than HEAD
 164
 165 A ref refers to an object by one of its names.  However, operations
 166 like git-show-ref convert that name to the default format (see above).
 167
 168 git-gc rewrites ref names to the default format iff that is newer.
 169
 170
 171 Remote protocol
 172
 173 During the negotation, a receiver needs to specify what hashes it
 174 understands.
 175
 176 When the sender is listing its refs, the names are converted to a
 177 hash understood by the client if necessary.  If this is not necessary,
 178 they are left unchanged.
 179
 180 When a receiver is updating refs, it should by follow the sender's
 181 idea of a hash change iff it's an upgrade (and the new function is
 182 ENABLED).  That is, if the sender sends name H2 for some ref, and the
 183 receiver has H1, but these refer to the same object, then the receiver
 184 should update its own ref name from H1 to H2 iff H2 uses a newer hash
 185 function.
 186
 187
 188 Equality testing
 189
 190 All software which tests for equality of git objects by checking
 191 whether their object names are equal needs to obtain a canonical name
 192 for both objects.
 193
 194 This is going to be quite annoying.
 195
 196 We should provide a convenient utility which tests whether two object
 197 names refer to the same object.
 198
 199 Note that semantically identical trees may (now) have different tree
 200 objects because those tree objects might contain different object
 201 names.  So (in some contexts at least) tree comparison cannot any
 202 longer be done by comparing names; rather an invocation of git diff is
 203 needed, or explicit generation of a tree object with the right name.
 204
 205
 206 Transition plan
 207
 208 Y0: Implement all of the above.  Test it.
 209
 210     Default configuration:
 211        SHA-1 is ENABLED
 212        SHA-512 is FORBIDDEN in bare repos
 213        SHA-512 is ENABLED in trees with working trees
 214        default HEAD hash is SHA-1
 215
 216     Effects:
 217
 218     Existing projects will not switch to SHA-512 willy-nilly.
 219     New projects will still use SHA-1.
 220
 221     Incompatible new-style commits cannot be pushed without server
 222     admin effort (or until future upgrade).
 223
 224     So all old git clients still work.
 225
 226 Y4: SHA-512 by default for new projects.
 227     Conversion enabled for existing projects.
 228     Old git software is now pretty firmly deprecated.
 229
 230     Default configuration change:
 231
 232        When creating a new bare tree, a configuration dropping is left
 233        (in `config') which specifies that SHA-1 is OBSOLESCENT
 234
 235        Default status for SHA-512 is FORBIDDEN if SHA-1 is ENABLED,
 236        or ENABLED if SHA-1 is OBSOLESCENT.
 237
 238        default HEAD hash is newest ENABLED hash.
 239
 240     Effects:
 241
 242     When creating a new working tree, it starts using SHA-512.
 243     A new server tree will accept SHA-512.
 244
 245     Existing server trees do not yet accept SHA-512.  They publish
 246     their SHA-1 hashes, so clients make commits with SHA-1.
 247
 248     To convert a project, an administrator would set SHA-1 to
 249     OBSOLESCENT on the server.  All clones after that will have HEAD
 250     with a SHA-512 name.  Fetches and pulls will update to SHA-512
 251     names.
 252
 253 will , and push one SHA-512 commit to
 254     mainline.
 255
 256
 257
 258     Default configuration change:
 259
 260     Effects:
 261
 262     When creating a new tree with working tree with git init (ie, no
 263     HEAD), the default HEAD hash is set to SHA-512 (because SHA-1 is
 264     OBSOLESCENT in a new tree and therefore SHA-512 is the only
 265     ENABLED hash and is the default).
 266
 267     Newly minted server trees accept SHA-512.
 268
 269
 270  start using SHA-512 by default.
 271
 272 Y6: Existing projects start being converted infectiously.
 273     It is hard to stop this happening.
 274     Old git software is firmly stuffed.
 275
 276     Default configuration change:
 277        SHA-1 is OBSOLESCENT
 278        (default for SHA-512, and HEAD hash, computed as in Y4)
 279
 280     Result is that by default all software
 281
 282     (Projects which do not want to convert need to set SHA-1 to
 283     ENABLED, explicitly, on their
 284
 285 Y6: Existing projects start using SHA-512.
 286
 287     Default configuration change:
 288        SHA-512 is ENABLED
 289        SHA-1 is OBSOLESCENT
 290        (default default HEAD hash is already SHA-512)
 291
 292       In existing repositories where no special action
 293
 294
 295 --
 296 Ian Jackson <ijackson@chiark.greenend.org.uk>   These opinions are my own.
 297
 298 If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
 299 a private address which bypasses my fierce spamfilter.