Logo Search packages:      
Sourcecode: tahoe-lafs version File versions  Download package

def allmydata::hashtree::IncompleteHashTree::set_hashes (   self,
  hashes = {},
  leaves = {} 
)

Add a bunch of hashes to the tree.

I will validate these to the best of my ability. If I already have a
copy of any of the new hashes, the new values must equal the existing
ones, or I will raise BadHashError. If adding a hash allows me to
compute a parent hash, those parent hashes must match or I will raise
BadHashError. If I raise BadHashError, I will forget about all the
hashes that you tried to add, leaving my state exactly the same as
before I was called. If I return successfully, I will remember all
those hashes.

I insist upon being able to validate all of the hashes that were
given to me. If I cannot do this because I'm missing some hashes, I
will raise NotEnoughHashesError (and forget about all the hashes that
you tried to add). Note that this means that the root hash must
either be included in 'hashes', or it must have been provided at some
point in the past.

'leaves' is a dictionary uses 'leaf index' values, which range from 0
(the left-most leaf) to num_leaves-1 (the right-most leaf), and form
the base of the tree. 'hashes' uses 'hash_index' values, which range
from 0 (the root of the tree) to 2*num_leaves-2 (the right-most
leaf). leaf[i] is the same as hash[num_leaves-1+i].

The best way to use me is to start by obtaining the root hash from
some 'good' channel and populate me with it:

 iht = IncompleteHashTree(numleaves)
 roothash = trusted_channel.get_roothash()
 iht.set_hashes(hashes={0: roothash})

Then use the 'bad' channel to obtain data block 0 and the
corresponding hash chain (a dict with the same hashes that
needed_hashes(0) tells you, e.g. {0:h0, 2:h2, 4:h4, 8:h8} when
len(L)=8). Hash the data block to create leaf0, then feed everything
into set_hashes() and see if it raises an exception or not::

 otherhashes = untrusted_channel.get_hashes()
 # otherhashes.keys() should == iht.needed_hashes(leaves=[0])
 datablock0 = untrusted_channel.get_data(0)
 leaf0 = HASH(datablock0)
 # HASH() is probably hashutil.tagged_hash(tag, datablock0)
 iht.set_hashes(otherhashes, leaves={0: leaf0})

If the set_hashes() call doesn't raise an exception, the data block
was valid. If it raises BadHashError, then either the data block was
corrupted or one of the received hashes was corrupted. If it raises
NotEnoughHashesError, then the otherhashes dictionary was incomplete.

Definition at line 322 of file hashtree.py.

