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_ 40
