extensions/browser/content_hash_tree.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
   6 #define EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_
   7
   8 #include <string>
   9 #include <vector>
  10
  11 namespace extensions {
  12
  13 // This takes a list of sha256 hashes, considers them to be leaf nodes of a
  14 // hash tree (aka Merkle tree), and computes the root node of the tree using
  15 // the given branching factor to hash lower level nodes together. Tree hash
  16 // implementations differ in how they handle the case where the number of
  17 // leaves isn't an integral power of the branch factor. This implementation
  18 // just hashes together however many are left at a given level, even if that is
  19 // less than the branching factor (instead of, for instance, directly promoting
  20 // elements). E.g., imagine we use a branch factor of 3 for a vector of 4 leaf
  21 // nodes [A,B,C,D]. This implemention will compute the root hash G as follows:
  22 //
  23 // |      G      |
  24 // |     / \     |
  25 // |    E   F    |
  26 // |   /|\   \   |
  27 // |  A B C   D  |
  28 //
  29 // where E = Hash(A||B||C), F = Hash(D), and G = Hash(E||F)
  30 //
  31 // The one exception to this rule is when there is only one node left. This
  32 // means that the root hash of any vector with just one leaf is the same as
  33 // that leaf. Ie RootHash([A]) == A, not Hash(A).
  34 std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes,
  35                                 int branch_factor);
  36
  37 }  // namespace extensions
  38
  39 #endif  // EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_