00322                                 {}, leaves={}):
        """Add a bunch of hashes to the tree.

        I will validate these to the best of my ability. If I already have a
        copy of any of the new hashes, the new values must equal the existing
        ones, or I will raise BadHashError. If adding a hash allows me to
        compute a parent hash, those parent hashes must match or I will raise
        BadHashError. If I raise BadHashError, I will forget about all the
        hashes that you tried to add, leaving my state exactly the same as
        before I was called. If I return successfully, I will remember all
        those hashes.

        I insist upon being able to validate all of the hashes that were
        given to me. If I cannot do this because I'm missing some hashes, I
        will raise NotEnoughHashesError (and forget about all the hashes that
        you tried to add). Note that this means that the root hash must
        either be included in 'hashes', or it must have been provided at some
        point in the past.

        'leaves' is a dictionary uses 'leaf index' values, which range from 0
        (the left-most leaf) to num_leaves-1 (the right-most leaf), and form
        the base of the tree. 'hashes' uses 'hash_index' values, which range
        from 0 (the root of the tree) to 2*num_leaves-2 (the right-most
        leaf). leaf[i] is the same as hash[num_leaves-1+i].

        The best way to use me is to start by obtaining the root hash from
        some 'good' channel and populate me with it:

         iht = IncompleteHashTree(numleaves)
         roothash = trusted_channel.get_roothash()
         iht.set_hashes(hashes={0: roothash})

        Then use the 'bad' channel to obtain data block 0 and the
        corresponding hash chain (a dict with the same hashes that
        needed_hashes(0) tells you, e.g. {0:h0, 2:h2, 4:h4, 8:h8} when
        len(L)=8). Hash the data block to create leaf0, then feed everything
        into set_hashes() and see if it raises an exception or not::

         otherhashes = untrusted_channel.get_hashes()
         # otherhashes.keys() should == iht.needed_hashes(leaves=[0])
         datablock0 = untrusted_channel.get_data(0)
         leaf0 = HASH(datablock0)
         # HASH() is probably hashutil.tagged_hash(tag, datablock0)
         iht.set_hashes(otherhashes, leaves={0: leaf0})

        If the set_hashes() call doesn't raise an exception, the data block
        was valid. If it raises BadHashError, then either the data block was
        corrupted or one of the received hashes was corrupted. If it raises
        NotEnoughHashesError, then the otherhashes dictionary was incomplete.
        """

        assert isinstance(hashes, dict)
        for h in hashes.values():
            assert isinstance(h, str)
        assert isinstance(leaves, dict)
        for h in leaves.values():
            assert isinstance(h, str)
        new_hashes = hashes.copy()
        for leafnum,leafhash in leaves.iteritems():
            hashnum = self.first_leaf_num + leafnum
            if hashnum in new_hashes:
                if new_hashes[hashnum] != leafhash:
                    raise BadHashError("got conflicting hashes in my "
                                       "arguments: leaves[%d] != hashes[%d]"
                                       % (leafnum, hashnum))
            new_hashes[hashnum] = leafhash

        remove_upon_failure = set() # we'll remove these if the check fails

        # visualize this method in the following way:
        #  A: start with the empty or partially-populated tree as shown in
        #     the HashTree docstring
        #  B: add all of our input hashes to the tree, filling in some of the
        #     holes. Don't overwrite anything, but new values must equal the
        #     existing ones. Mark everything that was added with a red dot
        #     (meaning "not yet validated")
        #  C: start with the lowest/deepest level. Pick any red-dotted node,
        #     hash it with its sibling to compute the parent hash. Add the
        #     parent to the tree just like in step B (if the parent already
        #     exists, the values must be equal; if not, add our computed
        #     value with a red dot). If we have no sibling, throw
        #     NotEnoughHashesError, since we won't be able to validate this
        #     node. Remove the red dot. If there was a red dot on our
        #     sibling, remove it too.
        #  D: finish all red-dotted nodes in one level before moving up to
        #     the next.
        #  E: if we hit NotEnoughHashesError or BadHashError before getting
        #     to the root, discard every hash we've added.

        try:
            num_levels = depth_of(len(self)-1)
            # hashes_to_check[level] is set(index). This holds the "red dots"
            # described above
            hashes_to_check = [set() for level in range(num_levels+1)]

            # first we provisionally add all hashes to the tree, comparing
            # any duplicates
            for i,h in new_hashes.iteritems():
                if self[i]:
                    if self[i] != h:
                        raise BadHashError("new hash %s does not match "
                                           "existing hash %s at %s"
                                           % (base32.b2a(h),
                                              base32.b2a(self[i]),
                                              self._name_hash(i)))
                else:
                    level = depth_of(i)
                    hashes_to_check[level].add(i)
                    self[i] = h
                    remove_upon_failure.add(i)

            for level in reversed(range(len(hashes_to_check))):
                this_level = hashes_to_check[level]
                while this_level:
                    i = this_level.pop()
                    if i == 0:
                        # The root has no sibling. How lonely. You can't
                        # really *check* the root; you either accept it
                        # because the caller told you what it is by including
                        # it in hashes, or you accept it because you
                        # calculated it from its two children. You probably
                        # want to set the root (from a trusted source) before
                        # adding any children from an untrusted source.
                        continue
                    siblingnum = self.sibling(i)
                    if self[siblingnum] is None:
                        # without a sibling, we can't compute a parent, and
                        # we can't verify this node
                        raise NotEnoughHashesError("unable to validate [%d]"%i)
                    parentnum = self.parent(i)
                    # make sure we know right from left
                    leftnum, rightnum = sorted([i, siblingnum])
                    new_parent_hash = pair_hash(self[leftnum], self[rightnum])
                    if self[parentnum]:
                        if self[parentnum] != new_parent_hash:
                            raise BadHashError("h([%d]+[%d]) != h[%d]" %
                                               (leftnum, rightnum, parentnum))
                    else:
                        self[parentnum] = new_parent_hash
                        remove_upon_failure.add(parentnum)
                        parent_level = depth_of(parentnum)
                        assert parent_level == level-1
                        hashes_to_check[parent_level].add(parentnum)

                    # our sibling is now as valid as this node
                    this_level.discard(siblingnum)
            # we're done!

        except (BadHashError, NotEnoughHashesError):
            for i in remove_upon_failure:
                self[i] = None
            raise
            raise


Generated by  Doxygen 1.6.0   Back to index