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
11namespace 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).
34std::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