src/allmydata/hashtree.py

   1 # -*- test-case-name: allmydata.test.test_hashtree -*-
   2
   3 from allmydata.util import mathutil # from the pyutil library
   4
   5 """
   6 Read and write chunks from files.
   7
   8 Version 1.0.0.
   9
  10 A file is divided into blocks, each of which has size L{BLOCK_SIZE}
  11 (except for the last block, which may be smaller).  Blocks are encoded
  12 into chunks.  One publishes the hash of the entire file.  Clients
  13 who want to download the file first obtain the hash, then the clients
  14 can receive chunks in any order.  Cryptographic hashing is used to
  15 verify each received chunk before writing to disk.  Thus it is
  16 impossible to download corrupt data if one has the correct file hash.
  17
  18 One obtains the hash of a complete file via
  19 L{CompleteChunkFile.file_hash}.  One can read chunks from a complete
  20 file by the sequence operations of C{len()} and subscripting on a
  21 L{CompleteChunkFile} object.  One can open an empty or partially
  22 downloaded file with L{PartialChunkFile}, and read and write chunks
  23 to this file.  A chunk will fail to write if its contents and index
  24 are not consistent with the overall file hash passed to
  25 L{PartialChunkFile} when the partial chunk file was first created.
  26
  27 The chunks have an overhead of less than 4% for files of size
  28 less than C{10**20} bytes.
  29
  30 Benchmarks:
  31
  32  - On a 3 GHz Pentium 3, it took 3.4 minutes to first make a
  33    L{CompleteChunkFile} object for a 4 GB file.  Up to 10 MB of
  34    memory was used as the constructor ran.  A metafile filename
  35    was passed to the constructor, and so the hash information was
  36    written to the metafile.  The object used a negligible amount
  37    of memory after the constructor was finished.
  38  - Creation of L{CompleteChunkFile} objects in future runs of the
  39    program took negligible time, since the hash information was
  40    already stored in the metafile.
  41
  42 @var BLOCK_SIZE:     Size of a block.  See L{BlockFile}.
  43 @var MAX_CHUNK_SIZE: Upper bound on the size of a chunk.
  44                      See L{CompleteChunkFile}.
  45
  46 free (adj.): unencumbered; not under the control of others
  47 Written by Connelly Barnes in 2005 and released into the
  48 public domain  with no warranty of any kind, either expressed
  49 or implied.  It probably won't make your computer catch on fire,
  50 or eat  your children, but it might.  Use at your own risk.
  51 """
  52
  53 from allmydata.util import base32
  54 from allmydata.util.hashutil import tagged_hash, tagged_pair_hash
  55
  56 __version__ = '1.0.0-allmydata'
  57
  58 BLOCK_SIZE     = 65536
  59 MAX_CHUNK_SIZE = BLOCK_SIZE + 4096
  60
  61 def roundup_pow2(x):
  62     """
  63     Round integer C{x} up to the nearest power of 2.
  64     """
  65     ans = 1
  66     while ans < x:
  67         ans *= 2
  68     return ans
  69
  70
  71 class CompleteBinaryTreeMixin:
  72     """
  73     Adds convenience methods to a complete binary tree.
  74
  75     Assumes the total number of elements in the binary tree may be
  76     accessed via C{__len__}, and that each element can be retrieved
  77     using list subscripting.
  78
  79     Tree is indexed like so::
  80
  81
  82                         0
  83                    /        \
  84                 1               2
  85              /    \          /    \
  86            3       4       5       6
  87           / \     / \     / \     / \
  88          7   8   9   10  11  12  13  14
  89
  90     """
  91
  92     def parent(self, i):
  93         """
  94         Index of the parent of C{i}.
  95         """
  96         if i < 1 or (hasattr(self, '__len__') and i >= len(self)):
  97             raise IndexError('index out of range: ' + repr(i))
  98         return (i - 1) // 2
  99
 100     def lchild(self, i):
 101         """
 102         Index of the left child of C{i}.
 103         """
 104         ans = 2 * i + 1
 105         if i < 0 or (hasattr(self, '__len__') and ans >= len(self)):
 106             raise IndexError('index out of range: ' + repr(i))
 107         return ans
 108
 109     def rchild(self, i):
 110         """
 111         Index of right child of C{i}.
 112         """
 113         ans = 2 * i + 2
 114         if i < 0 or (hasattr(self, '__len__') and ans >= len(self)):
 115             raise IndexError('index out of range: ' + repr(i))
 116         return ans
 117
 118     def sibling(self, i):
 119         """
 120         Index of sibling of C{i}.
 121         """
 122         parent = self.parent(i)
 123         if self.lchild(parent) == i:
 124             return self.rchild(parent)
 125         else:
 126             return self.lchild(parent)
 127
 128     def needed_for(self, i):
 129         """
 130         Return a list of node indices that are necessary for the hash chain.
 131         """
 132         if i < 0 or i >= len(self):
 133             raise IndexError('index out of range: 0 >= %s < %s' % (i, len(self)))
 134         needed = []
 135         here = i
 136         while here != 0:
 137             needed.append(self.sibling(here))
 138             here = self.parent(here)
 139         return needed
 140
 141     def depth_first(self, i=0):
 142         yield i, 0
 143         try:
 144             for child,childdepth in self.depth_first(self.lchild(i)):
 145                 yield child, childdepth+1
 146         except IndexError:
 147             pass
 148         try:
 149             for child,childdepth in self.depth_first(self.rchild(i)):
 150                 yield child, childdepth+1
 151         except IndexError:
 152             pass
 153
 154     def dump(self):
 155         lines = []
 156         for i,depth in self.depth_first():
 157             lines.append("%s%3d: %s" % ("  "*depth, i,
 158                                         base32.b2a_or_none(self[i])))
 159         return "\n".join(lines) + "\n"
 160
 161     def get_leaf_index(self, leafnum):
 162         return self.first_leaf_num + leafnum
 163
 164     def get_leaf(self, leafnum):
 165         return self[self.first_leaf_num + leafnum]
 166
 167 def depth_of(i):
 168     """Return the depth or level of the given node. Level 0 contains node 0
 169     Level 1 contains nodes 1 and 2. Level 2 contains nodes 3,4,5,6."""
 170     return mathutil.log_floor(i+1, 2)
 171
 172 def empty_leaf_hash(i):
 173     return tagged_hash('Merkle tree empty leaf', "%d" % i)
 174 def pair_hash(a, b):
 175     return tagged_pair_hash('Merkle tree internal node', a, b)
 176
 177 class HashTree(CompleteBinaryTreeMixin, list):
 178     """
 179     Compute Merkle hashes at any node in a complete binary tree.
 180
 181     Tree is indexed like so::
 182
 183
 184                         0
 185                    /        \
 186                 1               2
 187              /    \          /    \
 188            3       4       5       6
 189           / \     / \     / \     / \
 190          7   8   9   10  11  12  13  14  <- List passed to constructor.
 191
 192     """
 193
 194     def __init__(self, L):
 195         """
 196         Create complete binary tree from list of hash strings.
 197
 198         The list is augmented by hashes so its length is a power of 2, and
 199         then this is used as the bottom row of the hash tree.
 200
 201         The augmenting is done so that if the augmented element is at index
 202         C{i}, then its value is C{hash(tagged_hash('Merkle tree empty leaf',
 203         '%d'%i))}.
 204         """
 205
 206         # Augment the list.
 207         start = len(L)
 208         end   = roundup_pow2(len(L))
 209         self.first_leaf_num = end - 1
 210         L     = L + [None] * (end - start)
 211         for i in range(start, end):
 212             L[i] = empty_leaf_hash(i)
 213         # Form each row of the tree.
 214         rows = [L]
 215         while len(rows[-1]) != 1:
 216             last = rows[-1]
 217             rows += [[pair_hash(last[2*i], last[2*i+1])
 218                                 for i in xrange(len(last)//2)]]
 219         # Flatten the list of rows into a single list.
 220         rows.reverse()
 221         self[:] = sum(rows, [])
 222
 223     def needed_hashes(self, leafnum, include_leaf=False):
 224         """Which hashes will someone need to validate a given data block?
 225
 226         I am used to answer a question: supposing you have the data block
 227         that is used to form leaf hash N, and you want to validate that it,
 228         which hashes would you need?
 229
 230         I accept a leaf number and return a set of 'hash index' values, which
 231         are integers from 0 to len(self). In the 'hash index' number space,
 232         hash[0] is the root hash, while hash[len(self)-1] is the last leaf
 233         hash.
 234
 235         This method can be used to find out which hashes you should request
 236         from some untrusted source (usually the same source that provides the
 237         data block), so you can minimize storage or transmission overhead. It
 238         can also be used to determine which hashes you should send to a
 239         remote data store so that it will be able to provide validatable data
 240         in the future.
 241
 242         I will not include '0' (the root hash) in the result, since the root
 243         is generally stored somewhere that is more trusted than the source of
 244         the remaining hashes. I will include the leaf hash itself only if you
 245         ask me to, by passing include_leaf=True.
 246         """
 247
 248         needed = set(self.needed_for(self.first_leaf_num + leafnum))
 249         if include_leaf:
 250             needed.add(self.first_leaf_num + leafnum)
 251         return needed
 252
 253
 254 class NotEnoughHashesError(Exception):
 255     pass
 256
 257 class BadHashError(Exception):
 258     pass
 259
 260 class IncompleteHashTree(CompleteBinaryTreeMixin, list):
 261     """I am a hash tree which may or may not be complete. I can be used to
 262     validate inbound data from some untrustworthy provider who has a subset
 263     of leaves and a sufficient subset of internal nodes.
 264
 265     Initially I am completely unpopulated. Over time, I will become filled
 266     with hashes, just enough to validate particular leaf nodes.
 267
 268     If you desire to validate leaf number N, first find out which hashes I
 269     need by calling needed_hashes(N). This will return a list of node numbers
 270     (which will nominally be the sibling chain between the given leaf and the
 271     root, but if I already have some of those nodes, needed_hashes(N) will
 272     only return a subset). Obtain these hashes from the data provider, then
 273     tell me about them with set_hash(i, HASH). Once I have enough hashes, you
 274     can tell me the hash of the leaf with set_leaf_hash(N, HASH), and I will
 275     either return None or raise BadHashError.
 276
 277     The first hash to be set will probably be 0 (the root hash), since this
 278     is the one that will come from someone more trustworthy than the data
 279     provider.
 280
 281     """
 282
 283     def __init__(self, num_leaves):
 284         L = [None] * num_leaves
 285         start = len(L)
 286         end   = roundup_pow2(len(L))
 287         self.first_leaf_num = end - 1
 288         L     = L + [None] * (end - start)
 289         rows = [L]
 290         while len(rows[-1]) != 1:
 291             last = rows[-1]
 292             rows += [[None for i in xrange(len(last)//2)]]
 293         # Flatten the list of rows into a single list.
 294         rows.reverse()
 295         self[:] = sum(rows, [])
 296
 297
 298     def needed_hashes(self, leafnum, include_leaf=False):
 299         """Which new hashes do I need to validate a given data block?
 300
 301         I am much like HashTree.needed_hashes(), except that I don't include
 302         hashes that I already know about. When needed_hashes() is called on
 303         an empty IncompleteHashTree, it will return the same set as a
 304         HashTree of the same size. But later, once hashes have been added
 305         with set_hashes(), I will ask for fewer hashes, since some of the
 306         necessary ones have already been set.
 307         """
 308
 309         maybe_needed = set(self.needed_for(self.first_leaf_num + leafnum))
 310         if include_leaf:
 311             maybe_needed.add(self.first_leaf_num + leafnum)
 312         return set([i for i in maybe_needed if self[i] is None])
 313
 314     def _name_hash(self, i):
 315         name = "[%d of %d]" % (i, len(self))
 316         if i >= self.first_leaf_num:
 317             leafnum = i - self.first_leaf_num
 318             numleaves = len(self) - self.first_leaf_num
 319             name += " (leaf [%d] of %d)" % (leafnum, numleaves)
 320         return name
 321
 322     def set_hashes(self, hashes={}, leaves={}):
 323         """Add a bunch of hashes to the tree.
 324
 325         I will validate these to the best of my ability. If I already have a
 326         copy of any of the new hashes, the new values must equal the existing
 327         ones, or I will raise BadHashError. If adding a hash allows me to
 328         compute a parent hash, those parent hashes must match or I will raise
 329         BadHashError. If I raise BadHashError, I will forget about all the
 330         hashes that you tried to add, leaving my state exactly the same as
 331         before I was called. If I return successfully, I will remember all
 332         those hashes.
 333
 334         I insist upon being able to validate all of the hashes that were
 335         given to me. If I cannot do this because I'm missing some hashes, I
 336         will raise NotEnoughHashesError (and forget about all the hashes that
 337         you tried to add). Note that this means that the root hash must
 338         either be included in 'hashes', or it must have been provided at some
 339         point in the past.
 340
 341         'leaves' is a dictionary uses 'leaf index' values, which range from 0
 342         (the left-most leaf) to num_leaves-1 (the right-most leaf), and form
 343         the base of the tree. 'hashes' uses 'hash_index' values, which range
 344         from 0 (the root of the tree) to 2*num_leaves-2 (the right-most
 345         leaf). leaf[i] is the same as hash[num_leaves-1+i].
 346
 347         The best way to use me is to start by obtaining the root hash from
 348         some 'good' channel and populate me with it:
 349
 350          iht = IncompleteHashTree(numleaves)
 351          roothash = trusted_channel.get_roothash()
 352          iht.set_hashes(hashes={0: roothash})
 353
 354         Then use the 'bad' channel to obtain data block 0 and the
 355         corresponding hash chain (a dict with the same hashes that
 356         needed_hashes(0) tells you, e.g. {0:h0, 2:h2, 4:h4, 8:h8} when
 357         len(L)=8). Hash the data block to create leaf0, then feed everything
 358         into set_hashes() and see if it raises an exception or not::
 359
 360          otherhashes = untrusted_channel.get_hashes()
 361          # otherhashes.keys() should == iht.needed_hashes(leaves=[0])
 362          datablock0 = untrusted_channel.get_data(0)
 363          leaf0 = HASH(datablock0)
 364          # HASH() is probably hashutil.tagged_hash(tag, datablock0)
 365          iht.set_hashes(otherhashes, leaves={0: leaf0})
 366
 367         If the set_hashes() call doesn't raise an exception, the data block
 368         was valid. If it raises BadHashError, then either the data block was
 369         corrupted or one of the received hashes was corrupted. If it raises
 370         NotEnoughHashesError, then the otherhashes dictionary was incomplete.
 371         """
 372
 373         assert isinstance(hashes, dict)
 374         for h in hashes.values():
 375             assert isinstance(h, str)
 376         assert isinstance(leaves, dict)
 377         for h in leaves.values():
 378             assert isinstance(h, str)
 379         new_hashes = hashes.copy()
 380         for leafnum,leafhash in leaves.iteritems():
 381             hashnum = self.first_leaf_num + leafnum
 382             if hashnum in new_hashes:
 383                 if new_hashes[hashnum] != leafhash:
 384                     raise BadHashError("got conflicting hashes in my "
 385                                        "arguments: leaves[%d] != hashes[%d]"
 386                                        % (leafnum, hashnum))
 387             new_hashes[hashnum] = leafhash
 388
 389         remove_upon_failure = set() # we'll remove these if the check fails
 390
 391         # visualize this method in the following way:
 392         #  A: start with the empty or partially-populated tree as shown in
 393         #     the HashTree docstring
 394         #  B: add all of our input hashes to the tree, filling in some of the
 395         #     holes. Don't overwrite anything, but new values must equal the
 396         #     existing ones. Mark everything that was added with a red dot
 397         #     (meaning "not yet validated")
 398         #  C: start with the lowest/deepest level. Pick any red-dotted node,
 399         #     hash it with its sibling to compute the parent hash. Add the
 400         #     parent to the tree just like in step B (if the parent already
 401         #     exists, the values must be equal; if not, add our computed
 402         #     value with a red dot). If we have no sibling, throw
 403         #     NotEnoughHashesError, since we won't be able to validate this
 404         #     node. Remove the red dot. If there was a red dot on our
 405         #     sibling, remove it too.
 406         #  D: finish all red-dotted nodes in one level before moving up to
 407         #     the next.
 408         #  E: if we hit NotEnoughHashesError or BadHashError before getting
 409         #     to the root, discard every hash we've added.
 410
 411         try:
 412             num_levels = depth_of(len(self)-1)
 413             # hashes_to_check[level] is set(index). This holds the "red dots"
 414             # described above
 415             hashes_to_check = [set() for level in range(num_levels+1)]
 416
 417             # first we provisionally add all hashes to the tree, comparing
 418             # any duplicates
 419             for i,h in new_hashes.iteritems():
 420                 if self[i]:
 421                     if self[i] != h:
 422                         raise BadHashError("new hash %s does not match "
 423                                            "existing hash %s at %s"
 424                                            % (base32.b2a(h),
 425                                               base32.b2a(self[i]),
 426                                               self._name_hash(i)))
 427                 else:
 428                     level = depth_of(i)
 429                     hashes_to_check[level].add(i)
 430                     self[i] = h
 431                     remove_upon_failure.add(i)
 432
 433             for level in reversed(range(len(hashes_to_check))):
 434                 this_level = hashes_to_check[level]
 435                 while this_level:
 436                     i = this_level.pop()
 437                     if i == 0:
 438                         # The root has no sibling. How lonely. You can't
 439                         # really *check* the root; you either accept it
 440                         # because the caller told you what it is by including
 441                         # it in hashes, or you accept it because you
 442                         # calculated it from its two children. You probably
 443                         # want to set the root (from a trusted source) before
 444                         # adding any children from an untrusted source.
 445                         continue
 446                     siblingnum = self.sibling(i)
 447                     if self[siblingnum] is None:
 448                         # without a sibling, we can't compute a parent, and
 449                         # we can't verify this node
 450                         raise NotEnoughHashesError("unable to validate [%d]"%i)
 451                     parentnum = self.parent(i)
 452                     # make sure we know right from left
 453                     leftnum, rightnum = sorted([i, siblingnum])
 454                     new_parent_hash = pair_hash(self[leftnum], self[rightnum])
 455                     if self[parentnum]:
 456                         if self[parentnum] != new_parent_hash:
 457                             raise BadHashError("h([%d]+[%d]) != h[%d]" %
 458                                                (leftnum, rightnum, parentnum))
 459                     else:
 460                         self[parentnum] = new_parent_hash
 461                         remove_upon_failure.add(parentnum)
 462                         parent_level = depth_of(parentnum)
 463                         assert parent_level == level-1
 464                         hashes_to_check[parent_level].add(parentnum)
 465
 466                     # our sibling is now as valid as this node
 467                     this_level.discard(siblingnum)
 468             # we're done!
 469
 470         except (BadHashError, NotEnoughHashesError):
 471             for i in remove_upon_failure:
 472                 self[i] = None
 473             raise