Add code to compute the root hash for a hash tree

extensions/browser/content_hash_tree.h

+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
+#define EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
+
+#include <string>
+#include <vector>
+
+namespace extensions {
+
+// This takes a list of sha256 hashes, considers them to be leaf nodes of a
+// hash tree (aka Merkle tree), and computes the hash of the root node of the
+// tree using a branching factor of |block_size| / sizeof(sha256hash). The
+// block size should be a multiple of sizeof(sha256hash).

[Marijn Kruisselbrink, 2014/05/12 17:53:45]

From the code here it isn't entirely clear why you're passing block_size and
calculating the branching factor from that, instead of just passing the
branching factor directly. But I assume that for the way this method will be
used the block_size makes more sense?

[Marijn Kruisselbrink, 2014/05/12 17:53:45]

You should probably explicitly document how this method deals with
non-power-of-branching_factor leaf counts. Various specs involving binary merkle
trees that I can find all seem to handle this case differently (duplicating
hashes, not hashing hashes, etc), so I'm not sure if what you implemented is
what you intended (although it does seem as a reasonable approach for merkle
trees with arbitrary branching factors).

[asargent_no_longer_on_chrome, 2014/05/12 21:58:58]

Added documentation about numbers of nodes that are not integral powers of the
branching factor. 

[asargent_no_longer_on_chrome, 2014/05/12 21:58:58]

I refactored this code out from being inline in another method and didn't really
think about it too much. But I think you're right that it makes more sense to
pass in the branching factor, so I switched to doing that. 

+std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
+                                int block_size);
+
+}  // namespace extensions
+
+#endif  // EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_