docs/specifications/outline.rst

   1 ==============================
   2 Specification Document Outline
   3 ==============================
   4
   5 While we do not yet have a clear set of specification documents for Tahoe
   6 (explaining the file formats, so that others can write interoperable
   7 implementations), this document is intended to lay out an outline for what
   8 these specs ought to contain. Think of this as the ISO 7-Layer Model for
   9 Tahoe.
  10
  11 We currently imagine 4 documents.
  12
  13 1.  `#1: Share Format, Encoding Algorithm`_
  14 2.  `#2: Share Exchange Protocol`_
  15 3.  `#3: Server Selection Algorithm, filecap format`_
  16 4.  `#4: Directory Format`_
  17
  18 #1: Share Format, Encoding Algorithm
  19 ====================================
  20
  21 This document will describe the way that files are encrypted and encoded into
  22 shares. It will include a specification of the share format, and explain both
  23 the encoding and decoding algorithms. It will cover both mutable and
  24 immutable files.
  25
  26 The immutable encoding algorithm, as described by this document, will start
  27 with a plaintext series of bytes, encoding parameters "k" and "N", and either
  28 an encryption key or a mechanism for deterministically deriving the key from
  29 the plaintext (the CHK specification). The algorithm will end with a set of N
  30 shares, and a set of values that must be included in the filecap to provide
  31 confidentiality (the encryption key) and integrity (the UEB hash).
  32
  33 The immutable decoding algorithm will start with the filecap values (key and
  34 UEB hash) and "k" shares. It will explain how to validate the shares against
  35 the integrity information, how to reverse the erasure-coding, and how to
  36 decrypt the resulting ciphertext. It will result in the original plaintext
  37 bytes (or some subrange thereof).
  38
  39 The sections on mutable files will contain similar information.
  40
  41 This document is *not* responsible for explaining the filecap format, since
  42 full filecaps may need to contain additional information as described in
  43 document #3. Likewise it it not responsible for explaining where to put the
  44 generated shares or where to find them again later.
  45
  46 It is also not responsible for explaining the access control mechanisms
  47 surrounding share upload, download, or modification ("Accounting" is the
  48 business of controlling share upload to conserve space, and mutable file
  49 shares require some sort of access control to prevent non-writecap holders
  50 from destroying shares). We don't yet have a document dedicated to explaining
  51 these, but let's call it "Access Control" for now.
  52
  53
  54 #2: Share Exchange Protocol
  55 ===========================
  56
  57 This document explains the wire-protocol used to upload, download, and modify
  58 shares on the various storage servers.
  59
  60 Given the N shares created by the algorithm described in document #1, and a
  61 set of servers who are willing to accept those shares, the protocols in this
  62 document will be sufficient to get the shares onto the servers. Likewise,
  63 given a set of servers who hold at least k shares, these protocols will be
  64 enough to retrieve the shares necessary to begin the decoding process
  65 described in document #1. The notion of a "storage index" is used to
  66 reference a particular share: the storage index is generated by the encoding
  67 process described in document #1.
  68
  69 This document does *not* describe how to identify or choose those servers,
  70 rather it explains what to do once they have been selected (by the mechanisms
  71 in document #3).
  72
  73 This document also explains the protocols that a client uses to ask a server
  74 whether or not it is willing to accept an uploaded share, and whether it has
  75 a share available for download. These protocols will be used by the
  76 mechanisms in document #3 to help decide where the shares should be placed.
  77
  78 Where cryptographic mechanisms are necessary to implement access-control
  79 policy, this document will explain those mechanisms.
  80
  81 In the future, Tahoe will be able to use multiple protocols to speak to
  82 storage servers. There will be alternative forms of this document, one for
  83 each protocol. The first one to be written will describe the Foolscap-based
  84 protocol that tahoe currently uses, but we anticipate a subsequent one to
  85 describe a more HTTP-based protocol.
  86
  87 #3: Server Selection Algorithm, filecap format
  88 ==============================================
  89
  90 This document has two interrelated purposes. With a deeper understanding of
  91 the issues, we may be able to separate these more cleanly in the future.
  92
  93 The first purpose is to explain the server selection algorithm. Given a set
  94 of N shares, where should those shares be uploaded? Given some information
  95 stored about a previously-uploaded file, how should a downloader locate and
  96 recover at least k shares? Given a previously-uploaded mutable file, how
  97 should a modifier locate all (or most of) the shares with a reasonable amount
  98 of work?
  99
 100 This question implies many things, all of which should be explained in this
 101 document:
 102
 103 * the notion of a "grid", nominally a set of servers who could potentially
 104   hold shares, which might change over time
 105 * a way to configure which grid should be used
 106 * a way to discover which servers are a part of that grid
 107 * a way to decide which servers are reliable enough to be worth sending
 108   shares
 109 * an algorithm to handle servers which refuse shares
 110 * a way for a downloader to locate which servers have shares
 111 * a way to choose which shares should be used for download
 112
 113 The server-selection algorithm has several obviously competing goals:
 114
 115 * minimize the amount of work that must be done during upload
 116 * minimize the total storage resources used
 117 * avoid "hot spots", balance load among multiple servers
 118 * maximize the chance that enough shares will be downloadable later, by
 119   uploading lots of shares, and by placing them on reliable servers
 120 * minimize the work that the future downloader must do
 121 * tolerate temporary server failures, permanent server departure, and new
 122   server insertions
 123 * minimize the amount of information that must be added to the filecap
 124
 125 The server-selection algorithm is defined in some context: some set of
 126 expectations about the servers or grid with which it is expected to operate.
 127 Different algorithms are appropriate for different situtations, so there will
 128 be multiple alternatives of this document.
 129
 130 The first version of this document will describe the algorithm that the
 131 current (1.3.0) release uses, which is heavily weighted towards the two main
 132 use case scenarios for which Tahoe has been designed: the small, stable
 133 friendnet, and the allmydata.com managed grid. In both cases, we assume that
 134 the storage servers are online most of the time, they are uniformly highly
 135 reliable, and that the set of servers does not change very rapidly. The
 136 server-selection algorithm for this environment uses a permuted server list
 137 to achieve load-balancing, uses all servers identically, and derives the
 138 permutation key from the storage index to avoid adding a new field to the
 139 filecap.
 140
 141 An alternative algorithm could give clients more precise control over share
 142 placement, for example by a user who wished to make sure that k+1 shares are
 143 located in each datacenter (to allow downloads to take place using only local
 144 bandwidth). This algorithm could skip the permuted list and use other
 145 mechanisms to accomplish load-balancing (or ignore the issue altogether). It
 146 could add additional information to the filecap (like a list of which servers
 147 received the shares) in lieu of performing a search at download time, perhaps
 148 at the expense of allowing a repairer to move shares to a new server after
 149 the initial upload. It might make up for this by storing "location hints"
 150 next to each share, to indicate where other shares are likely to be found,
 151 and obligating the repairer to update these hints.
 152
 153 The second purpose of this document is to explain the format of the file
 154 capability string (or "filecap" for short). There are multiple kinds of
 155 capabilties (read-write, read-only, verify-only, repaircap, lease-renewal
 156 cap, traverse-only, etc). There are multiple ways to represent the filecap
 157 (compressed binary, human-readable, clickable-HTTP-URL, "tahoe:" URL, etc),
 158 but they must all contain enough information to reliably retrieve a file
 159 (given some context, of course). It must at least contain the confidentiality
 160 and integrity information from document #1 (i.e. the encryption key and the
 161 UEB hash). It must also contain whatever additional information the
 162 upload-time server-selection algorithm generated that will be required by the
 163 downloader.
 164
 165 For some server-selection algorithms, the additional information will be
 166 minimal. For example, the 1.3.0 release uses the hash of the encryption key
 167 as a storage index, and uses the storage index to permute the server list,
 168 and uses an Introducer to learn the current list of servers. This allows a
 169 "close-enough" list of servers to be compressed into a filecap field that is
 170 already required anyways (the encryption key). It also adds k and N to the
 171 filecap, to speed up the downloader's search (the downloader knows how many
 172 shares it needs, so it can send out multiple queries in parallel).
 173
 174 But other server-selection algorithms might require more information. Each
 175 variant of this document will explain how to encode that additional
 176 information into the filecap, and how to extract and use that information at
 177 download time.
 178
 179 These two purposes are interrelated. A filecap that is interpreted in the
 180 context of the allmydata.com commercial grid, which uses tahoe-1.3.0, implies
 181 a specific peer-selection algorithm, a specific Introducer, and therefore a
 182 fairly-specific set of servers to query for shares. A filecap which is meant
 183 to be interpreted on a different sort of grid would need different
 184 information.
 185
 186 Some filecap formats can be designed to contain more information (and depend
 187 less upon context), such as the way an HTTP URL implies the existence of a
 188 single global DNS system. Ideally a tahoe filecap should be able to specify
 189 which "grid" it lives in, with enough information to allow a compatible
 190 implementation of Tahoe to locate that grid and retrieve the file (regardless
 191 of which server-selection algorithm was used for upload).
 192
 193 This more-universal format might come at the expense of reliability, however.
 194 Tahoe-1.3.0 filecaps do not contain hostnames, because the failure of DNS or
 195 an individual host might then impact file availability (however the
 196 Introducer contains DNS names or IP addresses).
 197
 198 #4: Directory Format
 199 ====================
 200
 201 Tahoe directories are a special way of interpreting and managing the contents
 202 of a file (either mutable or immutable). These "dirnode" files are basically
 203 serialized tables that map child name to filecap/dircap. This document
 204 describes the format of these files.
 205
 206 Tahoe-1.3.0 directories are "transitively readonly", which is accomplished by
 207 applying an additional layer of encryption to the list of child writecaps.
 208 The key for this encryption is derived from the containing file's writecap.
 209 This document must explain how to derive this key and apply it to the
 210 appropriate portion of the table.
 211
 212 Future versions of the directory format are expected to contain
 213 "deep-traversal caps", which allow verification/repair of files without
 214 exposing their plaintext to the repair agent. This document wil be
 215 responsible for explaining traversal caps too.
 216
 217 Future versions of the directory format will probably contain an index and
 218 more advanced data structures (for efficiency and fast lookups), instead of a
 219 simple flat list of (childname, childcap). This document will also need to
 220 describe metadata formats, including what access-control policies are defined
 221 for the metadata.