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 this particular object
  38 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 * OBSOLESCENT: Every object in the object store has its hash
  76   calculated using H.  However, H is known to possibly have collisions
  77   which we try to tolerate.  When a collision occurs, the object text
  78   which is currently in the object store is preferred and the "new"
  79   object is thrown away.  Local creation of new objects with
  80   references using H is forbidden.
  81
  82   This is used as part of a gradual desupport strategy.  When the hash
  83   function is in this stage, existing history in all existing object
  84   stores is safe and cannot be corrupted or modified by receiving
  85   colliding objects.
  86
  87   New object stores which receive their data from a trustworthy sender
  88   over a trustworthy channel will receive correct data.  Bad object
  89   stores or untrustworthy channels could exploit collisions, but not
  90   in new regions of the history which are presumably using new names.
  91   So the collisons can only affect archaeology.
  92
  93   Merging previously-unrelated histories does introduce a collision
  94   hazard, but the collision would have had to have been introduced
  95   while H was still a "live" hash function in at least one of the two
  96   projects.
  97
  98 * FORBIDDEN: Objects do not have their hashes calculated using this
  99   hash function.  Attempts to reference an object by such a name
 100   fail.  Optionally the user may specify a tolerant mode where:
 101   a commit which refers to parents by obsolete names is taken to
 102   simply not have those parents; a commit which refers to a tree by
 103   an obsolete name is taken to have an empty tree.
 104
 105   This is used for two purposes:
 106
 107     - On a server, we use this to restrict the propagation of
 108       new hashes so as to enforce our compatibility intentions.
 109       Ie, hashes which we are "not ready for" are forbidden.
 110
 111     - Everywhere, we use this to get rid of old hash functions.
 112       It makes access to old history possible but difficult.
 113
 114 * FORGOTTEN: Objects do not have their hashes calculated using this
 115   hash function.  References to objects by all such names return dummy
 116   objects of the right shape: the empty blob; the empty tree; a root
 117   commit with an empty tree and dummy metadata.
 118
 119   This allows us to finally retire a hash function entirely.  We
 120   effectively throw away all the history which uses H.
 121
 122 During transfer protocols, the receiver will say which hashes are
 123 obsolete or forgotten, and the sender will not follow such references
 124 when computing the set of objects to send.  So receivers will not
 125 receive the objects which were named only by obsolete or forgotten
 126 names.
 127
 128
 129 Naming in newly-generated objects, queries, etc.
 130
 131 There is a `default' hash function, which is that which HEAD uses.
 132 (That is, HEAD refers to an object by some name.  The default hash
 133 function is that name's hash function.)
 134
 135 git tools produce always output object names in the default hash
 136 function.  (Including git-hash-object.)
 137
 138 As a consequence, newly generated objects will contain object
 139 references using the `default' hash function.
 140
 141 When HEAD is empty, there is a separate record of the default hash
 142 function.  This comes from a configured default in a new tree.  In an
 143 existing tree, using git checkout --orphan remembers the default hash
 144 function that HEAD had.
 145
 146 When HEAD is updated to a new commit, the name stored in HEAD uses the
 147 newer of the previous HEAD hash function and of the hash function used
 148 in the commit being stored.  ("Newer" is a built-in preference order,
 149 overrideable by configuration.)
 150
 151 This (together with the `forbidden' state, above) ensures that
 152 switching a project to use a new hash function is a deliberate
 153 decision: the default hash function needs to be changed to make the
 154 first first commit with the new hash function.  After that, provided
 155 the server accepts it, it's infectious.
 156
 157
 158 Naming of refs other than HEAD
 159
 160 A ref refers to an object by one of its names.  However, operations
 161 like git-show-ref convert that name to the default format (see above).
 162
 163 git-gc rewrites ref names to the default format.
 164
 165
 166 Remote protocol
 167
 168 During the negotation, a client needs to specify what names it
 169 understands, and which it prefers (its default).
 170
 171 When the server is listing its refs, the names are converted to the
 172 client's preferred format.
 173
 174
 175 Equality testing
 176
 177 All software which tests for equality of git objects by checking
 178 whether their object names are equal needs to obtain a canonical name
 179 for both objects.
 180
 181 This is going to be quite annoying.
 182
 183 Note that semantically identical trees may (now) have different tree
 184 objects because those tree objects might contain different object
 185 names.  So tree comparison cannot any longer be done by comparing
 186 names; rather an invocation of git diff is needed.
 187
 188
 189 Transition plan
 190
 191 Y0: Implement all of the above.  Test it.
 192
 193     Default configuration:
 194        SHA-1 is ENABLED and is default HEAD hash
 195
 196        SHA-512 is FORBIDDEN in bare repos
 197        SHA-512 is ENABLED in trees with working trees
 198
 199 Y5: New projects should start using SHA-512.
 200
 201     Default configuration change:
 202
 203        SHA-512 becomes ENABLED in *new* bare repos but remains
 204                   FORBIDDEN in existing ones
 205
 206
 207
 208 --
 209 Ian Jackson <ijackson@chiark.greenend.org.uk>   These opinions are my own.
 210
 211 If I emailed you from an address @fyvzl.net or @evade.org.uk, that is
 212 a private address which bypasses my fierce spamfilter.