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