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