blob: 534f69e79286caad80d2f9ba68383430ec1d4f18 [file] [log] [blame]
// 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.
#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