| // Copyright 2014 The Chromium Authors |
| // 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 root node of the tree using |
| // the given branching factor to hash lower level nodes together. Tree hash |
| // implementations differ in how they handle the case where the number of |
| // leaves isn't an integral power of the branch factor. This implementation |
| // just hashes together however many are left at a given level, even if that is |
| // less than the branching factor (instead of, for instance, directly promoting |
| // elements). E.g., imagine we use a branch factor of 3 for a vector of 4 leaf |
| // nodes [A,B,C,D]. This implemention will compute the root hash G as follows: |
| // |
| // | G | |
| // | / \ | |
| // | E F | |
| // | /|\ \ | |
| // | A B C D | |
| // |
| // where E = Hash(A||B||C), F = Hash(D), and G = Hash(E||F) |
| // |
| // The one exception to this rule is when there is only one node left. This |
| // means that the root hash of any vector with just one leaf is the same as |
| // that leaf. Ie RootHash([A]) == A, not Hash(A). |
| std::string ComputeTreeHashRoot(const std::vector<std::string>& leaf_hashes, |
| int branch_factor); |
| |
| } // namespace extensions |
| |
| #endif // EXTENSIONS_BROWSER_CONTENT_HASH_TREE_H_ |
